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 function 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:[1]
"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")), go_to(label("eval_dispatch")), "print_result", perform(op("announce_output"), const(";;; EC_Eval value:")), perform(op("user_print"), reg("val")), go_to(label("read_eval_print_loop")),
When we encounter an error in a
function
(such as the unknown
function
type error
indicated at apply_dispatch), we print an
error message and return to the driver loop.[2]
"unknown_expression_type", assign("val", const("unknown_expression_type_error")), go_to(label("signal_error")), "unknown_procedure_type", restore("continue"), /// clean up stack (from apply_dispatch) assign(val(const("unknown_procedure_type_error"))), go_to(label("signal_error")), "signal_error", perform(op("user_print"), reg("val")), go_to(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.[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.
function eceval() { return make_machine(list("exp", "env", "val", "proc", "argl", "continue", "unev"), eceval_operations, list(read_eval_print_loop, ... /* entire machine controller as given above */ )); }
We must define Scheme functions to simulate the operations used as primitives by the evaluator. These are the same functions we used for the metacircular evaluator in section 4.1, together with the few additional ones defined in footnotes throughout section 5.4.
const eceval_operations = list(list("is_self_evaluating", is_self_evaluating), ... /* complete list of operations for eceval machine */ );
Finally, we can initialize the global environment and run the evaluator:
const the_global_environment = setup_environment(); start(eceval);
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: function factorial (n) { return n === 1 ? 1 n * factorial(n - 1); } (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.
function factorial(n) { function iter(product, counter, max_count) { return counter > max_count ? product : fact_iter(counter * product, counter + 1, max_count); } return iter(1, 1, n); }
function factorial(n) { return n === 1 ? 1 : n * factorial(n - 1); }
function fib(n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }
overheadconstant $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$.
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
const the_global_environment = setup_environment(); function get_global_environment() { return the_global_environment; }
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.