| Sussman and Steele | December 22, 1975 | 26 | Some Implementation Issues |
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-
