3-5-streams.html

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html>
<head>
<meta charset="UTF-8">

<link rel="stylesheet" type="text/css" href="web-worker-interpreter/deps/codemirror/lib/codemirror.css" />
<link rel="stylesheet" type="text/css" href="css/isicp.css" />
<link rel="stylesheet" type="text/css" href="css/footnotes.css" />
<link rel="stylesheet" type="text/css" href="css/theme.css" />

<script src="js/helper.js"></script>
<script src="js/jquery.min.js"></script>
<script src="web-worker-interpreter/deps/codemirror/lib/codemirror.js"></script>
<script src="web-worker-interpreter/deps/codemirror/mode/scheme/scheme.js"></script>
<script src="web-worker-interpreter/coding.js"> </script>
<script>
  set_interpreter_path("web-worker-interpreter/");
  set_language("scheme");
</script>
<script src="js/footnotes.js"></script>

<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  tex2jax: {inlineMath: [['$','$']]}
});
</script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>

<title> iSICP 3.5 - Streams </title>

<script type="text/javascript">
  var _gaq = _gaq || [];
  _gaq.push(['_setAccount', 'UA-36868476-1']);
  _gaq.push(['_trackPageview']);

  (function() {
    var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
    ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
    var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
  })();

</script>
</head>
<body>

<div id="sidebox">
  <div class="tab"></div>
  <div class="content">
    
    <p> 
    
    <a href="index.html" class="navlink"> <img src='images/home.svg' width=32 height=32> </a>
    <span id="toc-link" class="navlink"> <img src='images/list.svg' width=32 height=32> </span>
    <span id="currently-editing-link" class="navlink"> <img src='images/file-edit.svg' width=32 height=32> </span>
    
    <script src="http://cdn.jotfor.ms/static/feedback2.js?3.2.310" type="text/javascript">
    new JotformFeedback({
    formId:'40222623177447',
    base:'http://jotform.me/',
    windowTitle:'Notify Me',
    background:'#FFA500',
    fontColor:'#FFFFFF',
    type:false,
    height:500,
    width:700
    });
    </script>
    <a class="lightbox-40222623177447" style="cursor:pointer;color:blue;text-decoration:underline;"><img src='images/envelope.svg' width=32 height=32></a>

    <p>
    
    <div id="currently-editing"> </div>


    <script>
    
    function hideAll() {
      $("#currently-editing").hide();
      $("#toc").hide();
    }
    
    $("#currently-editing-link").click(function() {
      hideAll();
      $("#currently-editing").show();
    });
    
    $("#toc-link").click(function() {
      hideAll();
      $("#toc").show();
    });
    
    </script>
    
    <div id="toc"> </div>
    
    <p style='font-size:12px'> (Click on the left edge of this green box to hide it!)
    
    <script>
    hideAll();
    $("#toc").show();
    </script>
  
  </div>
</div>

<script> 
$('#sidebox .tab').toggle(function(){
    $('#sidebox').animate({'right':'0%'});
}, function(){
    $('#sidebox').animate({'right':'-30%'});
});

$(document).ready(createTOC);

</script>

<div id="main">

<a href='index.html' style="float:left"> <img src='images/chevron-up.svg' height=64 width=64> </a>
<span style="float:right">
<a href='3-4-concurrency.html'> <img src='images/chevron-left.svg' height=64 width=64> </a>
<a href='4-0-metalinguistic-abstraction.html'> <img src='images/chevron-right.svg' height=64 width=64> </a>
</span>
<br> <br>

<h2> Streams </h2> 

<p> We've gained a good understanding of assignment as a tool in modeling, as well as an appreciation of the complex problems that assignment raises. It is time to ask whether we could have gone about things in a different way, so as to avoid some of these problems. In this section, we explore an alternative approach to modeling state, based on data structures called <tt>streams</tt> . As we shall see, streams can mitigate some of the complexity of modeling state.

<p> Let's step back and review where this complexity comes from. In an attempt to model real-world phenomena, we made some apparently reasonable decisions: We modeled real-world objects with local state by computational objects with local variables. We identified time variation in the real world with time variation in the computer. We implemented the time variation of the states of the model objects in the computer with assignments to the local variables of the model objects.

<p> Is there another approach? Can we avoid identifying time in the computer with time in the modeled world? Must we make the model change with time in order to model phenomena in a changing world? Think about the issue in terms of mathematical functions. We can describe the time-varying behavior of a quantity x as a function of time x(t). If we concentrate on x instant by instant, we think of it as a changing quantity. Yet if we concentrate on the entire time history of values, we do not emphasize change---the function itself does not change.@footnote{Physicists sometimes adopt this view by introducing the ``world lines'' of particles as a device for reasoning about motion. We've also already mentioned (section 2-2-3) that this is the natural way to think about signal-processing systems. We will explore applications of streams to signal processing in section 3-5-3.}

<p> If time is measured in discrete steps, then we can model a time function as a (possibly infinite) sequence. In this section, we will see how to model change in terms of sequences that represent the time histories of the systems being modeled. To accomplish this, we introduce new data structures called <tt>streams</tt> . From an abstract point of view, a stream is simply a sequence. However, we will find that the straightforward implementation of streams as lists (as in section 2-2-1) doesn't fully reveal the power of stream processing. As an alternative, we introduce the technique of <tt>delayed evaluation</tt> , which enables us to represent very large (even infinite) sequences as streams.

<p> Stream processing lets us model systems that have state without ever using assignment or mutable data. This has important implications, both theoretical and practical, because we can build models that avoid the drawbacks inherent in introducing assignment. On the other hand, the stream framework raises difficulties of its own, and the question of which modeling technique leads to more modular and more easily maintained systems remains open.

<h3> Streams Are Delayed Lists </h3> 

<p> As we saw in section 2-2-3, sequences can serve as standard interfaces for combining program modules. We formulated powerful abstractions for manipulating sequences, such as <tt>map</tt>, <tt>filter</tt>, and <tt>accumulate</tt>, that capture a wide variety of operations in a manner that is both succinct and elegant.

<p> Unfortunately, if we represent sequences as lists, this elegance is bought at the price of severe inefficiency with respect to both the time and space required by our computations. When we represent manipulations on sequences as transformations of lists, our programs must construct and copy data structures (which may be huge) at every step of a process.

<p> To see why this is true, let us compare two programs for computing the sum of all the prime numbers in an interval. The first program is written in standard iterative style:@footnote{Assume that we have a predicate <tt>prime?</tt> (e.g., as in section 1-2-6) that tests for primality.}

<div id="">
(define (sum-primes a b)
  (define (iter count accum)
    (cond ((> count b) accum)
          ((prime? count) (iter (+ count 1) (+ count accum)))
          (else (iter (+ count 1) accum))))
  (iter a 0))
</div>
<script>
prompt();
</script>

<p> The second program performs the same computation using the sequence operations of section 2-2-3:

<div id="">
(define (sum-primes a b)
  (accumulate +
              0
              (filter prime? (enumerate-interval a b))))
</div>
<script>
prompt();
</script>

<p> In carrying out the computation, the first program needs to store only the sum being accumulated. In contrast, the filter in the second program cannot do any testing until <tt>enumerate-interval</tt> has constructed a complete list of the numbers in the interval. The filter generates another list, which in turn is passed to <tt>accumulate</tt> before being collapsed to form a sum. Such large intermediate storage is not needed by the first program, which we can think of as enumerating the interval incrementally, adding each prime to the sum as it is generated.

<p> The inefficiency in using lists becomes painfully apparent if we use the sequence paradigm to compute the second prime in the interval from 10,000 to 1,000,000 by evaluating the expression

<div id="">
(car (cdr (filter prime?
                  (enumerate-interval 10000 1000000))))
</div>
<script>
prompt();
</script>

<p> This expression does find the second prime, but the computational overhead is outrageous. We construct a list of almost a million integers, filter this list by testing each element for primality, and then ignore almost all of the result. In a more traditional programming style, we would interleave the enumeration and the filtering, and stop when we reached the second prime.

<p> Streams are a clever idea that allows one to use sequence manipulations without incurring the costs of manipulating sequences as lists. With streams we can achieve the best of both worlds: We can formulate programs elegantly as sequence manipulations, while attaining the efficiency of incremental computation. The basic idea is to arrange to construct a stream only partially, and to pass the partial construction to the program that consumes the stream. If the consumer attempts to access a part of the stream that has not yet been constructed, the stream will automatically construct just enough more of itself to produce the required part, thus preserving the illusion that the entire stream exists. In other words, although we will write programs as if we were processing complete sequences, we design our stream implementation to automatically and transparently interleave the construction of the stream with its use.

<p> On the surface, streams are just lists with different names for the procedures that manipulate them. There is a constructor, <tt>cons-stream</tt>, and two selectors, <tt>stream-car</tt> and <tt>stream-cdr</tt>, which satisfy the constraints

<pre>
(stream-car (cons-stream x y)) = x
(stream-cdr (cons-stream x y)) = y
</pre>

<p> There is a distinguishable object, <tt>the-empty-stream</tt>, which cannot be the result of any <tt>cons-stream</tt> operation, and which can be identified with the predicate <tt>stream-null?</tt>.@footnote{In the @acronym{MIT} implementation, <tt>the-empty-stream</tt> is the same as the empty list <tt>'()</tt>, and <tt>stream-null?</tt> is the same as <tt>null?</tt>.}  Thus we can make and use streams, in just the same way as we can make and use lists, to represent aggregate data arranged in a sequence. In particular, we can build stream analogs of the list operations from Chapter 2, such as <tt>list-ref</tt>, <tt>map</tt>, and <tt>for-each</tt>:@footnote{This should bother you. The fact that we are defining such similar procedures for streams and lists indicates that we are missing some underlying abstraction. Unfortunately, in order to exploit this abstraction, we will need to exert finer control over the process of evaluation than we can at present. We will discuss this point further at the end of section 3-5-4. In section 4-2, we'll develop a framework that unifies lists and streams.}

<div id="">
(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons-stream (proc (stream-car s))
                   (stream-map proc (stream-cdr s)))))

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
             (stream-for-each proc (stream-cdr s)))))
