Interpreting lambda and Procedure Calling

Our new interpreter will handle defining and calling new procedures. This is not difficult, because all of the major mechanisms are already in place. We need the ability to define local variables (e.g., arguments), which we already implemented for let. We also need the ability to interpret the procedure bodies, but the interpreter we've got is just fine for that. We'll simply store the procedure bodies as s-expressions, and interpret them like any other expressions when the procedure is called.

Our representation of closures will be very simple. A closure mainly pairs an environment with a procedure body, but we also need to specify a list of argument the procedure will accept.

We'll define a procedure make-closure to construct a closure, given a pointer to an environment, a pointer to a list of argument names (symbols), and pointer to a procedure body (a list of expressions).

We'll also define the procedures closure-envt, closure-args, and closure-body to extract those parts when we call the procedure.

As a slight complication, we'd like to start out with some predefined procedures, and the easiest way to do that is simply to snarf the corresponding procedures from the underlying Scheme system, i.e., the language we're using to implement our interpreter. (If we were writing our interpreter in C or assembly language, we might write the code bodies of built-in procedures in that language.)

These snarfed procedures will be the built-in "primitive" operations in our language, which can be "glued together" by the interpreter to build new procedures, which may be arbitrarily complicated.

In the simple interpreter in the last chapter, we snarfed procedures directly--we just used closures in the underlying Scheme as procedures in our language. In the new interpreter, we need to distinguish between snarfed procedures (which we can simply call from inside the interpreter) and user-defined procedures, which we must interpret via recursive calls to eval.

Our representation of closures will therefore support two predicates. closure? will test an object to see if it is a closure of either sort. primitive-closure? will test whether a closure represents a snarfed procedure from the underlying Scheme system.

In the case of a primitive closure, calling the closure just consists of extracting the underlying Scheme closure, and calling it with the given argument values. (We don't snarf any procedures that depend on what environment they execute in. We only snarf functions like + and cons, which depend only on their arguments.)

A closure therefore has three important fields: a pointer to an environment, a pointer to a list of argument names, and a pointer to a code body. It also has a "hidden" type field, saying that what kind of object it is.

[ I'm glossing over the actual representation in the underlying Scheme system, because it really doesn't matter. It could be an association list, a vector, or whatever. ]

eval-lambda is the procedure called from eval-list to handle lambda expressions. It will be stored in binding of lambda of the name lambda (with binding type <special-form>, and extracted and called to actually interpret lambda's.

(define (eval-lambda lambda-form envt)
   (let ((formals (cadr lambda-form))
         (body (cddr lambda-form)))
      (make-closure envt formals body)))

eval-lambda simply extracts the argument list and body expression list from the lambda expression, and calls make-closure with them (and the current environment) to create the closure object. Storing the current environment in the closure ensures that when the closure is interpreted later, it will still be able to refer to the same bindings that were visible when it was created.

eval-combo is called from eval-list to evaluation combinations (procedure call expressions).

(Note that eval-list evaluates the operator expression before calling eval-combo, and hands it the closure plus a list of unevaluated argument expressions. This is not particularly significant--we could have passed the operator expression to eval-combo unevaluated, like the argument expressions, and have eval-combo evaluate it instead. As we've written it, we ensure that the operator expression is evaluated before the arguments. We could change it to get the opposite effect. This would still be legal--the Scheme standard does not specify the order of evaluation, and an implementation may even use different orders at different call sites.)

[ DONOVAN--maybe we should change it. RScheme evaluates the operator expression last, so maybe the interpreter should, too. ]

eval-combo evaluates the argument expressions in the given environment to get the argument values, using eval-multi, and calls eval-apply to call the given closure with those values.

(define (eval-combo proc arg-expr-list envt)
   ; use our own kind of apply to run our own kind of closures
   (eval-apply proc
               ; evaluate the arguments, collecting the results into a list
               (eval-multi arg-expr-list
                          envt)))

eval-apply does the actual procedure call, after the arguments have been evaluated. That is, it applies the given procedure (closure) to the given arguments.

If the closure we're calling is a primitive closure, we simply extract the underlying Scheme procedure and call that, using the standard Scheme procedure apply. Scheme's apply takes a list of any number of values, and calls the procedure as though the arguments had been passed to it in the normal way.

(To make sure that you understand that, here's a simple usage of Scheme's apply: (apply + '(1 2)). This call to apply will take the procedure + and call it with the values 1 and 2, just as if we had written (+ 1 2). Likewise, (apply list '(1 2 3 4)) returns the same thing as (list 1 2 3 4).)

(define (eval-apply proc arg-list)
   (if (primitive-closure? proc)
    
       ; it's a primitive, so extract the underlying language's
       ; closure for the primitive, and do a real (underlying Scheme)
       ; apply to call it
       (apply (closure-primitive proc) arg-list)
       
       ; it's not a primitive closure, so it must be something
       ; we created with make-closure
       ;
       ; first, bind the actuals into a new environment, which
       ; is scoped inside the environment in which the closure
       ; was closed
       (let ((new-envt (make-envt (closure-args proc) 
                                  arg-list
                                  (closure-envt proc))))
          ; then, evaluate the body forms, returning the 
          ; value of the last of them.
          (eval-sequence (closure-body proc)
                         new-envt))))

In the case of a user-defined (interpreted) closure, eval-combo creates a new environment to bind the arguments values, much as it does to bind the local variables of a let; it calls make-envt with the name list, the corresponding value list, and the old environment, and gets back a pointer to the new environment frame, scoped inside the old one.

There's a big difference here, though. The "old" environment that's used in creating the new one is not the environment that was passed to eval-combo. (Notice that eval-combo did not even pass that environment to eval-apply.)

When we call the closure, we extract the environment stored in the closure, and use that as the "old" environment. This ensures that the closure body will evaluate in the environment where it was defined, augmented with the bindings of its arguments. This is the crucial step in preserving lexical scope--the meanings of identifiers in the procedure body are fixed at the moment the closure is created, because it captures the current environment at that point.

Once the new environment is created, eval-combo simply calls eval-sequence to evaluate the sequence of body expressions and return the value of the last one. eval-combo simply returns this value as the return value of the procedure call. (Notice that the call to eval-sequence is a tail call, preserving the tail recursion of the program we're interpreting.)

Mutual Recursion Between Eval and Apply

It is important to understand the relationship between eval and eval-apply in the interpreter. This will help you understand how scoping is implemented, and will also help you understand the relationship between an interpreter and a compiler.

eval calls itself to evaluate normal nested expressions. It may do this indirectly, by using helper procedures that discriminate different kinds of expressions, but in general recursive calls to eval correspond to the nested structure of a procedure.

eval-apply is very different. When the interpreter gets to a procedure call, it calls eval-apply to jump to a different procedure, not a nested expression of the same procedure. (Note that the arguments to a procedure call are evaluated like any other nested expressions, by calling eval, but the call itself is done by eval-apply.)

Normal recursive calls to eval therefore correspond to the local nesting structure of the code, but calls to apply correspond to transfers of control to different procedures.

[ Any other miscellaneous stuff I should explain? Should have a pointer to the source file for the whole interpreter... ]

[ Say that's it for the interpreter for now... we'll come back to it when we talk about macros, and we'll talk about a compiler with very similar structure later... ]