sicp-ex-3.63


leafac

The function defined by Louis calls `(sqrt-stream x)' recursively, which yields a new sequence with the same values, only not memoized yet. Thus this version is slower, but if memoization didn't take place, both implementations would be the same.


cel

 (define (louis-sqrt-stream x)
   (cons-stream 1.0
                (stream-map (lambda (guess) (sqrt-improve guess x))
                                      (louis-sqrt-stream x))))

To access the second element in the stream (louis-sqrt-stream n) by taking the stream-car of (stream-cdr (louis-sqrt-stream n)) requires two evaluations of (louis-sqrt-stream n): one as the argument to stream-cdr and one in the course of applying that procedure to its argument. Thus one redundant evaluation is performed. Similarly, accessing the third element in the stream by taking the stream-car of (stream-cdr (stream-cdr (louis-sqrt-stream n))) requires two evaluations of (stream-cdr (louis-sqrt-stream n)): one as the argument to stream-cdr and one in the course of applying that procedure to its argument. (Memoization is irrelevant here, since the interpreter cannot see that the second application of stream-cdr to (louis-sqrt-stream n) is an application to the "same" object as the first application, due to the way Louis designed his procedure.) Thus one redundant evaluation is performed, on top of the redundancies involved in evaluating (stream-cdr (louis-sqrt-stream n)) twice. In general, to access the (k + 1)th element in the stream (by k + 1 applications of stream-cdr followed by one application of stream-car) requires one more than twice the number of redundant evaluations required to access the kth element. In other words, the number of redundant evaluations grows exponentially with the index of the element accessed. As already hinted, there would not have been further redundancy if our implementation of delay did not use memoization. For as a result of the distinctness of an "external" call to (louis-sqrt-stream n) from its own internal call to (louis-sqrt-stream n), the two calls to (stream-cdr (louis-sqrt-stream n)) made in the course of evaluating (stream-cdr (stream-cdr (louis-sqrt-stream n))), for example, cannot exploit memoization because the interpreter cannot see that stream-cdr is being applied to the "same" object in each case.

 (define (sqrt-stream x)
   (define guesses
     (cons-stream 1.0
                  (stream-map (lambda (guess) (sqrt-improve guess x))
                               guesses)))
   guesses)

Unlike the louis-sqrt-stream procedure, accessing the second element in the stream (sqrt-stream n) by taking the stream-car of (stream-cdr (sqrt-stream n)) does not create an second, internal call to (sqrt-stream n). Instead, evaluation of the (sqrt-stream n) argument passed to stream-cdr merely assigns the guesses variable to a value in the environment. This fact prevents the exponential growth of redundant evaluations observed in Louis's procedure. If, however, our implementation of delay did not use memoization, redundant evaluations would arise in another way. For example, to access the third element in the stream by taking the steam-car of (stream-cdr (stream-cdr (sqrt-stream n))) would require two "full" evaluations of (stream-cdr guesses): one as (a reduction of) the argument passed to stream-cdr and, due to the absence of memoization, another one in the course of evaluating the application of that procedure to its argument. In general, without the memoization optimization of delay, accessing the (k + 2)th element in the stream would require one more than twice the number of redundant evaluations required to access the (k + 1)th element. In other words, the number of redundant evaluations would grow exponentially with the index of the element accessed -- in the same way that Louis's procedure already does notwithstanding memoization.