5.7 Exercise 5.7

We can simulate the recursive and iterative exponentiation machines by wrapping them in make-machine declarations. This can be done mechanically.

First, the recursive machine:

(define recursive-exponentiation-machine

(make-machine

'(b n continue val)

(list (list '= =) (list '- -) (list '* *))

'(start-machine

(assign continue (label expt-done))

expt-loop

(test (op =) (reg n) (const 0))

(branch (label base-case))

(save continue)

(assign n (op -) (reg n) (const 1))

(save n)

(assign continue (label after-expt))

(goto (label expt-loop))

after-expt

(restore n)

(restore continue)

(assign val (op *) (reg b) (reg val))

(goto (reg continue))

base-case

(assign val (const 1))

(goto (reg continue))

expt-done)))

Verifying that it works:

Next, the iterative machine:

(define iterative-exponentiation-machine

(make-machine

'(b n val counter product)

(list (list '= =) (list '- -) (list '* *))

'(start-machine

(assign counter (reg n))

(assign product (const 1))

expt-iter

(test (op =) (reg counter) (const 0))

(branch (label after-expt))

(assign counter (op -) (reg counter) (const 1))

(assign product (op *) (reg b) (reg product))

(goto (label expt-iter))

after-expt

(assign val (reg product))

(goto (label expt-done))

expt-done)))

Verifying that it also works:

Of course, if we use the builtin expt function, we can see that this result is correct: