Problem Set 9
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 computations1. In this problem set you will handcraft two simple machines and then compare the performance of your handcrafted code to that of a compiler and the explicit control evaluator of Chapter 5.
Some things to keep in mind when writing your register machine code:
The following exercises should be prepared for discussion in tutorial.
The procedure expt is a procedure that takes two arguments, n and m, and returns n raised to the m-th power. So, for example, (expt 2 3) evaluates to 8. Assuming that m is non-negative, define, in Scheme, three different implementations for expt that all have different orders of growth. At least one of your three implementations must generate a recursive process and one must generate an iterative process. For each of your procedures, say what order of growth in time (number of machine operations) and space (stack depth) you expect them to use.
Make sure you define everything using only the available primitives.
Implement each of your procedures from Tutorial Exercise 1 as a register machine, and show both the data paths and controllers for each machine. For the data paths, a diagram is needed; for the controllers, a textual description in the manner of Chapter 5 is adequate. Also, be sure to clearly specify (e.g. as a comment in the code) which registers are input registers and which are output registers.
You will use the register machine simulator to test the register machines you designed in the tutorial exercises. To use the simulator, load the problem set code and type in your machine definitions. For example, you might use something like:
(define my-machine
(make-machine
'(x l val ...) ; list the registers you will use here
standard-primitives ; + - * / etc.
'(
; add your machine controller code here, for example
(assign x (reg val))
.
.
.
)))
You will find it convenient to define test procedures that load an input into a machine, run the machine, print some statistics, and return the result computed by the machine. Here is an example that works for a machine that has an input register lst and returns its result in register result. Depending on how you design your machine, you will most likely adapt this code:
(define (test-machine machine arg)
(set-register-contents! machine 'lst arg) ;; place input arg into 'lst register
(newline)
(display ";Resetting... ignore")
(let ((the-stack (machine 'stack)))
(the-stack 'initialize)
(newline)
(display ";Running on arg: ") (display arg)
(start machine)
(newline)
(display ";Run complete:")
(the-stack 'print-statistics))
(get-register-contents machine 'result))
Notice that we use the approximation that the number of operations performed is proportional to the number of save operations performed. This is a pretty good approximation for code from our compiler, but it isn't good for hand written code.
Define a test procedure and use it to debug your machines by running them on some representative inputs. Make a table that records the number of stack pushes (our approximation for the number of operations) and maximum stack depth (our approximation for the amount of space required) as a function of the magnitude of the exponent m.
Try to derive formulas for the total number of pushes and maximum stack depth used by your machines, as functions of the magnitude of m. In most cases, the functions will turn out to be polynomials in the magnitude of the exponent, in which case you should be able to exhibit exact formulas, not just orders of growth.
Having built hand-crafted register machines for our problem, we now want to compare their performance with code generated by the compiler and code generated by the evaluator.
There are two ways to run the compiler. First, you may simply compile an expression and obtain the list of machine instructions as a result, so that you can study it. For instance,
(define test-expression
'(define (f x y) (* (+ x y) (- x y))))
(define result (compile test-expression 'val 'return))
(pp result)
The second way to run the compiler is to apply the procedure compile-and-go to the expression. This compiles the expression and executes it in the environment of the explicit control evaluator machine eceval. When evaluation is complete, you are left in the read-eval-print loop talking to the explicit control evaluator. Then you can experiment with the compiled expression by evaluating further expressions.
The evaluator for this problem set is the explicit control evaluator of section 5.4. Warning: Do not use cond and let when interacting with the explicit control evaluator and the compiler (the explicit control evaluator does not handle these special forms, the compiler does not handle let).
To evaluate an expression in the eceval read-eval-print loop, type the expression after the prompt, followed by ctrl-X ctrl-E. After each evaluation, the simulator will print the number of stack and machine operations required to execute the code.3
Note that you can start up the evaluator by invoking (start-eceval) or you can use compile-and-go to enter the evaluator. Here is an example:
(compile-and-go '(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))) (total-pushes = 0 maximum-depth = 0) ;;; EC-Eval value: ok
;;; EC-Eval input: (fact 4) <== you type this, then C-X C-E (total-pushes = 31 maximum-depth = 14) ;;; EC-Eval value: 24
;;; EC-Eval input: (fact (fact 3)) <== you type this (total-pushes = 68 maximum-depth = 20) ;;; EC-Eval value: 720
;;; EC-Eval input: fact (total-pushes = 0 maximum-depth = 0) ;;; EC-Eval value: <compiled-procedure>
;;; EC-Eval input: (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) ;<== fact gets redefined (total-pushes = 3 maximum-depth = 3) ;;; EC-Eval value: ok
;;; EC-Eval input: fact (total-pushes = 0 maximum-depth = 0) ;;; EC-Eval value: (compound-procedure (n) ((if (= n 0) 1 (* n (fact (- n 1))))) <procedure-env>)
;;; EC-Eval input: (fact 4) ;<== redefined fact gets interpreted -- slower! (total-pushes = 144 maximum-depth = 20) ;;; EC-Eval value: 24
To exit back to regular Scheme type ctrl-C ctrl-C. To re-enter the evaluator with the previous global environment, you may do another compile-and-go. To start the evaluator with a reinitialized global environment, evaluate (start-eceval). To restart the read-eval-print loop without clearing the global environment, do (continue-eceval).
Compile and run the (Scheme) definitions of your three expt procedures, and make tables to record statistics.
Now redefine your expt procedures within the eceval read-eval-print loop and record corresponding statistics for the interpreted definitions.
Derive formulas for the total number of pushes and maximum stack depth required, as functions of the magnitude of m, for the compiled and interpreted procedures.
We'll consider the time used for a computation to be the total number of stack pushes, and the space used to be the maximum stack depth. For each of your procedures, determine the limiting ratio, as the exponent becomes large, of the time and space requirements for your hand-coded machines, versus the time and space requirements for the compiled and interpreted code.
Make listings of the code generated by the compiler for the definitions of your three procedures. Annotate these listings to indicate what various portions of the generated register code corresponds to, e.g. procedure definition, construction of argument lists, procedure application, etc.
Compare the listings with your hand-coded versions to see why the compiler's code is less efficient than yours. Suggest one improvement to the compiler that could lead it to do a better job. Write one or two clear paragraphs indicating how you might go about implementing your improvement. You needn't actually carry out the the implementation, but your description should be reasonably precise. For example, you should say what new information the compiler should keep track of, what new data structures may be required to maintain this information, and how the information should be used in generating the new, improved code.
To gain more understanding of the compiler (as described in Chapter 5 of the book), you will next make a small change to the language and modify the compiler accordingly. In particular, we wish to change variable assignment to actually return a useful value, in this case the new value of the variable. For example
(define x 1) (set! x 2) ; Value: 2 (* (set! x (+ x 1)) 10) ; Value: 30
To do this problem, you will need to think carefully about how the compiler generates code and ``preserves'' registers by using the stack. You should not add any new registers to your machine. You will also have to consider (at least when you are testing your code) what order arguments are evaluated in - we've said ``in any order'' but the compiler and the interpreter use a particular order (and is it the same?).
Turn in listings of your modifications to the compiler, together with test cases that show both the compiled code generated (using compile-and-display) and the results returned for your test cases (using compile-and-go). Remember, compiled code for your set! expressions will have this new behavior, but eceval itself will not, so keep this in mind when you are debugging.
Some test cases you should consider include:
(set! x 1) (set! x (+ 1 2)) (begin (set! x (+ 1 2)) 3) (+ x (set! x 10))
That's all folks - the last problem set! We hope you have found them entertaining, engrossing, and educational.
Turn in answers to the following questions along with your answers to the questions in the problem set:
This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html ps9-reg.
The translation was initiated by Tony Eng on 1998-11-16