</div>
<script>
prompt();
</script>

<tt>Stream-for-each</tt> is useful for viewing streams:

<div id="">
(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (newline)
  (display x))
</div>
<script>
prompt();
</script>

<p> To make the stream implementation automatically and transparently interleave the construction of a stream with its use, we will arrange for the <tt>cdr</tt> of a stream to be evaluated when it is accessed by the <tt>stream-cdr</tt> procedure rather than when the stream is constructed by <tt>cons-stream</tt>. This implementation choice is reminiscent of our discussion of rational numbers in section 2-1-2, where we saw that we can choose to implement rational numbers so that the reduction of numerator and denominator to lowest terms is performed either at construction time or at selection time. The two rational-number implementations produce the same data abstraction, but the choice has an effect on efficiency. There is a similar relationship between streams and ordinary lists. As a data abstraction, streams are the same as lists. The difference is the time at which the elements are evaluated. With ordinary lists, both the <tt>car</tt> and the <tt>cdr</tt> are evaluated at construction time. With streams, the <tt>cdr</tt> is evaluated at selection time.

<p> Our implementation of streams will be based on a special form called <tt>delay</tt>. Evaluating <tt>(delay <exp</tt>>) does not evaluate the expression <exp>, but rather returns a so-called <tt>delayed object</tt> , which we can think of as a ``promise'' to evaluate <exp> at some future time. As a companion to <tt>delay</tt>, there is a procedure called <tt>force</tt> that takes a delayed object as argument and performs the evaluation---in effect, forcing the <tt>delay</tt> to fulfill its promise. We will see below how <tt>delay</tt> and <tt>force</tt> can be implemented, but first let us use these to construct streams.

<tt>Cons-stream</tt> is a special form defined so that

<div id="">
(cons-stream <a> <b>)
</div>
<script>
prompt();
</script>


is equivalent to

<div id="">
(cons <a> (delay <b>))
</div>
<script>
prompt();
</script>

<p> What this means is that we will construct streams using pairs. However, rather than placing the value of the rest of the stream into the <tt>cdr</tt> of the pair we will put there a promise to compute the rest if it is ever requested. <tt>Stream-car</tt> and <tt>stream-cdr</tt> can now be defined as procedures:

<div id="">
(define (stream-car stream) (car stream))

(define (stream-cdr stream) (force (cdr stream)))
</div>
<script>
prompt();
</script>

<p> <tt>Stream-car</tt> selects the <tt>car</tt> of the pair; <tt>stream-cdr</tt> selects the <tt>cdr</tt> of the pair and evaluates the delayed expression found there to obtain the rest of the stream.@footnote{Although <tt>stream-car</tt> and <tt>stream-cdr</tt> can be defined as procedures, <tt>cons-stream</tt> must be a special form. If <tt>cons-stream</tt> were a procedure, then, according to our model of evaluation, evaluating <tt>(cons-stream <a</tt>> <@var{b>)} would automatically cause <b> to be evaluated, which is precisely what we do not want to happen. For the same reason, <tt>delay</tt> must be a special form, though <tt>force</tt> can be an ordinary procedure.}

<h4> The stream implementation in action </h4> 

<p> To see how this implementation behaves, let us analyze the ``outrageous'' prime computation we saw above, reformulated in terms of streams:

<div id="">
(stream-car
 (stream-cdr
  (stream-filter prime?
                 (stream-enumerate-interval 10000 1000000))))
</div>
<script>
prompt();
</script>

<p> We will see that it does indeed work efficiently.

<p> We begin by calling <tt>stream-enumerate-interval</tt> with the arguments 10,000 and 1,000,000. <tt>Stream-enumerate-interval</tt> is the stream analog of <tt>enumerate-interval</tt> (section 2-2-3):

<div id="">
(define (stream-enumerate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (stream-enumerate-interval (+ low 1) high))))
</div>
<script>
prompt();
</script>

<p> and thus the result returned by <tt>stream-enumerate-interval</tt>, formed by the <tt>cons-stream</tt>, is@footnote{The numbers shown here do not really appear in the delayed expression. What actually appears is the original expression, in an environment in which the variables are bound to the appropriate numbers. For example, <tt>(+ low 1)</tt> with <tt>low</tt> bound to 10,000 actually appears where <tt>10001</tt> is shown.}

<div id="">
(cons 10000
      (delay (stream-enumerate-interval 10001 1000000)))
</div>
<script>
prompt();
</script>

<p> That is, <tt>stream-enumerate-interval</tt> returns a stream represented as a pair whose <tt>car</tt> is 10,000 and whose <tt>cdr</tt> is a promise to enumerate more of the interval if so requested. This stream is now filtered for primes, using the stream analog of the <tt>filter</tt> procedure (section 2-2-3):

