Structure and Interpretation of Computer Programs (100 page)

Our Scheme evaluator register machine includes a stack and seven
registers:
exp
,
env
,
val
,
continue
,
proc
,
argl
, and
unev
.
Exp
is used to hold the expression
to be evaluated, and
env
contains the environment in which the
evaluation is to be performed. At the end of an evaluation,
val
contains the value obtained by evaluating the expression in the
designated environment. The
continue
register is used to
implement recursion, as explained in
section 
5.1.4
. (The evaluator needs to call
itself recursively, since evaluating an expression requires evaluating
its subexpressions.) The registers
proc
,
argl
, and
unev
are used in evaluating combinations.

We will not provide a data-path diagram to show how the registers and
operations of the evaluator are connected, nor will we give the
complete list of machine operations. These are implicit in the
evaluator's controller, which will be presented in detail.

The central element in the evaluator is the sequence of instructions
beginning at
eval-dispatch
. This corresponds to the
eval
procedure of the metacircular evaluator described in
section 
4.1.1
. When the controller starts at
eval-dispatch
, it evaluates the expression specified by
exp
in
the environment specified by
env
. When evaluation is complete,
the controller will go to the entry point stored in
continue
, and the
val
register will hold the value of the expression. As with the
metacircular
eval
, the structure of
eval-dispatch
is a
case analysis on the syntactic type of the expression to be
evaluated.
²⁰

eval-dispatch
  (test (op self-evaluating?) (reg exp))
  (branch (label ev-self-eval))
  (test (op variable?) (reg exp))
  (branch (label ev-variable))
  (test (op quoted?) (reg exp))
  (branch (label ev-quoted))
  (test (op assignment?) (reg exp))
  (branch (label ev-assignment))
  (test (op definition?) (reg exp))
  (branch (label ev-definition))
  (test (op if?) (reg exp))
  (branch (label ev-if))
  (test (op lambda?) (reg exp))
  (branch (label ev-lambda))
  (test (op begin?) (reg exp))
  (branch (label ev-begin))
  (test (op application?) (reg exp))
  (branch (label ev-application))
  (goto (label unknown-expression-type))

Numbers and strings (which are self-evaluating),
variables, quotations, and
lambda
expressions have no
subexpressions to be evaluated. For these, the evaluator simply
places the correct value in the
val
register and continues
execution at the entry point specified by
continue
. Evaluation
of simple expressions is performed by the following controller code:

ev-self-eval
  (assign val (reg exp))
  (goto (reg continue))
ev-variable
  (assign val (op lookup-variable-value) (reg exp) (reg env))
  (goto (reg continue))
ev-quoted
  (assign val (op text-of-quotation) (reg exp))
  (goto (reg continue))
ev-lambda
  (assign unev (op lambda-parameters) (reg exp))
  (assign exp (op lambda-body) (reg exp))
  (assign val (op make-procedure)
              (reg unev) (reg exp) (reg env))
  (goto (reg continue))

Observe how
ev-lambda
uses the
unev
and
exp
registers to hold the parameters and body of the lambda expression so
that they can be passed to the
make-procedure
operation, along
with the environment in
env
.

A procedure application is specified by a combination containing an
operator and operands. The operator is a subexpression whose value is
a procedure, and the operands are subexpressions whose values are the
arguments to which the procedure should be applied. The metacircular
eval
handles applications by calling itself recursively to
evaluate each element of the combination, and then passing the results
to
apply
, which performs the actual procedure application. The
explicit-control evaluator does the same thing; these recursive calls
are implemented by
goto
instructions, together with
use of the
stack to save registers that will be restored after the recursive call
returns. Before each call we will be careful to identify which
registers must be saved (because their values will be needed
later).
²¹

We begin the evaluation of an application by evaluating the operator
to produce a procedure, which will later be applied to the evaluated
operands. To evaluate the operator, we move it to the
exp
register and go to
eval-dispatch
. The environment in the
env
register is already the correct one in which to evaluate the
operator. However, we save
env
because we will need it later to
evaluate the operands. We also extract the operands into
unev
and save this on the stack. We set up
continue
so that
eval-dispatch
will resume at
ev-appl-did-operator
after the
operator has been evaluated. First, however, we save the old value of
continue
, which tells the controller where to continue after the
application.

ev-application
  (save continue)
  (save env)
  (assign unev (op operands) (reg exp))
  (save unev)
  (assign exp (op operator) (reg exp))
  (assign continue (label ev-appl-did-operator))
  (goto (label eval-dispatch))

Upon returning from evaluating the operator subexpression, we proceed
to evaluate the operands of the combination and to accumulate the
resulting arguments in a list, held in
argl
. First we restore
the unevaluated operands and the environment. We initialize
argl
to an empty list. Then we assign to the
proc
register the
procedure that was produced by evaluating the operator. If there are
no operands, we go directly to
apply-dispatch
. Otherwise we
save
proc
on the stack and start the argument-evaluation
loop:
²²

ev-appl-did-operator
  (restore unev)                  
; the operands
  (restore env)
  (assign argl (op empty-arglist))
  (assign proc (reg val))         
; the operator
  (test (op no-operands?) (reg unev))
  (branch (label apply-dispatch))
  (save proc)

