Lab 11:


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 streams. As we shall see, streams can mitigate some of the complexity of modeling state.

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.

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.

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 streams. 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 delayed evaluation, which enables us to represent very large (even infinite) sequences as streams.

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.


finish this during section

Exercise 1.

What is the type of the value of (delay (+ 1 27))? What is the type of the value of (force (delay (+ 1 27)))?

Exercise 2.

Evaluation of the expression

(stream-cdr (stream-cdr (cons-stream 1 '(2
produces an error. Why?

Exercise 3.

Consider the following two procedures.

(define (enumerate-interval low high) 
  (if (> low high) 
    (cons low (enumerate-interval (+ low 1) high)) ) ) 
(define (stream-enumerate-interval low high) 
  (if (> low high) 
    (cons-stream low (stream-enumerate-interval (+ low 1) high)) ) ) 

What's the difference between the following two expressions?

(delay (enumerate-interval 1 3)) 
(stream-enumerate-interval 1 3) 

Exercise 4.

An unsolved problem in number theory concerns the following algorithm for creating a sequence of positive integers s1, s2, ...

      Choose s1 to be some positive integer.
      For n > 1,
         if sn is odd, then sn+1 is 3sn+1;
         if sn is even, then sn+1 is sn/2.

No matter what starting value is chosen, the sequence always seems to end with the values 1, 4, 2, 1, 4, 2, 1, ... However, it is not known if this is always the case.

a. Write a procedure num-seq that, given a positive integer n as argument, returns the stream of values produced for n by the algorithm just given. For example, (num-seq 7) should return the stream representing the sequence 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, ...

b. Write a procedure seq-length that, given a stream produced by num-seq, returns the number of values that occur in the sequence up to and including the first 1. For example, (seq-length (num-seq 7)) should return 17. You should assume that there is a 1 somewhere in the sequence.


do this in section if possible; finish the rest at home

Exercise 5.

Complete the following:

Abelson & Sussman, exercises 3.50, 3.51, 3.52, 3.53, 3.54, 3.55, 3.56, 3.64 3.66, 3,68

Exercise 6.

Write and test two functions to manipulate nonnegative proper fractions. The first function, fract-stream, will take as its argument a list of two nonnegative integers, the numerator and the denominator, in which the numerator is less than the denominator. It will return an infinite stream of decimal digits representing the decimal expansion of the fraction. The second function, approximation, will take two arguments: a fraction stream and a nonnegative integer numdigits. It will return a list (not a stream) containing the first numdigits digits of the decimal expansion.

(fract-stream '(1 7)) should return the stream representing the decimal expansion of 1/7, which is 0.142857142857142857...

(stream-car (fract-stream '(1 7))) should return 1.

(stream-car (stream-cdr (stream-cdr (fract-stream '(1 7))))) should return 2.

(approximation (fract-stream '(1 7)) 4) should return (1 4 2 8).

(approximation (fract-stream '(1 2)) 4) should return (5 0 0 0).

Exercise 7.

Do the following reading:

Extra for Experts

Do this if you want to. This is NOT for credit.

Exercise 8.

Do exercises 3.59 - 3.62.

Exercise 9.

Consider this procedure:

(define (hanoi-stream n)
  (if (= n 0)
      (stream-append (hanoi-stream (- n 1))
                     (cons-stream n (hanoi-stream (- n 1))))))

It generates finite streams; here are the first few values:

(hanoi-stream 1) (1)
(hanoi-stream 2) (1 2 1)
(hanoi-stream 3) (1 2 1 3 1 2 1)
(hanoi-stream 4) (1 2 1 3 1 2 1 4 1 2 1 3 1 2 1)

Notice that each of these starts with the same values as the one above it, followed by some more values. There is no reason why this pattern can't be continued to generate an infinite stream whose first 2n - 1 elements are (hanoi-stream n). Generate this stream.