SICP 全笔记

Exercise 3.63. Louis Reasoner asks why the sqrt-stream procedure was not written in the following more straightforward way, without the local variable guesses:

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

Alyssa P. Hacker replies that this version of the procedure is considerably less efficient because it performs redundant computation. Explain Alyssa’s answer. Would the two versions still differ in efficiency if our implementation of delay used only (lambda () <exp>) without using the optimization provided by memo-proc (section 3.5.1)?

对比

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

第一个元素

当我们对 (sqrt-stream 2) 取 stream-car 的时候，

使用 local guess 的 (stream-car (cons-stream 1.0 (stream-map f guess)))

使用 (sqrt-stream x) 的 (stream-car (cons-stream 1.0 (stream-map f (sqrt-stream x))))

等价，暂时看不出区别。

第二个元素

当我们求 (sqrt-stream 2) 的第 1 个元素（stream-car 是取第 0 个元素）的时候

使用 local guess 的 (stream-car (stream-map f guess)) 。其中 guess 是 (1 . #[promise]) 。

使用 (sqrt-stream x) 的 (stream-car (stream-map f (sqrt-stream x))) 作为参数的 sqrt-stream 求值之后变为 (1 . #[promise]) 。

差别在 (sqrt-stream x) 多进行了一次调用，但调用之后的结果是一样的。

第三个元素

使用 local guess 的 (stream-car (stream-map f guess)) 。其中 guess 在 stream-map 中已经到了 (1.4166666666666665 . #[promise])

使用 (sqrt-stream x) 的 整个求值过程此时变为了 (stream-car (stream-cdr (stream-cdr (sqrt-stream x)))) 两个 stream-cdr 实际是对 (sqrt-stream x) 的第一个元素进行了两次求 average 的结果，得到了我们看到的 1.4166666666666665。

另外一个理解的角度

我们可以如下来构造一个无限整数流

(define t
  (cons-stream 1
               (stream-map (lambda (g)
                             (begin
                               (display g) (display " ")
                               (+ g 1)))
                           t)))

可以使用这样的方式

(define (t1 x)
  (cons-stream 1
               (stream-map (lambda (g)
                             (begin
                               (display g) (display " ")
                               (+ g x)))
                           (t1 x))))

两者的区别与本题的区别一样：在使用 stream-map 的时候，使用的是一个变量，还是自身过程调用作为参数。

下面我们来依次看看调用的情况

1 ]=> (stream-car t)

;Value: 1

1 ]=> (stream-cdr t)
1
;Value 17: (2 . #[promise 18])

1 ]=> (stream-cdr (stream-cdr t))
2
;Value 19: (3 . #[promise 20])

1 ]=> (stream-cdr (stream-cdr (stream-cdr t)))
3
;Value 21: (4 . #[promise 22])

这里我们可以看到每一次取 t，都只 display 一次 t 的前一个数。

1 ]=> (stream-car (t1 1))

;Value: 1

1 ]=> (stream-cdr (t1 1))
1
;Value 29: (2 . #[promise 30])

1 ]=> (stream-cdr (stream-cdr (t1 1)))
1 1 2
;Value 31: (3 . #[promise 32])

1 ]=> (stream-cdr (stream-cdr (stream-cdr (t1 1))))
1 1 2 1 2 3
;Value 33: (4 . #[promise 34])

这里打印出的 1 1 2 与 1 1 2 1 2 3 是怎么来的呢？从直觉上，我们可能会觉得每一次对 (t1 x) 调用 stream-map 的时候，又从 1 开始进行计算了，为什么还能够得到最后的答案呢？

我们可以使用替代模型来理解：

(t1 1) 实际为：

(cons-stream 1
    (stream-map f ;[promise 1]
        (cons-stream 1
            (stream-map f ; [promise 2]
                (cons-stream 1
                    (stream-map f
                        ....))))))

则求 (stream-cdr (stream-cdr (t1 1))) 时，在 [promise 2] 实际返回 (2 . #[promise])，这里的 2 返回到上一个 stream-map 中的时候又被加了 1，变为了 3。所以得到结果 (3 . #[promise])