| Guy L. Steele Jr. | 12 | LAMBDA: The Ultimate Declarative |
2. Lexical and Dynamic Binding
The examples of the previous section, by using only local variables, avoided the question of whether variables are lexically or dynamically scoped.
In this section we will see that lexical scoping is necessary in order to reflect the semantics of lambda-calculus-based models.
We might well ask, then, if LISP was originally based on lambda calculus, why do most current LISP systems employ dynamic binding rather than lexical?
The primary reason seems to be the introduction of stack hardware at about the time of early LISP development.
(This was not pure case and effect; rather, each phenomenon influenced the other.)
The point is that a dynamic bindings stack parallels the control stack in structure.
If one has an escape operator [Reynolds 72] (also known as CATCH [Moon 74] or EXIT [Wulf 71] [Wulf 72]) then the "control stack" may be, in general, a tree structure, just as the introduction of FUNARGs requires that the environment be tree-structured.
If these operators are forbidden, or only implemented in the "downward" sense (in the same way that ALGOL provides "downward funarg" (procedure arguments to functions) but not "upward funarg" (procedure-valued functions)) as they historically have been in most non-toy LISP systems, then hardware stack instructions can always be used for function calling and environment binding.
Since the introduction of stack hardware (e.g. in the PDP-6), most improvements to LISP's variable binding methods have therefore started with dynamic binding and then tried to patch it up.
MacLISP [Moon 74] uses the so-called shallow access scheme, in which the current value of a variable is in a fixed location, and old values are on a stack.
The advantage of this technique is that variables can be access using only a single memory reference.
When code is compiled, variables are divided into two classes: special variables are kept in their usual fixed locations, while local variable are kept where ever convenient, at the compiler's discretion, saving time over the relatively expensive special binding mechanism.
InterLISP [Teitelman 74] (before spaghetti stacks) used a deep access scheme, in which it was necessary to look up on the bindings stack to find variable bindings; if a variable was not bound on the stack, the its global value cell was checked.
The cost of the stack search was ameliorated by looking up, on entry to a function, the locations of variables needed by that function.
The advantage of this scheme is that the "top level" value of a variable is easily accessed, since it is always in the variable's value cell.
(InterLISP also divides variables into two classes for purposes of compilation; only specifial variables need be looked up on the bindings stack.)
Two other notable techniques are the use of vale cells as a cache for deep dynamic access scheme, and "spaghetti stacks" [Bobrow 73], which attempt to allow the user to choose between static and dynamic binding.
The problem with the latter is that they are so general that it is difficult for the compiler to optimize anything; also, they do not completely solve the problem of choosing between static and dynamic binding.
For example, the GEN-SQRT-OF-GIVEN-EXTRA-TOLERANCE function given in [Steele 76] cannot be handled properly with spaghetti stacks in the straightforward way.
The difficulty is that there is only one access link for each frame, while there are conceptually two distinct access methods, namely lexical and dynamic.
Unfortunately, dynamic binding creates two difficulties.
One is the well-known "FUNARG" problem [Moses 70]; the essence of this problem is that lexical scoping is desired for functional arguments.
The other is more subtle.
Consider the FACT example above.
If we were to use dynamic binding, then every time around the FACT1 loop it would be necessary to bind M and A on a stack.
Thus the binding stack would grow arbitrarily deep as we went around
