Gerald Jay Sussman

“ Lambda calculus is a model for the applicative component of programming languages. It models all non-imperative constructs as applications of functions and specifies the semantics of such expressions by a set of axioms or rewrite rules. One axiom states that a combination, i.e. an expression formed by a function applied to some arguments, is equivalent to the body of that function with the appropriate arguments substituted for the free occurrences of the formal parameters of the function in its body ”

“ Substitution Semantics and Programming Styles In the previous section we showed several different SCHEME programs for computing the factorial function. How are they different? We intuitively distinguish recursive from iterative programs, for example, by noting that recursive programs "call themselves" but in the last section we claimed to do iteration with a seemingly recursive program. Experienced programmers "know" that recursion uses up "stack" so a program implemented recursively will run out of stack on a sufficiently large problem. ”

“ A common iterative construct is the DO loop. The most general form we have seen in any programming language is the MacLISP DO [Moon] . It permits the simultaneous initialization of any number of control variables and the simultaneous stepping of these variables by arbitrary functions at each iteration step. The loop is terminated by an arbitrary predicate, and an arbitrary value may be returned. The DO loop may have a body, a series of expressions executed for effect on each iteration. ”

“ Recursive programs Now, let's see how lambda calculus may be used (informally) to model a computation. Consider the standard definition of the factorial function:
(DEFINE FACT (LAMBDA (N) (IF (= N 0) 1 (* N (FACT (- M 1) ) ) ) ) ) We are being very informal—lambda calculus as presented by [Church] does not include such constructs as DEFINE, IF, or =, *, or even 1! The "usual" lambda calculus construct for defining recursive functions is a rather obscure object called the "fixed-point" operator. We have been lax to avoid the hassle of "rigor mortis" in this tutorial paper. ”

“ 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. ”

“ 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 ”

“ 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. ”

“ Under a call-by-name implementation, the * mentioned above are in fact the actual argument expressions, each paired with the environment E. The evaluator has two additional rules:
when a variable x is to be evaluated in environment E1, then its associated expression-environment pair [A,E2] (which is equivalent to an ALGOL thunk) is looked up in E1, and then A is evaluated in E2. 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. ”

“ 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 ”

“ DEFINE This is analogous to the MacLISP DEFUN primitive (but note that the LAMBDA must appear explicitly!) . It is used for defining a function in the "global environment" permanently, as opposed to LABELS (see below) , which is used for temporary definitions in a local environment. DEFINE takes a name and a lambda expression; it closes the lambda expression in the global environment and stores the closure in the LISP value cell of the name (which is a LISP atom) . ”

“ 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 ”

“ This is another case where we must beware of using too much of the power of the host language; just as we must avoid using host recursion directly to implement recursion, so we must avoid using host interrupts directly to implement interrupts. We may not modify any register during a host language interrupt, except one (such as **TICK**) which is specifically intended to signal interrupts. Thus, if we were to add an interrupt character facility to SCHEME similar to that in MacLISP [Moon] , the MacLISP interrupt character function would merely set a register like **TICK** and dismiss ”

“ 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] . ”

“ A recursive control structure inherently creates expressions of unbounded size as a function of the recursion depth, while an iterative control structure produces a cycle of equivalent expressions, and so the expressions are of approximately the same size no matter how many iteration steps are taken. ”

“ MLOOP would eventually notice that this register had changed and dispatch to the interrupt handler. All this implies that the "microcode" for the interrupt handlers does not itself contain critical code that must be protected from host language interrupts.
When the scheduler is invoked, if there is another process waiting on the process queue, then the current process is swapped out and put on the end of the queue, and a new process swapped in from the front of the queue. The process stored on the queue consists of an atom which has the current frame and **VAL** register on its property list. ”

“ It will be convenient to think of an implementation machine which has certain operations, which are "micro-coded" in LISP; these are used to operate on various "registers", which are represented as free LISP variables. These registers are:
**EXP** The expression currently being evaluated. **ENV** A pointer to the environment in which to evaluate EXP. **CLINK** A pointer to the frame for the computation of which the current one is a subcomputation. **PC** The "program counter". As each "instruction" is executed, it updates **PC** to point to the next instruction to be executed. ”

“ A much simpler and more probable problem is that of building a pattern matcher with backtracking for segment matches. The matcher presented below is intended for matching single-level list structure patterns against lists of atoms. A pattern is a list containing three types of elements:
constant atoms, which match themselves only. (THV x) , which matches any single element in the expression consistently. We may abbreviate this as ?x by means of a LISP reader macro character. (THV* x) , which matches any segment of zero or more elements in the expression consistently. ”

“ The reason for this is that if the implementation language does not support certain kinds of control structures, then we will not be able to effectively interpret them. Thus, for example, if the control frame structure in the implementation language is constrained to be stack-like, then modelling more general control structures in the interpreted language will be very difficult unless we divorce ourselves from the constrained structures at the outset. ”

“ 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] [9] , 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. ”

“ After MATCH* matches a segment, it calls MATCH1 to continue the match, giving it a failure continuation which will back up and try to match a longer segment if possible. A failure can occur if a constant fails to match, or if one or the other of pattern and expression runs out before the other one does. ”

“ In the fourth section we will give a general discussion of the issues facing an implementor of an interpreter for a language based on lambda calculus. Finally, we will present a completely annotated interpreter for SCHEME, written in MacLISP [Moon] [4] , to acquaint programmers with the tricks of the trade of implementing non-recursive control structures in a recursive language like LISP.
This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. ”

“ They are used primarily for evaluation of components of combinations, but may be used for other purposes also. **TEM** A super-temporary register, used for random purposes, and not saved in **CLINK** frames or across interrupts. It therefore may not be used to pass information between "instructions" of the "machine", and so is best thought of as an internal hardware register. **QUEUE** A list of all processes other than the one currently being interpreted. **TICK** A magic register which a "hardware clock" sets to T every so often, used to drive the scheduler. ”

“ We can see here that no functional application returns a value in a computation of factorial in this situation. We believe that functional usage, where applicable (pun intended) , is more perspicuous than continuation-passing. We shall therefore use functional primitives such as * rather than ** wherever possible, keeping in mind that we could use ** instead if we wished.
Section 4: Some Implementation Issues The key problem is efficiency. Although it is easy to build an inefficient interpreter which straightforwardly performs expression substitutions ”

“ Acknowledgements This paper would not have happened if Sussman had not been forced to think about lambda calculus by having to teach 6.031, nor would it have happened had not Steele been forced to understand PLASMA by morbid curiosity.
This work developed out of an initial attempt to understand the actorness of actors. Steele thought he understood it, but couldn't explain it; Sussman suggested the experimental approach of actually building an "ACTORS interpreter". This interpreter attempted to intermix the use of actors and LISP lambda expressions in a clean manner. ”

“ E (NREST (CDR E) (- N 1) ) ) ) ) The main MATCH function also uses a subfunction called MATCH1 which takes four arguments: the tail of the pattern yet to be matched; the tail of the expression yet to be matched; the alist of match bindings made so far; and a continuation to call if the match fails at this point. A subfunction of MATCH, called MATCH*, handles the matching of segments of the expression against THV* match variables. It is in the matching of segments that the potential need for backtracking enters, for segments of various lengths may have to be tried. ”