Each cycle of the argument-evaluation loop evaluates an operand
from the list in
unev
and accumulates the result into
argl
.
To evaluate an operand, we place it in the
exp
register
and go to
eval-dispatch
, after setting
continue
so that
execution will resume with the argument-accumulation phase. But first
we save the arguments accumulated so far (held in
argl
), the
environment (held in
env
), and the remaining operands to be evaluated
(held in
unev
). A special case is made for the evaluation of the
last operand, which is handled at
ev-appl-last-arg
.

ev-appl-operand-loop
  (save argl)
  (assign exp (op first-operand) (reg unev))
  (test (op last-operand?) (reg unev))
  (branch (label ev-appl-last-arg))
  (save env)
  (save unev)
  (assign continue (label ev-appl-accumulate-arg))
  (goto (label eval-dispatch))

When an operand has been evaluated, the value is accumulated into the
list held in
argl
. The operand is then removed from the list of
unevaluated operands in
unev
, and the argument-evaluation continues.

ev-appl-accumulate-arg
  (restore unev)
  (restore env)
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (assign unev (op rest-operands) (reg unev))
  (goto (label ev-appl-operand-loop))

Evaluation of the last argument is handled differently. There is no
need to save the environment or the list of unevaluated operands
before going to
eval-dispatch
,
since they will not be required after the last operand is evaluated.
Thus, we return from the evaluation to a special entry point
ev-appl-accum-last-arg
, which restores the argument list, accumulates
the new argument, restores the saved procedure, and goes off to
perform the application.
²³

ev-appl-last-arg
  (assign continue (label ev-appl-accum-last-arg))
  (goto (label eval-dispatch))
ev-appl-accum-last-arg
  (restore argl)
  (assign argl (op adjoin-arg) (reg val) (reg argl))
  (restore proc)
  (goto (label apply-dispatch))

The details of the argument-evaluation loop determine the order in
which the interpreter evaluates the operands of a combination (e.g.,
left to right or right to left – see
exercise 
3.8
). This order is not determined
by the metacircular evaluator, which inherits its control structure
from the underlying Scheme in which it is implemented.
²⁴
Because the
first-operand
selector (used in
ev-appl-operand-loop
to extract successive operands
from
unev
) is implemented as
car
and the
rest-operands
selector is implemented as
cdr
, the
explicit-control evaluator will evaluate the operands of a combination
in left-to-right order.

The entry point
apply-dispatch
corresponds to the
apply
procedure of the metacircular evaluator. By the time we get to
apply-dispatch
, the
proc
register contains the procedure to
apply and
argl
contains the list of evaluated arguments to which
it must be applied. The saved value of
continue
(originally
passed to
eval-dispatch
and saved at
ev-application
),
which tells where to return with the result of the procedure
application, is on the stack. When the application is complete, the
controller transfers to the entry point specified by the saved
continue
, with the result of the application in
val
. As with
the metacircular
apply
, there are two cases to consider. Either
the procedure to be applied is a primitive or it is a compound
procedure.

apply-dispatch
  (test (op primitive-procedure?) (reg proc))
  (branch (label primitive-apply))
  (test (op compound-procedure?) (reg proc))  
  (branch (label compound-apply))
  (goto (label unknown-procedure-type))

We assume that each primitive is implemented so as to obtain its
arguments from
argl
and place its result in
val
. To
specify how the machine handles primitives, we would have to provide a
sequence of controller instructions to implement each primitive and
arrange for
primitive-apply
to dispatch to the
instructions for the primitive identified by the
contents of
proc
. Since we are interested in the structure of
the evaluation process rather than the details of the primitives, we
will instead just use an
apply-primitive-procedure
operation
that applies the procedure in
proc
to the arguments in
argl
. For the purpose of simulating the evaluator with the simulator
of section 
5.2
we use the procedure
apply-primitive-procedure
, which calls on the underlying Scheme
system to perform the application, just as we did for the metacircular
evaluator in section 
4.1.4
. After computing the
value of the primitive application, we restore
continue
and go
to the designated entry point.

primitive-apply
  (assign val (op apply-primitive-procedure)
              (reg proc)
              (reg argl))
  (restore continue)
  (goto (reg continue))

To apply a compound procedure, we proceed just as with the
metacircular evaluator. We construct a frame that binds the
procedure's parameters to the arguments, use this frame to
extend the environment carried by the procedure, and evaluate in this
extended environment the sequence of expressions that forms the body
of the procedure.
Ev-sequence
, described below in
section 
5.4.2
, handles the evaluation
of the sequence.

compound-apply
  (assign unev (op procedure-parameters) (reg proc))
  (assign env (op procedure-environment) (reg proc))
  (assign env (op extend-environment)
              (reg unev) (reg argl) (reg env))
  (assign unev (op procedure-body) (reg proc))
  (goto (label ev-sequence))

Compound-apply
is the only place in the interpreter where the
env
register is ever assigned a new value. Just as in the
metacircular evaluator, the new environment is constructed from the
environment carried by the procedure, together with the argument list
and the corresponding list of variables to be bound.

The portion of the explicit-control evaluator at
ev-sequence
is
analogous to the metacircular evaluator's
eval-sequence
procedure. It
handles sequences of expressions in procedure bodies or in explicit
begin
expressions.

Explicit
begin
expressions are evaluated by placing the sequence
of expressions to be evaluated in
unev
, saving
continue
on the
stack, and jumping to
ev-sequence
.