My interpreter uses the standard `environment model' of evaluation where a linked chain of lexical environment chains are maintained during evaluation. Every variable lookup goes through a `deep search' of the frames looking for a binding with a matching name. Needless to say, this is not blazingly fast. There are two parts to solving this. First is to reduce the need for the deep search, second is to optimize the fast path.
MIT Scheme supports first-class environments. The special form
the-environmentreturns the lexical environment at the point of invocation. The returned environment can be used as an argument to
evaland that's where the trouble begins. If
evalis called, the user is going to expect that the code will run in a context with the same bindings visible as where the environment was captured. This means we cannot move or collapse the environment frames because it may cause changes visible to the user. Even worse, if the user evals a
loads a file, it may inject bindings that were not previously visible. This means we cannot even cache the locations of the variables. The flexibility of first-class environments comes with a heavy cost. On the other hand, this flexibility is hardly ever used, so we end up paying this cost to no advantage.
So how do we fix this? First, because
(the-environment)is the only documented way to obtain a first-class environment, we can walk the SCode and determine whether a first-class environment will be needed. I do this when I construct an SCode lambda expression. If the body contains a call to
(the-environment), I construct a
StandardLambdaobject, but if it does not, I construct a
StandardLambda, when evaluated, constructs a
StandardClosure, when applied, constructs a
StandardEnvironmentmust be layed out exactly as specified by the source code and variable lookups must do a deep search because the user might inject bindings via
StaticEnvironmenthowever, has an important property: because the user cannot use
evalwith it (he can't name the object to pass it as an argument, so this does not create a user-visible restriction), we know that there will not be incremental definitions that could hide the bindings in the environment. We know the lexical depth and offset of all variables bound in a
So the first task is to identify and separate