SICP第3.5.2章无限流整数定义

Question

我正在阅读 SICP，但很难理解为无限流提供的一个示例：

https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-24.html#%_sec_3.5.2

We can do more interesting things by manipulating streams with operations such as add-streams, which produces the elementwise sum of two given streams:62

(define (add-streams s1 s2)
  (stream-map + s1 s2))

Now we can define the integers as follows:

(define integers (cons-stream 1 (add-streams ones integers)))

我显然可以理解 integers 定义背后的意图，但我正在努力 "simulate" 我脑海中的这个流。之前的例子不是问题，因为状态的维护是明确的。比如在这个例子中：

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))

我理解这个整数的定义没问题。

书中描述了ones的定义：

(define ones (cons-stream 1 ones))

This works much like the definition of a recursive procedure: ones is a pair whose car is 1 and whose cdr is a promise to evaluate ones. Evaluating the cdr gives us again a 1 and a promise to evaluate ones, and so on.

也许这条线让我失望了。 Ones 很简单，因为在每个 stream-cdr 上都会评估过程并提供新的“1”和下一个承诺。

当我尝试将此推理应用于 integers 时，我很难理解为什么结果流不是“1 2 2 2 2 2 ...”，因为整数会不断重新计算基本上从 1 点重新开始。

编辑我没有详细说明在我的问题中是否假设了记忆是我的疏忽。 SICP 确实提到了答案中提出的二次行为问题，并以记忆 delay 函数的形式提供了解决方案：

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))

Delay is then defined so that (delay ) is equivalent to

(memo-proc (lambda () <exp>))

Answer 1

参见foot note 56。

cons-stream must be a special form. If cons-stream were a procedure, then, according to our model of evaluation, evaluating (cons-stream <a> <b>) would automatically cause <b> to be evaluated, which is precisely what we do not want to happen.

Answer 2

我在这里遗漏的一点是 integers 根本没有被重新评估。 add-streams returns 的承诺是每个输入流的 stream-cdr。前面提到的"state"在反馈回路中保持。
它非常令人费解，老实说，它的力量似乎仍然很神奇。

Answer 3

如果我们的流被记忆化，那么作为参数传递给 add-streams 的 integers 总是 "one step behind" 我们正在枚举的 integers，所以它总是可以访问到记忆值。 (parens) 中的数字显示记忆值的使用：

Integers: 1, add-streams /    Ones: 1,     1,     1,     1,     1,     1,  ...
                         \Integers: 1,    (2),   (3),   (4),   (5),   (6), ...
                                   ===    ===    ===    ===    ===    ===
Results:  1                         2,     3,     4,     5,     6,     7,  ...

Memoized:                           2,     3,     4,     5,     6,

如果我们的流没有被记忆，那么每次在 integers 上调用 stream-cdr 时，都会创建一个新的 ones 系列，并将其添加到之前的所有 ones 中。

integers                          1
    ones                              1,  1,  1,  1,  1,  1,  ...
    integers                          1
        ones                              1,  1,  1,  1,  1,  ...
        integers                          1
            ones                              1,  1,  1,  1,  ...
            integers                          1
                ones                              1,  1,  1,  ...
                integers                          1
                    ones                              1,  1,  ...
                    integers                          1
                        ones                              1,  ...
                        integers                          1
                                 ==  ==  ==  ==  ==  ==  ==  
                                  1,  2,  3,  4,  5,  6,  7,  ...

所以 100 是通过将 ones 的元素相加 99 次和 integers 的 stream-car 生成的，后者是前 99 次调用 integers.

尽管第一个 add-streams 仅组合两个流，但第二个流将（在返回 1 之后）返回新 add-streams 的结果，其中第二个流将be 将是另一个 add-streams:

的结果

1, add-streams / 1,               1,               1, ...
               \ 1, add-streams / 1,               1, ...
                                \ 1, add-streams / 1, ...
                                                 \ 1, add-streams ...

所以 add-streams，有点像使用 cons 创建列表，正在创建成对的流，其中第一个是 1 的流，第二个是另一对流。

如果不记忆，这不是 integers 的实际实现，因为它的性能是 O(n^2):

Time to Access Elements

Element of    CPU Time
 integers      (msec)
==========    ========
      1 st           0
      2 nd           0
      4 th           0
      8 th           0
     16 th           0
     32 nd          47
     64 th          78
    128 th         313
    256 th       1,171
    512 th       4,500
  1,024 th      17,688
  2,048 th      66,609
  4,096 th     272,531

Answer 4

使用最简单的非记忆化流实现，我们得到：

(define (stream-map2 f s1 s2)
  (cons (f (car s1) (car s2)) 
    (lambda ()
      (stream-map2 f ((cdr s1)) ((cdr s2))))))

(define ones (cons 1 (lambda () ones)))

(define integers
    (cons 1 
      (lambda ()
        (stream-map2 + ones integers)))       ;; 1
  = 
    (cons 1 
      (lambda () 
        (cons (+ (car ones) (car integers))
          (lambda () 
            (stream-map2 + ones 
              (stream-map2 + ones integers))))))      ;; 2
  =
    (cons 1 
      (lambda () 
        (cons (+ (car ones) (car integers))
          (lambda () 
            (let ((i2 (stream-map2 + ones integers)))
              (stream-map2 + ones i2))))))

即

  = 
    (cons 1 
      (lambda () 
        (cons (+ (car ones) (car integers))
          (lambda () 
            (let ((i2 (cons (+ (car ones) (car integers))   ;; <---- 1
                        (lambda () 
                          (stream-map2 + ones 
                            (stream-map2 + ones integers))))))
              (cons (+ (car ones) (car i2))
                (lambda ()
                  (stream-map2 + ones ((cdr i2))))))))))
  = 
    (cons 1 
      (lambda () 
        (cons (+ (car ones) (car integers))
          (lambda () 
            (cons (+ (car ones) 
                     (+ (car ones) (car integers)))
              (lambda ()
                (stream-map2 + ones 
                  (stream-map2 + ones 
                    (stream-map2 + ones integers)))))))))     ;; 3
  =
    ....

我们确实看到了一个三角形，二次计算在这里展开。

SICP第3.5.2章无限流整数定义

SICP Chapter 3.5.2 infinite streams integers definition

stream

scheme

infinite

sicp

lazy-sequences