Exercise 3.82 · 习题

Exercise 3.82: Redo Exercise 3.5 on Monte
Carlo integration in terms of streams. The stream version of
estimate-integral will not have an argument telling how many trials to
perform. Instead, it will produce a stream of estimates based on successively
more trials.

A functional-programming view of time

Let us now return to the issues of objects and state that were raised at the
beginning of this chapter and examine them in a new light. We introduced
assignment and mutable objects to provide a mechanism for modular construction
of programs that model systems with state. We constructed computational
objects with local state variables and used assignment to modify these
variables. We modeled the temporal behavior of the objects in the world by the
temporal behavior of the corresponding computational objects.

Now we have seen that streams provide an alternative way to model objects with
local state. We can model a changing quantity, such as the local state of some
object, using a stream that represents the time history of successive states.
In essence, we represent time explicitly, using streams, so that we decouple
time in our simulated world from the sequence of events that take place during
evaluation. Indeed, because of the presence of delay there may be
little relation between simulated time in the model and the order of events
during the evaluation.

In order to contrast these two approaches to modeling, let us reconsider the
implementation of a “withdrawal processor” that monitors the balance in a
bank account. In 3.1.3 we implemented a simplified version of
such a processor:

(define (make-simplified-withdraw balance)
(lambda (amount)
(set! balance (- balance amount))
balance))

Calls to make-simplified-withdraw produce computational objects, each
with a local state variable balance that is decremented by successive
calls to the object. The object takes an amount as an argument and
returns the new balance. We can imagine the user of a bank account typing a
sequence of inputs to such an object and observing the sequence of returned
values shown on a display screen.

Alternatively, we can model a withdrawal processor as a procedure that takes as
input a balance and a stream of amounts to withdraw and produces the stream of
successive balances in the account:

(define (stream-withdraw balance amount-stream)
(cons-stream
balance
(stream-withdraw
(- balance (stream-car amount-stream))
(stream-cdr amount-stream))))

Stream-withdraw implements a well-defined mathematical function whose
output is fully determined by its input. Suppose, however, that the input
amount-stream is the stream of successive values typed by the user and
that the resulting stream of balances is displayed. Then, from the perspective
of the user who is typing values and watching results, the stream process has
the same behavior as the object created by make-simplified-withdraw.
However, with the stream version, there is no assignment, no local state
variable, and consequently none of the theoretical difficulties that we
encountered in 3.1.3. Yet the system has state!

This is really remarkable. Even though stream-withdraw implements a
well-defined mathematical function whose behavior does not change, the user’s
perception here is one of interacting with a system that has a changing state.
One way to resolve this paradox is to realize that it is the user’s temporal
existence that imposes state on the system. If the user could step back from
the interaction and think in terms of streams of balances rather than
individual transactions, the system would appear stateless.

From the point of view of one part of a complex process, the other parts appear
to change with time. They have hidden time-varying local state. If we wish to
write programs that model this kind of natural decomposition in our world (as
we see it from our viewpoint as a part of that world) with structures in our
computer, we make computational objects that are not functional—they must
change with time. We model state with local state variables, and we model the
changes of state with assignments to those variables. By doing this we make
the time of execution of a computation model time in the world that we are part
of, and thus we get “objects” in our computer.

Modeling with objects is powerful and intuitive, largely because this matches
the perception of interacting with a world of which we are part. However, as
we’ve seen repeatedly throughout this chapter, these models raise thorny
problems of constraining the order of events and of synchronizing multiple
processes. The possibility of avoiding these problems has stimulated the
development of
functional programming languages, which do not include
any provision for assignment or mutable data. In such a language, all
procedures implement well-defined mathematical functions of their arguments,
whose behavior does not change. The functional approach is extremely
attractive for dealing with concurrent systems.

On the other hand, if we look closely, we can see time-related problems
creeping into functional models as well. One particularly troublesome area
arises when we wish to design interactive systems, especially ones that model
interactions between independent entities. For instance, consider once more
the implementation of a banking system that permits joint bank accounts. In a
conventional system using assignment and objects, we would model the fact that
Peter and Paul share an account by having both Peter and Paul send their
transaction requests to the same bank-account object, as we saw in
3.1.3. From the stream point of view, where there are no “objects”
per se, we have already indicated that a bank account can be modeled as
a process that operates on a stream of transaction requests to produce a stream
of responses. Accordingly, we could model the fact that Peter and Paul have a
joint bank account by merging Peter’s stream of transaction requests with
Paul’s stream of requests and feeding the result to the bank-account stream
process, as shown in Figure 3.38.

SVG

Figure 3.38: A joint bank account, modeled by merging two streams of transaction requests.

The trouble with this formulation is in the notion of
merge. It will
not do to merge the two streams by simply taking alternately one request from
Peter and one request from Paul. Suppose Paul accesses the account only very
rarely. We could hardly force Peter to wait for Paul to access the account
before he could issue a second transaction. However such a merge is
implemented, it must interleave the two transaction streams in some way that is
constrained by “real time” as perceived by Peter and Paul, in the sense that,
if Peter and Paul meet, they can agree that certain transactions were processed
before the meeting, and other transactions were processed after the
meeting. This
is precisely the same constraint that we had to deal with in
3.4.1, where we found the need to introduce explicit synchronization to
ensure a “correct” order of events in concurrent processing of objects with
state. Thus, in an attempt to support the functional style, the need to merge
inputs from different agents reintroduces the same problems that the functional
style was meant to eliminate.

We began this chapter with the goal of building computational models whose

structure matches our perception of the real world we are trying to model. We

can model the world as a collection of separate, time-bound, interacting

objects with state, or we can model the world as a single, timeless, stateless

unity. Each view has powerful advantages, but neither view alone is completely

satisfactory. A grand unification has yet to emerge.

练习 3.82：用流的方式重做练习 3.5 中的蒙特卡罗积分。流版本的 estimate-integral 不需要一个参数来指定执行多少次试验，而是产生一个基于逐渐增多的试验次数的估计值流。

时间的函数式程序设计观

现在让我们回到本章开头提出的关于对象与状态的问题，从新的角度加以审视。我们引入赋值和可变对象，是为了提供一种机制，以模块化的方式构建对含有状态的系统进行建模的程序。我们构造了带有局部状态变量的计算对象，并用赋值来修改这些变量。我们通过对应计算对象的时间行为来对世界中对象的时间行为建模。

现在我们已经看到，流提供了一种对带有局部状态的对象建模的替代方式。我们可以用一个流来表示某个对象的局部状态，该流表示连续状态的时间历史，从而对一个变化中的量建模。从本质上说，我们用流显式地表示时间，从而将模拟世界中的时间与求值期间发生的事件序列解耦。确实，由于延迟的存在，模型中的模拟时间与求值期间的事件顺序之间可能几乎没有关联。

为了对比这两种建模方式，让我们重新考察一个监控银行账户余额的"取款处理器"的实现。在 3.1.3 中，我们实现了这样一个处理器的简化版本：

(define (make-simplified-withdraw balance)
(lambda (amount)
(set! balance (- balance amount))
balance))

对 make-simplified-withdraw 的调用产生计算对象，每个对象都有一个局部状态变量 balance，该变量被对对象的连续调用所递减。对象以一个金额作为参数并返回新的余额。我们可以想象银行账户的用户向这样的对象键入一系列输入，并在显示屏上观察返回值序列。

另外，我们也可以将取款处理器建模为一个过程，它以一个余额和一个取款金额流作为输入，产生账户中连续余额的流：

(define (stream-withdraw balance amount-stream)
(cons-stream
balance
(stream-withdraw
(- balance (stream-car amount-stream))
(stream-cdr amount-stream))))

