Or would it be possible to have a dynamic vector as your environment (so that you get O(1) lookup) at the cost of making constructing closures more costly (as you'd have to copy the bindings)?
Sure, you can do that. Besides the closure allocation cost you have to be careful if your Lisp supports setting variables directly:
(define x 2)
(define y (lambda (z) (+ x z))
(set! x 3)
Now you want the `x` referenced inside the lambda to refer to the new value of `x`. So if closure creation copies bindings in the parent scope then you have to introduce an extra indirection for mutable variables. This is called "assignment conversion".
(define x (make-ref 2))
(define y (lambda (z) (+ (read-ref x) z))
(set-ref! x 3)
Note also that it is unnecessary to store the number of bindings in the environment, because this number is implied by the lambda associated with the closure.
Awesome, that's exactly the answer I was hoping for. Is this a common way of compiling lisp or does it actually make things slower in the general case?
Both methods have pros and cons, and the most advanced implementations use a hybrid method. The copying method is probably the best to start with. It may make things slower in special circumstances, but in the common case it is faster because lambdas tend to have a small number of free variables. It is also way simpler, because linked environments have a tendency to retain garbage if you are not careful. For example:
(let ((x 1) (y 2))
(lambda (z) (+ x z))
If you use linked closures naively then the closure will keep `y` in memory even though it's garbage.
However, keep in mind that what you usually not think of as free variables are free variables. For example if you have this:
Then not only `y` but also `factorial` and `+` are free variables. With some work you can avoid storing those references in the closure. I believe that the state of the art is described in this paper: ftp://ftp.ecn.purdue.edu/qobi/99-105.pdf
A dynamic vector will not work in the general case because environments can "fork". You can, however, have shallow environments, where making a new environment based on an old one involves copying some or all of the old environment's fields. That can become a problem, however, if your language supports set!ting local variables - the local variable might be represented in more than one environment, so you'd have to keep track of that and do more than one store.
See Andrew Appel's "Compiling with Continuations", for example.
(let [x 1]
(defn make-adder [y]
(fn [] (+ x y)))
(defn make-multiplier [z]
(fn [] (* x z)))
(defn mutate! [new-x]
(set! x new-x)))
Now for
(make-adder 2)
we get a function whose environment includes x and y, whereas the environment for
(make-multiplier 2)
includes x and z. Assuming you have shallow environments, you'll have one environment [x' y] and another one [x'' z], whereas with deep environments (like in ClojureC) you'd have [[x] y] and [[x] z] where the [x] is shared between them. Now, if you call
(mutate! 3)
with deep environments you only need to store the 3 once (to x), whereas with shallow environments you'll need to store to x' and x''.
The technique used in most Lisp compilers (SBCL, etc) is as follows:
Say you have an outer lambda and an inner lambda. All variables (either arguments or local variables introduced by "let") defined in the outer lambda and used in the inner lambda are called the "free variables" of the inner lambda and the "closed over variables" of the outer lambda. Of the closed over variables of the outer lambda, all the ones that are assigned-to in the inner lambda are "assigned to variables." You can perform this classification in one pass before code generation.
Once you have annotated each lexical variable with its "closed over" and "assigned to" status, you can generate flat C functions in one code generation pass. The idea is to generate each inner lambda as a C function that accepts a hidden "environment vector" that contains the closed-over variables in the outer lambda. This environment vector is indexed simply by an integer index. Just handle the following AST constructs as follows:
LET: if the lexical variable introduced by the LET form is closed-over and assigned-to, it must be demoted to a box because the inner lambda can't modify the outer lambda's stack frame. Whereas you can generate a regular lexical variable directly as a C local variable, you have to generate a closed-over + assigned-to variable as a C variable that points to a single heap-allocated box that references a Lisp value.
VARIABLE-REF: for every reference to a variable, you have to look at it's status. If the variable is defined in the current lambda and not assigned-to, you can just emit a use of the C variable directly. If it is defined in the current lambda and assigned-to, you have to emit a load of the value from its box, a pointer to which is in a C variable in the current function. If the variable is defined in an outer lambda (it's a free variable of the current lambda), but not assigned-to, you have to emit the reference as a load (with a known constant index) from the environment vector. If it's a free variable and assigned-to, you have to load a reference to a box from the environment vector, then load the value from the box.
LAMBDA: assign each free variable of the lambda an index starting at 0 (which you will use when emitting references to free variables in the body of the lambda). Generate the LAMBDA expression as the creation of an object with two slots: a pointer to the C function of the inner lambda, and a pointer to an environment vector. Emit code to copy each free variable referenced in the inner lambda into the environment vector. Remember you might have multiple levels of nested lambdas, so follow the rules for VARIABLE-REF above when emitting each copy.
Then, just structure your calling convention so you can FUNCALL lambda objects and pas the environment vector as a hidden first argument.
Note that this requires a bit more environment book-keeping in your compiler than you might otherwise have. You really want each inner lambda to have a complete environment, including free variables. This is so you can keep track of which variable has which index in the environment vector. Say you have:
(defun foo()
(let ((x 0) (y 1) (z 2))
(labels ((bar () (+ x y))
(baz () (- z x)))
...)))
In "bar" your free variable indices probably look like {x: 0, y: 1} while in "baz" your free variable indices probably looks like {z: 0, x: 1}. You need to be able to keep track of these mappings separately, which you can't do if you attach these mappings in the environment structure you use for the LET form. Instead, you need to have a separate environment structure with entries in BAR and BAZ for the free variables of each lambda.
In practice this generates very good code, because most lambdas simply don't have very many free variables (at least so long as you don't naively generate LET forms as nested lambdas).
That's interesting. I was planning on having a pass that eliminated let expressions, turning them into immediately applied lambdas, but having read your comment, it sounds like this isn't such a good idea. I'll have to think about this.
I personally don't think it's worth the minor conceptual simplification to treat LET forms as lambdas, but YMMV. It's only slightly more complicated to handle both LET forms and LAMBDA forms as things that can introduce values into the compile-time environment, but substantially more complicated to do the unboxing and inlining you'd have to do to ensure that the common case of defining a bunch of local variables that are not closed over does not end up consing or performing a function call.
Are you forced to use as environment like:
Or would it be possible to have a dynamic vector as your environment (so that you get O(1) lookup) at the cost of making constructing closures more costly (as you'd have to copy the bindings)?