.vsp 8 .squish .c j 2sgronk <:s-bcode; .nofill 15.i 12.i ! .c ! i.select 1 15.i 12.i ! .c ! i.spw 13 15.i 12.i ! .c ! i.block  .( 0u8 ! .c ! :k i.spw 16 15.i 12.i ! .c ! i.select 0 15.i 12.i ! .c ! i.adjust 15.i 12.i ! .c ! i.sp )j q8\> !gronk! .c << text font >> .font 0 25fr1 .c << SCHEME font >> .font 1 22fg .c << heading fonts >> .font 2 30vrb .font 4 gls;foo1 .ulfont 5 .quote  .dummy _ .twinch 6.25 .tlinch 9 .sidm 53 .c << want to flush losing multiple cr's >> .crcomp .c << want to make leading spaces on line small >> .spw 16 .c << want to have at least 3 lines of a section on a page >> .sblock 5 .adjust .center 2MASSACHUSETTS INSTITUTE OF TECHNOLOGY .CENTER ARTIFICIAL INTELLIGENCE LABORATORY .sp 2 .spread /0AI Memo No. 453//December 1977 .sp 2 .center 2Some Little Interpreters for LISP-Like Languages .sp .center or, The Art of the Interpreter .sp 2 .center 0by .sp .center Guy Lewis Steele Jr. * and Gerald Jay Sussman .sp 2 0Abstract: .sp .sp 2 .in 10 .un 10 Keywords:__LISP, SCHEME, LISP-like languages, lambda-calculus, lexical scoping, dynamic scoping, fluid variables, control structures, environments .in 0 .sp 2 This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory's artificial intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-75-C-0643. .sp *__NSF Fellow .page .spage .php1 .he1 1Steele and Sussman  .he2 1Some Little Interpreters0 .nofill .crreta What we got here: REVAL 0 1 7 recursion equation interpreter - no LAMBDA Environments TEVAL 0 1 7 FEVAL 1 3 7 has fluids FEVAL1 has fluids, no funargs FEVAL2 0 1 3 7 has lexicals AND fluids Normal Order NEVAL 0 2 7 normal order NFEVAL normal w/lexical and fluid Neat things you can do by hacking LOOKUP Shallow vs. deep? Property of lookup only. Call-by-need Neat ways to do PRIMOP/DEFINE CPSEVAL 0 1 7 9 cps-style primitives meta-circular lifted Additional magic forms FOOEVAL FEVAL2 with ASETQ, FLUIDSETQ, and LABELS SEVAL 0 1 4 6 has extensible syntax (dispatched syntax lookup) BSEVAL 0 1 4 5 6 bound syntaxfns (??) SCHEVAL 0 1 3 4 6 8 the quintessential language 0. lexicals 1. applicative order 2. normal order 3. fluids 4. extra syntax 5. bound syntax 6. global environment 7. wired-in primops 8. has CATCH 9. CPS .crcomp .adjust .page .section @.__General Structure of Interpreters for LISP-Like Languages .sp The core of a LISP interpreter is the two procedures 1EVAL* and 1APPLY*. 1EVAL* interprets an expression relative to a given environment. .page .nofill .select 1 .spw 13 .block 2 (DEFINE (BIND VARS ARGS ENV) (COND ((= (LENGTH VARS) (LENGTH ARGS)) (CONS (CONS VARS ARGS) ENV)) (T (ERROR '|WRONG NUMBER OF ARGUMENTS| (LIST VARS ARGS))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (VALUE NAME ENV) (VALUE1 NAME (LOOKUP NAME ENV))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (VALUE1 NAME SLOT) (COND ((EQ SLOT '&UNBOUND) (ERROR '|CAN'T REFERENCE UNBOUND VARIABLE| NAME)) (T (CAR SLOT)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 3 (DEFINE (LOOKUP NAME ENV) (COND ((NULL ENV) '&UNBOUND) (T (LOOKUP1 NAME (CAAR ENV) (CDAR ENV) (CDR ENV))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 6 (DEFINE (LOOKUP1 NAME VARS VALS REST) (COND ((NULL VARS) (LOOKUP NAME REST)) ((EQ NAME (CAR VARS)) VALS) (T (LOOKUP1 NAME (CDR VARS) (CDR VALS) REST)))) .spw 16 .select 0 .adjust .sp .page .section A.__REQ:__A Complete Metacircular Interpreter for Recursion Equations .sp The language interpreted by REQ is a dialect of LISP which allows no free variables except for names of primitive or defined procedures, and no definitions of procedures within other procedures. This universal language is essentially that of Kleene recursion equations {ref}. The driver loop reads in definitions of procedures of the abstract form: .sp .nofill f(a,b,c,...) = .adjust .sp and saves them. It can also read in requests to apply some defined procedure to some arguments (or, more generally, to evaluate any expression, which may refer to defined functions, but need not, for example a request to see the value of a variable), in which case it prints the resulting value. The defined procedures may refer to each other and to initially supplied primitive procedures (such as 1CAR*, 1CONS*, etc.). Definitions may contain "forward references", as long as all necessary definitions are present at the time of a request for a computation. Definitions are written as LISP s-expressions in the form: .sp .nofill .select 1 .spw 13 .block 1 (DEFINE (F A B C ...) ) .spw 16 .select 0 .adjust .sp An expression may consist of variable references, constants (numbers and quoted s-expressions), procedure calls, and conditional expressions (1COND*). The interpreter is presented here as a set of such definitions, and so is meta-circular {ref}. The language processed by REQ is intended to be evaluated in applicative order; that is, all arguments to a function are fully evaluated before an attempt is made to apply the function to the arguments. (It is necessary to state this explicitly here, as it is not inherent in the form of the meta-circular definition. See [Reynolds] for an explication of this problem.) The driver loop is conceptually started by a request to invoke 1DRIVER* with no arguments. The expression 1* is intended to represent a constant list structure containing definitions of primitive functions. Note carefully the use of the variable 1TOPENV*. When 1DRIVER-LOOP-1* calls 1EVAL* it passes as both 1ENV* and 1TOPENV* the current top-level environment, which contains definitions of all primitive functions and all functions defined so far by the user. 1TOPENV* is passed around by 1EVAL* and 1APPLY*, and is used only in 1APPLY*. The bodies of user functions are evaluated in an environment consisting of 1TOPENV* plus the formal parameters of the function bound to the respective arguments. Thus, the only variables visible to the body of a function are its formal parameters plus the global function definitions, with the former having priority. We shall have occasion to refer to this situation later. .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER) (DRIVER-LOOP (PRINT '|LITHP ITH LITHTENING|))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER-LOOP TOPENV HUNOZ) (DRIVER-LOOP-1 TOPENV (READ))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 9 (DEFINE (DRIVER-LOOP-1 TOPENV FORM) (COND ((ATOM FORM) (DRIVER-LOOP TOPENV (PRINT (EVAL FORM TOPENV TOPENV)))) ((EQ (CAR FORM) 'DEFINE) (DRIVER-LOOP (BIND (LIST (CAADR FORM)) (LIST (LIST '&FUNCTION (CDADR FORM) (CADDR FORM))) TOPENV) (PRINT (CAADR FORM)))) (T (DRIVER-LOOP TOPENV (PRINT (EVAL FORM TOPENV TOPENV)))))) .spw 16 .select 0 .adjust .sp .c REVAL - recursion equations interpreter .nofill .select 1 .spw 13 .block 11 (DEFINE (EVAL EXP ENV TOPENV) (COND ((ATOM EXP) (COND ((NUMBERP EXP) EXP) (T (VALUE EXP ENV)))) ((EQ (CAR EXP) 'QUOTE) (CADR EXP)) ((EQ (CAR EXP) 'COND) (EVCOND (CDR EXP) ENV TOPENV)) (T (APPLY (EVAL (CAR EXP) ENV TOPENV) (EVLIS (CDR EXP) ENV TOPENV) TOPENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 7 (DEFINE (APPLY FUN ARGS TOPENV) (COND ((PRIMOP FUN) (PRIMOP-APPLY FUN ARGS)) ((EQ (CAR FUN) '&FUNCTION) (EVAL (CADADR FUN) (BIND (CAADR FUN) ARGS TOPENV) TOPENV)) (T (ERROR '|UNKNOWN FUNCTION| (LIST FUN ARGS))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 5 (DEFINE (EVCOND CLAUSES ENV TOPENV) (COND ((NULL CLAUSES) NIL) ((EVAL (CAAR CLAUSES) ENV TOPENV) (EVAL (CADAR CLAUSES) ENV TOPENV)) (T (EVCOND (CDR CLAUSES) ENV TOPENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (EVLIS ARGLIST ENV TOPENV) (COND ((NULL ARGLIST) NIL) (T (CONS (EVAL (CAR ARGLIST) ENV TOPENV) (EVLIS (CDR ARGLIST) ENV TOPENV))))) .spw 16 .select 0 .adjust .sp {topenv is the gritch that probably caused fluids to get invented in the first place} .page .section B.__REQVC:__A Metacircular Interpreter for Recursion Equations Using Value Cells .sp The definition of REQ is conceptually clean in that (except for 1READ* and 1PRINT*) no side effects are necessary in its operation. The top level driver loop iterates, reading in expressions, and on seeing a 1DEFINE*-form augments the top-level environment simply by adding a new binding to it. One consequence of this, however, is that less recent bindings get pushed farther and farther down, and so become more and more expensive to access. One would like to be able to access function definitions quickly, because they are used all the time. One needs a way to access a variable binding in constant time given the atomic symbol representing that variable. The solution adopted in most LISP systems is to regard atomic symbols as data structures having accessible components. (Given this view, they are no longer conceptually "atomic" or indivisible!) Typical components are the "property list" and "value cell". We shall assume that there are two primitive procedures which our interpreter can use. 1(GETVC )* will deliver as its value the contents of the value cell of the specified atomic symbol. 1(SETVC )* will put the given s-expression in the value cell of the given symbol (a side effect!). We can then define the top-level environment to be those values which are in the value cells of the atomic symbols. We assume that the symbols representing primitive procedures initially have those procedures in their value cells, and that all other symbols initially have 1&UNBOUND* in their value cells. We will use 1SETVC* only in a controlled way, by redefining some of our utility and driver routines. .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (VALUE1 NAME SLOT) (COND ((EQ SLOT '&UNBOUND) (COND ((EQ (GETVC NAME) '&UNBOUND) (ERROR '|CAN'T REFERENCE UNBOUND VARIABLE| NAME)) (T (GETVC NAME)))) (T (CAR SLOT)))) .spw 16 .select 0 .adjust .sp We arrange for 1NIL* to represent the top-level environment by changing 1VALUE1* to check the value cell of a symbol if 1LOOKUP* cannot find a value for it. .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER) (DRIVER-LOOP NIL (PRINT '|LITHP ITH LITHTENING|))) .spw 16 .select 0 .adjust .sp The top-level environment resides in the global state of all the value cells, and so we do not represent it explicitly in our recursion equations. .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER-LOOP HUNOZ HUKAIRZ) (DRIVER-LOOP-1 (READ))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 9 (DEFINE (DRIVER-LOOP-1 TOPENV FORM) (COND ((ATOM FORM) (DRIVER-LOOP TOPENV (PRINT (EVAL FORM TOPENV TOPENV)))) ((EQ (CAR FORM) 'DEFINE) (DRIVER-LOOP (SETVC (CAADR FORM) (LIST '&FUNCTION (CDADR FORM) (CADDR FORM))) (PRINT (CAADR FORM)))) (T (DRIVER-LOOP TOPENV (PRINT (EVAL FORM TOPENV TOPENV)))))) .spw 16 .select 0 .adjust .sp When a 1DEFINE*-form is encountered, we use 1SETVC* to install the new definition in the value cell of the symbol which represents the name of the defined procedure. .page .section C.__LEX with Bug:__An Incorrect Interpreter for Lexically Scoped LISP .sp The interpreter LEX (and all following interpreters, until further notice), are written as recursion equations suitable for interpretation by REQ (or REQVC). Thus these interpreters are not necessarily meta-circular (though they may be if the language they interpret is only an extension of REQ's). For example, if the whole of LEX were read into REQ and then the form 1(DRIVER)* were read in, one would then be able to read in definitions in the LEX language (running by two levels of interpretation: REQ interpreting LEX interpreting whatever followed). The dialect of LISP interpreted by LEX allows the free use of functional arguments. An expression of the form .sp .nofill .select 1 .spw 13 .block 1 1(LAMBDA (A B C ...) ) .spw 16 .select 0 .adjust .sp evaluates to a function, which may then be used as if it had been given a name 1F* by a definition 1(DEFINE_(F_...)_...)* and then the name 1F* were referred to. However, if any free variable reference appears in the body of the 1LAMBDA*-expression, and there is a binding of that variable in some other 1LAMBDA*-expression (or 1DEFINE*-form) which lexically contains it, then the variable reference is construed to refer to the innermost (nearest) such surrounding binding of that variable. Thus, variables in this language are scoped as in ALGOL [Naur]. The 1LAMBDA*-expressions in this language are intended to reflect the behavior of lambda-calculus {ref}. The LEX interpreter exhibited here is modelled on the interpreter REQ. As we will see shortly, this will produce a bug, which will arise from the attempt to mix 1LAMBDA*-calculus with recursion equations. In the next section we will correct this bug. The 1EVAL* in LEX is similar to that in REQ, except that 1TOPENV* is not passed around, and a new clause has been added to recognize 1LAMBDA*-expressions. When one is seen, a 1&FUNARG* object is produced, which is intended to be the function denoted by the 1LAMBDA*-expression with respect to the environment in which it was encountered (this is the parameter 1ENV* passed to 1EVAL*). A 1&FUNARG* object differs from a 1&FUNCTION* object as used by REQ in that it contains an environment in which the "code" or "script" {ref} for the function is closed. This environment contains values for variables lexically apparent to the 1LAMBDA*-expression. In REQ this was unnecessary because all functions referred only to their parameters and the global environment, and so all functions were, in effect, closed in the top-level environment. In LEX, functions can refer to bound variables other than its own parameters, and so each function must specify precisely which free variables are visible to its body. The 1APPLY* in LEX differs from the one in REQ in that when applying a 1&FUNARG* object it binds the parameters onto the environment contained in the 1&FUNARG* object, rather than onto the top-level environment. In this way the body of the 1LAMBDA*-expression sees variables lexically apparent to the 1LAMBDA*-expression, plus the parameter bindings, with the latter having precedence. The driver for LEX differs from the one for REQ. In 1DRIVER-LOOP-1*, there are two changes. First, only one copy of TOPENV is given to 1EVAL*, not two, because in LEX 1EVAL* and 1APPLY* evidently do not need to pass 1TOPENV* around for the sake of providing an environment to bind onto. Second, functions produced by 1DEFINE* are 1&FUNARG* objects, and so must contain an environment. Thus we put a pointer to 1TOPENV* in the 1&FUNARG* object. This is where the bug arises. We want functions to be able to refer to other functions whose 1DEFINE* forms may not have been read in yet. If, however, a pointer to 1TOPENV* is included in the 1&FUNARG* object for the earlier function, that version of 1TOPENV* will not contain the definition of the later function. In providing for the correct modelling of lambda-calculus, we have lost the ability to model recursion equations. Of course, this interpreter will suffice if all we want to do is model lambda-calculus, which does not permit such circular references. .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER) (DRIVER-LOOP (PRINT '|LITHP ITH LITHTENING|))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER-LOOP TOPENV HUNOZ) (DRIVER-LOOP-1 TOPENV (READ))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 9 (DEFINE (DRIVER-LOOP-1 TOPENV FORM) (COND ((ATOM FORM) (DRIVER-LOOP TOPENV (PRINT (EVAL FORM TOPENV)))) ((EQ (CAR FORM) 'DEFINE) (DRIVER-LOOP (BIND (LIST (CAADR FORM)) (LIST (LIST '&FUNARG (CDADR FORM) (CADDR FORM) TOPENV)) TOPENV) (PRINT (CAADR FORM)))) (T (DRIVER-LOOP TOPENV (PRINT (EVAL FORM TOPENV)))))) .spw 16 .select 0 .adjust .sp .c TEVAL - simple lexical interpreter with funargs .nofill .select 1 .spw 13 .block 12 (DEFINE (EVAL EXP ENV) (COND ((ATOM EXP) (COND ((NUMBERP EXP) EXP) (T (VALUE EXP ENV)))) ((EQ (CAR EXP) 'QUOTE) (CADR EXP)) ((EQ (CAR EXP) 'LAMBDA) (LIST '&FUNARG (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'COND) (EVCOND (CDR EXP) ENV)) (T (APPLY (EVAL (CAR EXP) ENV) (EVLIS (CDR EXP) ENV))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 8 (DEFINE (APPLY FUN ARGS) (COND ((PRIMOP FUN) (PRIMOP-APPLY FUN ARGS)) ((EQ (CAR FUN) '&FUNARG) (EVAL (CADDR FUN) (BIND (CADR FUN) ARGS (CADDDR FUN)))) (T (ERROR '|UNKNOWN FUNCTION| (LIST FUN ARGS))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 5 (DEFINE (EVCOND CLAUSES ENV) (COND ((NULL CLAUSES) NIL) ((EVAL (CAAR CLAUSES) ENV) (EVAL (CADAR CLAUSES) ENV)) (T (EVCOND (CDR CLAUSES) ENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (EVLIS ARGLIST ENV) (COND ((NULL ARGLIST) NIL) (T (CONS (EVAL (CAR ARGLIST) ENV) (EVLIS (CDR ARGLIST) ENV))))) .spw 16 .select 0 .adjust .sp .page .section D.__LEX:__A Correct Interpreter for Lexically Scoped LISP .sp Our basic problem is that we wish to provide at the top level a means of incrementally modifying the top-level environment so that circular definitions can be used. Achieving this circularity requires some kind of conceptual side-effect. One way we can accomplish this is to use value cells, just as we did for REQVC. The primitive 1SETVC* provides us with the necessary side-effect for modifying the top-level environment. However, the local environments stored in 1&FUNARG* objects are not subject to modification. As before, 1NIL* represents the top-level environment, and we use the 1VALUE1* routine of REQVC, which first searches the given local environment, and then checks the top-level environment if necessary. The driver loop makes up 1&FUNARG* objects which contain 1NIL* as the environment of closure. .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER) (DRIVER-LOOP NIL (PRINT '|LITHP ITH LITHTENING|))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER-LOOP HUNOZ HUKAIRZ) (DRIVER-LOOP-1 (READ))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 9 (DEFINE (DRIVER-LOOP-1 FORM) (COND ((ATOM FORM) (DRIVER-LOOP NIL (PRINT (EVAL FORM TOPENV)))) ((EQ (CAR FORM) 'DEFINE) (DRIVER-LOOP (SETVC (CAADR FORM) (LIST '&FUNARG (CDADR FORM) (CADDR FORM) NIL)) (PRINT (CAADR FORM)))) (T (DRIVER-LOOP NIL (PRINT (EVAL FORM TOPENV)))))) .spw 16 .select 0 .adjust .sp Another way we could have solved our problem would be to pass around 1TOPENV* as we did in REQ; but instead of using 1TOPENV* within 1APPLY*, we would pass it to 1VALUE* along with the local environment. 1VALUE* would first check the local environment using 1LOOKUP*, and then check the top-level environment in the same manner. The effect is that we have broken the environment of every 1&FUNARG* object into two parts, local and global, such that we can shoehorn extra function definitions into the second part incrementally. Thus, alhough we avoid the particular side-effect of the primitive 1SETVC*, we have introduced a conceptual side-effect in that the meaning of a 1&FUNARG* object can still change over time, thanks to the alteration of the second part. In either of these ways we can achieve a synthesis of the recursion equation approach and the lambda-calculus approach. As long as we make use only of locally bound variables, our programs will emulate lambda-calculus; if we make use only of global variables and immediately bound parameters, our programs will emulate recursion equations. But what of the interactions between the two worlds? Can we be sure that our synthesis has not somehow destroyed the intuitive semantics of one or the other discipline? Are there other possible extensions of either which excludes the other? .page .section E.__FLU:__An Interpreter for LISP with Fluid (Dynamically Bound) Variables .sp Let us go back to our original definition of REQ, and consider afresh the possibility of introducing lambda-notation into the language, so that function definitions may be mentioned within other functions. We naturally want to do this with minimal perturbation to the existing interpreter. Let us suppose that we start with a version of REQ which does not pass around 1TOPENV*; all functions remain the same, except that 1EVAL* and 1APPLY* take one fewer parameter each. We still need the contents of 1TOPENV*, however, in order to perform the 1BIND* in 1APPLY*. We notice, however, that 1APPLY* is called only from 1EVAL*, and that 1EVAL* has available to it the paremeter 1ENV*. Now 1ENV* is guaranteed to contain the top-level environment within it -- possibly with other bindings as well, but that will not affect the behavior of properly written recursion equations. We therefore alter 1APPLY* to take an additional parameter 1ENV*, and alter 1EVAL* to pass its environment along. Now, in order to allow lambda-notation, we add a clause to 1EVAL* which will detect 1LAMBDA*-expressions and produce an appropriate 1FUNCTION* object just like the 1&FUNCTION* objects made up by REQ's top-level driver. In this way we have produced a version of REQ which is simpler (because we don't have to pass around 1TOPENV*) and which allows lambda-notation. However, it does not model lambda-calculus, because no care is taken to ensure that a 1&FUNCTION* object gets run in the associated lexical environment. Instead, it is applied in whatever environment is extant at the time it is invoked. What we have, in fact, is the "fluid" or "dynamic" variable binding behavior usually attributed to LISP. Notice that we have shown 1EVAL* as including an environment in the 1&FUNCTION* object even though it is not later used. We have done this to make a point. Suppose we were to alter the third argument to 1BIND* in 1APPLY* from 1ENV* to 1(CADDDR_FUN)*. Comparing the result with the LEX interpreter, we see that we would then have a lexically scoped language! Our point is that the difference between lexical and fluid scoping is a very tiny one. There are two environments floating around in 1APPLY*, one in the 1&FUNCTION* object and one passed from 1EVAL*. Which discipline of variable scoping you get depends only on which one you grab when it is time to 1BIND*. .sp .c FEVAL - simple fluid interpreter (CRUFTY OLD LISP) .nofill .select 1 .spw 13 .block 13 (DEFINE (EVAL EXP ENV) (COND ((ATOM EXP) (COND ((NUMBERP EXP) EXP) (T (VALUE EXP ENV)))) ((EQ (CAR EXP) 'QUOTE) (CADR EXP)) ((EQ (CAR EXP) 'LAMBDA) (LIST '&FUNCTION (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'COND) (EVCOND (CDR EXP) ENV)) (T (APPLY (EVAL (CAR EXP) ENV) (EVLIS (CDR EXP) ENV) ENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 8 (DEFINE (APPLY FUN ARGS ENV) (COND ((PRIMOP FUN) (PRIMOP-APPLY FUN ARGS)) ((EQ (CAR FUN) '&FUNCTION) (EVAL (CADDR FUN) (BIND (CADR FUN) ARGS ENV))) (T (ERROR '|UNKNOWN FUNCTION| (LIST FUN ARGS))))) .spw 16 .select 0 .adjust .sp {Can be bummed: &funarg => lambda, and don't cons in env} {cf. recursion eqns interpreter} .page .section F.__FLUBUM:__A Bummed Version of the Fluid Interpreter .sp Now, being good hackers, we want to eliminate unnecessary code. We can either not include an environment in the 1&FUNCTION* object, or we can not pass an environment from 1EVAL* to 1APPLY*. We did the latter in LEX. If, however, we were starting from REQ without a 1TOPENV*, as postulated, we would more likely do the former. This would be more consistent with the existing format of functions in REQ, and also it's very easy to pass 1ENV* from 1EVAL* to 1APPLY*. (In a machine language implementation it would probably take no effort at all -- the environment most likely would be sitting around in some register anyway!) We still have the problem of how the incremental changes to the top-level environment are to take effect, if we do not pass around 1TOPENV* explicitly. We will assume that we adopt the method of value cells. Now, if we do not include an environment in our 1&FUNCTION* objects, we notice the following neat hack: we can use the word 1LAMBDA* as a substitute for 1&FUNCTION*, and then we do not need to "cons up" a functional object at all! Instead, we can just return the 1LAMBDA*-expression itself from 1EVAL*, knowing that 1APPLY* will treat it as a function object! Next, we note that we can save a little code in 1EVAL*. Rather than having a special test for 1LAMBDA*, we can just require the user to write 1(QUOTE (LAMBDA_...))* instead of simply 1(LAMBDA_...)*, because after all 1EVAL* will only return the same 1LAMBDA*-expression anyway. By this sequence of hacks and bums we have progressed from a simple recursion equations interpreter to what is essentially LISP 1.5. .sp .c FEVAL1 - bummed simple fluid interpreter .nofill .select 1 .spw 13 .block 13 (DEFINE (EVAL EXP ENV) (COND ((ATOM EXP) (COND ((NUMBERP EXP) EXP) (T (VALUE EXP ENV)))) ((EQ (CAR EXP) 'QUOTE) (CADR EXP)) ((EQ (CAR EXP) 'LAMBDA) EXP) ((EQ (CAR EXP) 'COND) (EVCOND (CDR EXP) ENV)) (T (APPLY (EVAL (CAR EXP) ENV) (EVLIS (CDR EXP) ENV) ENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 8 (DEFINE (APPLY FUN ARGS ENV) (COND ((PRIMOP FUN) (PRIMOP-APPLY FUN ARGS)) ((EQ (CAR FUN) 'LAMBDA) (EVAL (CADDR FUN) (BIND (CADR FUN) ARGS ENV))) (T (ERROR '|UNKNOWN FUNCTION| (LIST FUN ARGS))))) .spw 16 .select 0 .adjust .sp {could just flush the test for LAMBDA in EVAL and use QUOTE!} {we have coerced the representation for the function to BE the function?!} .page .c FEVAL2 mixed implementation of lexicals and fluids .nofill .select 1 .spw 13 .block 17 (DEFINE (EVAL EXP ENV FENV) (COND ((ATOM EXP) (COND ((NUMBERP EXP) EXP) (T (VALUE EXP ENV)))) ((EQ (CAR EXP) 'QUOTE) (CADR EXP)) ((EQ (CAR EXP) 'LAMBDA) (LIST '&FUNARG (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'FLAMBDA) (LIST '&FLUNARG (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'COND) (EVCOND (CDR EXP) ENV)) ((EQ (CAR EXP) 'FLUID) (VALUE (CADR EXP) FENV)) (T (APPLY (EVAL (CAR EXP) ENV) (EVLIS (CDR EXP) ENV) FENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 15 (DEFINE (APPLY FUN ARGS FENV) (COND ((PRIMOP FUN) (PRIMOP-APPLY FUN ARGS FENV)) ((EQ (CAR FUN) '&FUNARG) (EVAL (CADDR FUN) (BIND (CADR FUN) ARGS (CADDDR FUN)) FENV)) ((EQ (CAR FUN) '&FLUNARG) (EVAL (CADDR FUN) (CADDDR FUN) (BIND (CADR FUN) ARGS FENV))) (T (ERROR '|UNKNOWN FUNCTION| (LIST FUN ARGS))))) .spw 16 .select 0 .adjust .sp .page .c NEVAL - simple lexical interpreter with call-by-name .nofill .select 1 .spw 13 .block 12 (DEFINE (EVAL EXP ENV) (COND ((ATOM EXP) (COND ((NUMBERP EXP) EXP) (T (VALUE EXP ENV)))) ((EQ (CAR EXP) 'QUOTE) (CADR EXP)) ((EQ (CAR EXP) 'LAMBDA) (LIST '&FUNARG (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'COND) (EVCOND (CDR EXP) ENV)) (T (APPLY (EVAL (CAR EXP) ENV) (THUNKLIS (CDR EXP) ENV))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 8 (DEFINE (APPLY FUN ARGS) (COND ((PRIMOP FUN) (PRIMOP-APPLY FUN (DETHUNKLIS ARGS))) ((EQ (CAR FUN) '&FUNARG) (EVAL (CADDR FUN) (BIND (CADR FUN) ARGS (CADDDR FUN)))) (T (ERROR '|UNKNOWN FUNCTION| (LIST FUN ARGS))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (VALUE NAME ENV) (VALUE1 NAME (LOOKUP NAME ENV))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (VALUE1 NAME SLOT) (COND ((EQ SLOT '&UNBOUND) (ERROR '|CAN'T REFERENCE UNBOUND VARIABLE| NAME)) (T (DETHUNK (CAR SLOT))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DETHUNK THUNK) (EVAL (CAR THUNK) (CDR THUNK))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (MAKE-THUNK EXP ENV) (CONS EXP ENV)) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (THUNKLIS ARGLIST ENV) (COND ((NULL ARGLIST) NIL) (T (CONS (MAKE-THUNK (CAR ARGLIST) ENV) (THUNKLIS (CDR ARGLIST) ENV))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (DETHUNKLIS THUNKLIST) (COND ((NULL THUNKLIST) NIL) (T (CONS (DETHUNK (CAR THUNKLIST)) (DETHUNKLIS (CDR THUNKLIST)))))) .spw 16 .select 0 .adjust .sp .page .c NFEVAL - simple lexical interpreter with call-by-name and fluids .nofill .select 1 .spw 13 .block 17 (DEFINE (EVAL EXP ENV FENV) (COND ((ATOM EXP) (COND ((NUMBERP EXP) EXP) (T (VALUE EXP ENV)))) ((EQ (CAR EXP) 'QUOTE) (CADR EXP)) ((EQ (CAR EXP) 'LAMBDA) (LIST '&FUNARG (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'FLAMBDA) (LIST '&FLUNARG (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'COND) (EVCOND (CDR EXP) ENV)) ((EQ (CAR EXP) 'FLUID) (VALUE (CADR EXP) FENV)) (T (APPLY (EVAL (CAR EXP) ENV) (THUNKLIS (CDR EXP) ENV) FENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 15 (DEFINE (APPLY FUN ARGS FENV) (COND ((PRIMOP FUN) (PRIMOP-APPLY FUN (DETHUNKLIS ARGS FENV))) ((EQ (CAR FUN) '&FUNARG) (EVAL (CADDR FUN) (BIND (CADR FUN) ARGS (CADDDR FUN)) FENV)) ((EQ (CAR FUN) '&FLUNARG) (EVAL (CADDR FUN) (CADDDR FUN) (BIND (CADR FUN) ARGS FENV))) (T (ERROR '|UNKNOWN FUNCTION| (LIST FUN ARGS))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (VALUE NAME ENV) (VALUE1 (LOOKUP NAME ENV))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (VALUE1 NAME SLOT) (COND ((EQ SLOT '&UNBOUND) (ERROR '|CAN'T REFERENCE UNBOUND VARIABLE| NAME)) (T (DETHUNK (CAR SLOT))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DETHUNK THUNK FENV) (EVAL (CAR THUNK) (CDR THUNK) FENV)) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (MAKE-THUNK EXP ENV) (CONS EXP ENV)) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (THUNKLIS ARGLIST ENV) (COND ((NULL ARGLIST) NIL) (T (CONS (MAKE-THUNK (CAR ARGLIST) ENV) (THUNKLIS (CDR ARGLIST) ENV))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (DETHUNKLIS THUNKLIST FENV) (COND ((NULL THUNKLIST) NIL) (T (CONS (DETHUNK (CAR THUNKLIST) FENV) (DETHUNKLIS (CDR THUNKLIST) FENV))))) .spw 16 .select 0 .adjust .sp .page .c CPSEVAL - tail-recursive recursion eqns meta-circular - slightly bummed .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER) (DRIVER-LOOP THE-INITIAL-ENVIRONMENT (PRINT '|LITHP ITH LITHTENING|))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER-LOOP ENV HUNOZ) (DRIVER-LOOP-1 ENV (READ))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 9 (DEFINE (DRIVER-LOOP-1 ENV FORM) (COND ((ATOM FORM) (EVAL FORM ENV ENV (LIST DRIVER-LOOP-2))) ((EQ (CAR FORM) 'DEFINE) (DRIVER-LOOP (BIND (LIST (CAADR FORM)) (LIST (LIST '&FUNCTION (CDADR FORM) (CADDR FORM))) ENV) (PRINT (CAADR FORM)))) (T (EVAL FORM ENV ENV (LIST DRIVER-LOOP-2))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (DRIVER-LOOP-2 RESULT ENV) (DRIVER-LOOP ENV (PRINT RESULT))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 17 (DEFINE (EVAL EXP ENV TOPENV PDL) (COND ((ATOM EXP) (COND ((NUMBERP EXP) (POPJ EXP TOPENV PDL)) (T (POPJ (VALUE EXP ENV) TOPENV PDL)))) ((EQ (CAR EXP) 'QUOTE) (POPJ (CADR EXP) TOPENV PDL)) ((EQ (CAR EXP) 'COND) (EVCOND (CDR EXP) ENV TOPENV PDL)) ((EQ (CAR EXP) 'CATCH) (EVAL (CADDR EXP) (BIND (LIST (CADR EXP)) (LIST (CONS '&ESCAPE PDL)) ENV) TOPENV PDL)) (T (EVAL (CAR EXP) ENV TOPENV (CONS EVLIS (CONS (CDR EXP) (CONS ENV PDL))))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (POPJ RESULT TOPENV PDL) ((CAR PDL) RESULT TOPENV (CDR PDL))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (EVLIS FN TOPENV PDL) ;PDL = (ARGS ENV . PDL) (EVLIS1 (CAR PDL) NIL (CADR PDL) TOPENV (CONS FN (CDDR PDL)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 10 (DEFINE (EVLIS1 ARGLIST EVALARGS ENV TOPENV PDL) ;PDL = (FN . PDL) (COND ((NULL ARGLIST) (APPLY (CAR PDL) (REVERSE EVALARGS) TOPENV (CDR PDL))) (T (EVAL (CAR ARGLIST) ENV TOPENV (CONS EVLIS2 (CONS (CDR ARGLIST) (CONS EVALARGS (CONS ENV PDL)))))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (EVLIS2 ARG TOPENV PDL) ;PDL = (ARGLIST EVALARGS ENV . PDL) (EVLIS1 (CAR PDL) (CONS ARG (CADR PDL)) (CADDR PDL) TOPENV (CDDDR PDL))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 6 (DEFINE (EVCOND CLAUSES ENV TOPENV PDL) (COND ((NULL CLAUSES) (POPJ NIL TOPENV PDL)) (T (EVAL (CAAR CLAUSES) ENV TOPENV (CONS EVCOND1 (CONS CLAUSES (CONS ENV PDL))))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 3 (DEFINE (EVCOND1 PRED TOPENV PDL) ;PDL = (CLAUSES ENV . PDL) (COND (PRED (EVAL (CADAAR PDL) (CADR PDL) TOPENV (CDDR PDL))) (T (EVCOND (CDAR PDL) (CADR PDL) TOPENV (CDDR PDL))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 10 (DEFINE (APPLY FUN ARGS TOPENV PDL) (COND ((PRIMOP FUN) (POPJ (PRIMOP-APPLY FUN ARGS) TOPENV PDL)) ((EQ (CAR FUN) '&FUNCTION) (EVAL (CADADR FUN) (BIND (CAADR FUN) ARGS TOPENV) TOPENV PDL)) ((EQ (CAR FUN) '&ESCAPE) (POPJ (CAR ARGS) TOPENV (CDR FUN))) (T (ERROR '|UNKNOWN FUNCTION| (LIST FUN ARGS))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (VALUE NAME ENV) (VALUE1 (LOOKUP NAME ENV))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (VALUE1 NAME SLOT) (COND ((EQ SLOT '&UNBOUND) (ERROR '|CAN'T REFERENCE UNBOUND VARIABLE| NAME)) (T (CAR SLOT)))) .spw 16 .select 0 .adjust .sp {explain how to eliminate "second-order-ness" by putting a COND dispatch in POPJ} {installing fluids would just pass around fenv like mad in parallel to pdl} {explain how this would affect CATCH} .page .c an FEVAL2 with lexicals, fluids, and CATCH, using CATCH in the host language .nofill .select 1 .spw 13 .block 22 (DEFINE (EVAL EXP ENV FENV) (COND ((ATOM EXP) (COND ((NUMBERP EXP) EXP) (T (VALUE EXP ENV)))) ((EQ (CAR EXP) 'QUOTE) (CADR EXP)) ((EQ (CAR EXP) 'LAMBDA) (LIST '&FUNARG (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'FLAMBDA) (LIST '&FLUNARG (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'COND) (EVCOND (CDR EXP) ENV)) ((EQ (CAR EXP) 'FLUID) (VALUE (CADR EXP) FENV)) ((EQ (CAR EXP) 'CATCH) (CATCH J (EVAL (CADDR EXP) (BIND (LIST (CADR EXP)) (LIST (CONS '&CATCHTAG J)) ENV)))) (T (APPLY (EVAL (CAR EXP) ENV) (EVLIS (CDR EXP) ENV) FENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 17 (DEFINE (APPLY FUN ARGS FENV) (COND ((PRIMOP FUN) (PRIMOP-APPLY FUN ARGS FENV)) ((EQ (CAR FUN) '&FUNARG) (EVAL (CADDR FUN) (BIND (CADR FUN) ARGS (CADDDR FUN)) FENV)) ((EQ (CAR FUN) '&FLUNARG) (EVAL (CADDR FUN) (CADDDR FUN) (BIND (CADR FUN) ARGS FENV))) ((EQ (CAR FUN) '&CATCHTAG) ((CDR FUN) (CAR ARGS))) (T (ERROR '|UNKNOWN FUNCTION| (LIST FUN ARGS))))) .spw 16 .select 0 .adjust .sp .page .c FEVAL2 with ASETQ, FLUIDSETQ, LABELS .nofill .select 1 .spw 13 .block 27 (DEFINE (EVAL EXP ENV FENV) (COND ((ATOM EXP) (COND ((NUMBERP EXP) EXP) (T (VALUE EXP ENV)))) ((EQ (CAR EXP) 'QUOTE) (CADR EXP)) ((EQ (CAR EXP) 'LAMBDA) (LIST '&FUNARG (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'FLAMBDA) (LIST '&FLUNARG (CADR EXP) (CADDR EXP) ENV)) ((EQ (CAR EXP) 'COND) (EVCOND (CDR EXP) ENV)) ((EQ (CAR EXP) 'FLUID) (VALUE (CADR EXP) FENV)) ((EQ (CAR EXP) 'ASETQ) (ASSIGN (EVAL (CADDR EXP) ENV FENV) (CADR EXP) ENV)) ((EQ (CAR EXP) 'FLUIDSETQ) (ASSIGN (EVAL (CADDR EXP) ENV FENV) (CADR EXP) FENV)) ((EQ (CAR EXP) 'LABELS) (EVAL (CADDR EXP) (LABELSBIND (CADR EXP) ENV FENV) FENV)) (T (APPLY (EVAL (CAR EXP) ENV) (EVLIS (CDR EXP) ENV) FENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 15 (DEFINE (APPLY FUN ARGS FENV) (COND ((PRIMOP FUN) (PRIMOP-APPLY FUN ARGS FENV)) ((EQ (CAR FUN) '&FUNARG) (EVAL (CADDR FUN) (BIND (CADR FUN) ARGS (CADDDR FUN)) FENV)) ((EQ (CAR FUN) '&FLUNARG) (EVAL (CADDR FUN) (CADDDR FUN) (BIND (CADR FUN) ARGS FENV))) (T (ERROR '|UNKNOWN FUNCTION| (LIST FUN ARGS))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (ASSIGN VALUE VAR ENV) (ASSIGN1 VAR (LOOKUP VAR ENV) VALUE)) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 4 (DEFINE (ASSIGN1 VAR SLOT VALUE) (COND ((EQ SLOT '&UNBOUND) (ERROR '|CAN'T ASSIGN TO AN UNBOUND VARIABLE| VAR)) (T (CAR (RPLACA SLOT VALUE))))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (LABELSBIND DEFNS ENV FENV) (LABELSEVLIS DEFNS NIL (LABELSENV DEFNS NIL NIL ENV) FENV)) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 6 (DEFINE (LABELSENV DEFNS VARS VALS ENV) (COND ((NULL DEFNS) (BIND VARS VALS ENV)) (T (LABELSENV (CDR DEFNS) (CONS (CAR DEFNS) VARS) (CONS '&UNASSIGNED VALS) ENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 7 (DEFINE (LABELSEVLIS DEFNS VALS ENV FENV) (COND ((NULL DEFNS) (LABELSRET (RPLACD (CAR ENV) VALS) ENV)) (T (LABELSEVLIS (CDR DEFNS) (CONS (EVAL (CADAR DEFNS) ENV FENV) VALS) ENV FENV)))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (LABELSRET GARBAGE ENV) ENV) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 2 (DEFINE (VALUE NAME ENV) (VALUE1 NAME (LOOKUP NAME ENV))) .spw 16 .select 0 .adjust .sp .nofill .select 1 .spw 13 .block 6 (DEFINE (VALUE1 NAME SLOT) (COND ((EQ SLOT '&UNBOUND) (ERROR '|CAN'T REFERENCE UNBOUND VARIABLE| NAME)) ((EQ (CAR SLOT) '&UNASSIGNED) (ERROR '|CAN'T REFERENCE UNASSIGNED LABELS VARIABLE| NAME)) (T (CAR SLOT)))) .spw 16 .select 0 .adjust .sp .section Notes .page .section References .sp 2 .in 8 .block 4 .un 8 [Declarative] .br Steele, Guy Lewis Jr. LAMBDA: The Ultimate Declarative. AI Memo 379. MIT AI Lab (Cambridge, November 1976). .block 4 .un 8 [Imperative] .br Steele, Guy Lewis Jr., and Sussman, Gerald Jay. LAMBDA: The Ultimate Imperative. AI Memo 353. MIT AI Lab (Cambridge, March 1976). .block 4 .un 8 [Landin] .br Landin, Peter J. "A Correspondence between ALGOL 60 and Church's Lambda-Notation." Comm. ACM 8, 2-3 (February and March 1965). .block 4 .un 8 [Moon] .br Moon, David A. MacLISP Reference Manual, Revision 0. Project MAC, MIT (Cambridge, April 1974). .block 4 .un 8 [Moses] .br Moses, Joel. The Function of FUNCTION in LISP. AI Memo 199, MIT AI Lab (Cambridge, June 1970). .block 4 .un 8 [Naur] .br Naur, Peter (Ed.), et al. "Revised Report on the Algorithmic Language ALGOL 60." Comm. ACM 6, 1 (January 1963), 1-20. .block 4 .un 8 [RABBIT] .br Steele, Guy Lewis Jr. Compiler Optimization Based on Viewing LAMBDA as Rename plus Goto. S.M. thesis. MIT (Cambridge, May 1977). .block 4 .un 8 [Reynolds] .br Reynolds, John C. "Definitional Interpreters for Higher Order Programming Languages." ACM Conference Proceedings 1972. .block 4 .un 8 [SCHEME] .br Sussman, Gerald Jay, and Steele, Guy Lewis Jr. SCHEME: An Interpreter for Extended Lambda Calculus. AI Memo 349. MIT AI Lab (Cambridge, December 1975). .block 4 .un 8 [Smith and Hewitt] .br Smith, Brian C. and Hewitt, Carl. A PLASMA Primer (Draft). MIT AI Lab (Cambridge, October 1975). .in 0