(registers x y t) (operations * +) (controller (assign y (const 5)) (assign t (op *) (reg x) (const 7)) (assign y (op +) (reg t) (reg y)) (assign t (op *) (reg x) (reg x)) (assign t (op *) (reg t) (const 3)) (assign y (op +) (reg t) (reg y)))Given the machine which computes f(x), write a new machine which has inputs in a and b registers and computes f(a)/f(b). You may also use a continue register and a stack.
; Contract -- inputs in reg a and b; output will be in y (registers x y t a b continue) (operations * + /) (controller (assign x (reg a)) (assign continue (label f_of_b)) (goto (label f_of_x)) f_of_b (save y) (assign x (reg b)) (assign continue (label divide_em)) (goto (label f_of_x)) ; This is the old f(x) f_of_x (assign y (const 5)) (assign t (op *) (reg x) (const 7)) (assign y (op +) (reg t) (reg y)) (assign t (op *) (reg x) (reg x)) (assign t (op *) (reg t) (const 3)) (assign y (op +) (reg t) (reg y)) (goto (reg continue)) divide_em (restore t) ; f(a) (assign y (op /) (reg t) (reg y)) )
(define (sqrt x)
(define (good-enough? ..))
(define (improve ..))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1))
We can define a register machine for this calculation. Assume for now that
good-enough? and improve are primitives in the machine.
Rather than jump directly to the register machine "code", we can
generate the data and control flow diagrams for this problem:
And now the register machine:
(registers x guess) (operations good-enough? improve) (controller loop (test (op good-enough?) (reg guess) (reg x)) (branch (label done)) (assign guess (op improve) (reg guess) (reg x)) (goto (label loop)) done)Both the operation and the test box may in fact be implemented as additional register code. For example, we can update our machine given that improve is defined within sqrt as
(define (improve guess)
(average guess (/ x guess)))
as shown in
(define (explode b n)
(define (ex-iter base counter product)
(if (= counter 0)
product
(ex-iter (* base base)
(- count 1)
(* base product))))
(ex-iter b n 1))
The register code would be
(register b n base counter product) (operations * - =) (controller ; Contract: inputs in b, n; output in product ; initialize to start iteration (assign base (reg b)) (assign counter (reg n)) (assign product (const 1)) ex-iter (test (op =) (reg counter) (const 0)) (branch (label done)) ; calculate args for next iteration (assign product (op *) (reg base) (reg product)) (assign base (op *) (reg base) (reg base)) (assign count (op -) (reg count) (const 1)) (goto (label ex-iter)) done)Implementation of recursive processes, on the other hand, requires some way to ``remember'' two important things. First, we must keep track of how deep into the recursion we are and where we are supposed to return to each step of the way. Second, we must remember the intermediate state of a computation so that, upon return from the recursive call, the deferred operations can be completed. This leads us to one useful calling convention governing the use of a stack. We can use a continue register to indicate where to go when done, and use the stack to keep track of our recursion. In this convention, the calling routine saves away the registers it will need in order to complete the computation upon return.
Note that alternative calling conventions are possible. For example, we could arrange that the subroutine which is called is responsible for saving on the stack the values of any registers which that subroutine is going to touch, and then must restore the stack when all done.
Folding this ideas into an example, consider a register machine to implement the following recursive explode process:
(define (explode b n)
(if (= n 0)
1
(* b (explode (* b b)
(- n 1)))))
The corresponding register machine might be:
; Contract - inputs in b and n; output in val (registers b n val continue) (operations = * -) (controller (assign continue (label done)) explode (test (op =) (reg n) (const 0)) (branch (label basecase)) ; Remember things before the recursion (save b) (save continue) ; Calc args for recursive call (assign b (op *) (reg b) (reg b)) (assign n (op -) (reg n) (const 1)) (assign continue (label deferred_ops)) (goto (label explode)) deferred_ops (restore continue) (restore b) (assign val (op *) (reg b) (reg val)) (goto (reg continue)) basecase (assign val (const 1)) (goto (reg continue)) done)