Chapter 5, Computing with Register Machines

Exercise 5.5


I computed for n = 4. Since we are counting from 0, this means we are trying to find the 5th term of fibonacci.

For reference, register machine for fibonacci:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
(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)
   ;; set up to compute Fib(n - 2)
   (assign n (op -) (reg n) (const 2))
   (save continue)
   (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)

For clarity, I prefixed numbers in stack with the variable names.

The contents of stack are shown from left to right, with right most being the top element.

  1. Stack: Empty n: 4
    continue: fib-done

  2. After first fib-loop iteration:
    Stack: fib-done n:4
    n: 3
    continue: afterfib-n-1

  3. After second fib-loop iteration:
    Stack: fib-done n:4 afterfib-n-1 n:3
    n: 2
    continue: afterfib-n-1

  4. After third fib-loop iteration:
    Stack: fib-done n:4 afterfib-n-1 n:3 afterfib-n-1 n:2
    n: 1
    continue: afterfib-n-1

  5. After fourth fib-loop iteration: (no change because it causes a jump to base-case - immediate-answer)
    Stack: fib-done n:4 afterfib-n-1 n:3 afterfib-n-1 n:2
    n: 1
    continue: afterfib-n-1

  6. After immediate-answer
    Stack: fib-done n:4 afterfib-n-1 n:3 afterfib-n-1 n:2
    n: 1
    continue: afterfib-n-1
    val: 1

  7. Now we jump to afterfib-n-1.

  8. After afterfib-n-1:
    Stack: fib-done n:4 afterfib-n-1 n:3 afterfib-n-1 val:1
    n: 0
    continue: afterfib-n-2
    val: 1
    (Note that at this point the top of stack contains (fib 1) - base case value).

  9. Jump to fib-loop.

  10. Since n = 0, fib-loop causes jump to immediate-answer.

  11. After immediate-answer:
    Stack: fib-done n:4 afterfib-n-1 n:3 afterfib-n-1 val:1
    n: 0
    continue: afterfib-n-2
    val: 0

  12. Jump to afterfib-n-2.

  13. After afterfib-n-2:
    Stack: fib-done n:4 afterfib-n-1 n:3
    n: 0
    continue: afterfib-n-1
    val: 1

  14. Jump to afterfib-n-1.

  15. After afterfib-n-1:
    Stack: fib-done n:4 afterfib-n-1 val:1
    n: 1
    continue: after-fib-n-2
    val: 1

  16. Jumpt to fib-loop.

  17. Since n = 1, fib-loop causes jumpt to immediate-answer.
    Stack: fib-done n:4 afterfib-n-1 val:1
    n: 1
    continue: after-fib-n-2
    val: 1

  18. Jump to afterfib-n-2.

  19. After afterfib-n-2:
    Stack: fib-done n:4
    n: 1
    continue: after-fib-n-1
    val: 2

  20. Jump to afterfib-n-1.

  21. After afterfib-n-1:
    Stack: fib-done val:2
    n: 2
    continue: after-fib-n-2
    val: 2

  22. Jump to fib-loop:
    Stack: fib-done val:2 after-fib-n-2 n:2
    n: 1
    continue: after-fib-n-1
    val: 2

  23. Jump to fib-loop.

  24. Since n = 1, fib-loop causes jump to immediate-answer.

  25. After immediate-answer:
    Stack: fib-done val:2 after-fib-n-2 n:2
    n: 1
    continue: afterfib-n-1
    val: 1

  26. Jump to afterfib-n-1.

  27. After afterfib-n-1:
    Stack: fib-done val:2 after-fib-n-2 val:1
    n: 0
    continue: after-fib-n-2
    val: 1

  28. Jump to fib-loop.

  29. Since n=0, fib-loop causes jump to immediate-answer.

  30. After immediate-answer:
    Stack: fib-done val:2 after-fib-n-2 val:1
    n: 0
    continue: after-fib-n-2
    val: 0

  31. Jump to after-fib-n-2.

  32. After after-fib-n-2:
    Stack: fib-done val:2
    n: 1
    continue: after-fib-n-2
    val: 1

  33. Jump to afterfib-n-2:
    Stack: Empty
    n: 1
    continue: fib-done
    val: 3

  34. Jump to fib-done.

  35. val = 3 contains the answer!