lambdaand 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
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-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
Our representation of closures will therefore support two predicates.
closure? will test an object to see if it is a closure of
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
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
of the name
lambda (with binding type
extracted and called to actually interpret
(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
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).
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
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-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 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
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
(apply + '(1 2)). This call
to apply will take the procedure
+ and call it with the
2, just as if we had written
(+ 1 2).
(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,
creates a new environment to bind the arguments values, much as it does
to bind the local variables of a
let; it calls
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
not even pass that environment to
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.)
It is important to understand the relationship between
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 handle
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
Normal recursive calls to
eval therefore correspond to the local
nesting structure of the code, but calls to
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... ]