[r6rs-discuss] [Formal] Remove double phase semantics

From: AndrevanTonder <andre>
Date: Sun Nov 26 12:25:06 2006

On Sat, 25 Nov 2006, Marcin 'Qrczak' Kowalczyk wrote:

> AndrevanTonder <andre_at_het.brown.edu> writes:
>
>> The much cleaner semantics is the one in which a separate set of
>> bindings is instantiated for each level.
>
> Let's imagine a Scheme compiler which hosts its own interpreter.
> Certain libraries (e.g. the standard library) are provided only in the
> compiled form, and the interpreter just links to their version which
> is compiled into the interpreter program instead of interpreting their
> source. Assume that they contain mutable state.
>
> In this case I think it's easy to have bindings shared between levels,
> and it's hard to separate them.

In the encoding I have in mind, there is no need to recompile a library for
different levels, so I do not think this is a big problem. The difference with
the shared model is as follows. Consider a library

    (library bar
      (export g)
      (import (only foo f))
      (define (g) (f)))

In the separate-binding model it gets compiled to

    (define (bar-invoke level)
      (let ((foo-f ($import-value 'foo-f level)))
        (letrec* ((bar-g (lambda () (foo-f))))
          ($export-value 'bar-g level bar-g)))

where non-primitive imports are copied to a local reference foo-f. In the
shared-binding model, it gets compiled to

    (define (bar-invoke)
      (letrec* ((bar-g (lambda () (foo-f))))
        ($export-value 'bar-g level bar-g)))

where foo-f now refers to a statically known global.

It has been pointed out to me that the fact that foo-f is local may inhibit
some optimizations that are directly possible in the shared-binding model.
However, in the most common case where f does not mutate any free variables, or
refer to any procedure that does, the first encoding can be simplified to the
second. Whether compiler writers wish to spend time on this optimization is a
separate question, though.

[TECHNICAL]

For anyone interested in the technicalities, here is a worked out example:

     (library foo
       (export f)
       (import r6rs)
       (define f
         (let ((x 0))
           (lambda ()
             (set! x (+ x 1))
             x))))

     (library bar
       (export m)
       (import r6rs (for foo expand))
       (define-syntax m
         (lambda (e)
           (f))))

     (library baz
       (export)
       (import (for r6rs run expand)
               (for bar expand (meta 2))
               (for foo run (meta 2)))
       (let-syntax ((n (lambda (e)
                         (let-syntax ((o (lambda (e) (+ (f) (m)))))
                           (+ (m) (o))))))
         (display (n)) ;==> 4
         (display (f)))) ;==> 1

   This compiles to (inessential stuff omitted)

    (define (foo-invoke level)
      (letrec* ((foo-f ---))

        ;; Copy local value to a global binding called foo-f:level

        ($export-value 'foo-f level foo-f)))

    (define (bar-visit level)

      ;; Copy global binding foo-f:(level+1) to local foo-f:1
      ;; Only level 1 bindings ever residualize in visit-time code.

      (let ((foo-f:1 ($import-value 'foo-f (+ 1 level))))

        ;; Register macro called bar-m:level in global macro env.

        ($register-macro! bar-m level
          (lambda (e) (foo-f:1))))

    (define (baz-invoke level)

      ;; Copy global binding foo-f:level to local foo-f
      ;; Only level 0 bindings ever residualize in invoke-time code.

      (let ((foo-f ($import-value 'foo-f level)))
        (display 4)
        (display (foo-f)))

    Here are the definitions of $import-value and $export-value.
    They contain a trivial use of "eval", which can even be avoided if
    level = 0 by having a fixed set of 0-level variables, although that
    is probably not even worth the trouble.

     (define ($import-value name level)
       ;; returns the global binding called name:level
       (eval (append-level name level)))

     (define ($export-value name level value)
       ;; sets global location name:level to value.
       ;; $copy-register is a global location
       (set! $copy-register value)
       (eval `(define ,(append-level name level) $copy-register)))

    Consider for example the inner reference to (m) in the library baz.
    My expander will append the current level to obtain the denotation
    bar-m:2, which has a binding in the macro table due to the level-2
    visit of bar. This macro contains a reference to the local foo-f:1
    in the expanded bar, which, during the level-2 visit of bar was
    copied from the global value foo-f:3 that was established during the
    invocation of foo at level 3.

    Note that in BAZ, only the residualized level 0 reference to foo-f needs an
    $import-value in the expanded code. The level 2 reference to f in the inner
    let-syntax immediately expands to foo-f:2, for which a
    global binding is available due to the import of foo for (meta 2).

    Some properties of this encoding:

      - All non-primitive variable references in expanded visit-time and
        invoke-time bodies are to local variables.
      - I treat primitives specially. They are not copied. For example,
        CAR just expands to CAR.
      - If foo-f did not mutate a free variable, it could be lifted to
        a static global binding.
      - The encoding expands all references to Scheme variables, avoiding
        thinks like (env-ref 'name level) in compiled body-code completely.

   Andre
Received on Sun Nov 26 2006 - 12:20:45 UTC