LEXICAL_ADDRESSING.md

Lexical Addressing

Static analysis is a phase prior to evaluation that replaces variables with their location in the environment.

We don't know what the values of variables will be at run-time, but we can work out their locations.

We do this with the help of a compile-time environment ct-env that just stores variables, not values.

For example consider this let expression

(let ((x 10)) x)

If we were evaluating that naively we would be doing something like

(define (eval-let expr env)
        (eval (let-body expr)
              (extend env
                      (eval-bindings (let-bindings expr)
                                     env))
)

Where eval-bindings evaluates the value part of each binding and returns tuples of (var evaluated-val)

Static analysis proceeds analogously, but we don't need to (and can't) evaluate anything,

(define (analyze-let expr ct-env)
        (analyze (let-body expr)
                 (ct-extend ct-env (vars (let-bindings expr)))
)

where (vars bindings) is just (map car bindings)

and similarily for other language constructs.

Continuing with our naive run-time evaluation analogy, variable are looked up in the current environment:

(define (eval-var var env)
        (lookup var env)
)

The only transformations we perform during lexical addressing is to annotate the variables with their locations in the compile-time environment:

(define (analyze-var var ct-env)
        (annotate-var var (ct-lookup var ct-env))
)

That depends on ct-extend and ct-lookup

(define (ct-extend ct-env vars)
        (cons vars ct-env)
)

(define (ct-lookup var ct-env)
        (define (lookup-in-env ct-env frame-counter)
                (define (lookup-in-frame frame offset)
                        (cond ((null? frame) null)
                              ((eq (car frame) var) offset)
                              (else (lookup-in-frame (cdr frame)
                                                     (+ offset 1))))
                )
                (if (null? ct-env)
                    (error "no binding for" var)
                    (let ((offset (lookup-in-frame (car ct-env) 0)))
                         (if (null? offset)
                             (lookup-in-env (cdr ct-env) (+ frame-counter 1))
                             (list frame-counter offset)
                         )
                    )
                )
        )
        (lookup-in-env ct-env 0)
)

All it's doing is searching the environment for the location of the variable, and returning a tuple of (frame offset).

For example

(ct-lookup 'y '((a b) (c d) (x y z)))

should return (2 1)

The other thing we need to handle is when we see a lambda. It's simpler than you might think, and completely analogous to let:

(define (analyze-lambda expr ct-env)
        (analyze (lambda-body expr)
                 (ct-extend ct-env (lambda-args expr))
        )
)

No need to create any compile-time equivalent to closures or anything like that, we just analyse the body in the environment that the lambda is created in, which is exactly what lexical variables require.

The only thing we need to ensure to make all this work is that the run-time environments will be constructed with identical frames and offsets. They no longer need variables, or hash tables to find them.

A run time environment is then just a linked list of arrays of values, and a run-time lookup is just:

(define (lookup frame offset env)
        (if (eq frame 0)
            (index offset (car env))
            (lookup (- frame 1) offset (cdr env))
        )
)

And since we've already done the analysis we know the environment must be there and we don't even need to check for null!

V2 Wrinkles

in V2 I've gone to a hybrid stack/register VM, where variables local to a function are on the stack rather than in the environment. This is still lexically addressable, the offset in the environment is the same as the position on the stack, but there are a few complications.

1. we need to distinguish local variables LVAR from environmental ones VAR.
2. LVAR are annotated with a single number, the stack position.
3. lexical analysis of let and letrec still need to create new ctenvs (to support shadowing) but let and letrec in fact create LVARs so within a nested let or letrec we need to add up the sizes of parent ctenv up to and including the function to calculate the actual stack position for LVARs