<div id="">
(define (stream-filter pred stream)
  (cond ((stream-null? stream) the-empty-stream)
        ((pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (else (stream-filter pred (stream-cdr stream)))))
</div>
<script>
prompt();
</script>

<p> <tt>Stream-filter</tt> tests the <tt>stream-car</tt> of the stream (the <tt>car</tt> of the pair, which is 10,000). Since this is not prime, <tt>stream-filter</tt> examines the <tt>stream-cdr</tt> of its input stream. The call to <tt>stream-cdr</tt> forces evaluation of the delayed <tt>stream-enumerate-interval</tt>, which now returns

<div id="">
(cons 10001
      (delay (stream-enumerate-interval 10002 1000000)))
</div>
<script>
prompt();
</script>

<p> <tt>Stream-filter</tt> now looks at the <tt>stream-car</tt> of this stream, 10,001, sees that this is not prime either, forces another <tt>stream-cdr</tt>, and so on, until <tt>stream-enumerate-interval</tt> yields the prime 10,007, whereupon <tt>stream-filter</tt>, according to its definition, returns

<div id="">
(cons-stream (stream-car stream)
             (stream-filter pred (stream-cdr stream)))
</div>
<script>
prompt();
</script>


which in this case is

<div id="">
(cons 10007
      (delay
        (stream-filter
         prime?
         (cons 10008
               (delay
                 (stream-enumerate-interval 10009
                                            1000000))))))
</div>
<script>
prompt();
</script>

<p> This result is now passed to <tt>stream-cdr</tt> in our original expression. This forces the delayed <tt>stream-filter</tt>, which in turn keeps forcing the delayed <tt>stream-enumerate-interval</tt> until it finds the next prime, which is 10,009. Finally, the result passed to <tt>stream-car</tt> in our original expression is

<div id="">
(cons 10009
      (delay
        (stream-filter
         prime?
         (cons 10010
               (delay
                 (stream-enumerate-interval 10011
                                            1000000))))))
</div>
<script>
prompt();
</script>

<p> <tt>Stream-car</tt> returns 10,009, and the computation is complete. Only as many integers were tested for primality as were necessary to find the second prime, and the interval was enumerated only as far as was necessary to feed the prime filter.

<p> In general, we can think of delayed evaluation as ``demand-driven''programming, whereby each stage in the stream process is activated only enough to satisfy the next stage. What we have done is to decouple the actual order of events in the computation from the apparent structure of our procedures. We write procedures as if the streams existed ``all at once'' when, in reality, the computation is performed incrementally, as in traditional programming styles.

<h4> Implementing <tt>delay</tt> and <tt>force</tt> </h4> 

<p> Although <tt>delay</tt> and <tt>force</tt> may seem like mysterious operations, their implementation is really quite straightforward. <tt>Delay</tt> must package an expression so that it can be evaluated later on demand, and we can accomplish this simply by treating the expression as the body of a procedure. <tt>Delay</tt> can be a special form such that

<div id="">
(delay <exp>)
</div>
<script>
prompt();
</script>

<p> is syntactic sugar for

<div id="">
(lambda () <exp>)
</div>
<script>
prompt();
</script>

<p> <tt>Force</tt> simply calls the procedure (of no arguments) produced by <tt>delay</tt>, so we can implement <tt>force</tt> as a procedure:

<div id="">
(define (force delayed-object)
  (delayed-object))
</div>
<script>
prompt();
</script>

<p> This implementation suffices for <tt>delay</tt> and <tt>force</tt> to work as advertised, but there is an important optimization that we can include. In many applications, we end up forcing the same delayed object many times. This can lead to serious inefficiency in recursive programs involving streams. (See Exercise 3-57.)  The solution is to build delayed objects so that the first time they are forced, they store the value that is computed. Subsequent forcings will simply return the stored value without repeating the computation. In other words, we implement <tt>delay</tt> as a special-purpose memoized procedure similar to the one described in Exercise 3-27. One way to accomplish this is to use the following procedure, which takes as argument a procedure (of no arguments) and returns a memoized version of the procedure. The first time the memoized procedure is run, it saves the computed result. On subsequent evaluations, it simply returns the result.

<div id="">
(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))
</div>
<script>
prompt();
</script>

<p> <tt>Delay</tt> is then defined so that <tt>(delay <exp</tt>>) is equivalent to

<div id="">
(memo-proc (lambda () <exp>))
</div>
<script>
prompt();
</script>

<p> and <tt>force</tt> is as defined previously.@footnote{There are many possible implementations of streams other than the one described in this section. Delayed evaluation, which is the key to making streams practical, was inherent in Algol 60's <tt>call-by-name</tt> parameter-passing method. The use of this mechanism to implement streams was first described by Landin (1965). Delayed evaluation for streams was introduced into Lisp by Friedman and Wise (1976). In their implementation, <tt>cons</tt> always delays evaluating its arguments, so that lists automatically behave as streams. The memoizing optimization is also known as <tt>call-by-need</tt> . The Algol community would refer to our original delayed objects as <tt>call-by-name thunks</tt> and to the optimized versions as <tt>call-by-need thunks</tt> .}

<div class="exercise">
<p> <b>Exercise 3.50:</b> Complete the following definition, which generalizes <tt>stream-map</tt> to allow procedures that take multiple arguments, analogous to <tt>map</tt> in section 2-2-3, footnote Footnote 12.

<div id="">
(define (stream-map proc . argstreams)
  (if (<??> (car argstreams))
      the-empty-stream
      (<??>
       (apply proc (map <??> argstreams))
       (apply stream-map
              (cons proc (map <??> argstreams))))))
</div>
<script>
prompt();
</script>
</div>

<div class="exercise">
<p> <b>Exercise 3.51:</b> In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it:

<div id="">
(define (show x)
  (display-line x)
  x)
</div>
<script>
prompt();
</script>

<p> What does the interpreter print in response to evaluating each expression in the following sequence?@footnote{Exercises such as Exercise 3-51 and Exercise 3-52 are valuable for testing our understanding of how <tt>delay</tt> works. On the other hand, intermixing delayed evaluation with printing---and, even worse, with assignment---is extremely confusing, and instructors of courses on computer languages have traditionally tormented their students with examination questions such as the ones in this section. Needless to say, writing programs that depend on such subtleties is odious programming style. Part of the power of stream processing is that it lets us ignore the order in which events actually happen in our programs. Unfortunately, this is precisely what we cannot afford to do in the presence of assignment, which forces us to be concerned with time and change.}

<div id="">
(define x (stream-map show (stream-enumerate-interval 0 10)))

(stream-ref x 5)

(stream-ref x 7)
</div>
<script>
prompt();
</script>
</div>

<div class="exercise">
<b>Exercise 3.52:</b> Consider the sequence of
expressions

<div id="">
(define sum 0)

(define (accum x)
  (set! sum (+ x sum))
  sum)

(define seq (stream-map accum (stream-enumerate-interval 1 20)))
(define y (stream-filter even? seq))
(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
                         seq))

(stream-ref y 7)

(display-stream z)
</div>
<script>
prompt();
</script>

<p> What is the value of <tt>sum</tt> after each of the above expressions is evaluated?  What is the printed response to evaluating the <tt>stream-ref</tt> and <tt>display-stream</tt> expressions?  Would these responses differ if we had implemented <tt>(delay <exp</tt>>) simply as <tt>(lambda () <exp</tt>>) without using the optimization provided by <tt>memo-proc</tt>?  Explain
</div>

<h3> Infinite Streams </h3> 

<p> 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:

<div id="">
(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define integers (integers-starting-from 1))
</div>
<script>
prompt();
</script>

<p> This makes sense because <tt>integers</tt> will be a pair whose <tt>car</tt> is 1 and whose <tt>cdr</tt> 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.

<p> Using <tt>integers</tt> we can define other infinite streams, such as the stream of integers that are not divisible by 7:

<div id="">
(define (divisible? x y) (= (remainder x y) 0))

(define no-sevens
  (stream-filter (lambda (x) (not (divisible? x 7)))
                 integers))
</div>
<script>
prompt();
</script>

<p> Then we can find integers not divisible by 7 simply by accessing elements of this stream:

<div id="">
(stream-ref no-sevens 100)
117
</div>
<script>
prompt();
</script>

<p> In analogy with <tt>integers</tt>, we can define the infinite stream of Fibonacci numbers:

<div id="">
(define (fibgen a b)
  (cons-stream a (fibgen b (+ a b))))

(define fibs (fibgen 0 1))
</div>
<script>
prompt();
</script>

<p> <tt>Fibs</tt> is a pair whose <tt>car</tt> is 0 and whose <tt>cdr</tt> is a promise to evaluate <tt>(fibgen 1 1)</tt>. When we evaluate this delayed <tt>(fibgen 1 1)</tt>, it will produce a pair whose <tt>car</tt> is 1 and whose <tt>cdr</tt> is a promise to evaluate <tt>(fibgen 1 2)</tt>, and so on.

<p> For a look at a more exciting infinite stream, we can generalize the <tt>no-sevens</tt> example to construct the infinite stream of prime numbers, using a method known as the <tt>sieve of Eratosthenes</tt> .@footnote{Eratosthenes, a third-century @acronym{B.C.} Alexandrian Greek philosopher, is famous for giving the first accurate estimate of the circumference of the Earth, which he computed by observing shadows cast at noon on the day of the summer solstice. Eratosthenes's sieve method, although ancient, has formed the basis for special-purpose hardware ``sieves''that, until recently, were the most powerful tools in existence for locating large primes. Since the 70s, however, these methods have been superseded by outgrowths of the probabilistic techniques discussed in section 1-2-6.} 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 <tt>S</tt>, form a stream whose first element is the first element of <tt>S</tt> and the rest of which is obtained by filtering all multiples of the first element of <tt>S</tt> out of the rest of <tt>S</tt> and sieving the result. This process is readily described in terms of stream operations:

<div id="">
(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))
</div>
<script>
prompt();
</script>

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

<div id="">
(stream-ref primes 50)
233
</div>
<script>
prompt();
</script>

<p> It is interesting to contemplate the signal-processing system set up by <tt>sieve</tt>, shown in the ``Henderson diagram'' in Figure 3-31.@footnote{We have named these figures after Peter Henderson, who was the first person to show us diagrams of this sort as a way of thinking about stream processing. Each solid line represents a stream of values being transmitted. The dashed line from the <tt>car</tt> to the <tt>cons</tt> and the <tt>filter</tt> indicates that this is a single value rather than a stream.}  The input stream feeds into an ``un<tt>cons</tt>er'' 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 <tt>cons</tt>ed 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.

<div class="exercise">
<b>Figure 3.31:</b> The prime sieve viewed as a
signal-processing system.

<pre>
  +---------------------------------------------------------------+
  | sieve                                                         |
  |                                                               |
  |        __/|                                        |\__       |
  |     __/car|........................................|   \__    |
  |   _/      |           :                            |      \_  |
----><_       |           V                            |  cons _>---->
  |    \__    |    +------------+    +------------+    |    __/   |
  |       \cdr|--->| filter:    |    | sieve      |--->| __/      |
  |          \|    |            |--->|            |    |/         |
  |                | not        |    |            |               |
  |                | divisible? |    |            |               |
  |                +------------+    +------------+               |
  +---------------------------------------------------------------+
</pre>
</div>

<h4> Defining streams implicitly </h4> 

<p> The <tt>integers</tt> and <tt>fibs</tt> 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 <tt>ones</tt> to be an infinite stream of ones:

<div id="">
(define ones (cons-stream 1 ones))
</div>
<script>
prompt();
</script>

<p> This works much like the definition of a recursive procedure: <tt>ones</tt> is a pair whose <tt>car</tt> is 1 and whose <tt>cdr</tt> is a promise to evaluate <tt>ones</tt>. Evaluating the <tt>cdr</tt> gives us again a 1 and a promise to evaluate <tt>ones</tt>, and so on.

<p> We can do more interesting things by manipulating streams with operations such as <tt>add-streams</tt>, which produces the elementwise sum of two given streams:@footnote{This uses the generalized version of <tt>stream-map</tt> from Exercise 3-50.}

<div id="">
(define (add-streams s1 s2)
  (stream-map + s1 s2))
</div>
<script>
prompt();
</script>

<p> Now we can define the integers as follows:

<div id="">
(define integers (cons-stream 1 (add-streams ones integers)))
</div>
<script>
prompt();
</script>

<p> This defines <tt>integers</tt> to be a stream whose first element is 1 and the rest of which is the sum of <tt>ones</tt> and <tt>integers</tt>. Thus, the second element of <tt>integers</tt> is 1 plus the first element of <tt>integers</tt>, or 2; the third element of <tt>integers</tt> is 1 plus the second element of <tt>integers</tt>, or 3; and so on. This definition works because, at any point, enough of the <tt>integers</tt> stream has been generated so that we can feed it back into the definition to produce the next integer.

<p> We can define the Fibonacci numbers in the same style:

<div id="">
(define fibs
  (cons-stream 0
               (cons-stream 1
                            (add-streams (stream-cdr fibs)
                                         fibs))))
</div>
<script>
prompt();
</script>

<p> This definition says that <tt>fibs</tt> is a stream beginning with 0 and 1, such that the rest of the stream can be generated by adding <tt>fibs</tt> to itself shifted by one place:

<pre>
      1  1  2  3  5  8   13  21  ... = <tt>(stream-cdr fibs)</tt>
      0  1  1  2  3  5   8   13  ... = <tt>fibs</tt>
0  1  1  2  3  5  8  13  21  34  ... = <tt>fibs</tt>
</pre>

<p> <tt>Scale-stream</tt> is another useful procedure in formulating such stream definitions. This multiplies each item in a stream by a given constant:

<div id="">
(define (scale-stream stream factor)
  (stream-map (lambda (x) (* x factor)) stream))
</div>
<script>
prompt();
</script>

For example,

<div id="">
(define double (cons-stream 1 (scale-stream double 2)))
</div>
<script>
prompt();
</script>

<p> produces the stream of powers of 2: 1, 2, 4, 8, 16, 32, ....

<p> 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:

<div id="">
(define primes
  (cons-stream
   2
   (stream-filter prime? (integers-starting-from 3))))
</div>
<script>
prompt();
</script>

<p> 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 <em>[sqrt]</em>(n):

<div id="">
(define (prime? n)
  (define (iter ps)
    (cond ((> (square (stream-car ps)) n) true)
          ((divisible? n (stream-car ps)) false)
          (else (iter (stream-cdr ps)))))
  (iter primes))
</div>
<script>
prompt();
</script>

<p> This is a recursive definition, since <tt>primes</tt> is defined in terms of the <tt>prime?</tt> predicate, which itself uses the <tt>primes</tt> stream. The reason this procedure works is that, at any point, enough of the <tt>primes</tt> 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 <em>[sqrt]</em>(n)).@footnote{This last point is very subtle and relies on the fact that p_(n+1) &lt;= p_n^2. (Here, p_k denotes the kth prime.)  Estimates such as these are very difficult to establish. The ancient proof by Euclid that there are an infinite number of primes shows that p_(n+1)&lt;= p_1 p_2...p_n + 1, and no substantially better result was proved until 1851, when the Russian mathematician P. L. Chebyshev established that p_(n+1)&lt;= 2p_n for all n. This result, originally conjectured in 1845, is known as <tt>Bertrand's hypothesis</tt> . A proof can be found in section 22.3 of Hardy and Wright 1960.}

<div class="exercise">
<b>Exercise 3.53:</b> Without running the program, describe the elements of the stream defined by

<div id="">
(define s (cons-stream 1 (add-streams s s)))
</div>
<script>
prompt();
</script>
</div>

<div class="exercise">
<b>Exercise 3.54:</b> Define a procedure <tt>mul-streams</tt>, analogous to <tt>add-streams</tt>, that produces the elementwise product of its two input streams. Use this together with the stream of <tt>integers</tt> to complete the following definition of the stream whose nth element (counting from 0) is n + 1 factorial:

<div id="">
(define factorials (cons-stream 1 (mul-streams <??> <??>)))
</div>
<script>
prompt();
</script>
</div>

<div class="exercise">
<b>Exercise 3.55:</b> Define a procedure <tt>partial-sums</tt> that takes as argument a stream S and returns the stream whose elements are S_0, S_0 + S_1, S_0 + S_1 + S_2, .... For example, <tt>(partial-sums integers)</tt> should be the stream 1, 3, 6, 10, 15, ....
</div>

<div class="exercise">
<b>Exercise 3.56:</b> A famous problem, first raised by R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers <tt>S</tt> and notice the following facts about it.

<ul>

<li>
<tt>S</tt> begins with 1.
</li>

<li>
The elements of <tt>(scale-stream S 2)</tt> are also
elements of <tt>S</tt>.
</li>

<li>
The same is true for <tt>(scale-stream S 3)</tt>
and <tt>(scale-stream 5 S)</tt>.
</li>

<li>
These are all the elements of <tt>S</tt>.
</li>
</ul>

Now all we have to do is combine elements from these sources. For this we define a procedure <tt>merge</tt> that combines two ordered streams into one ordered result stream, eliminating repetitions:

<div id="">
(define (merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((s1car (stream-car s1))
               (s2car (stream-car s2)))
           (cond ((< s1car s2car)
                  (cons-stream s1car (merge (stream-cdr s1) s2)))
                 ((> s1car s2car)
                  (cons-stream s2car (merge s1 (stream-cdr s2))))
                 (else
                  (cons-stream s1car
                               (merge (stream-cdr s1)
                                      (stream-cdr s2)))))))))
