sicp-ex-5.5

  
  
  
 using the example of factorial in the book. 
 (set-register-contents! machine 'n 2) 
  
 1. n = 2 
 (save continue) ;; stack: ((label fact-done)) 
 (save n)             ;;  stack (2 (label fact-done)) 
 (assign n (op -) (reg n) (const 1)) ;; n =1 
 (assign continue (label after-fact)) ;; continue: (label after-fact) 
  
 2. n =1. go to base-case 
 (restore n)      ;; n: 2; stack: ((label fact-done)) 
 (restore continue) ;; continue: label fact-done stack: () 
  

Factorial
=========

State for factorial 4 at each label:

================    ================    ================    ================
fact-loop           fact-loop           fact-loop           fact-loop
----------------    ----------------    ----------------    ----------------
n=4 c=done          n=3 c=aft           n=2 c=aft           n=1 c=aft
----------------    ----------------    ----------------    ----------------
----------------    fact-done      <    fact-done           fact-done
                    4              <    4                   4
                    ----------------    after-fact     <    after-fact
                                        3              <    3
                                        ----------------    after-fact     <
                                                            2              <
                                                            ----------------


================    ================    ================    ================
base-case           after-fact          after-fact          after-fact
----------------    ----------------    ----------------    ----------------
n=1 c=aft           n=1 c=aft v=1       n=2 c=aft v=2       n=3 c=aft v=6
----------------    ----------------    ----------------    ----------------
fact-done           fact-done           fact-done           fact-done
4                   4                   4                   4
after-fact          after-fact          after-fact          ----------------
3                   3                   3
after-fact          after-fact          ----------------
2                   2
----------------    ----------------


================
fact-done
----------------
n=4 c=done v=24
----------------
----------------


Fibonacci
=========

State for 4th Fibonacci at each label

================    ================    ================    ================
fib-loop            fib-loop            fib-loop            fib-loop
----------------    ----------------    ----------------    ----------------
n=4 c=done          n=3 c=afn-1         n=2 c=afn-1         n=1 c=afn-1
----------------    ----------------    ----------------    ----------------
----------------    fib-done       <    fib-done            fib-done
                    4              <    4                   4
                    ----------------    afterfib-n-1   <    afterfib-n-1
                                        3              <    3
                                        ----------------    afterfib-n-1   <
                                                            2              <
                                                            ----------------


================    ================    ================    ================
immediate-answer    afterfib-n-1        fib-loop            immediate-answer
----------------    ----------------    ----------------    ----------------
n=1 c=afn-1         n=1 c=afn-1 v=1     n=0 c=afn-2 v=1     n=0 c=afn-2 v=1
----------------    ----------------    ----------------    ----------------
fib-done            fib-done            fib-done            fib-done
4                   4                   4                   4
afterfib-n-1        afterfib-n-1        afterfib-n-1        afterfib-n-1
3                   3                   3                   3
afterfib-n-1        afterfib-n-1        afterfib-n-1   <    afterfib-n-1
2                   2                   1              <    1
----------------    ----------------    ----------------    ----------------


================    ================    ================    ================
afterfib-n-2        afterfib-n-1        fib-loop            immediate-answer
----------------    ----------------    ----------------    ----------------
n=0 c=afn-2 v=0     n=0 c=afn-1 v=1     n=1 c=afn-2 v=1     n=1 c=afn-2 v=1
----------------    ----------------    ----------------    ----------------
fib-done            fib-done            fib-done            fib-done
4                   4                   4                   4
afterfib-n-1        afterfib-n-1        afterfib-n-1   <    afterfib-n-1
3                   3                   1              <    1
afterfib-n-1        ----------------    ----------------    ----------------
1
----------------


================    ================    ================    ================
afterfib-n-2        afterfib-n-1        fib-loop            fib-loop
----------------    ----------------    ----------------    ----------------
n=1 c=afn-2 v=1     n=1 c=afn-1 v=2     n=2 c=afn-2 v=2     n=1 c=afn-1 v=2
----------------    ----------------    ----------------    ----------------
fib-done            fib-done            fib-done       <    fib-done
4                   4                   2              <    2
afterfib-n-1       -----------------    ----------------    afterfib-n-2   <
1                                                           2              <
----------------                                            ----------------


================    ================    ================    ================
immediate-answer    afterfib-n-1        fib-loop            immediate-answer
----------------    ----------------    ----------------    ----------------
n=1 c=afn-1 v=2     n=1 c=afn-1 v=1     n=0 c=afn-2 v=1     n=0 c=afn-2 v=1
----------------    ----------------    ----------------    ----------------
fib-done            fib-done            fib-done            fib-done
2                   2                   2                   2
afterfib-n-2        afterfib-n-2        afterfib-n-2   <    afterfib-n-2
2                   2                   1              <    1
----------------    ----------------    ----------------    ----------------


================    ================    ================
afterfib-n-2        afterfib-n-2        fib-done
----------------    ----------------    ----------------
n=0 c=afn-2 v=0     n=0 c=afn-2 v=1     n=1 c=done v=3
----------------    ----------------    ----------------
fib-done            fib-done            ----------------
2                   2
afterfib-n-2        ----------------
1
----------------

Newly pushed values marked with '<'

Wish I had picked 3 instead of 4.