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 traceentry
which turns out very useful.
1
2
3
4
(traceentry sqrtstream)
(traceentry sqrtstream1) ;Louis version renamed to avoid conflict
(traceentry streammap)
(traceentry sqrtimprove)
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
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
32
33
34
35
36
37
38
39
40
41
42
43
44

 Original  Louis 

 1 ]=> (define orig (sqrtstream 2))  1 ]=> (define louis (sqrtstream1 2)) 
  
 [Entering #[compproc 169 sqrtstream]  [Entering #[compproc 175 sqrtstream1] 
 ;Value: orig  Args: 2] 
  ;Value: louis 
 1 ]=> (streamref orig 0)  
  1 ]=> (streamref louis 0) 
 ;Value: 1.  
  ;Value: 1. 
 1 ]=> (streamref orig 1)  
  1 ]=> (streamref louis 1) 
 [Entering #[compproc 170 streammap]  
 Args: #[compproc 171]  [Entering #[compproc 175 sqrtstream1] 
 ((1. . #[compproc 172]))]  Args: 2] 
 [Entering #[compproc 173 sqrtimprove]  [Entering #[compproc 170 streammap] 
 Args: 1.  Args: #[compproc 176] 
 2]  ((1. . #[compproc 177]))] 
 ;Value: 1.5  [Entering #[compproc 173 sqrtimprove] 
  Args: 1. 
 1 ]=> (streamref orig 2)  2] 
  ;Value: 1.5 
 [Entering #[compproc 170 streammap]  
 Args: #[compproc 171]  1 ]=> (streamref louis 2) 
 ((1.5 . #[compproc 174]))]  
 [Entering #[compproc 173 sqrtimprove]  [Entering #[compproc 175 sqrtstream1] 
 Args: 1.5  Args: 2] 
 2]  [Entering #[compproc 170 streammap] 
 ;Value: 1.4166666666666665  Args: #[compproc 178] 
  ((1. . #[compproc 179]))] 
  [Entering #[compproc 173 sqrtimprove] 
  Args: 1. 
  2] 
  [Entering #[compproc 170 streammap] 
  Args: #[compproc 176] 
  ((1.5 . #[compproc 180]))] 
  [Entering #[compproc 173 sqrtimprove] 
  Args: 1.5 
  2] 
  ;Value: 1.4166666666666665 
  

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
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

 Original  Louis 

 1 ]=> (define nmorig (sqrtstream 2))  1 ]=> (define nmlouis (sqrtstream1 2)) 
  
 [Entering #[compproc 182 sqrtstream]  [Entering #[compproc 190 sqrtstream1] 
 Args: 2]  Args: 2] 
 ;Value: nmorig  ;Value: nmlouis 
  
 1 ]=> (streamref nmorig 0)  1 ]=> (streamref nmlouis 0) 
  
 ;Value: 1.  ;Value: 1. 
  
 1 ]=> (streamref nmorig 1)  1 ]=> (streamref nmlouis 1) 
  
 [Entering #[compproc 183 streammap]  [Entering #[compproc 190 sqrtstream1] 
 Args: #[compproc 184]  Args: 2] 
 ((1. . #[compproc 185]))]  [Entering #[compproc 183 streammap] 
 [Entering #[compproc 186 sqrtimprove]  Args: #[compproc 191] 
 Args: 1.  ((1. . #[compproc 192]))] 
 2]  [Entering #[compproc 186 sqrtimprove] 
 ;Value: 1.5  Args: 1. 
  2] 
 1 ]=> (streamref nmorig 2)  ;Value: 1.5 
  
 [Entering #[compproc 183 streammap]  1 ]=> (streamref nmlouis 2) 
 Args: #[compproc 187]  
 ((1. . #[compproc 185]))]  [Entering #[compproc 190 sqrtstream1] 
 [Entering #[compproc 186 sqrtimprove]  Args: 2] 
 Args: 1.  [Entering #[compproc 183 streammap] 
 2]  Args: #[compproc 193] 
 [Entering #[compproc 183 streammap]  ((1. . #[compproc 194]))] 
 Args: #[compproc 188]  [Entering #[compproc 186 sqrtimprove] 
 ((1. . #[compproc 185]))]  Args: 1. 
 [Entering #[compproc 186 sqrtimprove]  2] 
 Args: 1.  [Entering #[compproc 190 sqrtstream1] 
 2]  Args: 2] 
 [Entering #[compproc 183 streammap]  [Entering #[compproc 183 streammap] 
 Args: #[compproc 187]  Args: #[compproc 195] 
 ((1.5 . #[compproc 189]))]  ((1. . #[compproc 196]))] 
 [Entering #[compproc 186 sqrtimprove]  [Entering #[compproc 186 sqrtimprove] 
 Args: 1.5  Args: 1. 
 2]  2] 
 ;Value: 1.4166666666666665  [Entering #[compproc 183 streammap] 
  Args: #[compproc 193] 
  ((1.5 . #[compproc 197]))] 
  [Entering #[compproc 186 sqrtimprove] 
  Args: 1.5 
  2] 
  ;Value: 1.4166666666666665 

Note that here Louis has become exponential  accessing nth element requires $\, \sum_{i=1}^{n1} 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 nonmemoized original are of same comlexity.
Some pointers/outline to understand:
First ignore the memoize part and undertand how Louis works:
Note that (sqrtstream1 2)
always returns same object, lets call it C.
Letâ€™s assume we already defined the object, louis
as (define louis (sqrtstream1 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(streammap (lambda(guess) (sqrtimprove x guess)) (sqrtstream1 2))
. Lets call this promise as X. 
When we access 1st element of
louis
 We evaluate X which requires first to invoke(sqrtstream1 2)
(this call returns C) and thenstreammap
is invoked on C. Then we get(1/2, promise1)
wherepromise1
means/represents callingstreammap
withsqrtimprove
on cdr(streamcdr) of(sqrtstream1 2)
. Thus the final result becomes(1, 1/2, promise1)
(for representation purpose only  the final result will not be like this but contains promises/memoizeproc wrapper). 
Now, when we access 2nd element of
louis
 we evaluatepromise1
: we first need to access cdr of the result of (sqrtstream1 2)(this results a call to sqrtstream1)  which is (1/2, promise1)  as we saw while accessing 1st element above  lets call this res2
 then
streammap
is invoked on the res2, the result of last step. consstream
is created with following parts: result of applying
sqrtimprove
on first element of res2  thus applyingsqrtimprove
on 1/2. promise2
to applystreammap
on cdr of res2  thus cdr ofpromise1
 which means cdr of cdr of C(result of(sqrtstream 2)
).
 result of applying
Now, it is simple to understand while considering of adding/removing memoize.
memoize comes into picture only with cdr(streamcdr).