Structure and Interpretation of Computer Programs (101 page)

ev-begin
  (assign unev (op begin-actions) (reg exp))
  (save continue)
  (goto (label ev-sequence))

The implicit sequences in procedure bodies are handled by jumping to
ev-sequence
from
compound-apply
, at which point
continue
is already on the stack, having been saved at
ev-application
.

The entries at
ev-sequence
and
ev-sequence-continue
form a loop that
successively evaluates each expression in a sequence. The list of
unevaluated expressions is kept in
unev
. Before evaluating each
expression, we check to see if there are additional expressions to be
evaluated in the sequence. If so, we save the rest of the unevaluated
expressions (held in
unev
) and the environment in which these
must be evaluated (held in
env
) and call
eval-dispatch
to
evaluate the expression. The two saved registers are restored upon
the return from this evaluation, at
ev-sequence-continue
.

The final expression in the sequence is handled differently, at the
entry point
ev-sequence-last-exp
. Since there are no more
expressions to be evaluated after this one, we need not save
unev
or
env
before going to
eval-dispatch
. The value of
the whole sequence is the value of the last expression, so after the
evaluation of the last expression there is nothing left to do except
continue at the entry point currently held on the stack (which was saved
by
ev-application
or
ev-begin
.)
Rather than setting up
continue
to arrange for
eval-dispatch
to return here and then restoring
continue
from
the stack and continuing at that entry point, we restore
continue
from
the stack before going to
eval-dispatch
, so that
eval-dispatch
will continue at that entry point after evaluating the
expression.

