3.5.2 Infinite Streams

We have seen how to support the illusion of manipulating streams as complete

entities even though, in actuality, we compute only as much of the stream as we

need to access. We can exploit this technique to represent sequences

efficiently as streams, even if the sequences are very long. What is more

striking, we can use streams to represent sequences that are infinitely long.

For instance, consider the following definition of the stream of positive

integers:

我们已经了解了如何支持将流作为完整实体来操作的幻觉——尽管实际上我们只计算了访问所需的那部分流。我们可以利用这一技术将序列高效地表示为流，即使序列非常长也不例外。更令人惊叹的是，我们可以用流来表示无穷长的序列。例如，考虑下面对正整数流的定义：

This makes sense because integers will be a pair whose car is 1

and whose cdr is a promise to produce the integers beginning with 2.

This is an infinitely long stream, but in any given time we can examine only a

finite portion of it. Thus, our programs will never know that the entire

infinite stream is not there.

这是合理的，因为 integers 将是一个序对，其 car 为 1，其 cdr 是一个承诺：产生从 2 开始的整数。这是一个无穷长的流，但在任何给定时刻我们只能检查它的有限部分。因此，我们的程序永远不会知道整个无限流并不在那里。

Using integers we can define other infinite streams, such as the stream

of integers that are not divisible by 7:

利用 integers，我们可以定义其他的无限流，例如不能被 7 整除的整数流：

Then we can find integers not divisible by 7 simply by accessing elements of

this stream:

然后我们只需访问这个流的元素，就可以找到不能被 7 整除的整数：

In analogy with integers, we can define the infinite stream of Fibonacci

numbers:

类比于 integers，我们可以定义无限的 Fibonacci 数流：

Fibs is a pair whose car is 0 and whose cdr is a promise

to evaluate (fibgen 1 1). When we evaluate this delayed (fibgen 1

1), it will produce a pair whose car is 1 and whose cdr is a

promise to evaluate (fibgen 1 2), and so on.

fibs 是一个序对，其 car 为 0，其 cdr 是对 `(fibgen 1 1)` 求值的承诺。当我们对这个延迟的 `(fibgen 1 1)` 求值时，它将产生一个序对，其 car 为 1，其 cdr 是对 `(fibgen 1 2)` 求值的承诺，如此递推下去。

For a look at a more exciting infinite stream, we can generalize the

no-sevens example to construct the infinite stream of prime numbers,

using a method known as the

sieve of Eratosthenes.

We start with the integers beginning with 2, which is the first prime. To get

the rest of the primes, we start by filtering the multiples of 2 from the rest

of the integers. This leaves a stream beginning with 3, which is the next

prime. Now we filter the multiples of 3 from the rest of this stream. This

leaves a stream beginning with 5, which is the next prime, and so on. In other

words, we construct the primes by a sieving process, described as follows: To

sieve a stream S, form a stream whose first element is the first element

of S and the rest of which is obtained by filtering all multiples of the

first element of S out of the rest of S and sieving the

result. This process is readily described in terms of stream operations:

为了看到一个更令人兴奋的无限流，我们可以将"无七倍数"的例子加以推广，用一种称为埃拉托色尼筛法 (sieve of Eratosthenes) 的方法构造无限的素数流。我们从 2 开始，2 是第一个素数。为了得到其余的素数，我们先从其余整数中过滤掉 2 的倍数，留下以 3 开头的流，3 是下一个素数。然后从该流的其余部分中过滤掉 3 的倍数，留下以 5 开头的流，5 是下一个素数，如此继续。换言之，我们通过一个筛选过程来构造素数，该过程描述如下：对流 S 进行筛选，构造一个流，其第一个元素是 S 的第一个元素，其余部分通过从 S 的其余部分中过滤掉 S 第一个元素的所有倍数、并对结果再次筛选而得到。这一过程可以用流操作简洁地描述：

Now to find a particular prime we need only ask for it:

现在，要找到某个特定的素数，只需请求它即可：

It is interesting to contemplate the signal-processing system set up by

sieve, shown in the “Henderson diagram” in

Figure 3.31. The input stream

feeds into an “unconser” that separates the first element of the

stream from the rest of the stream. The first element is used to construct a

divisibility filter, through which the rest is passed, and the output of the

filter is fed to another sieve box. Then the original first element is

consed onto the output of the internal sieve to form the output stream.

Thus, not only is the stream infinite, but the signal processor is also

infinite, because the sieve contains a sieve within it.

Figure 3.31: The prime sieve viewed as a signal-processing system.

Subheading: Defining streams implicitly

