Read Structure and Interpretation of Computer Programs Online
Authors: Harold Abelson and Gerald Jay Sussman with Julie Sussman
Structure and Interpretation of Computer Programs (102 page)
(define eceval-operations
(list (list 'self-evaluating? self-evaluating)
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.
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
5.2.4
), and adding an instruction at the
evaluator's
print-result
entry point to print the
statistics:
print-result
(perform (op print-stack-statistics))
; added instruction
(perform
(op announce-output) (const ";;; EC-Eval value:"))
...
; same as before
Interactions with the evaluator now look like this:
;;; 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:
120
Note 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 5.26.
Use the monitored stack to explore the tail-recursive property of the
evaluator (section
5.4.2
). Start the
evaluator and define the iterative
factorial
procedure from
section
1.2.1
:
(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
n
. Record the maximum
stack depth and the number of pushes required to compute
n
! for each of
these values.
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
n
>
1.
Note that the number of operations used is a linear function of
n
and is thus determined by two constants.
Exercise 5.27.
For comparison with exercise
5.26
, 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
n
, the maximum depth of the stack and the total number
of pushes used in evaluating
n
! for
n
>
1. (Again, these functions
will be linear.) Summarize your experiments by filling in the
following table with the appropriate expressions in terms of
n
:
| 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 5.28.
Modify the definition of the evaluator by changing
eval-sequence
as described in
section
5.4.2
so that the evaluator is no
longer tail-recursive. Rerun your experiments from
exercises
5.26
and
5.27
to demonstrate
that both versions of the
factorial
procedure now require space
that grows linearly with their input.
Exercise 5.29.
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
n
for the maximum depth of the stack
required to compute
F
i
b
(
n
) for
n
>
2. Hint: In
section
1.2.2
we argued that the space used by this
process grows linearly with
n
.
b. Give a formula for the total number of pushes used to compute
F
i
b
(
n
) for
n
>
2. 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
F
i
b
(
n
). 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
a
F
i
b
(
n
+ 1) +
b
and give the values of
a
and
b
.
Exercise 5.30.
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.
32
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.
19
See Batali et al. 1982 for more
information on the chip and the method by which it was designed.
20
In our controller, the dispatch is written as a
sequence of
test
and
branch
instructions. Alternatively,
it could have been written in a data-directed style (and in a real
system it probably would have been) to avoid the need to perform
sequential tests and to facilitate the definition of new expression
types. A machine designed to run Lisp would probably include a
dispatch-on-type
instruction that would efficiently execute such
data-directed dispatches.
21
This is an important but subtle point in translating
algorithms from a procedural language, such as Lisp, to a
register-machine language. As an alternative to saving only what is
needed, we could save all the registers (except
val
) before each
recursive call. This is called a
framed-stack
discipline. This
would work but might save more registers than necessary; this could be
an important consideration in a system where stack operations are
expensive. Saving registers whose contents will not be needed later
may also hold onto useless data that could otherwise be
garbage-collected, freeing space to be reused.
22
We add to the evaluator data-structure procedures in
section
4.1.3
the following two procedures
for manipulating argument lists:
(define (empty-arglist) '())
(define (adjoin-arg arg arglist)
(append arglist (list arg)))
We also use an additional syntax procedure to test for the
last operand in a combination:
(define (last-operand? ops)
(null? (cdr ops)))
23
The optimization of treating the last operand
specially is known as
evlis tail recursion
(see
Wand 1980).
We could be somewhat more efficient
in the argument evaluation loop if we made evaluation of the first
operand a special case too. This would permit us to postpone
initializing
argl
until after evaluating the first operand, so
as to avoid saving
argl
in this case. The compiler in
section
5.5
performs this optimization. (Compare
the
construct-arglist
procedure of
section
5.5.3
.)
24
The
order of operand evaluation in the metacircular evaluator is
determined by the order of evaluation of the arguments to
cons
in the procedure
list-of-values
of section
4.1.1
(see exercise
4.1
).
25
We saw in
section
5.1
how to implement such a
process with a register machine that had no stack; the state of the
process was stored in a fixed set of registers.
26
This implementation of tail recursion in
ev-sequence
is one variety of a well-known optimization technique used
by many compilers. In compiling a procedure that ends with a procedure call,
one can replace the call by a jump to the called procedure's entry point.
Building this strategy into the interpreter, as we have done in this section,
provides the optimization uniformly throughout the language.
27
We can define
no-more-exps?
as follows:
(define (no-more-exps? seq) (null? seq))
28
This isn't really cheating. In an actual
implementation built from scratch, we would use our explicit-control
evaluator to interpret a Scheme program that performs source-level
transformations like
cond->if
in a syntax phase that runs before
execution.
29
We assume here that
read
and the
various printing operations are
available as primitive machine operations, which is useful for our
simulation, but completely unrealistic in practice. These
are actually extremely complex operations. In practice, they would be
implemented using low-level input-output operations
such as transferring single characters to and from a device.
To support the
get-global-environment
operation we define
(define the-global-environment (setup-environment))
(define (get-global-environment)
the-global-environment)
30
There are other
errors that we would like the interpreter to handle, but these are not
so simple. See exercise
5.30
.
31
We
could perform the stack initialization only after errors, but doing it in
the driver loop will be convenient for monitoring the evaluator's
performance, as described below.
32
Regrettably, this is the normal state of affairs in
conventional compiler-based language systems such as C.
In UNIX
T
M
the system “dumps core,” and in
DOS/Windows
T
M
it becomes catatonic.
The Macintosh
T
M
displays a
picture of an exploding bomb and offers you the opportunity to reboot
the computer – if you're lucky.