流

Streams.

We obviously cannot create such a sequence explicitly as it would literally take forever, but with delayed evaluation we can create the code that knows how to produce the infinite sequence.

stream 是以 thunk 的形式表示的，当调用该 thunk 时将返回一个 pair <val, next-thunk>。其中，val 为序列中当前元素的值，而 next-thunk 为接下来的元素序列形成的 stream。

无限序列由 cons 单元的嵌套结构表示，cons 单元的 car 与 cdr 分别为当前值与被延时求值的对象 (promise)。序列的后一个 cons 单元通过求值 cdr 部分产生。这个过程不断重复，从而形成无限序列。

Using Streams

powers-of-two 是 Racket 中的一个 built-in stream，它是一个由 2 的幂次方组成的无限值序列。注意 stream 本质上是一个包含 pair 的 thunk；因此在取值之前需要进行调用。

1
2
3
4

> (car (power-of-two))
2
> (car (cdr (power-of-two)))
4

自然的，我们想要定义函数 that operates over streams 来获得某些信息。下面的 number-until 函数将会计算满足条件的元素在给定 stream 中的位置。

1
2
3
4
5
6
7
8
9
10

(define (number-until stream tester)
  (letrec ([f (lambda (stream ans)
                (let ([pr (stream)])
                  (if (tester (car pr))
                      ans
                      (f (cdr pr) (+ ans 1)))))])
    (f stream 1)))

> (number-until powers-of-two (lambda (x) (= x 16)))
4

Defining Streams

按照 stream 的定义，我们尝试定义一个无限长的全 1 序列。

1

(define ones (lambda () (cons 1 (lambda () (cons 1 ...)))))) ; infinite def. (not realistic)

这是一种朴素的无限定义；但我们能够很容易发现其中隐藏的递归规律：后面重复的部分就是 ones 本身。

1

(define ones (lambda () (cons 1 ones)))                      ; correct def.

需要注意的是，对 stream 的定义，核心在于利用了延时求值 (delayed evaluation) 的 idiom。使用定义本身来进行定义，这被称作递归定义 (recursive definition)。递归定义的完整性需要借助延时求值来保证。

例如在上述定义中，我们在对 ones 的定义中使用了 ones 本身，但由于 thunk 的存在，主体部分的求值过程被延迟了，这保证了递归定义的完整性。如果不这样做的话 (见下例)：

1
2
3

(define ones (cons 1 ones))                                  ; wrong def.

> ones: undefined. cannot reference an identifier before its definition

由于没有 thunk 来对 ones 定义的主体部分的求值过程进行延迟，程序在定义 ones 的过程将立即对主体部分的递归定义进行求值，但它将会发现 ones 的定义并未完成，于是 undefined 错误将会产生。

接下来我们尝试自己定义一个 powers-of-two:

1
2
3

(define powers-of-two
  (letrec ([f (lambda (x) (cons x (lambda () (f (* x 2))))])
              (lambda () (f 2))))

注意到在 stream 与 stream 操作函数的定义中，我们常常需要一个辅助函数 f。在上例中，辅助函数 f 对于某个参数 x，输出一个 pair <x, thunk>。其中 thunk 包装的是 f 对于参数 2x 计算的结果；那么整个 stream 就可以表示为 (lambda () (f 2))：一个封装 f(2) 的 thunk。

Reference

Course info:

Programming Languages, Part B, University of Washington, Lecturer: Professor Dan Grossman.