</div>
<script>
prompt();
</script>

Then the required stream may be constructed with <tt>merge</tt>, as follows:

<div id="">
(define S (cons-stream 1 (merge <??> <??>)))
</div>
<script>
prompt();
</script>

Fill in the missing expressions in the places marked <??> above.
</div>

<div class="exercise">
<b>Exercise 3.57:</b> How many additions are performed when we compute the nth Fibonacci number using the definition of <tt>fibs</tt> based on the <tt>add-streams</tt> procedure?  Show that the number of additions would be exponentially greater if we had implemented <tt>(delay <exp</tt>>) simply as <tt>(lambda () <exp</tt>>), without using the optimization provided by the <tt>memo-proc</tt> procedure described in section 3-5-1.@footnote{This exercise shows how call-by-need is closely related to ordinary memoization as described in Exercise 3-27. In that exercise, we used assignment to explicitly construct a local table. Our call-by-need stream optimization effectively constructs such a table automatically, storing values in the previously forced parts of the stream.} 
</div>

<div class="exercise">
<b>Exercise 3.58:</b> Give an interpretation of the stream computed by the following procedure:

<div id="">
(define (expand num den radix)
  (cons-stream
   (quotient (* num radix) den)
   (expand (remainder (* num radix) den) den radix)))
</div>
<script>
prompt();
</script>

(<tt>Quotient</tt> is a primitive that returns the integer quotient of two integers.)  What are the successive elements produced by <tt>(expand 1 7 10)</tt>?  What is produced by <tt>(expand 3 8 10)</tt>? 
</div>

<div class="exercise">
<b>Exercise 3.59:</b> In section 2-5-3 we saw how to implement a polynomial arithmetic system representing polynomials as lists of terms. In a similar way, we can work with <tt>power series</tt> , such as

<pre>
               x^2     x^3       x^4
e^x = 1 + x + ----- + ----- + --------- + ...
                2     3 * 2   4 * 3 * 2

             x^2       x^4
cos x = 1 - ----- + --------- - ...
              2     4 * 3 * 2

             x^3         x^5
sin x = x - ----- + ------------- - ...
            3 * 2   5 * 4 * 3 * 2
</pre>

represented as infinite streams. We will represent the series a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ... as the stream whose elements are the coefficients a_0, a_1, a_2, a_3, ....

<ul>
@item
The integral of the series a_0 + a_1 x + a_2 x^2 + a_3 x^3 + ... is the series

<pre>
             1             1             1
c + a_0 x + --- x_1 r^2 + --- a_2 r^3 + --- a_3 r^4 + ...
             2             3             4
</pre>

where c is any constant. Define a procedure <tt>integrate-series</tt> that takes as input a stream a_0, a_1, a_2, ... representing a power series and returns the stream a_0, (1/2)a_1, (1/3)a_2, ... of coefficients of the non-constant terms of the integral of the series. (Since the result has no constant term, it doesn't represent a power series; when we use <tt>integrate-series</tt>, we will <tt>cons</tt> on the appropriate constant.)

@item
The function x |-> e^x is its own derivative. This implies that e^x and the integral of e^x are the same series, except for the constant term, which is e^0 = 1. Accordingly, we can generate the series for e^x as

<div id="">
(define exp-series
  (cons-stream 1 (integrate-series exp-series)))
</div>
<script>
prompt();
</script>

Show how to generate the series for sine and cosine, starting from the facts that the derivative of sine is cosine and the derivative of cosine is the negative of sine:

<div id="">
(define cosine-series
  (cons-stream 1 <??>))

(define sine-series
  (cons-stream 0 <??>))
</div>
<script>
prompt();
</script>
</ul>
</div>

<div class="exercise">
<b>Exercise 3.60:</b> With power series represented as streams of coefficients as in Exercise 3-59, adding series is implemented by <tt>add-streams</tt>. Complete the definition of the following procedure for multiplying series:

<div id="">
(define (mul-series s1 s2)
  (cons-stream <??> (add-streams <??> <??>)))
</div>
<script>
prompt();
</script>

You can test your procedure by verifying that sin^2 x + cos^2 x = 1, using the series from Exercise 3-59.
</div>

<div class="exercise">
<b>Exercise 3.61:</b> Let S be a power series (Exercise 3-59) whose constant term is 1. Suppose we want to find the power series 1/S, that is, the series X such that S * X = 1. Write S = 1 + S_R where S_R is the part of S after the constant term. Then we can solve for X as follows:

<pre>
        S * X = 1
(1 + S_R) * X = 1
  X + S_R * X = 1
            X = 1 - S_R * X
</pre>

In other words, X is the power series whose constant term is 1 and whose higher-order terms are given by the negative of S_R times X. Use this idea to write a procedure <tt>invert-unit-series</tt> that computes 1/S for a power series S with constant term 1. You will need to use <tt>mul-series</tt> from Exercise 3-60. 
</div>

<div class="exercise">
<b>Exercise 3.62:</b> Use the results of Exercise 3-60 and Exercise 3-61 to define a procedure <tt>div-series</tt> that divides two power series. <tt>Div-series</tt> should work for any two series, provided that the denominator series begins with a nonzero constant term. (If the denominator has a zero constant term, then <tt>div-series</tt> should signal an error.)  Show how to use <tt>div-series</tt> together with the result of Exercise 3-59 to generate the power series for tangent. 
</div>

<h3> Exploiting the Stream Paradigm </h3> 

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.

<h4> Formulating iterations as stream processes </h4> 

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 section 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:

<div id="">
(define (sqrt-improve guess x)
  (average guess (/ x guess)))
</div>
<script>
prompt();
</script>

In our original <tt>sqrt</tt> 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:@footnote{We can't use <tt>let</tt> to bind the local variable <tt>guesses</tt>, because the value of <tt>guesses</tt> depends on <tt>guesses</tt> itself. Exercise 3-63 addresses why we want a local variable here.}

<div id="">
(define (sqrt-stream x)
  (define guesses
    (cons-stream 1.0
                 (stream-map (lambda (guess)
                               (sqrt-improve guess x))
                             guesses)))
  guesses)

(display-stream (sqrt-stream 2))
1.
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
...
</div>
<script>
prompt();
</script>

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.)

Another iteration that we can treat in the same way is to generate an approximation to [pi], based upon the alternating series that we saw in section 1-3-1:

<pre>
[pi]        1     1     1
---- = 1 - --- + --- - --- + ...
  4         3     5     7
</pre>

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 <tt>partial-sums</tt> procedure of Exercise 3-55) and scale the result by 4:

