A flat environment does not have a chain of frames. It has a single frame with two components. The binding vector that is common to all environment structures, and a vector of pointers to the lexically visible binding cells. The lexically visible cells are indirect because the bindings may be shared among several closures. For example, look at this code:
(let ((counter 0) (increment 1)) ... (lambda () (set! counter (+ counter increment))) (lambda () counter) ...)We have two lambda expressions that must be closed over the same variable
counter. In a chained environment model, invoking either closure would extend the common shared environment where the
incrementvariables were bound. In a flat environment model, invoking the second closure would lead to an environment structure like this:
bindings: #() ;; empty argument bindings lexical: #(<pointer to counter>)while invoking the first closure would lead to this:
bindings: #() ;; empty argument bindings lexical: #(<pointer to counter> <pointer to increment>)This is fairly straightforward in principle, but the devil is in the details. It took me a fair amount of time to fiddle around with the code and come up with something that worked.
The first step was to add a new phase to the interpreter. A partial evaluation walk is done on the code before calling the actual
eval. In the partial evaluation phase, the code tree is rebuilt and certain nodes in the tree are replaced. A partial environment is kept as the code is walked. When a variable is encountered, it is looked up in the partial environment. If it is found in the immediately enclosing frame, it is turned into an
Argumentvariable with the appropriate offset. If it is not found at all, it is turned into a
FreeVariable. If it is found in an intermediate frame, things get tricky. We have to consider the lambda expressions that are associated with the intervening frames and decide how the variable will be accessed.
When we partially evaluate a lambda expression, we first have to check whether we'll need a first-class environment for it. Fortunately, this is an easy test: we just have to walk the body of the expression and look for a call to the
the-environmentspecial form. If we need a first-class environment, then we simply punt on any optimization other than
Argumentvariables because we'll just do a deep search every time we access a lexical variable. On the other hand, if we don't need a first-class environment, we construct a
PartialStaticClosurefor the lambda expression. When we partially evaluate the
PartialStaticClosure, we construct a
PartialStaticEnvironmentthat we use for partially evaluating the body of the lambda expression.
The entire process of partial evaluation is very similar to that of ‘normal’ evaluation, but there are a couple of differences. Partial evaluation produces a
PartialResultthat contains the rebuilt code tree. Conditionals are partially evaluated along both branches and the
PartialResults are combined into a new conditional node. Partial closures are partially evaluated right away (instead of being returned) as if they had been applied to arguments, but of course the resulting
PartialEnvironmentdoesn't contain runtime values, it only contains binding information.
PartialClosureleads to the construction of a
PartialEnvironment. Variable lookup in a
PartialEnvironmenteither returns the argument offset, or an indication that a deep search is necessary. The rebuilt lambda expression becomes a
StandardLambda, when it is actually evaluated, a
StandardClosureis built. When the
StandardClosureis applied to arguments, the bindings are placed in a
StandardEnvironment. Variable lookup in a
StandardEnvironmentuses deep search, and in this way retain the old chained environment model for first-class environments when necessary.
But if we don't need a first-class environment, we do things a bit differently. The lambda expression becomes a
StaticLambda(the word static in this case meaning that the location of the bindings never change). When a
StaticLambdais partially evaluated, a
PartialStaticClosureis created. This leads to the construction of a
PartialStaticEnvironmentwhere variable lookup happens differently. At regular eval time, a
StaticClosure, and when a
StaticClosureis applied, it creates a
Alas, I've arrived at work. More details later...