# SICP Solutions

### Chapter 3, Modularity, Objects, and State

#### Exercise 3.63

This took me quite some time to figure out. I also used the Louis style in few exercises before - well, it turns out to be very expensive way and should not be used.

I used trace-entry which turns out very useful.

It will take quite a lot of writing to explain the exact behaviour. Instead I will just put the output from trace and give some pointers.

In Summary - its a bad idea to go with Louis version. And without memoize it gets worse!

#### Using memoize

Clearly, as we can see, Louis version computation do not take advantage of the previous values computed/accessed and accessing nth element of the stream requires O(n) operations always.

While Original also requires O(n) operations to access nth element for the first time but if earlier element is already accessed then it uses that result. for eg accessing 3rd element after accessing second element will only require O(1) operations but if no element is accessed before and we access 3rd element first time then it rquires O(n) operations.

#### Without Memoize

Note that here Louis has become exponential - accessing nth element requires $\, \sum_{i=1}^{n-1} g(i) \,$ where g(i) is the cost of accessing ith element. This is similar to the fibonacci recursive process complexity as we have seen earlier and it requires similar run time - exponential.

The original process is now, always O(n) irrespective of the case that whether any element being accessed before. Thus this is still better then Louis - even when we are not using memoize. Note that memoized Louis and non-memoized original are of same comlexity.

Some pointers/outline to understand:

First ignore the memoize part and undertand how Louis works:

Note that (sqrt-stream-1 2) always returns same object, lets call it C.

Let’s assume we already defined the object, louis as (define louis (sqrt-stream-1 2)). And we access 0th, 1st and 2nd element of louis in that order.

• When we access 0th element of louis- We get 1 and a promise to to evaluate (stream-map (lambda(guess) (sqrt-improve x guess)) (sqrt-stream-1 2)). Lets call this promise as X.

• When we access 1st element of louis - We evaluate X which requires first to invoke (sqrt-stream-1 2)(this call returns C) and then stream-map is invoked on C. Then we get (1/2, promise-1) where promise-1 means/represents calling stream-map with sqrt-improve on cdr(stream-cdr) of (sqrt-stream-1 2). Thus the final result becomes (1, 1/2, promise-1) (for representation purpose only - the final result will not be like this but contains promises/memoize-proc wrapper).

• Now, when we access 2nd element of louis - we evaluate promise-1:

• we first need to access cdr of the result of (sqrt-stream-1 2)(this results a call to sqrt-stream-1) - which is (1/2, promise-1) - as we saw while accessing 1st element above - lets call this res2
• then stream-map is invoked on the res2, the result of last step.
• cons-stream is created with following parts:
• result of applying sqrt-improve on first element of res2 - thus applying sqrt-improve on 1/2.
• promise-2 to apply stream-map on cdr of res2 - thus cdr of promise-1 - which means cdr of cdr of C(result of (sqrt-stream 2)).

Now, it is simple to understand while considering of adding/removing memoize.

memoize comes into picture only with cdr(stream-cdr).