<div id="">
(define (pi-summands n)
  (cons-stream (/ 1.0 n)
               (stream-map - (pi-summands (+ n 2)))))

(define pi-stream
  (scale-stream (partial-sums (pi-summands 1)) 4))

(display-stream pi-stream)
4.
2.666666666666667
3.466666666666667
2.8952380952380956
3.3396825396825403
2.9760461760461765
3.2837384837384844
3.017071817071818
...
</div>
<script>
prompt();
</script>

This gives us a stream of better and better approximations to [pi], although the approximations converge rather slowly. Eight terms of the sequence bound the value of [pi] between 3.284 and 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 <tt>sequence accelerator</tt> that converts a sequence of approximations to a new sequence that converges to the same value as the original, only faster.

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 nth term of the original sum sequence, then the accelerated sequence has terms

<pre>
             (S_(n+1) - S_n)^2
S_(n+1) - ------------------------
          S_(n-1) - 2S_n + S_(n+1)
</pre>

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

<div id="">
(define (euler-transform s)
  (let ((s0 (stream-ref s 0))           ; S_(n-1)
        (s1 (stream-ref s 1))           ; S_n
        (s2 (stream-ref s 2)))          ; S_(n+1)
    (cons-stream (- s2 (/ (square (- s2 s1))
                          (+ s0 (* -2 s1) s2)))
                 (euler-transform (stream-cdr s)))))
</div>
<script>
prompt();
</script>

We can demonstrate Euler acceleration with our sequence of approximations to [pi]:

<div id="">
(display-stream (euler-transform pi-stream))
3.166666666666667
3.1333333333333337
3.1452380952380956
3.13968253968254
3.1427128427128435
3.1408813408813416
3.142071817071818
3.1412548236077655
...
</div>
<script>
prompt();
</script>

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 <tt>tableau</tt> ) in which each stream is the transform of the preceding one:

<div id="">
(define (make-tableau transform s)
  (cons-stream s
               (make-tableau transform
                             (transform s))))
</div>
<script>
prompt();
</script>

The tableau has the form

<pre>
s_00   s_01   s_02   s_03   s_04   ...
       s_10   s_11   s_12   s_13   ...
              s_20   s_21   s_22   ...
                            ...
</pre>

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

<div id="">
(define (accelerated-sequence transform s)
  (stream-map stream-car
              (make-tableau transform s)))
</div>
<script>
prompt();
</script>

We can demonstrate this kind of ``super-acceleration'' of the [pi] sequence:

<div id="">
(display-stream (accelerated-sequence euler-transform
                                      pi-stream))
4.
3.166666666666667
3.142105263157895
3.141599357319005
3.1415927140337785
3.1415926539752927
3.1415926535911765
3.141592653589778
...
</div>
<script>
prompt();
</script>

The result is impressive. Taking eight terms of the sequence yields the correct value of [pi] to 14 decimal places. If we had used only the original [pi] sequence, we would need to compute on the order of 10^13 terms (i.e., expanding the series far enough so that the individual terms are less then 10^(-13)) to get that much accuracy!

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.

<div class="exercise">
<b>Exercise 3.63:</b> Louis Reasoner asks why the <tt>sqrt-stream</tt> procedure was not written in the following more straightforward way, without the local variable <tt>guesses</tt>:

<div id="">
(define (sqrt-stream x)
  (cons-stream 1.0
               (stream-map (lambda (guess)
                             (sqrt-improve guess x))
                           (sqrt-stream x))))
</div>
<script>
prompt();
</script>

Alyssa P. Hacker replies that this version of the procedure is considerably less efficient because it performs redundant computation. Explain Alyssa's answer. Would the two versions still differ in efficiency if our implementation of <tt>delay</tt> used only <tt>(lambda () <exp</tt>>) without using the optimization provided by <tt>memo-proc</tt> (section 3-5-1)? 
</div>

<div class="exercise">
<b>Exercise 3.64:</b> Write a procedure <tt>stream-limit</tt> that takes as arguments a stream and a number (the tolerance). It should examine the stream until it finds two successive elements that differ in absolute value by less than the tolerance, and return the second of the two elements. Using this, we could compute square roots up to a given tolerance by

<div id="">
(define (sqrt x tolerance)
  (stream-limit (sqrt-stream x) tolerance))
</div>
<script>
prompt();
</script>
</div>

<div class="exercise">
<b>Exercise 3.65:</b> Use the series

<pre>
            1     1     1
ln 2 = 1 - --- + --- - --- + ...
            2     3     4
</pre>

to compute three sequences of approximations to the natural logarithm of 2, in the same way we did above for [pi]. How rapidly do these sequences converge?
</div>

<h4> Infinite streams of pairs </h4> 

In section 2-2-3, we saw how the sequence paradigm handles traditional nested loops as processes defined on sequences of pairs. If we generalize this technique to infinite streams, then we can write programs that are not easily represented as loops, because the ``looping'' must range over an infinite set.

For example, suppose we want to generalize the <tt>prime-sum-pairs</tt> procedure of section 2-2-3 to produce the stream of pairs of <em>all</em> integers (i,j) with i &lt;= j such that i + j is prime. If <tt>int-pairs</tt> is the sequence of all pairs of integers (i,j) with i &lt;= j, then our required stream is simply@footnote{As in section 2-2-3, we represent a pair of integers as a list rather than a Lisp pair.}

<div id="">
(stream-filter (lambda (pair)
                 (prime? (+ (car pair) (cadr pair))))
               int-pairs)
</div>
<script>
prompt();
</script>

Our problem, then, is to produce the stream <tt>int-pairs</tt>. More generally, suppose we have two streams S = (S_i) and T = (T_j), and imagine the infinite rectangular array

<pre>
(S_0, T_0)  (S_0, T_1)  (S_0, T_2)  ...
(S_1, T_0)  (S_1, T_1)  (S_1, T_2)  ...
(S_2, T_0)  (S_2, T_1)  (S_2, T_2)  ...
   ...
</pre>

We wish to generate a stream that contains all the pairs in the array that lie on or above the diagonal, i.e., the pairs

<pre>
(S_0, T_0)  (S_0, T_1)  (S_0, T_2)  ...
            (S_1, T_1)  (S_1, T_2)  ...
                        (S_2, T_2)  ...
                                    ...
</pre>

(If we take both S and T to be the stream of integers, then this will be our desired stream <tt>int-pairs</tt>.)

Call the general stream of pairs <tt>(pairs S T)</tt>, and consider it to be composed of three parts: the pair (S_0,T_0), the rest of the pairs in the first row, and the remaining pairs:@footnote{See Exercise 3-68 for some insight into why we chose this decomposition.}

<pre>
(S_0, T_0) | (S_0, T_1)  (S_0, T_2)  ...
-----------+-----------------------------
           | (S_1, T_1)  (S_1, T_2)  ...
           |             (S_2, T_2)  ...
           |                         ...
</pre>

Observe that the third piece in this decomposition (pairs that are not in the first row) is (recursively) the pairs formed from <tt>(stream-cdr S)</tt> and <tt>(stream-cdr T)</tt>. Also note that the second piece (the rest of the first row) is

<div id="">
(stream-map (lambda (x) (list (stream-car s) x))
            (stream-cdr t))
</div>
<script>
prompt();
</script>

Thus we can form our stream of pairs as follows:

<div id="">
(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (<combine-in-some-way>
       (stream-map (lambda (x) (list (stream-car s) x))
                   (stream-cdr t))
       (pairs (stream-cdr s) (stream-cdr t)))))
</div>
<script>
prompt();
</script>

In order to complete the procedure, we must choose some way to combine the two inner streams. One idea is to use the stream analog of the <tt>append</tt> procedure from section 2-2-1:

<div id="">
(define (stream-append s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (stream-append (stream-cdr s1) s2))))
</div>
<script>
prompt();
</script>

This is unsuitable for infinite streams, however, because it takes all the elements from the first stream before incorporating the second stream. In particular, if we try to generate all pairs of positive integers using

<div id="">
(pairs integers integers)
</div>
<script>
prompt();
</script>

our stream of results will first try to run through all pairs with the first integer equal to 1, and hence will never produce pairs with any other value of the first integer.

To handle infinite streams, we need to devise an order of combination that ensures that every element will eventually be reached if we let our program run long enough. An elegant way to accomplish this is with the following <tt>interleave</tt> procedure:@footnote{The precise statement of the required property on the order of combination is as follows: There should be a function f of two arguments such that the pair corresponding to element i of the first stream and element j of the second stream will appear as element number f(i,j) of the output stream. The trick of using <tt>interleave</tt> to accomplish this was shown to us by David Turner, who employed it in the language KRC (Turner 1981).}

<div id="">
(define (interleave s1 s2)
  (if (stream-null? s1)
      s2
      (cons-stream (stream-car s1)
                   (interleave s2 (stream-cdr s1)))))
</div>
<script>
prompt();
</script>

Since <tt>interleave</tt> takes elements alternately from the two streams, every element of the second stream will eventually find its way into the interleaved stream, even if the first stream is infinite.

We can thus generate the required stream of pairs as

<div id="">
(define (pairs s t)
  (cons-stream
   (list (stream-car s) (stream-car t))
   (interleave
    (stream-map (lambda (x) (list (stream-car s) x))
                (stream-cdr t))
    (pairs (stream-cdr s) (stream-cdr t)))))
