| Sussman and Steele | December 22, 1975 | 24 | Some Implementation Issues |
functional interpretation of the lambda calculus, i.e. the view that a "expression" (combination) represents a value to be "returned" (to replace the combination) to its "caller" (the process evaluating the combination containing the original one). The interpreter must provide for correctly resuming the caller when the callee has returned its value. The state of the computation at the time of the call must therefore be preserved. We see, then, that part of the state of the computation must be (a pointer to) the preserved state of its caller; we will call this component of the state the clink [McDermott and Sussman][1] [Bobrow and Wegbreit][2]. Just before the evaluation of a subexpression, the state of the current computation, including the clink, must be gathered together into a single data structure, which we will call a frame; the clink is then altered to point to this new frame. The evaluation of the subexpression then returns by restoring the state of the process from the current clink. Note that the value of the subexpression had better not be part of the state, for otherwise it would be lost by the state restoration. Thus, we only build a new frame if further computation would result in losing information which might be necessary. This only occurs if we must somehow return to that state. This in turn can only occur if we must evaluate an expression whose value must be obtained in order to continue computation in the current state.
This implies that no frame need be created in order to apply a lambda expression to its arguments. This in turn implies that the iterative and continuation-passing styles lead to no net creation of frames, because they are implemented only in terms of explicit lambda applications, whereas the recursive style leads to the creation of one net frame per level of recursive depth, because the recursive invocation involves the evaluation of a expression containing the recursive lambda application as a subexpression.
A clink in a lambda calculus-based interpreter is in fact equivalent to a low-level default continuation as created by the PLASMA interpreter. Such a continuation is a (closed) lambda expression of one argument whose script will carry on the computation after receiving the value of the subexpression. The clink mechanism is therefore not necessary, if we are willing to transform all our programs into pure continuation-passing style. We could do this explicitly, by requiring the user to write his programs in this form; or implicitly, as PLASMA does, by creating these one-argument continuations as necessary, passing them as hidden extra arguments to lambda expressions which behave like functions. On the other hand, we may think of a clink as a highly optimized continuation, whose "script" is that carefully coded portion of the lambda calculus interpreter which restores the frame and then carries on. We find this notion useful in defining a primitive, CATCH (named for the CATCH construct in MacLISP [Moon][3]), for "hairy control structure", similar to Reynolds' ESCAPE operator [Reynolds][4], which makes these low-level continuations available to the user. Note that PLASMA has a similar facility for getting hold of the low-level continuations, namely the "≡≡>" receiver construct.
Another problem for the implementor of an interpreter of a lambda calculus based language is the order in which to perform reductions. There are two standard orders of evaluation (and several other semi-standard ones, which we will not consider here). The first is Normal Order, which
- ↑ [McDermott and Sussman]
McDermott, Drew V. and Sussman, Gerald Jay. The CONNIVER Reference Manual. AI Memo 295a. MIT AI Lab (Cambridge, January 1974). - ↑ [Bobrow and Wegbreit]
Bobrow, Daniel G. and Wegbreit, Ben. "A Model and Stack Implementation of Multiple Environments." CACM 16, 10 (October 1973) pp. 591-603. - ↑ [Moon]
Moon, David A. MACLISP Reference Manual, Revision 0. Project MAC, MIT (Cambridge, April 1974). - ↑ [Reynolds]
Reynolds, John C. "Definitional Interpreters for Higher Order Programming Languages." ACM Conference Proceedings 1972.
