How many additions are performed when we compute the $n^{th} $ Fibonacci number using the definition of fibs based on the add-streams procedure? Show that the number of additions would be exponentially greater if we had implemented (delay ⟨exp⟩) simply as (lambda () ⟨exp⟩), without using the optimization provided by the memo-proc procedure.

(define fibs
	(cons-stream
		0
		(cons-stream 1 (add-streams (stream-cdr fibs) fibs))))
	
(define (memo-proc proc)
	(let ((already-run? false) (result false))
		(lambda ()
			(if (not already-run?)
				(begin (set! result (proc))
							 (set! already-run? true)
							 result)
				result))))
				
(define (add-streams s1 s2) (stream-map + s1 s2))

He who forget

on the first sight, if you simply draw a graph like below (like I do), this question would be very confusing. shouldn’t It be like this? isn’t the number of addition is always $n-2$ whether we apply memo-proc ?

      fibs: 0  1  1  2 ...
  cdr fibs: 1  1  2  3 ...
            +  +  +  +
fibs: 0  1  1  2  3  5 ...

well, for the evaluation result, it’s right, but wrong when it comes to how it is evaluated.

let’s expand it a little bit.

fibs = [0, 1, add fibs fibs.next] ;; for simplcity, rewrite fibs

;; expand till the third value can be evaluated
fibs = [0, 1, add [0, 1, add fibs fibs.next] [1, add fibs fibs.next]]
;; progress the otter 'add' of the third item (r shift for one item)
fibs = [0, 1, 1, add [1, add fibs fibs.next] [add fibs fibs.next]]

wow, the third value comes out as 1. and it’s obvious that it takes one add operation because we change one add. keep up for the forth value.

;; add fibs fibs.next <=> 1, add [1, add fibs fibs.next] [add fibs fibs.next]
;; above transformation equivalent and takes one add operation
fibs = [0, 1, 1, add [1, add fibs fibs.next] [1, add [1, add fibs fibs.next] [add fibs fibs.next]]]
fibs = [0, 1, 1, 2, add [add fibs fibs.next] [add [1, add fibs fibs.next] [add fibs fibs.next]]]

;; make a variable
f+ = [add fibs fibs.next]
fibs = [0, 1, 1, 2, add f+ [add [1, f+] [f+]]]

;; the first item in f+ is 1, and it is evaluated for two times
;; which brings two add operation
;; fibs = [0, 1, 1, 2, add f+ [add [1, f+] [f+]]]
;;                         ^                ^
;; plus two add should be performed to make the value move to otter space
;; fibs(4) = 3, A(4) = 2+2 = 4

;; so on and so forth

see, we not ‘remember’ each item, instead, each item is decomposed till reach fibs[0] and fibs[1].

for a general case w/o memo-proc, let $A(n)$ be the number of addition for the $n^{th}$ fibs, there is,

$$ A(n) = A(n-1) + A(n-2)+1,\ where~A(0) = 0,\ A(1)=0 $$

$A(2) = A(0) + A(1)+1 = 1$

$A(3) = A(1) + A(2)+1 = 2$

$A(4) = A(2) + A(3)+1 = 4$

$…$

and it will end up result to, in which k is the exponential base.

$$ k^{n-2}>\phi^{n-2},\ where\ \phi=\frac{\sqrt{5}+1}{2} $$

He who memo

the memo version does exactly the one at the very beginning

      fibs: 0  1  1  2 ...
  cdr fibs: 1  1  2  3 ...
            +  +  +  +
fibs: 0  1  1  2  3  5 ...

however, the question is, how the hack does scheme remember it? where does it preserve the value?