</div>
<script>
prompt();
</script>

<div class="exercise">
<b>Exercise 3.66:</b> Examine the stream <tt>(pairs integers integers)</tt>. Can you make any general comments about the order in which the pairs are placed into the stream? For example, about how many pairs precede the pair (1,100)?  the pair (99,100)? the pair (100,100)? (If you can make precise mathematical statements here, all the better. But feel free to give more qualitative answers if you find yourself getting bogged down.) 
</div>

<div class="exercise">
<b>Exercise 3.67:</b> Modify the <tt>pairs</tt> procedure so that <tt>(pairs integers integers)</tt> will produce the stream of <em>all</em> pairs of integers (i,j) (without the condition i <= j). Hint: You will need to mix in an additional stream. 
</div>

<div class="exercise">
<b>Exercise 3.68:</b> Louis Reasoner thinks that building a stream of pairs from three parts is unnecessarily complicated. Instead of separating the pair (S_0,T_0) from the rest of the pairs in the first row, he proposes to work with the whole first row, as follows:

<div id="">
(define (pairs s t)
  (interleave
   (stream-map (lambda (x) (list (stream-car s) x))
               t)
   (pairs (stream-cdr s) (stream-cdr t))))
</div>
<script>
prompt();
</script>

Does this work?  Consider what happens if we evaluate <tt>(pairs integers integers)</tt> using Louis's definition of <tt>pairs</tt>. 
</div>

<div class="exercise">
<b>Exercise 3.69:</b> Write a procedure <tt>triples</tt> that takes three infinite streams, S, T, and U, and produces the stream of triples (S_i,T_j,U_k) such that i <= j <= k. Use <tt>triples</tt> to generate the stream of all Pythagorean triples of positive integers, i.e., the triples (i,j,k) such that i <= j and i^2 + j^2 = k^2. 
</div>

<div class="exercise">
<b>Exercise 3.70:</b> It would be nice to be able to generate streams in which the pairs appear in some useful order, rather than in the order that results from an <em>ad hoc</em> interleaving process. We can use a technique similar to the <tt>merge</tt> procedure of Exercise 3-56, if we define a way to say that one pair of integers is ``less than'' another. One way to do this is to define a ``weighting function'' W(i,j) and stipulate that (i_1,j_1) is less than (i_2,j_2) if W(i_1,j_1) < W(i_2,j_2). Write a procedure <tt>merge-weighted</tt> that is like <tt>merge</tt>, except that <tt>merge-weighted</tt> takes an additional argument <tt>weight</tt>, which is a procedure that computes the weight of a pair, and is used to determine the order in which elements should appear in the resulting merged stream.@footnote{We will require that the weighting function be such that the weight of a pair increases as we move out along a row or down along a column of the array of pairs.}  Using this, generalize <tt>pairs</tt> to a procedure <tt>weighted-pairs</tt> that takes two streams, together with a procedure that computes a weighting function, and generates the stream of pairs, ordered according to weight. Use your procedure to generate

<ul>
@item
the stream of all pairs of positive integers (i,j) with i <= j
ordered according to the sum i + j

@item
the stream of all pairs of positive integers (i,j) with i <= j,
where neither i nor j is divisible by 2, 3, or 5, and the pairs are
ordered according to the sum 2 i + 3 j + 5 i j.

</ul>
</div>