ev-sequence
  (assign exp (op first-exp) (reg unev))
  (test (op last-exp?) (reg unev))
  (branch (label ev-sequence-last-exp))
  (save unev)
  (save env)
  (assign continue (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev (op rest-exps) (reg unev))
  (goto (label ev-sequence))
ev-sequence-last-exp
  (restore continue)
  (goto (label eval-dispatch))

In chapter 1 we said that the process described by a procedure such as

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

is an iterative process. Even though the procedure is syntactically
recursive (defined in terms of itself), it is not logically necessary
for an evaluator to save information in passing from one call to
sqrt-iter
to the next.
²⁵
An evaluator that can
execute a procedure such as
sqrt-iter
without requiring
increasing storage as the procedure continues to call itself is called
a
tail-recursive
evaluator.
The metacircular implementation of
the evaluator in chapter 4 does not specify whether the evaluator is
tail-recursive, because that evaluator inherits its mechanism for
saving state from the underlying Scheme. With the explicit-control
evaluator, however, we can trace through the evaluation process to see
when procedure calls cause a net accumulation of information on the
stack.

Our evaluator is tail-recursive, because in order to evaluate the final
expression of a sequence we transfer directly to
eval-dispatch
without
saving any information on the stack. Hence, evaluating the final expression
in a sequence – even if it is a procedure call (as in
sqrt-iter
, where
the
if
expression, which is the last expression in the procedure body,
reduces to a call to
sqrt-iter
) – will not cause any information to be
accumulated on the stack.
²⁶

If we did not think to take advantage of the fact that it was
unnecessary to save information in this case, we might have
implemented
eval-sequence
by treating all the expressions in a
sequence in the same way – saving the registers, evaluating the expression,
returning to restore the registers, and repeating this until all the
expressions have been evaluated:
²⁷

ev-sequence
  (test (op no-more-exps?) (reg unev))
  (branch (label ev-sequence-end))
  (assign exp (op first-exp) (reg unev))
  (save unev)
  (save env)
  (assign continue (label ev-sequence-continue))
  (goto (label eval-dispatch))
ev-sequence-continue
  (restore env)
  (restore unev)
  (assign unev (op rest-exps) (reg unev))
  (goto (label ev-sequence))
ev-sequence-end
  (restore continue)
  (goto (reg continue))

This may seem like a minor change to our previous code for evaluation
of a sequence: The only difference is that we go through the
save-restore cycle for the last expression in a sequence as well as
for the
others. The interpreter will still give the same value for
any expression. But this change is fatal to the tail-recursive
implementation, because we must now return after evaluating the final
expression in a sequence in order to undo the (useless) register
saves. These extra saves will accumulate during a nest of procedure
calls. Consequently, processes such as
sqrt-iter
will require
space proportional to the number of iterations rather than requiring
constant space. This difference can be significant. For example,
with tail recursion, an infinite loop can be expressed using only the
procedure-call mechanism:

(define (count n)
  (newline)
  (display n)
  (count (+ n 1)))

Without tail recursion, such a procedure would eventually run out of
stack space, and expressing a true iteration would require some
control mechanism other than procedure call.

As with the metacircular evaluator, special forms are handled by
selectively evaluating fragments of the expression. For an
if
expression, we must evaluate the predicate and decide, based on the
value of predicate, whether to evaluate the consequent or the
alternative.

Before evaluating the predicate, we save the
if
expression
itself so that we can later extract the consequent or alternative. We
also save the environment, which we will need later in order to
evaluate the consequent or the alternative, and we save
continue
, which we will need later in order to return to the
evaluation of the expression that is waiting for the value of the
if
.

ev-if
  (save exp)                    
; save expression for later
  (save env)
  (save continue)
  (assign continue (label ev-if-decide))
  (assign exp (op if-predicate) (reg exp))
  (goto (label eval-dispatch))  
; evaluate the predicate

When we return from evaluating the predicate, we test whether it was
true or false and, depending on the result, place either the
consequent or the alternative in
exp
before going to
eval-dispatch
. Notice that restoring
env
and
continue
here sets up
eval-dispatch
to have the correct environment and
to continue at the right place to receive the value of the
if
expression.

ev-if-decide
  (restore continue)
  (restore env)
  (restore exp)
  (test (op true?) (reg val))
  (branch (label ev-if-consequent))
ev-if-alternative
  (assign exp (op if-alternative) (reg exp))
  (goto (label eval-dispatch))
ev-if-consequent
  (assign exp (op if-consequent) (reg exp))
  (goto (label eval-dispatch))

Assignments are handled by
ev-assignment
, which is reached from
eval-dispatch
with the assignment expression in
exp
. The code at
ev-assignment
first evaluates the value part of the expression and
then installs the new value in the environment.
Set-variable-value!
is assumed to be available as a machine
operation.

ev-assignment
  (assign unev (op assignment-variable) (reg exp))
  (save unev)                   
; save variable for later
  (assign exp (op assignment-value) (reg exp))
  (save env)
  (save continue)
  (assign continue (label ev-assignment-1))
  (goto (label eval-dispatch))  
; evaluate the assignment value
ev-assignment-1
  (restore continue)
  (restore env)
  (restore unev)
  (perform
   (op set-variable-value!) (reg unev) (reg val) (reg env))
  (assign val (const ok))
  (goto (reg continue))

Definitions are handled in a similar way:

ev-definition
  (assign unev (op definition-variable) (reg exp))
  (save unev)                   
; save variable for later
  (assign exp (op definition-value) (reg exp))
  (save env)
  (save continue)
  (assign continue (label ev-definition-1))
  (goto (label eval-dispatch))  
; evaluate the definition value
ev-definition-1
  (restore continue)
  (restore env)
  (restore unev)
  (perform
   (op define-variable!) (reg unev) (reg val) (reg env))
  (assign val (const ok))
  (goto (reg continue))

Exercise 5.23.
  
Extend the evaluator to handle derived expressions such as
cond
,
let
, and so on (section 
4.1.2
).
You may “cheat” and assume that the syntax
transformers such as
cond->if
are available as machine
operations.
²⁸

Exercise 5.24.
  
Implement
cond
as a new basic special form without
reducing it to
if
. You will have to construct a loop that tests
the predicates of successive
cond
clauses until you find one
that is true, and then use
ev-sequence
to evaluate the actions
of the clause.

Exercise 5.25.
  
Modify the evaluator so that it uses normal-order evaluation,
based on the lazy evaluator of section 
4.2
.

With the implementation of the explicit-control evaluator we come to
the end of a development, begun in chapter 1, in which we have
explored successively more precise models of the evaluation process.
We started with the relatively informal substitution model, then
extended this in chapter 3 to the environment model, which enabled us
to deal with state and change. In the metacircular evaluator of
chapter 4, we used Scheme itself as a language for making more explicit
the environment structure constructed during evaluation of an
expression. Now, with register machines, we have taken a close look
at the evaluator's mechanisms for storage management,
argument passing, and control. At
each new level of description, we have had to raise issues and resolve
ambiguities that were not apparent at the previous, less precise
treatment of evaluation. To understand the behavior of the
explicit-control evaluator, we can simulate it and monitor its
performance.

We will install a driver loop in our evaluator machine. This plays
the role of the
driver-loop
procedure of
section 
4.1.4
. The evaluator will repeatedly print a
prompt, read an expression, evaluate the expression by going to
eval-dispatch
, and print the result. The following instructions form
the beginning of the explicit-control evaluator's controller
sequence:
²⁹

read-eval-print-loop
  (perform (op initialize-stack))
  (perform
   (op prompt-for-input) (const ";;; EC-Eval input:"))
  (assign exp (op read))
  (assign env (op get-global-environment))
  (assign continue (label print-result))
  (goto (label eval-dispatch))
print-result
  (perform
   (op announce-output) (const ";;; EC-Eval value:"))
  (perform (op user-print) (reg val))
  (goto (label read-eval-print-loop))

When we encounter an error in a procedure (such as the “unknown
procedure type error” indicated at
apply-dispatch
), we print an
error message and return to the driver loop.
³⁰

unknown-expression-type
  (assign val (const unknown-expression-type-error))
  (goto (label signal-error))
unknown-procedure-type
  (restore continue)    
; clean up stack (from 
apply-dispatch
)
  (assign val (const unknown-procedure-type-error))
  (goto (label signal-error))
signal-error
  (perform (op user-print) (reg val))
  (goto (label read-eval-print-loop))

For the purposes of the simulation, we initialize the stack each time
through the driver loop, since it might not be empty after an error
(such as an undefined variable) interrupts an evaluation.
³¹

If we combine all the code fragments presented in sections
5.4.1
-
5.4.4
, we can create an
evaluator machine model that we can run using the register-machine simulator
of section 
5.2
.

(define eceval
  (make-machine
   '(exp env val proc argl continue unev)
   eceval-operations
  '(
    read-eval-print-loop
      <
entire machine controller as given above
>
   )))

We must define Scheme procedures to simulate the
operations used as primitives by the evaluator. These are
the same procedures we used for the metacircular evaluator in
section 
4.1
, together with the few additional ones
defined in footnotes throughout section 
5.4
.