a lazy explicit evaluator - solution of SICP exercise 5.25

Modified the explicit evaluator to a lazy one. And here are the main blocks I added.

actual-value
    (save continue)
    (save env)
    (save exp)
    (assign continue (label force-it))
    (goto (label eval-dispatch))
force-it
    (test (op thunk?) (reg val))
    (branch (label thunk-extract))
    (restore exp)
    (restore env)
    (restore continue)
    (goto (reg continue))
thunk-extract
    (assign env (op thunk-env) (reg val))
    (assign exp (op thunk-exp) (reg val))
    (goto (label actual-value))

Here is the whole source file

Playing with Fibonacci - solution of SICP exercise 5.29

Here is the exercise and my answer.

Exercise 5.29.  Monitor the stack operations in the tree-recursive Fibonacci computation:

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

b. Give a formula for the total number of pushes used to compute Fib(n) for n > 2. You should find that the number of pushes (which correlates well with the time used) grows exponentially with n. Hint: Let S(n) be the number of pushes used in computing Fib(n). You should be able to argue that there is a formula that expresses S(n) in terms of S(n - 1), S(n - 2), and some fixed ``overhead'' constant k that is independent of n. Give the formula, and say what k is. Then show that S(n) can be expressed as a Fib(n + 1) + b and give the values of a and b.

My answer:

From Fibonacci function definition above, we can make the conclusion that
S(n) = S(n-1) + S(n-2) + k.
This looks already like the orignal Fibnacci sequence but let's have a look at S(0) and S(1).

S(0) contains only the overhead pushes, let's say this is [a], but not the k above.
S(1) is same.
For S(n) and n>2, k includes not only [a] but also pushes before computation of [+] of S(n-1) and S(n-2).

So S(n) should look like below:

a, a, 2a + k, 3a + 2k, 5a + 4k, ... ...
And the original Fibonacci is:
0, 1, 1, 2, 3, 5, ... ...

Then S(n) must has the format below.

aFib(n+1) + b.

And if given 2 total pushes, etc., S(1) and S(2), we can calculate the value of [a] and [k] as below.
a=16 and k=40.

Experiment: