As we saw in section 3.1.2, one of the major benefits of introducing assignment is that we can increase the modularity of our systems by encapsulating, or hiding, parts of the state of a large system within local variables. Stream models can provide an equivalent modularity without the use of assignment. As an illustration, we can reimplement the Monte Carlo estimation of $\pi$, which we examined in section 3.1.2, from a stream-processing point of view.

The key modularity issue was that we wished to hide the internal state of a random-number generator from programs that used random numbers. We began with a procedure rand-update, function rand_update, whose successive values furnished our supply of random numbers, and used this to produce a random-number generator:

Original	JavaScript
(define rand (let ((x random-init)) (lambda () (set! x (rand-update x)) x)))	function make_rand() { let x = random_init; return () => { x = rand_update(x); return x; }; } const rand = make_rand();

In the stream formulation there is no random-number generator per se, just a stream of random numbers produced by successive calls to rand-update: rand_update:

Original	JavaScript
(define random-numbers (cons-stream random-init (stream-map rand-update random-numbers)))	const random_numbers = pair(random_init, () => stream_map(rand_update, random_numbers));

We use this to construct the stream of outcomes of the Cesàro experiment performed on consecutive pairs in the random-numbers random_numbers stream:

Original	JavaScript
(define cesaro-stream (map-successive-pairs (lambda (r1 r2) (= (gcd r1 r2) 1)) random-numbers)) (define (map-successive-pairs f s) (cons-stream (f (stream-car s) (stream-car (stream-cdr s))) (map-successive-pairs f (stream-cdr (stream-cdr s)))))	function map_successive_pairs(f, s) { return pair(f(head(s), head(stream_tail(s))), () => map_successive_pairs( f, stream_tail(stream_tail(s)))); } const dirichlet_stream = map_successive_pairs((r1, r2) => gcd(r1, r2) === 1, random_numbers);

The cesaro-stream dirichlet_stream is now fed to a monte-carlo monte_carlo procedure, function, which produces a stream of estimates of probabilities. The results are then converted into a stream of estimates of $\pi$. This version of the program doesn't need a parameter telling how many trials to perform. Better estimates of $\pi$ (from performing more experiments) are obtained by looking farther into the pi stream:

Original	JavaScript
(define (monte-carlo experiment-stream passed failed) (define (next passed failed) (cons-stream (/ passed (+ passed failed)) (monte-carlo (stream-cdr experiment-stream) passed failed))) (if (stream-car experiment-stream) (next (+ passed 1) failed) (next passed (+ failed 1)))) (define pi (stream-map (lambda (p) (sqrt (/ 6 p))) (monte-carlo cesaro-stream 0 0)))	function monte_carlo(experiment_stream, passed, failed) { function next(passed, failed) { return pair(passed / (passed + failed), () => monte_carlo(stream_tail(experiment_stream), passed, failed)); } return head(experiment_stream) ? next(passed + 1, failed) : next(passed, failed + 1); } const pi = stream_map(p => math_sqrt(6 / p), monte_carlo(dirichlet_stream, 0, 0));

There is considerable modularity in this approach, because we still can formulate a general monte-carlo procedure monte_carlo function that can deal with arbitrary experiments. Yet there is no assignment or local state.

Exercise 3.84 Exercise 3.6 discussed generalizing the random-number generator to allow one to reset the random-number sequence so as to produce repeatable sequences of random numbers. Produce a stream formulation of this same generator that operates on an input stream of requests to generate "generate" a new random number or to reset "reset" the sequence to a specified value and that produces the desired stream of random numbers. Don't use assignment in your solution.

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 3.85 Redo exercise 3.5 on Monte Carlo integration in terms of streams. The stream version of estimate-integral 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.

Add solution

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

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 delayed evaluation 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 section 3.1.3 we implemented a simplified version of such a processor:

Original	JavaScript
(define (make-simplified-withdraw balance) (lambda (amount) (set! balance (- balance amount)) balance))	function make_simplified_withdraw(balance) { return amount => { balance = balance - amount; return balance; }; }

Calls to make-simplified-withdraw 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 function that takes as input a balance and a stream of amounts to withdraw and produces the stream of successive balances in the account:

Original	JavaScript
(define (stream-withdraw balance amount-stream) (cons-stream balance (stream-withdraw (- balance (stream-car amount-stream)) (stream-cdr amount-stream))))	function stream_withdraw(balance, amount_stream) { return pair(balance, () => stream_withdraw(balance - head(amount_stream), stream_tail(amount_stream))); }

Stream-withdraw The function stream_withdraw implements a well-defined mathematical function whose output is fully determined by its input. Suppose, however, that the input amount-stream 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. 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 section 3.1.3. Yet the system has state!

This is really remarkable. Even though stream-withdraw 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.[1]

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 functions implement well-defined mathematical functions of their arguments, whose behavior does not change. The functional approach is extremely attractive for dealing with concurrent systems.[2]

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 section 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.65.

Figure 3.65 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.[3] This is precisely the same constraint that we had to deal with in section 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.[4]