图 3.31 中用"Henderson 图"展示了 sieve 所建立的信号处理系统，值得细细玩味。输入流进入一个"拆对器"，将流的第一个元素与流的其余部分分开。第一个元素被用于构造一个整除性过滤器，其余部分经该过滤器过滤后，输出被送入另一个 sieve 盒。然后，原始的第一个元素被 cons 到内部 sieve 的输出上，形成输出流。这样，不仅流是无限的，信号处理器本身也是无限的，因为 sieve 内部包含一个 sieve。

图 3.31：将素数筛视为信号处理系统。

小节标题：隐式定义流

The integers and fibs streams above were defined by specifying

“generating” procedures that explicitly compute the stream elements one by

one. An alternative way to specify streams is to take advantage of delayed

evaluation to define streams implicitly. For example, the following expression

defines the stream ones to be an infinite stream of ones:

上面的 integers 流和 fibs 流是通过指定"生成"过程来定义的，这些过程逐个显式地计算流的元素。指定流的另一种方式是利用延迟求值来隐式地定义流。例如，下面的表达式将流 ones 定义为一个无限的全 1 流：

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 是一个序对，其 car 为 1，其 cdr 是对 ones 求值的承诺。对 cdr 求值，我们再次得到 1 和一个对 ones 求值的承诺，如此反复。

We can do more interesting things by manipulating streams with operations such

as add-streams, which produces the elementwise sum of two given

streams:

通过用 add-streams 之类的操作对流进行处理，我们可以做更有趣的事情。add-streams 产生两个给定流的逐元素之和：

Now we can define the integers as follows:

现在我们可以如下定义 integers：

This defines integers to be a stream whose first element is 1 and the

rest of which is the sum of ones and integers. Thus, the second

element of integers is 1 plus the first element of integers, or

2; the third element of integers is 1 plus the second element of

integers, or 3; and so on. This definition works because, at any point,

enough of the integers stream has been generated so that we can feed it

back into the definition to produce the next integer.

We can define the Fibonacci numbers in the same style:

这将 integers 定义为一个流，其第一个元素为 1，其余部分是 ones 与 integers 的逐元素之和。因此，integers 的第二个元素是 1 加上 integers 的第一个元素，即 2；integers 的第三个元素是 1 加上 integers 的第二个元素，即 3；依此类推。这个定义之所以有效，是因为在任何时刻，integers 流都已生成了足够多的元素，可以反馈给定义来产生下一个整数。我们也可以用同样的风格定义 Fibonacci 数：

This definition says that fibs is a stream beginning with 0 and 1, such

that the rest of the stream can be generated by adding fibs to itself

shifted by one place:

这个定义表明，fibs 是一个以 0 和 1 开头的流，其余部分可以通过将 fibs 与自身错位一位后相加来生成：

Scale-stream is another useful procedure in formulating such stream

definitions. This multiplies each item in a stream by a given constant:

scale-stream 是在表述此类流定义时另一个有用的过程，它将流中的每个元素乘以给定的常数：

For example,

例如，

produces the stream of powers of 2: 1, 2, 4, 8, 16, 32, ….

产生 2 的幂次流：1, 2, 4, 8, 16, 32, ……

An alternate definition of the stream of primes can be given by starting with

the integers and filtering them by testing for primality. We will need the

first prime, 2, to get started:

素数流还有另一种定义方式：从整数流出发，通过检验素性对其进行过滤。我们需要第一个素数 2 来启动这一过程：

This definition is not so straightforward as it appears, because we will test

whether a number n is prime by checking whether n is divisible by a

prime (not by just any integer) less than or equal to n:

这个定义并不像看起来那么直白，因为我们检验一个数 n 是否为素数的方法，是检查 n 能否被某个小于或等于 n 的素数（而非任意整数）整除：

This is a recursive definition, since primes is defined in terms of the

prime? predicate, which itself uses the primes stream. The

reason this procedure works is that, at any point, enough of the primes

stream has been generated to test the primality of the numbers we need to check

next. That is, for every n we test for primality, either n is not

prime (in which case there is a prime already generated that divides it) or

n is prime (in which case there is a prime already generated—i.e., a

prime less than n—that is greater than

n).

这是一个递归定义，因为 primes 的定义依赖于谓词 prime?，而 prime? 本身又用到了 primes 流。这个过程之所以能正常工作，是因为在任何时刻，primes 流都已生成了足够多的素数，可以用来检验接下来需要检验的数的素性。也就是说，对于我们检验素性的每个 n，要么 n 不是素数（此时已有一个生成的素数能整除它），要么 n 是素数（此时已有一个生成的素数——即某个小于 n 的素数——大于 n）。