| Sussman and Steele | December 22, 1975 | 23 | Some Implementation Issues |
(DEFINE CONS (LAMBDA (A B) (LAMBDA (M) (IF (EQ M 'FIRST?) A (IF (EQ M 'REST?) B (IF (EQ M 'LIST?) 'YES (ERROR '|UNRECOGNIZED MESSAGE - CONS| M 'WRNG-TYPE-ARG)))))))
Note that we have used explicit eq tests on the incoming message rather than the implicit pattern-matching of the cases statement, but the underlying semantics of the approach are the same.
There are several important consequences of closing every lambda expression in the environment from which it is passed (i.e., in its "lexical" or "static" environment). First, the axioms of lambda calculus are automatically preserved. Thus, referential transparency is enforced. This in turn implies that there are no "fluid" variable bindings (as there are in standard stack implementations of LISP such as MacLISP). Second, the upward funarg problem [Moses][1] requires that the environment structure be potentially tree-like. Finally, the environment at any point in a computation can never be deeper than the lexical depth of the expression being evaluated at that time; i.e., the environment contains bindings only for variables bound in lambdas lexically surrounding the expression being evaluated. This is true even if recursive functions are involved. It follows that if list structures are used to implement environments, the time to look up a variable is proportional only to the lexical distance from the reference to the binding and not to the depth of recursion or any other dynamic parameter. Therefore it is not necessarily as expensive as many people have been led to believe. Furthermore, it is not even necessary to scan the environment for the variable, since its value must be in a known position relative to the top of the environment structure; this position can be computed by a compiler at compile time on the basis of lexical scope. The tree-like structure of an environment prevents one from merely indexing into the it, however; it is necessary to cdr down it. (Some ALGOL compilers use a similar technique involving base registers pointing to sets of variables for each level of block nesting; it is necessary to determine the base pointer for the block desired for a variable reference, but then the variable is at a known offset from the base address.) It also follows that an iterative programming style will lead to no net accumulation of environment structures in the interpreter. The recursive style, with or without continuation-passing, will lead to accumulation of environment structures as a function of the recursion depth, not because any environment becomes arbitrarily deep, but rather because at each level of recursion it is necessary to save the environment at that point. It is saved by the interpreter in the case of traditional recursion, so that computation can continue in the correct environment on return from the recursive call; it is saved as part of the continuation closure in continuation-passing.
Another problem is concerned with control. This is a consequence of the
- ↑ [Moses]
Moses, Joel. The Function of FUNCTION in LISP. AI Memo 199, MIT AI Lab (Cambridge, June 1970).
