Scheme: An Interpreter for Extended Lambda Calculus/Section 4
Section 4: Some Implementation Issues
[edit]The key problem is efficiency. Although it is easy to build an inefficient interpreter which straightforwardly performs expression substitutions; such an interpreter performs much unnecessary copying of intermediate expressions. The standard solution to this problem is to use an auxiliary structure, called the environment, which represents a set of virtual substitutions. Thus, when evaluating an expression of the form
in environment
instead of reducing it by performing
Subst[<args> <vars> <body>]
we reduce it to
<body>in environment
where pairlis creates a new environment E' in which the <vars> are logically paired with (i.e. "bound to") the corresponding <args>* (the precise meaning of <args>* will be explained presently), and in which any variables not in <vars> are bound as they were in E.
When using environments, it is necessary to keep them straight. For example, the following expression should manage to evaluate to 7:
(((LAMBDA (X) (LAMBDA (Y) (+ X Y))) 3) 4)
A substitution interpreter would cause the free occurrence of x in the inner lambda expression to be replaced by 3 before applying that lambda expression to 4. An interpreter which uses environments must arrange for the expression (+ x y) to be evaluated in an environment such that x is bound to 3 and y is bound to 4. This implies that when the inner lambda expression is applied to 4, there must be associated with it an environment in which x is bound to 3. In order to solve this problem we introduce the notion of a closure [McCarthy] [Moses] which is a data structure containing a lambda expression, and an environment to be used when that lambda expression is applied to arguments. We will notate a closure using the beta construct (our own notation, but isomorphic to the LISP funarg construct) as follows:
(BETA (LAMBDA <vars> <body>) <environment>)
When a lambda expression is to be evaluated, because it was passed as an argument, it evaluates to a closure of that lambda expression in the environment it is evaluated in (i.e., the environment it was passed from):
in environment
evaluates to
in environment
When a closure is to be applied to some arguments:
in environment
this is performed by reducing the application expression to
<body>in environment
That is, any free variables in the closed lambda expression refer to the environment as of the time of closure (E1), not as of the time of application (E2), whereas the arguments are evaluated in the application environment as expected.
This notion of closure has gone by many other names in other contexts. In LISP, for example, such a closure has been traditionally known as a funarg. ALGOL has several related ideas. Every ALGOL procedure is, at the time of its invocation, essentially a "downward funarg". In addition, expressions which are passed by name instead of by value are closed through the use of mechanisms called thunks [Ingerman]. It turns out that an actor (other than a cell or a serializer) is also a closure. Hewitt [Smith and Hewitt] describes an actor as consisting of a script, which is code to be executed, and a set of acquaintances, which are other actors which it knows about. We contend that the script is in fact identical to the lambda expression in a closure, and that the set of acquaintances is in effect an environment. As an example, consider the following code for cons; taken from [Smith and Hewitt] (cf. [Fischer]):
When the form[CONS ≡ (≡> [=A =B] (CASES (≡> FIRST? A) (≡> REST? B) (≡> LIST? YES)))]
(cons x y) is evaluated, the result is an (evaluated) cases statement, which is a receiver ready to accept a message such as "first?" or "rest?". This resulting receiver evidently knows about the actors x and y as being bound to the variables a and b; it is evidently a closure of the cases script plus a set of acquaintances which includes x and y (as well as "first?" and "rest?" and "yes", for example; PLASMA considers such "constant acquaintances" to be part of the set, whereas in SCHEME we might prefer to consider them part of the script). Once we realize that it is a closure and nothing more, we can see easily how to express the same semantics in SCHEME: (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 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][2] [Bobrow and Wegbreit][3]. 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][4]), for "hairy control structure", similar to Reynolds' ESCAPE operator [Reynolds][5], 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 corresponds roughly to ALGOL's "call by name", and the second is Applicative Order, which corresponds roughly to ALGOL's "call by value" or to LISP functional application.
Under a call-by-name implementation, the <args>* mentioned above are in fact the actual argument expressions, each paired with the environment E. The evaluator has two additional rules:
- when a variable
xis to be evaluated in environmentE1, then its associated expression-environment pair [A,E2] (which is equivalent to an ALGOL thunk) is looked up inE1, and thenAis evaluated inE2. - when a "primitive operator" is to be applied, its arguments must be evaluated at that time, and then the operator applied in a call-by-value manner.
Under a call-by-value implementation, the <args>* are the values of the argument expressions; i.e., the argument expressions are evaluated in environment E, and only then is the lambda expression applied. Note that this leads to trouble in defining conditionals. Under call-by-name one may define predicates to return (LAMBDA (X Y) X) for TRUE and (LAMBDA (X Y) Y) for FALSE, and then one may simply write
((= A B) <do this if TRUE> <do this if FALSE>)
This trick depends implicitly on the order of evaluation. It will not work under call-by-value, nor in general under any other reductive order except Normal Order. It is therefore necessary to introduce a special primitive operator (such as "if") which is applied in a call-by-name manner. This leads us to the interesting conclusion that a practical lambda calculus interpreter cannot be purely call-by-name or call-by-value; it is necessary to have at least a little of each.
There is a fundamental problem, however, with using Normal Order evaluation in a lambda calculus interpreter, which is brought out by the iterative programming style. We already know that no net frames are created by iterative programs, and that no net environment structures are created either. The problem is that under a call-by-name implementation there may be a net thunk structure created proportional in size to the number of iteration steps. This problem is inherent in Normal Order, because Normal Order substitution semantics exhibit the same phenomenon of increasing expression size. Therefore iteration cannot be effectively modeled in a call-by-name interpreter. An alternative view is that a call-by-name interpreter remembers more than is logically necessary to perform the computations indicated by the original expressions. This is indicated by the fact that the Applicative Order substitution semantics lead to expressions of fixed maximum size independent of the number of iteration steps.
It turns out that this conflict between call-by-name and iteration is resolved by the use of continuation-passing. If we use a pure continuation-passing programming style, then Normal Order and Applicative Order are the same order! In pure continuation-passing no combination is ever a subcombination of another combination. (This is the justification for the fact mentioned above that no clinks are needed if pure continuation-passing style is used.) Thus, if we wish to model iteration in pure lambda calculus without even an if primitive, we can use Normal Order substitutions and express the iteration in the continuation-passing style.
Under any reductive order, whether Normal Order, Applicative Order, or any other order, it is in practice convenient to introduce a means of terminating the evaluation process on a given form; in order to do this we introduce three different and equally useful notions. The first is the primitive operator such as +; the evaluator can apply such an operator directly, without substituting a lambda expression for the operator and reducing the resulting form. The second is the self-evaluating constant; this is used for primitive objects such as numbers, which effectively behave as if always "bound to themselves" in any environment. The third is the quoting function, which protects its argument from reductions so that it is returned as is; this is used for treating forms as data in the usual LISP manner.
These three ideas are not logically necessary, since the evaluation process will (eventually) terminate when no reductions can be made, but they are a great convenience for introducing various functions and data into the lambda calculus. Note too that some are easily defined in terms of the others; for example, instead of letting 3 be a self-evaluating constant, we could let 3 be a primitive operator of no arguments which returned 3, or we could merely quote it; similarly, instead of quoting forms we could let forms be a self-evaluating data type, as in MDL [Galley and Pfister] (better known as MUDDLE), written with different parentheses. Because, as we have said, these constructs are all strictly for convenience, we will not strive for any kind of minimality, but will continue to use all three notions in our interpreter, as we already have in our examples. We provide an interface so that all MacLISP subrs may be used as primitive operators; we define numbers to be self-evaluating; and we will use QUOTE to quote forms as in LISP (and thus we may use the "'" character as an abbreviation).
One final issue which the implementor of a lambda calculus based interpreter should consider is that of extensions to the language, such as primitives for side effects, multiprocessing, and synchronization of processes. Note that these are ideas which are very hard, if not impossible, to model using the substitution semantics of the lambda calculus, but which are easily incorporated in other semantic models, including the environment interpreter and, perhaps more notably, the ACTORS model [Greif and Hewitt]. The fundamental problem with modelling such concepts using substitution semantics is that substitution produces copies of expressions, and so cannot model the notion of sharing very well. In an interpreter which uses environments, all instances of a variable scoped in a given environment refer to the same virtual substitution contained in that environment, and so may be thought of as sharing a value cell in that environment. We can take advantage of this sharing by introducing a primitive operator which modifies the contents of a value cell; since all occurrences refer to the same value cell, changing the contents of that value cell will change the result of future references to that value cell (i.e., occurrences of the variable which invoke the virtual substitution mechanism). Such a primitive operator would then be similar to the SET function of LISP, or the := of ALGOL. We include such an operator, ASET, in our interpreter.
Introducing multiprocessing into the interpreter is fairly straightforward; all that is necessary is to introduce a mechanism for time-slicing the interpreter among several processes. One can even model this in substitution semantics by supposing that there can be more than one expression, and at each step an expression is randomly chosen to perform a reduction within. (On the other hand, synchronizing of the processes is very hard to model using substitution semantics!)
Since our value cells effectively solve the readers and writers problem (i.e. reads and writes of variables are indivisible) no more than our side effect primitive is necessary to synchronize our processes [Dijkstra] [Knuth] [Lamport]. However, the techniques for achieving synchronization using only := are quite cumbersome and opaque. It behooves the implementor to make things easier for the user by introducing a more tractable synchronization primitive (e.g. P+V or monitors or path expressions or ...). Machine language programmers have long known that the easiest way to synchronize processes is to turn off the scheduling clock during the execution of critical code. We have introduced such a primitive, EVALUATE!UNINTERRUPTIBLY, (which is a sort of "over-anxious serializer", because it locks out the whole world) into our interpreter.
References
[edit]- ↑ [Moses]
Moses, Joel. The Function of FUNCTION in LISP. AI Memo 199, MIT AI Lab (Cambridge, June 1970). - ↑ [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.