Stream-withdraw 实现了一个定义明确的数学函数，其输出完全由其输入决定。然而，假设输入 amount-stream 是用户连续键入的值的流，而产生的余额流被显示出来。那么，从键入值并观察结果的用户的角度来看，流处理过程与 make-simplified-withdraw 创建的对象具有相同的行为。然而，在流版本中，没有赋值，没有局部状态变量，因而也没有我们在 3.1.3 中遇到的那些理论困难。然而这个系统是有状态的！

这确实令人惊叹。尽管 stream-withdraw 实现了一个行为不变的定义明确的数学函数，但用户的感受却是在与一个具有变化状态的系统交互。解开这一悖论的一种方式是认识到：正是用户在时间中的存在把状态强加给了这个系统。如果用户能够跳出这种交互，从余额流而不是单笔交易的角度来思考，系统就会显得是无状态的。

从一个复杂计算过程的某一部分的视角来看，其他部分似乎随时间而变化，它们拥有隐藏的随时间变化的局部状态。如果我们希望编写程序，以计算机中的结构来对我们所在世界中这种自然分解方式建模（正如我们作为该世界的一部分所看到的那样），我们就要创建不具有函数性的计算对象——它们必须随时间变化。我们用局部状态变量对状态建模，用对这些变量的赋值来对状态的改变建模。通过这样做，我们使计算的执行时间对应于我们所处世界中的时间，从而在计算机中得到了"对象"。

用对象建模强大而直观，这在很大程度上是因为它与我们作为世界的一部分与世界交互的感知相吻合。然而，正如我们在本章中反复看到的，这些模型引发了约束事件顺序和同步多个计算过程的棘手问题。回避这些问题的可能性促进了函数式程序设计语言 (functional programming languages) 的发展，这类语言不包含任何赋值或可变数据的机制。在这样的语言中，所有过程都实现定义明确的参数数学函数，其行为不会改变。函数式方法对于处理并发系统极具吸引力。

另一方面，如果我们仔细审视，也会发现与时间相关的问题正悄然渗入函数式模型。一个特别棘手的领域出现在我们希望设计交互式系统时，尤其是那些对独立实体之间交互建模的系统。例如，再次考虑允许联名银行账户的银行系统的实现。在使用赋值和对象的传统系统中，我们通过让 Peter 和 Paul 都向同一个银行账户对象发送交易请求，来对 Peter 和 Paul 共享账户这一事实建模，正如我们在 3.1.3 中所见。从流的观点来看，其中没有严格意义上的"对象"，我们已经指出银行账户可以被建模为一个计算过程，它作用于交易请求流以产生响应流。因此，我们可以通过将 Peter 的交易请求流与 Paul 的请求流合并，并将结果送入银行账户流处理过程，来对 Peter 和 Paul 拥有联名银行账户这一事实建模，如图 3.38 所示。

SVG

图 3.38：联名银行账户，通过合并两个交易请求流来建模。

这种表述的问题在于合并 (merge) 的概念。简单地交替取 Peter 的一个请求和 Paul 的一个请求来合并两个流是行不通的。假设 Paul 很少访问账户，我们不能强迫 Peter 等待 Paul 访问账户之后才能发起第二笔交易。然而，无论如何实现这种合并，它都必须以某种方式将两个交易流交织起来，而这种方式受到 Peter 和 Paul 所感知的"实际时间"的约束：如果 Peter 和 Paul 相遇，他们能够确认某些交易是在会面之前处理的，另一些是在会面之后处理的。这正是我们在 3.4.1 中不得不处理的同一约束——我们在那里发现需要引入显式同步，以确保带状态对象并发处理中事件的"正确"顺序。因此，在试图支持函数式风格的过程中，将来自不同主体的输入合并的需求重新引入了函数式风格本应消除的那些问题。

我们以构建结构与我们试图建模的现实世界感知相匹配的计算模型为目标，开始了本章的讨论。我们可以将世界建模为一组相互独立、受时间约束、彼此交互的有状态对象，也可以将世界建模为一个单一的、超越时间的、无状态的整体。每种观点都各有强大的优势，但单独依靠任何一种观点都不能令人完全满意。一种宏大的统一尚待出现。