Problem Set 12
Register Machines and Compilation
**FINAL EXAM**: The final will be held on Monday, May 18, from 1:30 to 4:30 in Johnson Athletic Center (W34-100). It will cover the whole course with extra emphasis on the material not covered in the previous two quizzes, namely, Problem Sets 10, 11, and 12 and chapters 4-5 of the book.
Register machines provide a means of customizing code for particular
processes. In principle, customization leads to more efficient code,
since one can avoid the overhead that comes from a compiler's
obligation to handle more general computations
. In this problem set you will handcraft two simple
machines and compare them to the compiler and the explicit control
evaluator of Chapter 5.
The register machines you define should use only the following few primitives:
+ - * / inc dec = < > zero? not true false nil cons car cdr pair? null? list eq? symbol? write-line.
Even though code generated by the compilers uses more complex primitives, (e.g. lookup-variable-value extend-environment ...,) your hand-crafted code should turn out to run more efficiently.
Remember that register machine instructions are only of the following
types: test branch assign goto save restore perform. In this
problem set, you should not need to use perform. Remember also
that the only values that can be assigned to registers or tested in
branches are constants, fetches from registers, or primitive
operations applied to fetches from registers. No nested operations
are permitted.