SICP 全笔记

Exercise 3.52. Consider the sequence of expressions

(define sum 0)
(define (accum x)
  (set! sum (+ x sum))
  sum)
(define seq (stream-map accum (stream-enumerate-interval 1 20)))
(define y (stream-filter even? seq))
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
(stream-ref y 7)
(display-stream z)

What is the value of sum after each of the above expressions is evaluated? What is the printed response to evaluating the stream-ref and display-stream expressions? Would these responses differ if we had implemented (delay <exp>) simply as (lambda () <exp>) without using the optimization provided by memo-proc ? Explain.

sum 的值

有了之前对 stream-mapstream-enumerate-interval 的理解,我们知道 stream-map 第一次实际只对第一个元素进行计算,之后的元素都放到 delay 中。下面是依次计算的结果:

  1. seq 为 (1 . #[promise])stream-enumerate-interval 产生的序列是 (1),此时 sum 为 1。
  2. y 为 (6 . #[promise])stream-enumerate-interval 产生的序列是 (1 2 3),此时 sum 为 6,
  3. z 为 (10 . #[promise])stream-enumerate-interval 产生的序列是 (1 2 3 4) ,此时的 sum 为 10。
  4. 运行至 (stream-ref y 7)stream-enumerate-interval 将会产生序列 (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16),sum 为其和 130
  5. (display-stream z)stream-enumerate-interval 将会产生 1-20 的数字,sum 为其总和。打印的数字为
10
15
45
55
105
120
190
210

因为我们的解释器对 force 使用了优化,所以,每次求值都不会让 stream 从头开始求,使得 sum 值与数列前 n 项和一直一致。

假如我们的 force 过程没有优化,那么结果会不一样。看下面的代码。(注意 **特殊过程** delay-1 的实现,必须使用宏)

;; cons-stream implementation

(define-syntax delay-1
  (syntax-rules ()
    ((delay-1 x)
     (lambda () x))))

(define (force-1 delayed)
  (delayed))

(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force-1 (cdr stream)))

(define-syntax cons-stream
  (syntax-rules ()
    ((cons-stream a b)
     (cons a (delay-1 b)))))

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons-stream (proc (stream-car s))
                   (stream-map proc (stream-cdr s)))))

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin
        (proc (stream-car s))
        (stream-for-each proc (stream-cdr s)))))

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (newline)
  (display x))

(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))

(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))


(define sum 0)

(define (accum x)
  (set! sum (+ x sum))
  sum)

(define seq (stream-map accum (stream-enumerate-interval 1 20)))
; seq: (1 . procedure)
; sum: 1

(define y (stream-filter even? seq))
; seq: (1 . procedure)
; sum: 6
;   y: (6 . procedure)

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))
; seq: (1 . procedure)
; sum: 15
;   z: (15 . procedure)

(stream-ref y 7)
; => 162
; seq: (1 . procedure)
; sum: 162


(display-stream z)
; seq: (1 . procedure)
;15
;180
;230
;305


从 z 开始和之前不一样,因为 seq 永远都是从 1 开始的。下一个数字为 (sum + x)。在 z 求值的时候,sum = 6,seq 序列将循环地得到 (1, (6) + 2, (6 + 2) + 3, (6 + 2 + 3) + 4 ...) 第一个5的除数则为 15,后续计算被 delay。所以 z 为 (15 . procedure)