3.5.3 Exploiting the Stream Paradigm

Streams with delayed evaluation can be a powerful modeling tool, providing many

of the benefits of local state and assignment. Moreover, they avoid some of

the theoretical tangles that accompany the introduction of assignment into a

programming language.

带有延迟求值的流可以成为一种强大的建模工具，它提供了局部状态与赋值的诸多优点，同时也规避了将赋值引入程序设计语言时所伴随的一些理论困境。

The stream approach can be illuminating because it allows us to build systems

with different module boundaries than systems organized around assignment to

state variables. For example, we can think of an entire time series (or

signal) as a focus of interest, rather than the values of the state variables

at individual moments. This makes it convenient to combine and compare

components of state from different moments.

Subheading: Formulating iterations as stream processes

流的方式之所以具有启发性，在于它允许我们以不同于围绕状态变量赋值所组织的系统的模块边界来构建系统。例如，我们可以将整条时间序列（或信号）作为关注的焦点，而不是将注意力放在各个时刻状态变量的取值上。这使得组合与比较来自不同时刻的状态分量变得十分方便。

小节标题：将迭代表述为流的计算过程

In section 1.2.1, we introduced iterative processes, which proceed by

updating state variables. We know now that we can represent state as a

“timeless” stream of values rather than as a set of variables to be updated.

Let’s adopt this perspective in revisiting the square-root procedure from

1.1.7. Recall that the idea is to generate a sequence of better

and better guesses for the square root of x by applying over and over again

the procedure that improves guesses:

在 1.2.1 节中，我们介绍了迭代型计算过程——它通过不断更新状态变量向前推进。现在我们知道，可以将状态表示为一个"无时间性"的值的流，而不必将其表示为一组待更新的变量。让我们带着这一视角重新审视 1.1.7 节中的求平方根过程。回想一下，其思路是通过反复应用改进猜测值的过程，生成一个对 x 的平方根越来越精确的猜测序列：

In our original sqrt procedure, we made these guesses be the successive

values of a state variable. Instead we can generate the infinite stream of

guesses, starting with an initial guess of 1:

在我们原来的 sqrt 过程中，这些猜测值被表示为某个状态变量的相继取值。现在，我们可以改为生成猜测值的无穷流，以初始猜测 1 作为起点：

We can generate more and more terms of the stream to get better and better

guesses. If we like, we can write a procedure that keeps generating terms

until the answer is good enough. (See Exercise 3.64.)

我们可以不断生成这条流的更多项，从而得到越来越精确的猜测值。如有需要，还可以编写一个过程，让它持续生成各项，直到结果足够精确为止。（参见练习 3.64。）

Another iteration that we can treat in the same way is to generate an

approximation to π, based upon the alternating series that we saw in

1.3.1:

π

4

另一个可以用同样方式处理的迭代，是基于我们在 1.3.1 节见过的交错级数来生成 π 的近似值：

π

4

=

1
−

1
3

+

1
5

−

1
7

+

…

.

We first generate the stream of summands of the series (the reciprocals of the

odd integers, with alternating signs). Then we take the stream of sums of more

and more terms (using the partial-sums procedure of Exercise 3.55)

and scale the result by 4:

…

.

我们首先生成该级数各被加项的流（即奇数的倒数，符号交替变换）。然后利用练习 3.55 中的 partial-sums 过程，取出前缀和组成的流，再将结果乘以 4：

This gives us a stream of better and better approximations to π,

although the approximations converge rather slowly. Eight terms of the

sequence bound the value of π between 3.284 and 3.017.

这给了我们一条对 π 越来越精确的近似值的流，尽管这些近似值的收敛相当缓慢。序列的前八项将 π 的值界定在 3.284 与 3.017 之间。

So far, our use of the stream of states approach is not much different from

updating state variables. But streams give us an opportunity to do some

interesting tricks. For example, we can transform a stream with a

迄今为止，我们对状态流方式的运用与更新状态变量并无太大区别。但流为我们提供了施展一些有趣技巧的机会。例如，我们可以用一个

sequence accelerator that converts a sequence of approximations to a

new sequence that converges to the same value as the original, only faster.

序列加速器 (sequence accelerator) 来变换一条流——它将一个近似值序列转换为一个新序列，该新序列收敛到与原序列相同的值，但速度更快。

One such accelerator, due to the eighteenth-century Swiss mathematician

Leonhard Euler, works well with sequences that are partial sums of alternating

series (series of terms with alternating signs). In Euler’s technique, if

S

n is the n

其中一种加速器由十八世纪瑞士数学家莱昂哈德·欧拉提出，它对交错级数（各项符号交替变换的级数）的部分和序列效果尤佳。在欧拉的技术中，若 S

n 是原部分和序列的第 n 项，则

th term of the original sum sequence, then the

accelerated sequence has terms

S

加速后的序列的各项为

S

n
+
1

−

(

S

n
+
1

−

S
n

)
2

S

n
−
1

−
2

S
n

+

S

n
+
1

.

Thus, if the original sequence is represented as a stream of values, the

transformed sequence is given by

.

因此，若原序列被表示为一条值的流，则变换后的序列由以下代码给出：

We can demonstrate Euler acceleration with our sequence of approximations to

π:

我们可以用对 π 的近似值序列来演示欧拉加速：

Even better, we can accelerate the accelerated sequence, and recursively

accelerate that, and so on. Namely, we create a stream of streams (a structure

we’ll call a

tableau) in which each stream is the transform of the

preceding one:

更进一步，我们可以对已加速的序列再次加速，再递归地对其加速，如此往复。也就是说，我们构造一个由流组成的流（我们将这种结构称为

tableau），其中每条流都是前一条流经过变换后的结果：

The tableau has the form

s

该 tableau 的形式为

s

00

s

01

s

02

s

03

s

04

…

s

10

s

11

s

12

s

13

…

s

20

s

21

s

22

…

…

Finally, we form a sequence by taking the first term in each row of the

tableau:

……

最后，我们从表格每一行中取出第一项，构成一个新序列：

We can demonstrate this kind of “super-acceleration” of the π

sequence:

我们可以演示这种对 π 序列的"超级加速"：

The result is impressive. Taking eight terms of the sequence yields the

correct value of π to 14 decimal places. If we had used only the

original π sequence, we would need to compute on the order of 10

结果令人印象深刻。取序列的八项，便能得到精确到小数点后 14 位的 π 值。若直接使用原始的 π 序列，则需要计算大约 10

13

terms (i.e., expanding the series far enough so that the individual terms are

less than 10

13

项（即展开级数，直至每一项都小于 10

−

13) to get that much accuracy!

−

13）才能达到同样的精度！

We could have implemented these acceleration techniques without using streams.

But the stream formulation is particularly elegant and convenient because the

entire sequence of states is available to us as a data structure that can be

manipulated with a uniform set of operations.

这些加速技术完全可以不借助流来实现。但流的表述方式格外优雅、方便，因为整个状态序列作为一个数据结构全程可用，可以用一套统一的操作加以处理。