SICP Section 5.1 Designing Register Machines

Exercise 5.2. (and 5.1) Use the register-machine language to describe the iterative factorial machine of exercise 5.1.

Answer:
(controller (assign p (const 1)) (assign c (const 1)) test-c (test (op >) (reg c) (reg n)) (branch (label factorial-done)) (assign t (op *) (reg p) (reg c)) (assign p (reg t)) (assign t (op +) (reg c) (const 1)) (assign c (reg t)) (goto (label test-c)) factorial-done)
Exercise 5.3. Design a machine to compute square roots using Newton's method, as described in section 1.1.7:
(define (sqrt x) (define (good-enough? guess) (< (abs (- (square guess) x)) 0.001)) (define (improve guess) (average guess (/ x guess))) (define (sqrt-iter guess) (if (good-enough? guess) guess (sqrt-iter (improve guess)))) (sqrt-iter 1.0))
Begin by assuming that good-enough? and improve operations are available as primitives. Then show how to expand these in terms of arithmetic operations. Describe each version of the sqrt machine design by drawing a data-path diagram and writing a controller definition in the register-machine language.

Answer: I am skipping the data-path diagrams for the three different versions of sqrt. Controller definitions of the three versions in the register-machine language follow. All three versions assume that abs, square and average are available as primitive operations along with - and /.

Version 1.
(controller (assign guess (const 1.0)) sqrt-iter (test (op good-enough?) (reg guess)) (branch (label sqrt-done)) (assign guess (op improve) (reg guess)) (goto (label sqrt-iter)) sqrt-done)
Version 2. In this version good-enough? is expanded using arithmetic operations.
(controller (assign guess (const 1.0)) sqrt-iter (assign t (op square) (reg guess)) (assign t (op -) (reg t) (reg x)) (assign t (op abs) (reg t)) (test (op <) (reg t) (const 0.001)) (branch (label sqrt-done)) (assign guess (op improve) (reg guess)) (goto (label sqrt-iter)) sqrt-done)
Version 3. Improve is also expanded using arithmetic operations.
(controller (assign guess (const 1.0)) sqrt-iter (assign t (op square) (reg guess)) (assign t (op -) (reg t) (reg x)) (assign t (op abs) (reg t)) (test (op <) (reg t) (const 0.001)) (branch (label sqrt-done)) (assign t (op /) (reg x) (reg guess)) (assign guess (op average) (reg t) (reg guess)) (goto (label sqrt-iter)) sqrt-done)
Exercise 5.4. Specify register machines that implement each of the following procedures. For each machine, write a controller instruction sequence and draw a diagram showing the data paths.

a. Recursive exponentiation:
(define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1)))))
b. Iterative exponentiation:
(define (expt b n) (define (expt-iter counter product) (if (= counter 0) product (expt-iter (- counter 1) (* b product)))) (expt-iter n 1))

Answer:
a. Recursive exponentiation.
(controller (assign continue (label expt-done)) expt-loop (test (op =) (reg n) (const 0)) ;; Test for (= n 0) (branch (label base-case)) ;; We only need to save continue as b is constant throughout ;; and the successive values of n are not used for calculation. (save continue) (assign n (op -) (reg n) (const 1)) (assign continue (label after-expt)) (goto (label expt-loop)) after-expt (restore continue) (assign val (op *) (reg b) (reg val)) (goto (reg continue)) base-case (assign val (const 1)) (goto (reg continue)) expt-done)
b. Iterative exponentiation.
(controller (assign counter (reg n)) (assign product (const 1)) expt-loop (test (op =) (reg counter) (const 0)) (branch (label expt-done)) ;; We don't have to save any value in the stack. ;; The result of exponentiation will be available in register product at the end of calculation. (assign counter (op -) (reg counter) (const 1)) (assign product (op *) (reg b) (reg product)) (goto (label expt-loop)) expt-done)
Exercise 5.5. Hand-simulate the factorial and Fibonacci machines, using some nontrivial input (requiring execution of at least one recursive call). Show the contents of the stack at each significant point in the execution.

Answer: (factorial 3)
Init:
continue = fact-done; n = 3;


Iteration round 1.
Test (= n 1) fails.
Stack: continue => fact-done; n=> 3.
n = 2; continue = after-fact.


Iteration round 2.
Test (= n 1) fails.
Stack: continue => after-fact, fact-done; n=> 2, 3.
n = 1; continue = after-fact.


Iteration round 3.
Test (= n 1) succeeds. Proceed to base-case
val = 1; proceed to after-fact


After-fact round 1.
n <= 2. continue <= after-fact.
Stack: continue => fact-done; n=> 3.
val = 2 * 1 = 2


After-fact round 2.
n <= 3. continue <= fact-done.
Stack: empty
val = 3 * 2 = 6
Proceed to fact-done


Exercise 5.6. Ben Bitdiddle observes that the Fibonacci machine's controller sequence has an extra save and an extra restore, which can be removed to make a faster machine. Where are these instructions?

Answer: The redundant save and restore statements occur in the set of instructions labeled afterfib-n-1. The (restore continue) and (save continue) statements that occur at the top can be removed as the value of continue will never change between restore and save calls. The machine can be now re-written as follows:
(controller (assign continue (label fib-done)) fib-loop (test (op <) (reg n) (const 2)) (branch (label immediate-answer)) ;; set up to compute Fib(n - 1) (save continue) (assign continue (label afterfib-n-1)) (save n) ; save old value of n (assign n (op -) (reg n) (const 1)); clobber n to n - 1 (goto (label fib-loop)) ; perform recursive call afterfib-n-1 ; upon return, val contains Fib(n - 1) (restore n) ;; (restore continue) ;; **REDUNDANT** ;; set up to compute Fib(n - 2) (assign n (op -) (reg n) (const 2)) ;; (save continue) ;; **REDUNDANT** (assign continue (label afterfib-n-2)) (save val) ; save Fib(n - 1) (goto (label fib-loop)) afterfib-n-2 ; upon return, val contains Fib(n - 2) (assign n (reg val)) ; n now contains Fib(n - 2) (restore val) ; val now contains Fib(n - 1) (restore continue) (assign val ; Fib(n - 1) + Fib(n - 2) (op +) (reg val) (reg n)) (goto (reg continue)) ; return to caller, answer is in val immediate-answer (assign val (reg n)) ; base case: Fib(n) = n (goto (reg continue)) fib-done)