5.5 Exercise 5.5

5.5.1 Factorial machine

(controller

(assign continue (label fact-done))

fact-loop

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

(branch (label base-case))

(save continue)

(save n)

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

(assign continue (label after-fact))

(goto (label fact-loop))

after-fact

(restore n)

(restore continue)

(assign val (op *) (reg n) (reg val))

(goto (reg continue))

base-case

(assign val (const 1))

(goto (reg continue))

fact-done)

After each instruction, if any register values have changed, they all will be shown in a table, like this:

The stack will also be shown when it is updated, like this:

(assign continue (label fact-done))

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

(branch (label base-case))

This evaluates to false, so we don’t branch.

(save continue)

(save n)

This adds two values to the stack:

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

(assign continue (label after-fact))

(goto (label fact-loop))

This updates the values of n and continue for the next recursive call, and jumps to the beginning of the loop.

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

(branch (label base-case))

In this case, we do take this branch, moving to the base-case label.

(assign val (const 1))

(goto (reg continue))

At this point, we have first assigned to the val register where the final result will be stored, and will jump to the instruction currently pointed at by the continue register – that is, the after-fact label.

(restore n)

(restore continue)

(assign val (op *) (reg n) (reg val))

(goto (reg continue))

We assign the final val and will presently jump to fact-done, ending the procedure.

5.5.2 Fibonacci machine

(controller

(assign continue (label fib-done))

fib-loop

(test (op <) (reg n) (const 2))

(branch (label immediate-answer))

(save continue)

(assign continue (label afterfib-n-1))

(save n)

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

(goto (label fib-loop))

afterfib-n-1

(restore n)

(restore continue)

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

(save continue)

(assign continue (label afterfib-n-2))

(save val)

(goto (label fib-loop))

afterfib-n-2

(assign n (reg val))

(restore val)

(restore continue)

(assign val

(op +) (reg val) (reg n))

(goto (reg continue))

immediate-answer

(assign val (reg n))

(goto (reg continue))

fib-done)

Our register values will start out like this:

And our stack is empty:

(assign continue (label fib-done))

(test (op <) (reg n) (const 2))

(branch (label immediate-answer))

This is false, so we don’t branch.

(save continue)

(assign continue (label afterfib-n-1))

(save n)

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

(goto (label fib-loop))

We decrement n and move on to the next loop.

(test (op <) (reg n) (const 2))

(branch (label immediate-answer))

This is false, so we don’t branch.

(save continue)

(assign continue (label afterfib-n-1))

This happens to do nothing.

(save n)

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

(goto (label fib-loop))

We decrement n and move on to the next loop.

(test (op <) (reg n) (const 2))

(branch (label immediate-answer))

This is now true, so we will branch.

(assign val (reg n))

(goto (reg continue))

We write the base case value into the val register and will presently jump to afterfib-n-1.

(restore n)

(restore continue)

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

(save continue)

(assign continue (label afterfib-n-2))

We prepare to jump into the other recursive branch for the first time.

(save val)

(goto (label fib-loop))

We also save the value of Fib(1) – we’re going to need it later.

After this, we will begin looping again.

(test (op <) (reg n) (const 2))

(branch (label immediate-answer))

This is true, so we branch.

(assign val (reg n))

(goto (reg continue))

We write the base case value into the val register (overwriting the value that we saved to the stack earlier) and will presently jump to afterfib-n-1.

(assign n (reg val))

This happens to do nothing.

(restore val)

(restore continue)

(assign val (op +) (reg val) (reg n))

(goto (reg continue))

This also happens to do nothing. After this, we will jump to afterfib-n-1 for another recursive go-around.

(restore n)

(restore continue)

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

(save continue)

Notice how we have popped this label off of the stack and immediately put it back.

(assign continue (label afterfib-n-2))

(save val)

(goto (label fib-loop))

(test (op <) (reg n) (const 2))

(branch (label immediate-answer))

This is true, so we will branch.

(assign val (reg n))

(goto (reg continue))

This happens to do nothing.

(assign n (reg val))

This happens to do nothing.

(restore val)

(restore continue)

(assign val (op +) (reg val) (reg n))

(goto (reg continue))

With this final addition, we reach our final answer and exit the procedure.