自引用流的评估

Question

我在 SICP 讲座系列的讲座 6B 中遇到了以下示例，需要一些帮助来理解它是如何评估的。

示例使用流处理创建大于1的无限整数流：

; utility procedure
(define (add-streams s1 s2)                                     ; Returns a stream containing the element-wise sums of s1 and s2 
  (cond ((empty-stream? s1) s2)                                 ; If either stream is empty, return the non-empty one
        ((empty-stream? s2) s1)
        (else                                                    
         (cons-stream (+ (head s1) (head s2))                   ; Otherwise, return a new stream whose first element is the sum of the heads of s1 and s2
                      (add-streams (tail s1) (tail s2)))))      ; ...and whose tail is the result of recursively adding the streams in the tails of s1 and s2.


(define ones (cons-stream 1                                     ; infinite stream of 1s                              
                              ones))

(define integers (cons-stream 1                                 ; infinite stream of increasing integers, starting from 1                              
                              (add-streams integers ones)))

我知道

integers

是通过增加连续

add-streams

调用返回的流的头部来建立的，但我不太确定我是否理解它是如何评估的。

integers

是所有大于 1 的整数的流，所以我们可以访问这个集合中的第 3 个整数，如下所示：

(head (tail (tail integers)))

最里面的

tail

强制

(add-streams integers ones)

承诺评价：

(add-streams integers ones) ----->  (cons (+ (head integers) (head ones))
                                          (delay (add-streams (tail integers) (tail ones))))
                            
                            ----->  (cons 2
                                          (delay (add-streams (tail integers) (tail ones))))

外部

tail

调用然后强制

(add-streams (tail integers) (tail ones))

承诺评估：

(add-streams (tail integers)
             (tail ones))       -----> (add-streams (cons 2 (delay ...))
                                                    (cons 1 (delay ...)))
                                          
                                -----> (cons (+ (head (cons 2 (delay ...)))
                                                (head (cons 1 (delay ...))))
                                             (delay (add-streams (tail (cons 2 (delay ...)))
                                                                 (tail (cons 1 (delay ...))))))
                                    
                                -----> (cons 3
                                             (delay (add-streams (cons 3 (delay ...))
                                                                 (cons 1 (delay ...)))))

当我们调用 head 调用外部

tail

调用的结果时，我们得到 3，这是预期的答案。

但是，我不确定我是否正确评估了这一点。我特别不确定第二个缩减步骤中显示的

(tail integers)

调用。我在第三步减少到

(add-streams (cons 2 (delay ...)) (cons 1 (delay ...)))

，这是正确的吗？

Answer 1

我认为你对发生的事情的总结是正确的。然而，我也认为最好的思考方式是两件事之一。第一个可能没有第二个有用，这就是为什么我把它放在第一位。

要么 (1) 考虑事物的语义，不要太担心评估。

在这种情况下，正确的思考方式是：

• the stream of ones 是头是

  1

  尾巴是ones 的流;
• 自然数流（不是整数：没有有序的整数流！（为什么？））是头部为

  0

  （或

  1

  ，如果你想让你的自然数从

  1

  开始）的流其尾部是整数流，每个整数都加上了

  1

  。

或者 (2)，写一个流的实现，然后你可以说服它告诉你发生了什么。

下面是这样一个实现。我很抱歉这是用 Racket 写的，而不是纯 Scheme。在这个实现中，

delay

被称为

postpone

，而

force

被称为

ensure

：这样做是为了与这些东西的任何本地实现并驾齐驱。您可以控制：

• 流是否在确保时报告正在发生的事情；
• 流是否记住被确保的结果。

特别注意，流 not 表示为conses：它们表示为过程。所以 cons 和流之间没有双关语：流是完全不同的东西。还要注意

cons-stream

推迟both它的论点。

(define ensure-reports
  ;; Do streams report when being ensured
  (make-parameter #t))

(define ensure-memoizes
  ;; Do streams memoize their values
 (make-parameter #t))

(define-syntax postpone
  ;; postpone is delay
  (syntax-rules ()
    [(_ form)
     (let ([ensured #f]
           [value #f])
       (thunk
        (cond
          [ensured
           (when (ensure-reports)
             (eprintf "[~S is ~S]~%" 'form value))
           value]
          [else
           (let ([v form])
             (when (ensure-reports)
               (eprintf "[~S to ~S]~%" 'form v))
             (when (ensure-memoizes)
               (set! value v)
               (set! ensured #t))
             v)])))]))

(define (ensure postponed)
  ;; ensure is force
  (postponed))

(define-syntax cons-stream
  (syntax-rules ()
    [(_ head-form tail-form)
     (let ([h (postpone head-form)]
           [t (postpone tail-form)])
       (λ (k)
         (case k
           [(head)
            (ensure h)]
           [(tail)
            (ensure t)]
           [(null-stream?)
            #f]
           [else
            (error 'cons-stream "what?")])))]))

(define (head s)
  (s 'head))

(define (tail s)
  (s 'tail))

(define null-stream
  ;; A null stream is a stream whose head and tail are itself and which
  ;; knows it is null.  This is like NIL / () in CL but unlike () in Scheme.
  (λ (k)
    (case k
      [(head) null-stream]
      [(tail) null-stream]
      [(null-stream?) #t]
      [else
       (error 'null-stream "what?")])))

(define (null-stream? s)
  (s 'null-stream?))

(define (stream-nth n stream)
  ;; nth element of a stream
  (unless (>= n 0)
    (error 'stream-nth "negative creep"))
  (let snl ([m n]
            [s stream])
    (cond
      [(null-stream? s)
       (error 'stream-nth "out of stream")]
      [(zero? m)
       (head s)]
      [else
       (snl (- m 1) (tail s))])))

(define-syntax list-stream
  ;; like list but for streams
  (syntax-rules ()
    [(_)
     null-stream]
    [(_ h more ...)
     (cons-stream h (list-stream more ...))]))

(define (stream-to-list stream)
  ;; finite stream to list of elements
  (let sll ([s stream]
            [a '()])
    (if (null-stream? s)
        (reverse a)
        (sll (tail s)
             (cons (head s) a)))))

鉴于此我们可以写

add-streams

，只是从问题中稍微重命名一些东西：

(define (add-streams s1 s2)
  (cond [(null-stream? s1) s2]
        [(null-stream? s2) s1]
        [else
         (cons-stream (+ (head s1) (head s2))
                      (add-streams (tail s1) (tail s2)))]))

现在定义

ones

和

naturals

（同样，不是

integers

）：

(define ones
  (cons-stream 1 ones))

(define naturals
  (cons-stream 0 (add-streams naturals ones)))

现在，终于，你可以得到它来告诉你发生了什么：

> (head (tail (tail naturals)))
[(add-streams naturals ones) to #<procedure>]
[(add-streams naturals ones) is #<procedure>]
[ones to #<procedure:ones>]
[(add-streams (tail s1) (tail s2)) to #<procedure>]
[0 to 0]
[1 to 1]
[(+ (head s1) (head s2)) to 1]
[1 is 1]
[(+ (head s1) (head s2)) to 2]
2

Answer 2

SICP 流具有

(stream-cons a b) == (cons a (delay b))

。我不确定作者是否展示了实际的

delay

实现，但在 Scheme 中它正在记忆——它创建一个 promise 作为内存结构（对象）计算值并在第一次访问时存储它，并在每次后续访问时直接返回它。

因此，SICP 流表示为一个

cons

对，其

car

字段包含现成的值，而

cdr

字段包含记忆承诺：

(define (head s) (car s))

(define (tail s) (force (cdr s)))

force

的定义使其能够识别已经强制执行的承诺，并且在这种情况下只会返回存储的值。

那么，我们有：

(define ones (cons 1 (delay ones)))

;; ones :=> <1 . {promise1 DELAYED (thunk ones)}> 
;;          -- pseudocode representation of a memory object

让我们从 10 开始整数，这样更容易理解下面的冗长代码清单：

(define ints (cons 10 (delay (add-streams ints ones))))

;; ints :=> <10 . {promise2 DELAYED (thunk (add-streams ints ones))}>
;;          -- pseudocode representation of a memory object

所以第一个

tail

应用于

ones

力

ones

的

cdr

从而改变 ones

 所指结构的内容

为

ones :=> <1 . {promise1 FORCED ones}>

（象征性地）。

现在，它是这样的：

(head (tail (tail ints)))
= ;1           ; pseudocode .......
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}> ]
       [ints :=> <10 . {promise2 DELAYED (thunk (add-streams ints ones))}>]
       [b  (tail ints)]
       [a  (tail b)])
  (head a))
= ;2
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}> ]
       [ints :=> <10 . {promise2 DELAYED (thunk (add-streams ints ones))}>]
       [b  (tail ints)]
       [a  (force (cdr b))])
  (head a))
= ;3
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}> ]
       [ints :=> <10 . {promise2 DELAYED (thunk (add-streams ints ones))}>]
       [b  (force (cdr ints))]
       [a  (force (cdr b))])
  (head a))
= ;4
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED c}>]
       [c  (add-streams ints ones)]
       [b  (force (cdr ints))]
       [a  (force (cdr b))])
  (head a))
= ;5
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED c}>]
       [h1 (head ints)]
       [h2 (head ones)]
       [c (cons (+ h1 h2) (delay
                (add-streams (tail ints) (tail ones))))]
       [b  c]
       [a  (force (cdr b))])
  (head a))
= ;6
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED c}>]
       [c    :=> <11 . {promise3 DELAYED (thunk 
                         (add-streams (tail ints) (tail ones)))}>]
       [b  c]
       [a  (force (cdr b))])
  (head a))
= ;7
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 DELAYED (thunk 
                         (add-streams (tail ints) (tail ones)))}>]
       [a  (force (cdr b))])
  (head a))
= ;8
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED d}>]
       [d  (add-streams (tail ints) (tail ones))]
       [a  (force (cdr b))])
  (head a))
= ;9
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED d}>]
       [d  (add-streams (tail ints) (tail ones))]
       [a  d])
  (head a))
= ;10
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [s1  (tail ints)]
       [s2  (tail ones)]
       [a  (add-streams s1 s2)])
  (head a))
= ;11
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [s1  (force (cdr ints))]
       [s2  (force (cdr ones))]
       [a  (add-streams s1 s2)])
  (head a))
= ;12
(letrec
      ([ones :=> <1 . {promise1 DELAYED (thunk ones)}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [s1  b]
       [s2  (force (cdr ones))]
       [a  (add-streams s1 s2)])
  (head a))
= ;13
(letrec
      ([ones :=> <1 . {promise1 FORCED ones}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [s2  (force (cdr ones))]
       [a  (add-streams b s2)])
  (head a))

继续，

= ;14
(letrec
      ([ones :=> <1 . {promise1 FORCED ones}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [s2  ones]
       [a  (add-streams b s2)])
  (head a))
= ;15
(letrec
      ([ones :=> <1 . {promise1 FORCED ones}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [a  (add-streams b ones)])
  (head a))
= ;16
(letrec
      ([ones :=> <1 . {promise1 FORCED ones}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [a    :=> <12 . {promise4 DELAYED (thunk
                         (add-streams (tail b) (tail ones)))}>])
  (head a))
= ;17
(letrec
      ([ones :=> <1 . {promise1 FORCED ones}>]
       [ints :=> <10 . {promise2 FORCED b}>]
       [b    :=> <11 . {promise3 FORCED a}>]
       [a    :=> <12 . {promise4 DELAYED (thunk
                         (add-streams (tail b) (tail ones)))}>])
  (car a))
= ;18
12

希望这足以说明这里发生了什么。

特别是，

ones

的尾巴，一旦被强制，就变成了

ones

本身，并且此后一直如此强制 - 之后没有更多的

delay

了。

以上当然遵循定义

(define (add-streams s1 s2)
  (cond [(null-stream? s1) s2]
        [(null-stream? s2) s1]
        [else
         (cons (+ (head s1) (head s2))
               (delay
                 (add-streams (tail s1) (tail s2))))]))

从上面可以看出，memoizing promise 实现只是表面上的不同，但最终在功能上等同于尾部变异实现，这可以在 this answer 中真正看到，尽管在不同的设置中。

Sylwester 在上面的 comments 中给出了这种尾部变异方法的变体，与这里的 SICP 风格用例相匹配：

(define-syntax cons-stream
  (syntax-rules ()
    ((_ a d)
     (letrec ([pair (cons a 
                       (lambda ()
                          (set-cdr! pair d)
                          (cdr pair)))])
       pair))))

在其下，调用

(head (tail (tail ints)))

结果为

ones ; ==> #0=(1 . #0#)

和

ints ; ==> (10 11 12 . #<procedure>)

.

ones ; ==> #0=(1 . #0#)

字面意思是

ones = <1 . ones>

，这实际上与上面推导中的

<1 . {promise1 FORCED ones}>

相同。