Running the Evaluator

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 . 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(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))apply-dispatch)

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 -, we can create an evaluator machine model that we can run using the register-machine simulator of section .

(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 , together with the few additional ones defined in footnotes throughout section .

(define eceval-operations (list (list 'self-evaluating? self-evaluating)complete list of operations for eceval machine))

Finally, we can initialize the global environment and run the evaluator:

(define the-global-environment (setup-environment))(start eceval) ;;; EC-Eval input: (define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y)))) ;;; EC-Eval value: ok ;;; EC-Eval input: (append '(a b c) '(d e f)) ;;; EC-Eval value: (a b c d e f)

Of course, evaluating expressions in this way will take much longer than if we had directly typed them into Scheme, because of the multiple levels of simulation involved. Our expressions are evaluated by the explicit-control-evaluator machine, which is being simulated by a Scheme program, which is itself being evaluated by the Scheme interpreter.

Monitoring the performance of the evaluator

Simulation can be a powerful tool to guide the implementation of
evaluators. Simulations make it easy not only to explore variations
of the register-machine design but also to monitor the performance of
the simulated evaluator. For example, one important factor in
performance is how efficiently the evaluator uses the stack. We can
observe the number of stack operations required to evaluate various
expressions by defining the evaluator register machine with the
version of the simulator that collects statistics on stack use
(section ), and adding an instruction at the
evaluator's `print-result` entry point to print the
statistics:

print-result (perform (op print-stack-statistics))Interactions with the evaluator now look like this:; added instruction(perform (op announce-output) (const ";;; EC-Eval value:")) ...; same as before

;;; EC-Eval input: (define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n))) (total-pushes = 3 maximum-depth = 3) ;;; EC-Eval value: ok ;;; EC-Eval input: (factorial 5) (total-pushes = 144 maximum-depth = 28) ;;; EC-Eval value: 120Note that the driver loop of the evaluator reinitializes the stack at the start of each interaction, so that the statistics printed will refer only to stack operations used to evaluate the previous expression.

**Exercise.** Use the monitored stack to explore the tail-recursive property of the
evaluator (section ). Start the
evaluator and define the iterative `factorial` procedure from
section :

(define (factorial n) (define (iter product counter) (if (> counter n) product (iter (* counter product) (+ counter 1)))) (iter 1 1))Run the procedure with some small values of

a. You will find that the maximum depth required to evaluate *n*! is
independent of *n*. What is that depth?

b. Determine from your data a formula in terms of *n* for the total
number of push operations used in evaluating *n*! for any .
Note that the number of operations used is a linear function of *n*
and is thus determined by two constants.

**Exercise.**
For comparison with exercise , explore the
behavior of the following procedure for computing factorials
recursively:

(define (factorial n) (if (= n 1) 1 (* (factorial (- n 1)) n)))By running this procedure with the monitored stack, determine, as a function of

Maximum depth | Number of pushes | |

Recursive | ||

factorial | ||

Iterative | ||

factorial |

The maximum depth is a measure of the amount of space used by the evaluator in carrying out the computation, and the number of pushes correlates well with the time required.

**Exercise.**
Modify the definition of the evaluator by changing
`eval-sequence` as described in
section so that the evaluator is no
longer tail-recursive. Rerun your experiments from
exercises and to demonstrate
that both versions of the `factorial` procedure now require space
that grows linearly with their input.

**Exercise.**
Monitor the stack operations in the tree-recursive Fibonacci computation:

(define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))a. Give a formula in terms of

b. Give a formula for the total number of pushes used to compute
for .
You should find that the number of
pushes (which correlates well with the time used) grows exponentially
with *n*. Hint: Let *S*(*n*) be the number of pushes used in computing
.
You should be able to argue that there is a formula
that expresses *S*(*n*) in terms of *S*(*n*-1), *S*(*n*-2), and some fixed
``overhead'' constant *k* that is independent of *n*. Give the
formula, and say what *k* is. Then show that *S*(*n*) can be expressed
as
and give the values of *a* and *b*.

**Exercise.**
Our evaluator currently catches and signals only two kinds of
errors--unknown expression types and unknown procedure types. Other
errors will take us out of the evaluator read-eval-print loop. When
we run the evaluator using the register-machine simulator, these
errors are caught by the underlying Scheme system. This is analogous
to the computer crashing when a user program makes an
error.^{} It is a large project to make a real
error system work, but it is well worth the effort to understand what
is involved here.

a. Errors that occur in the evaluation process, such as an attempt to
access an unbound variable, could be caught by changing the lookup
operation to make it return a distinguished condition code, which cannot
be a possible value of any user variable. The evaluator can test
for this condition code and then do what is necessary to go to `
signal-error`. Find all of the places in the evaluator where such a
change is necessary and fix them. This is lots of work.

b. Much worse is the problem of handling errors that are signaled by
applying primitive procedures, such as an attempt to divide by zero or
an attempt to extract the `car` of a symbol. In a professionally
written high-quality system, each primitive application is checked for
safety as part of the primitive. For example, every call to `car`
could first check that the argument is a pair. If the argument is not
a pair, the application would return a distinguished condition code to
the evaluator, which would then report the failure. We could arrange
for this in our register-machine simulator by making each primitive
procedure
check for applicability and returning an appropriate distinguished
condition code on failure. Then the `primitive-apply` code in the
evaluator can check for the condition code and go to `
signal-error` if necessary. Build this structure and make it work.
This is a major project.