Thursday, October 9, 2008

Now that we have static environments, we can take advantage of the known locations of lexical variables. For instance, if the variable is bound in the immediately enclosing lambda, we can simply fetch it because it cannot be shadowed. If a variable is completely free in a fragment of code, that is, if it is a `global' or `top-level' variable, we can grab the value cell at load time and simply dereference it to evaluate the variable.

Before loading or evaluating a piece of SCode, we make a pre-pass over it to `compile' the variable lookup. (We could do this at lambda-construction time, but then we'd have to make multiple passes over deeply nested lambda expressions. Nonetheless, multiple passes are much simpler to understand. When contructing a lambda, we'd walk the body and replace all the lambda-bound variables that are free in the body with variables that `knew' their lexical depth. And it is unlikely that the lexical depth will exceed a very small number, so the multiple passes wouldn't add up. On the other hand, you would still need a final pass just before evaluation, and if you were too simple-minded about multiple passes you'd end up with an exponential growth factor.)

As I was saying, we make a pre-pass over the code to `compile' the variable lookup. We create a LexicalMap that holds a model of the runtime environment, and as we walk the code, we simulate the variable lookup against the lexical map. As we simulate the lookup, we note how deep we have to search, whether there will be incremental bindings in any of the frames, and where we ultimately find the variable (if at all). If we find the variable, we look at the path we used to get at it and create an instance of a specialized variable class that performs that particular style of lookup at runtime. If we don't find the variable, we create an instance of a specialized variable class that performs a deep search.