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
SchemeJavaScript
itself as a language for making more
explicit the environment structure constructed during evaluation of an
expression.component.
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-loopdriver_loopprocedurefunction
of section 4.1.4. The evaluator
will repeatedly print a prompt, read
an expression,a program,
evaluate
the expressionthe program
by going to
eval-dispatch,
eval_dispatch,
and print the result.
If nothing is entered at the prompt, we jump to the label
evaluator_done, which is
the last entry point in the controller.
The following instructions form the beginning of the
explicit-control evaluator's controller sequence:[1]
"read_evaluate_print_loop",
perform(list(op("initialize_stack"))),
assign("comp", list(op("user_read"),
constant("EC-evaluate input:"))),
assign("comp", list(op("parse"), reg("comp"))),
test(list(op("is_null"), reg("comp"))),
branch(label("evaluator_done")),
assign("env", list(op("get_current_environment"))),
assign("val", list(op("scan_out_declarations"), reg("comp"))),
save("comp"), // so we can use it to temporarily hold $\texttt{*unassigned*}$ values
assign("comp", list(op("list_of_unassigned"), reg("val"))),
assign("env", list(op("extend_environment"),
reg("val"), reg("comp"), reg("env"))),
perform(list(op("set_current_environment"), reg("env"))),
restore("comp"), // the program
assign("continue", label("print_result")),
go_to(label("eval_dispatch")),
"print_result",
perform(list(op("user_print"),
constant("EC-evaluate value:"), reg("val"))),
go_to(label("read_evaluate_print_loop")),
Original
JavaScript
We store the current environment, initially the global environment,
in the variable current_environment
and update it each time around the loop to remember past declarations.
The operations
get_current_environment and
set_current_environment
simply get and set this variable.
let current_environment = the_global_environment;
function get_current_environment() {
return current_environment;
}
function set_current_environment(env) {
current_environment = env;
}
When we encounter an
error in a
procedurefunction
(such as the
unknown procedure type errorunknown function type error
indicated at
apply-dispatch),apply_dispatch),
we print an error message and return to the driver loop.[2]
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)
(such as an undeclared name)
interrupts an evaluation.[3]
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.
Original
JavaScript
(define eceval
(make-machine
'(exp env val proc argl continue unev)
eceval-operations
'(
read-eval-print-loop
$\langle$entire machine controller as given above$\rangle$
)))
const eceval = make_machine(list("comp", "env", "val", "fun",
"argl", "continue", "unev"),
eceval_operations,
list("read_evaluate_print_loop",
$\langle{}$entire machine controller as given above$\rangle$
"evaluator_done"));
We must define
Scheme proceduresJavaScript functions
to simulate the operations used as primitives by the evaluator. These are
the same
proceduresfunctions
we used for the metacircular evaluator in
section 4.1, together with the few additional
ones defined in footnotes throughout section 5.4.
Original
JavaScript
(define eceval-operations
(list (list 'self-evaluating? self-evaluating)
\textit{complete list of operations for eceval machine}))
Finally, we can initialize the global environment and run the evaluator:
Original
JavaScript
(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
expressionsprograms
in this way will take much longer
than if we had directly typed them into
Scheme,JavaScript,
because of the
multiple levels of simulation involved. Our
expressionsprograms
are evaluated
by the explicit-control-evaluator machine, which is being simulated by
a
SchemeJavaScript
program, which is itself being evaluated by the
SchemeJavaScript
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
expressionsprograms
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-resultprint_result
entry point to print the statistics:
Original
JavaScript
print-result
(perform (op print-stack-statistics)); added instruction
(perform
(op announce-output) (const "EC-Eval value:"))
$\ldots$ ; same as before
"print_result",
perform(list(op("print_stack_statistics"))), // added instruction
// rest is same as before
perform(list(op("user_print"),
constant("EC-evaluate value:"), reg("val"))),
go_to(label("read_evaluate_print_loop")),
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
EC-evaluate input:
function factorial (n) {
return n === 1
? 1
: factorial(n - 1) * n;
}
total pushes = 4
maximum depth = 3
EC-evaluate value:
undefined
EC-evaluate input:
factorial(5);
total pushes = 151
maximum depth = 28
EC-evaluate 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.program.
Exercise 5.29
Use the monitored stack to explore the
tail-recursive property of the
evaluator (section 5.4.2). Start the
evaluator and define the
iterative factorialprocedurefunction
from section 1.2.1:
function factorial(n) {
function iter(product, counter) {
return counter > n
? product
: iter(counter * product,
counter + 1);
}
return iter(1, 1);
}
Run the
procedurefunction
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.
You will find that the maximum depth required to evaluate
$n!$ is independent of
$n$. What is that depth?
Determine from your data a formula in terms of
$n$ for the total number of push operations
used in evaluating $n!$ for any
$n \geq 1$. Note that the number of
operations used is a linear function of $n$
and is thus determined by two constants.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 5.30
For comparison with exercise 5.29, explore
the behavior of the following
procedurefunction
for computing
factorials recursively:
Original
JavaScript
(define (factorial n)
(if (= n 1)
1
(* (factorial (- n 1)) n)))
function factorial(n) {
return n === 1
? 1
: factorial(n - 1) * n;
}
By running this
procedurefunction
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 \geq 1$. (Again, these functions will be
linear.) Summarize your experiments by filling in the following table with
the appropriate expressions in terms of $n$:
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.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 2.93
Modify the definition of the evaluator by changing
eval-sequence
as described in section 5.4.2ev_return
as described in section 5.4.2
so that the evaluator is no longer
tail-recursive. Rerun your experiments from
exercises 5.29
and 5.30 to demonstrate that both versions of
the factorialprocedurefunction
now require space that grows linearly with their input.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 5.31
Monitor the stack operations in the tree-recursive
Fibonacci computation:
Original
JavaScript
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
function fib(n) {
return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
Give a formula in terms of $n$ for the
maximum depth of the stack required to compute
${\textrm{Fib}}(n)$ for
$n \geq 2$. Hint: In
section 1.2.2 we argued that the space
used by this process grows linearly with $n$.
Give a formula for the total number of pushes used to compute
${\textrm{Fib}}(n)$ for
$n \geq 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 ${\textrm{Fib}}(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 {\textrm{Fib}}(n+1) + b$ and give the
values of $a$ and
$b$.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
Exercise 5.32
Our evaluator currently catches and signals only two kinds of
errors—unknown
expression
component
types and unknown
procedurefunction
types. Other errors will take us out of the evaluator
read-eval-print
read-evaluate-print
loop.
When we run the evaluator using the register-machine simulator, these
errors are caught by the underlying
SchemeJavaScript
system. This is analogous
to the computer crashing when a user program makes an error.[4]
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.
Errors that occur in the evaluation process, such as an attempt to
access an unbound
variable,name,
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.name.
The evaluator can test
for this condition code and then do what is necessary to go to
signal-error.signal_error.
Find all of the places in the evaluator where such a
change is necessary and fix them. This is lots of work.
Much worse is the problem of handling errors that are signaled by
applying primitive
proceduresfunctions
such as an attempt to divide by zero or an attempt to extract the
car
of a symbol.
head
of a string.
In a professionally written high-quality system, each
primitive application is checked for safety as part of the primitive.
For example, every call to
carhead
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
procedurefunction
check for applicability and returning an appropriate distinguished
condition code on failure. Then the
primitive-applyprimitive_apply
code in the evaluator can check for the condition code and go to
signal-errorsignal_error
if necessary. Build this structure and make it work.
This is a major project.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.
[1]
We assume
here that
readuser_read,
parse,
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,
theyreading and printing
would be
implemented using low-level input-output operations such as transferring
single characters to and from a device.
Original
JavaScript
To support the
get-global-environment operation we define
(define the-global-environment (setup-environment))
(define (get-global-environment)
the-global-environment)
[2]
There are
other errors that we would like the interpreter to handle, but these are not
so simple. See exercise 5.32.
[3]
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.
Regrettably, this is the normal state of affairs in
conventional compiler-based language systems such as C.
In UNIX$^{\textrm{TM}}$ the system dumps
core, and in
DOS/Windows$^{\textrm{TM}}$
it becomes catatonic. The
Macintosh$^{\textrm{TM}}$ displays a picture of
an exploding bomb and offers you the opportunity to reboot the
computer—if you're lucky.
This manifests itself as, for example, a kernel panic or a blue
screen of death or even a reboot. Automatic rebooting is an approach
typically used on phones and tablets. Most modern operating systems do a
decent job of preventing user programs from causing an entire machine to
crash.