<div class="exercise">
<b>Exercise 3.71:</b> Numbers that can be expressed as the sum of two cubes in more than one way are sometimes called <tt>Ramanujan numbers</tt> , in honor of the mathematician Srinivasa Ramanujan.@footnote{To quote from G. H. Hardy's obituary of Ramanujan (Hardy 1921): ``It was Mr. Littlewood (I believe) who remarked that `every positive integer was one of his friends.'  I remember once going to see him when he was lying ill at Putney. I had ridden in taxi-cab No. 1729, and remarked that the number seemed to me a rather dull one, and that I hoped it was not an unfavorable omen. `No,' he replied, `it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways.''' The trick of using weighted pairs to generate the Ramanujan numbers was shown to us by Charles Leiserson.} Ordered streams of pairs provide an elegant solution to the problem of computing these numbers. To find a number that can be written as the sum of two cubes in two different ways, we need only generate the stream of pairs of integers (i,j) weighted according to the sum i^3 + j^3 (see Exercise 3-70), then search the stream for two consecutive pairs with the same weight. Write a procedure to generate the Ramanujan numbers. The first such number is 1,729. What are the next five? 
</div>

<div class="exercise">
<b>Exercise 3.72:</b> In a similar way to Exercise 3-71 generate a stream of all numbers that can be written as the sum of two squares in three different ways (showing how they can be so written). 
</div>

<h4> Streams as signals </h4> 

We began our discussion of streams by describing them as computational analogs of the ``signals'' in signal-processing systems. In fact, we can use streams to model signal-processing systems in a very direct way, representing the values of a signal at successive time intervals as consecutive elements of a stream. For instance, we can implement an <tt>integrator</tt> or <tt>summer</tt> that, for an input stream x = (x_i), an initial value C, and a small increment dt, accumulates the sum

<pre>
           i
          ---
S_i = C + >   x_j dt
          ---
          j=1
</pre>

and returns the stream of values S = (S_i). The following <tt>integral</tt> procedure is reminiscent of the ``implicit style'' definition of the stream of integers (section 3-5-2):

<div id="">
(define (integral integrand initial-value dt)
  (define int
    (cons-stream initial-value
                 (add-streams (scale-stream integrand dt)
                              int)))
  int)
</div>
<script>
prompt();
</script>

Figure 3-32 is a picture of a signal-processing system that corresponds to the <tt>integral</tt> procedure. The input stream is scaled by dt and passed through an adder, whose output is passed back through the same adder. The self-reference in the definition of <tt>int</tt> is reflected in the figure by the feedback loop that connects the output of the adder to one of the inputs.

<div class="exercise">
<b>Figure 3.32:</b> The <tt>integral</tt> procedure viewed
as a signal-processing system.

<pre>
                             initial-value
                                  |
       +-----------+              |   |\__
input  |           |      |\__    +-->|   \_  integral
------>| scale: dt +----->|   \_      |cons_>--*------->
       |           |      | add_>---->| __/    |
       +-----------+  +-->| __/       |/       |
                      |   |/                   |
                      |                        |
                      +------------------------+
</pre>
</div>

<div class="exercise">
<b>Exercise 3.73:</b> We can model electrical circuits using streams to represent the values of currents or voltages at a sequence of times. For instance, suppose we have an <tt>RC circuit</tt> consisting of a resistor of resistance R and a capacitor of capacitance C in series. The voltage response v of the circuit to an injected current i is determined by the formula in Figure 3-33, whose structure is shown by the accompanying signal-flow diagram.

Write a procedure <tt>RC</tt> that models this circuit. <tt>RC</tt> should take as inputs the values of R, C, and dt and should return a procedure that takes as inputs a stream representing the current i and an initial value for the capacitor voltage v_0 and produces as output the stream of voltages v. For example, you should be able to use <tt>RC</tt> to model an RC circuit with R = 5 ohms, C = 1 farad, and a 0.5-second time step by evaluating <tt>(define RC1 (RC 5 1 0.5))</tt>. This defines <tt>RC1</tt> as a procedure that takes a stream representing the time sequence of currents and an initial capacitor voltage and produces the output stream of voltages. 
</div>

<div class="exercise">
<b>Figure 3.33:</b> An RC circuit and the associated
signal-flow diagram.

<pre>
  +                 -
 ->----'\/\/\,---| |---
  i                 C

              / t
              |  i
 v  =  v   +  |      dt + R i
        0     |
              / 0

         +--------------+
     +-->|   scale: R   |---------------------+   |\_
     |   +--------------+                     |   |  \_
     |                                        +-->|    \   v
  i  |   +--------------+     +------------+      | add >--->
 ----+-->|  scale: 1/C  |---->|  integral  |----->|   _/
         +--------------+     +------------+      | _/
                                                  |/
</pre>
</div>

<div class="exercise">
<b>Exercise 3.74:</b> Alyssa P. Hacker is designing a system to process signals coming from physical sensors. One important feature she wishes to produce is a signal that describes the <tt>zero crossings</tt>

of the input signal. That is, the resulting signal should be + 1 whenever the input signal changes from negative to positive, - 1 whenever the input signal changes from positive to negative, and 0 otherwise. (Assume that the sign of a 0 input is positive.)  For example, a typical input signal with its associated zero-crossing signal would be

<div id="">
... 1  2  1.5  1  0.5  -0.1  -2  -3  -2  -0.5  0.2  3  4 ...
... 0  0    0  0    0     -1  0   0   0     0    1  0  0 ...
</div>
<script>
prompt();
</script>

In Alyssa's system, the signal from the sensor is represented as a stream <tt>sense-data</tt> and the stream <tt>zero-crossings</tt> is the corresponding stream of zero crossings. Alyssa first writes a procedure <tt>sign-change-detector</tt> that takes two values as arguments and compares the signs of the values to produce an appropriate 0, 1, or - 1. She then constructs her zero-crossing stream as follows:

<div id="">
(define (make-zero-crossings input-stream last-value)
  (cons-stream
   (sign-change-detector (stream-car input-stream) last-value)
   (make-zero-crossings (stream-cdr input-stream)
                        (stream-car input-stream))))

(define zero-crossings (make-zero-crossings sense-data 0))
</div>
<script>
prompt();
</script>

Alyssa's boss, Eva Lu Ator, walks by and suggests that this program is approximately equivalent to the following one, which uses the generalized version of <tt>stream-map</tt> from Exercise 3-50:

<div id="">
(define zero-crossings
  (stream-map sign-change-detector sense-data <expression>))
</div>
<script>
prompt();
</script>

Complete the program by supplying the indicated <expression>.
</div>

<div class="exercise">
<b>Exercise 3.75:</b> Unfortunately, Alyssa's zero-crossing detector in Exercise 3-74 proves to be insufficient, because the noisy signal from the sensor leads to spurious zero crossings. Lem E. Tweakit, a hardware specialist, suggests that Alyssa smooth the signal to filter out the noise before extracting the zero crossings. Alyssa takes his advice and decides to extract the zero crossings from the signal constructed by averaging each value of the sense data with the previous value. She explains the problem to her assistant, Louis Reasoner, who attempts to implement the idea, altering Alyssa's program as follows:

<div id="">
(define (make-zero-crossings input-stream last-value)
  (let ((avpt (/ (+ (stream-car input-stream) last-value) 2)))
    (cons-stream (sign-change-detector avpt last-value)
                 (make-zero-crossings (stream-cdr input-stream)
                                      avpt))))
</div>
<script>
prompt();
</script>

This does not correctly implement Alyssa's plan. Find the bug that Louis has installed and fix it without changing the structure of the program. (Hint: You will need to increase the number of arguments to <tt>make-zero-crossings</tt>.) 
</div>

<div class="exercise">
<b>Exercise 3.76:</b> Eva Lu Ator has a criticism of Louis's approach in Exercise 3-75. The program he wrote is not modular, because it intermixes the operation of smoothing with the zero-crossing extraction. For example, the extractor should not have to be changed if Alyssa finds a better way to condition her input signal. Help Louis by writing a procedure <tt>smooth</tt> that takes a stream as input and produces a stream in which each element is the average of two successive input stream elements. Then use <tt>smooth</tt> as a component to implement the zero-crossing detector in a more modular style. 
</div>

<h3> Streams and Delayed Evaluation </h3> 

The <tt>integral</tt> procedure at the end of the preceding section shows how we can use streams to model signal-processing systems that contain feedback loops. The feedback loop for the adder shown in Figure 3-32 is modeled by the fact that <tt>integral</tt>'s internal stream <tt>int</tt> is defined in terms of itself:

<div id="">
(define int
  (cons-stream initial-value
               (add-streams (scale-stream integrand dt)
                            int)))
</div>
<script>
prompt();
</script>

The interpreter's ability to deal with such an implicit definition depends on the <tt>delay</tt> that is incorporated into <tt>cons-stream</tt>. Without this <tt>delay</tt>, the interpreter could not construct <tt>int</tt> before evaluating both arguments to <tt>cons-stream</tt>, which would require that <tt>int</tt> already be defined. In general, <tt>delay</tt> is crucial for using streams to model signal-processing systems that contain loops. Without <tt>delay</tt>, our models would have to be formulated so that the inputs to any signal-processing component would be fully evaluated before the output could be produced. This would outlaw loops.

Unfortunately, stream models of systems with loops may require uses of <tt>delay</tt> beyond the ``hidden'' <tt>delay</tt> supplied by <tt>cons-stream</tt>. For instance, Figure 3-34 shows a signal-processing system for solving the differential equation dy/dt = f(y) where f is a given function. The figure shows a mapping component, which applies f to its input signal, linked in a feedback loop to an integrator in a manner very similar to that of the analog computer circuits that are actually used to solve such equations.

<div class="exercise">
<b>Figure 3.34:</b> An ``analog computer circuit'' that
solves the equation dy/dt = f(y).

<pre>
                            y_0
                             |
                             V
    +----------+  dy   +----------+     y
+-->|  map: f  +------>| integral +--*----->
|   +----------+       +----------+  |
|                                    |
+------------------------------------+
</pre>
</div>

Assuming we are given an initial value y_0 for y, we could try to model this system using the procedure

<div id="">
(define (solve f y0 dt)
  (define y (integral dy y0 dt))
  (define dy (stream-map f y))
  y)
</div>
<script>
prompt();
</script>

This procedure does not work, because in the first line of <tt>solve</tt> the call to <tt>integral</tt> requires that the input <tt>dy</tt> be defined, which does not happen until the second line of <tt>solve</tt>.

On the other hand, the intent of our definition does make sense, because we can, in principle, begin to generate the <tt>y</tt> stream without knowing <tt>dy</tt>. Indeed, <tt>integral</tt> and many other stream operations have properties similar to those of <tt>cons-stream</tt>, in that we can generate part of the answer given only partial information about the arguments. For <tt>integral</tt>, the first element of the output stream is the specified <tt>initial-value</tt>. Thus, we can generate the first element of the output stream without evaluating the integrand <tt>dy</tt>. Once we know the first element of <tt>y</tt>, the <tt>stream-map</tt> in the second line of <tt>solve</tt> can begin working to generate the first element of <tt>dy</tt>, which will produce the next element of <tt>y</tt>, and so on.

To take advantage of this idea, we will redefine <tt>integral</tt> to expect the integrand stream to be a <tt>delayed argument</tt> . <tt>Integral</tt> will <tt>force</tt> the integrand to be evaluated only when it is required to generate more than the first element of the output stream:

<div id="">
(define (integral delayed-integrand initial-value dt)
  (define int
    (cons-stream initial-value
                 (let ((integrand (force delayed-integrand)))
                   (add-streams (scale-stream integrand dt)
                                int))))
  int)
</div>
<script>
prompt();
</script>

Now we can implement our <tt>solve</tt> procedure by delaying the evaluation of <tt>dy</tt> in the definition of <tt>y</tt>:@footnote{This procedure is not guaranteed to work in all Scheme implementations, although for any implementation there is a simple variation that will work. The problem has to do with subtle differences in the ways that Scheme implementations handle internal definitions. (See section 4-1-6.)}

<div id="">
(define (solve f y0 dt)
  (define y (integral (delay dy) y0 dt))
  (define dy (stream-map f y))
  y)
</div>
<script>
prompt();
</script>

In general, every caller of <tt>integral</tt> must now <tt>delay</tt> the integrand argument. We can demonstrate that the <tt>solve</tt> procedure works by approximating eapprox 2.718 by computing the value at y = 1 of the solution to the differential equation dy/dt = y with initial condition y(0) = 1:

<div id="">
(stream-ref (solve (lambda (y) y) 1 0.001) 1000)
2.716924
</div>
<script>
prompt();
</script>

<div class="exercise">
<b>Exercise 3.77:</b> The <tt>integral</tt> procedure used above was analogous to the ``implicit'' definition of the infinite stream of integers in section 3-5-2. Alternatively, we can give a definition of <tt>integral</tt> that is more like <tt>integers-starting-from</tt> (also in section 3-5-2):

<div id="">
(define (integral integrand initial-value dt)
  (cons-stream initial-value
               (if (stream-null? integrand)
                   the-empty-stream
                   (integral (stream-cdr integrand)
                             (+ (* dt (stream-car integrand))
                                initial-value)
                             dt))))
</div>
<script>
prompt();
</script>

When used in systems with loops, this procedure has the same problem as does our original version of <tt>integral</tt>. Modify the procedure so that it expects the <tt>integrand</tt> as a delayed argument and hence can be used in the <tt>solve</tt> procedure shown above. 
</div>

<div class="exercise">
<b>Figure 3.35:</b> Signal-flow diagram for the solution
to a second-order linear differential equation.

<pre>
               dy_0                y_0
                |                   |
                V                   V
   ddy     +----------+    dy  +----------+    y
+--------->| integral +-----*--+ integral +--*--->
|          +----------+     |  +----------+  |
|                           |                |
|            +----------+   |                |
|     __/|<--+ scale: a |<--+                |
|   _/   |   +----------+                    |
+--<_add |                                   |
     \__ |   +----------+                    |
        \|<--+ scale: b |<-------------------+
             +----------+
</pre>
</div>

<div class="exercise">
<b>Exercise 3.78:</b> Consider the problem of designing a signal-processing system to study the homogeneous second-order linear differential equation

<pre>
d^2 y        d y
-----  -  a -----  -  by  =  0
d t^2        d t
</pre>

The output stream, modeling y, is generated by a network that contains a loop. This is because the value of d^2y/dt^2 depends upon the values of y and dy/dt and both of these are determined by integrating d^2y/dt^2. The diagram we would like to encode is shown in Figure 3-35. Write a procedure <tt>solve-2nd</tt> that takes as arguments the constants a, b, and dt and the initial values y_0 and dy_0 for y and dy/dt and generates the stream of successive values of y. 
</div>

<div class="exercise">
<b>Exercise 3.79:</b> Generalize the <tt>solve-2nd</tt> procedure of Exercise 3-78 so that it can be used to solve general second-order differential equations d^2 y/dt^2 = f(dy/dt, y). 
</div>

<div class="exercise">
<b>Exercise 3.80:</b> A <tt>series RLC circuit</tt> 

consists of a resistor, a capacitor, and an inductor connected in series, as shown in Figure 3-36. If R, L, and C are the resistance, inductance, and capacitance, then the relations between voltage (v) and current (i) for the three components are described by the equations

<pre>
v_R = i_R R

         d_(i L)
v_L = L ---------
           d t

         d v_C
i_C = C -------
          d t
</pre>


and the circuit connections dictate the relations

<pre>
i_R = i_L = -i_C

v_C = v_L + v_R
</pre>

Combining these equations shows that the state of the circuit (summarized by v_C, the voltage across the capacitor, and i_L, the current in the inductor) is described by the pair of differential equations

<pre>
d v_C        i_L
-----  =  -  ---
 d t          C

d i_L      1           R
-----  =  --- v_C  -  --- i_L
 d t       L           L
</pre>


The signal-flow diagram representing this system of differential equations is shown in Figure 3-37.

</div>

<pre>
<b>Figure 3.36:</b> A series RLC circuit.
              + v_R -
        i_R
     +--->----'\/\/\,--------+
     |                       |  i_L
    \|/          R          \|/
  +  |  i_C                  |_   +
    -+-                      __)
v_C -+- C                   (_)   v_L
     |                       __)
  -  |                       |    -
     +-----------------------+
</pre>

<div class="exercise">
<b>Figure 3.37:</b> A signal-flow diagram for the
solution to a series RLC circuit.

<pre>
                 +-------------+
+----------------+  scale: l/L |<--+
|                +-------------+   |
|                                  |
|                +-------------+   |  v_C
|       dv_C +-->|   integral  +---*------>
|            |   +-------------+
|            |        ^
|            |        | v_(C_0)
|            |
|            |   +-------------+
|            +---+ scale: -l/C |<--+
|                +-------------+   |
|  |\__                            |
+->|   \_  di_L  +-------------+   |  i_L
   | add_>------>|   integral  +---*------>
+->| __/         +-------------+   |
|  |/                 ^            |
|                     | i_(L_0)    |
|                                  |
|                +-------------+   |
+----------------+ scale: -R/L |<--+
                 +-------------+
</pre>
</div>

Write a procedure <tt>RLC</tt> that takes as arguments the parameters R, L, and C of the circuit and the time increment dt. In a manner similar to that of the <tt>RC</tt> procedure of Exercise 3-73, <tt>RLC</tt> should produce a procedure that takes the initial values of the state variables, v_(C_0) and i_(L_0), and produces a pair (using <tt>cons</tt>) of the streams of states v_C and i_L. Using <tt>RLC</tt>, generate the pair of streams that models the behavior of a series RLC circuit with R = 1 ohm, C = 0.2 farad, L = 1 henry, dt = 0.1 second, and initial values i_(L_0) = 0 amps and v_(C_0) = 10 volts.

<h4> Normal-order evaluation </h4> 

The examples in this section illustrate how the explicit use of <tt>delay</tt> and <tt>force</tt> provides great programming flexibility, but the same examples also show how this can make our programs more complex. Our new <tt>integral</tt> procedure, for instance, gives us the power to model systems with loops, but we must now remember that <tt>integral</tt> should be called with a delayed integrand, and every procedure that uses <tt>integral</tt> must be aware of this. In effect, we have created two classes of procedures: ordinary procedures and procedures that take delayed arguments. In general, creating separate classes of procedures forces us to create separate classes of higher-order procedures as well.@footnote{This is a small reflection, in Lisp, of the difficulties that conventional strongly typed languages such as Pascal have in coping with higher-order procedures. In such languages, the programmer must specify the data types of the arguments and the result of each procedure: number, logical value, sequence, and so on. Consequently, we could not express an abstraction such as ``map a given procedure <tt>proc</tt> over all the elements in a sequence'' by a single higher-order procedure such as <tt>stream-map</tt>. Rather, we would need a different mapping procedure for each different combination of argument and result data types that might be specified for a <tt>proc</tt>. Maintaining a practical notion of ``data type'' in the presence of higher-order procedures raises many difficult issues. One way of dealing with this problem is illustrated by the language ML (Gordon, Milner, and Wadsworth 1979), whose ``polymorphic data types'' include templates for higher-order transformations between data types. Moreover, data types for most procedures in ML are never explicitly declared by the programmer. Instead, ML includes a <tt>type-inferencing</tt> mechanism that uses information in the environment to deduce the data types for newly defined procedures.}

One way to avoid the need for two different classes of procedures is to make all procedures take delayed arguments. We could adopt a model of evaluation in which all arguments to procedures are automatically delayed and arguments are forced only when they are actually needed (for example, when they are required by a primitive operation). This would transform our language to use normal-order evaluation, which we first described when we introduced the substitution model for evaluation in section 1-1-5. Converting to normal-order evaluation provides a uniform and elegant way to simplify the use of delayed evaluation, and this would be a natural strategy to adopt if we were concerned only with stream processing. In section 4-2, after we have studied the evaluator, we will see how to transform our language in just this way. Unfortunately, including delays in procedure calls wreaks havoc with our ability to design programs that depend on the order of events, such as programs that use assignment, mutate data, or perform input or output. Even the single <tt>delay</tt> in <tt>cons-stream</tt> can cause great confusion, as illustrated by Exercise 3-51 and Exercise 3-52. As far as anyone knows, mutability and delayed evaluation do not mix well in programming languages, and devising ways to deal with both of these at once is an active area of research.

<h3> Modularity of Functional Programs and Modularity of Objects </h3> 

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 <tt>rand-update</tt>, whose successive values furnished our supply of random numbers, and used this to produce a random-number generator:

<div id="">
(define rand
  (let ((x random-init))
    (lambda ()
      (set! x (rand-update x))
      x)))
</div>
<script>
prompt();
</script>

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

<div id="">
(define random-numbers
  (cons-stream random-init
               (stream-map rand-update random-numbers)))
</div>
<script>
prompt();
</script>

We use this to construct the stream of outcomes of the Ces@`aro experiment performed on consecutive pairs in the <tt>random-numbers</tt> stream:

<div id="">
(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)))))
</div>
<script>
prompt();
</script>

The <tt>cesaro-stream</tt> is now fed to a <tt>monte-carlo</tt> procedure, 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 <tt>pi</tt> stream:

<div id="">
(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)))
</div>
<script>
prompt();
</script>

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

<div class="exercise">
<b>Exercise 3.81:</b> 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 <tt>generate</tt> a new random number or to <tt>reset</tt> the sequence to a specified value and that produces the desired stream of random numbers. Don't use assignment in your solution. 
</div>

<div class="exercise">
<b>Exercise 3.82:</b> Redo Exercise 3-5 on Monte Carlo integration in terms of streams. The stream version of <tt>estimate-integral</tt> will not have an argument telling how many trials to perform. Instead, it will produce a stream of estimates based on successively more trials. 
</div>

<h4> A functional-programming view of time </h4> 

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 <tt>delay</tt> 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:

<div id="">
(define (make-simplified-withdraw balance)
  (lambda (amount)
    (set! balance (- balance amount))
    balance))
</div>
<script>
prompt();
</script>

Calls to <tt>make-simplified-withdraw</tt> produce computational objects, each with a local state variable <tt>balance</tt> that is decremented by successive calls to the object. The object takes an <tt>amount</tt> 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:

<div id="">
(define (stream-withdraw balance amount-stream)
  (cons-stream
   balance
   (stream-withdraw (- balance (stream-car amount-stream))
                    (stream-cdr amount-stream))))
</div>
<script>
prompt();
</script>

<tt>Stream-withdraw</tt> implements a well-defined mathematical function whose output is fully determined by its input. Suppose, however, that the input <tt>amount-stream</tt> 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 <tt>make-simplified-withdraw</tt>. 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 <tt>stream-withdraw</tt> 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.@footnote{Similarly in physics, when we observe a moving particle, we say that the position (state) of the particle is changing. However, from the perspective of the particle's world line in space-time there is no change involved.}

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 <tt>functional programming languages</tt> , 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.@footnote{John Backus, the inventor of Fortran, gave high visibility to functional programming when he was awarded the @acronym{ACM} Turing award in 1978. His acceptance speech (Backus 1978) strongly advocated the functional approach. A good overview of functional programming is given in Henderson 1980 and in Darlington, Henderson, and Turner 1982.}

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 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''<em>per se</em>, 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.

<div class="exercise">
<b>Figure 3.38:</b> A joint bank account, modeled by
merging two streams of transaction requests.

<pre>
Peter's requests   +---------+     +---------+
------------------>|         |     |         |
Paul's requests    |  merge  |---->| bank    |---->
------------------>|         |     | account |
                   +---------+     +---------+
</pre>
</div>

The trouble with this formulation is in the notion of <tt>merge</tt> . 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.@footnote{Observe that, for any two streams, there is in general more than one acceptable order of interleaving. Thus, technically, ``merge'' is a relation rather than a function---the answer is not a deterministic function of the inputs. We already mentioned (Footnote 39) that nondeterminism is essential when dealing with concurrency. The merge relation illustrates the same essential nondeterminism, from the functional perspective. In section 4-3, we will look at nondeterminism from yet another point of view.} 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.@footnote{The object model approximates the world by dividing it into separate pieces. The functional model does not modularize along object boundaries. The object model is useful when the unshared state of the ``objects'' is much larger than the state that they share. An example of a place where the object viewpoint fails is quantum mechanics, where thinking of things as individual particles leads to paradoxes and confusions. Unifying the object view with the functional view may have little to do with programming, but rather with fundamental epistemological issues.}

<br>
<br>

<hr>

<div id="footnotes">
<h3 id='Notes'> Notes </h3>
 </div>

<hr>

<p> <a rel="license" href="http://creativecommons.org/licenses/by-sa/3.0/deed.en_US" target="_blank"><img alt="Creative Commons License" style="border-width:0" src="http://i.creativecommons.org/l/by-sa/3.0/88x31.png" /></a><br /> Based on Structure and Interpretation of Computer Programs, a work at <a xmlns:dct="http://purl.org/dc/terms/" href="http://mitpress.mit.edu/sicp/" rel="dct:source" target="_blank">http://mitpress.mit.edu/sicp/</a>.

</div>

<a href="https://github.com/zodiac/isicp" target="_blank"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_green_007200.png" alt="Fork me on GitHub"></a>

</body>
</html>