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))

————————————————————————————————————————————————————————————————————————

a.

inputs are in b and n, output is in val

(controller
    (assign continue (label expt-done))
  expt-loop
    (test (op =) (reg n) (const 1))
    (branch n-is-answer)
    (save n)
    (save continue)
    (assign n (op -) (reg n) (const 1))
    (assign continue (label got-sub-result))
    (goto expt-loop)
  got-sub-result
    (restore continue)
    (restore n)
    (assign n (op *) (reg n) (reg val))
  n-is-answer
    (assign val (reg n))
    (goto (reg continue))
  expt-done)

b.

(controller
    (assign val (const 1))
  loop
    (test (op =) (reg n) (const 0))
    (branch end)
    (assign n (op -) (reg n) (const 1))
    (assign val (op *) (reg val) (reg b))
    (goto (label loop))
  end)