I got the impression that people were not really comfortable with
streams, and especially with stream-get.  So I've written up some more
notes on streams.  I hope you will find it useful.  --Prof. Wand

****************************************************************


                           More on Streams



When we say (cons Exp1 Exp2), Exp1 and Exp2 are evaluated before the cons
returns.  So we can't use cons to create infinite lists.  For example,
you might think of writing something like

(define ints-from
  (lambda (n)
    (cons n (ints-from (+ n 1)))))

to create the list of all the integers starting from n, but this
doesn't work:  it goes into an infinite loop.

Instead, let's build a LAZY cons.  A lazy cons is going to be like a
cons, except it doesn't evaluate its arguments when it's built.  It
only evaluates them when somebody asks it for its car or cdr.

This may sound mysterious, but it's really easy.  Instead of building
a cons, just use a cons-thunk:  a thunk that returns a cons.

If I write

(lambda () (cons Exp1 Exp2))

Exp1 and Exp2 are not evaluated now-- instead, you get a procedure
which, WHEN INVOKED, evaluates its body, including the Exp1 and Exp2.

An ordinary list is either '() or a cons whose cdr is a list.  So
a lazy list is a lazy cons whose (lazy) cdr is a lazy list.  

By this definition a lazy list is always infinite-- we can simulate finite
lazy lists by making everything after "the end" an end-marker:

(define null-lazy-list
  (lambda () 
    (cons end-marker
          null-lazy-list)))
        
And of course a stream is exactly the same thing as a lazy list.

Now we can write ints-from:

(define ints-from
  (lambda (n)
    (lambda ()
      (cons n (ints-from (+ n 1))))))

(ints-from 1) returns (lambda () (cons 1 (ints-from (+ 1 1))))  

((ints-from 1)) returns (cons 1 (ints-from 2))  :  a list whose car is
1 and whose cdr is the LAZY LIST of integers starting from 2.

So building lazy lists is easy:  to build a lazy list, you write

(lambda ()
  (cons the-car
        thunk-which-builds-the-cdr))

Of course, there may be considerable computation before you get the
car and cdr, but this computation won't be done until the thunk is
run.  You might even have side effects.  For example, we had this
example last time:

(define prompt-read
  (lambda (prompt)
    (printf "~d " prompt)
    (read)))

(define make-input-stream
  (lambda (prompt)
    (lambda ()
      (cons (prompt-read prompt)
            (make-input-stream prompt)))))

which makes a stream out of expressions read from the standard input.
Whenever you run the thunk [say, by writing ((make-input-stream  "input>")) ] 
prompt-read gets called, which reads from the input stream.

Now, you won't get anywhere until you know how to take a lazy list
apart.  A first try would be to define

(define lazy-car
  (lambda (lazy-list) (car (lazy-list))))

(define lazy-cdr
  (lambda (lazy-list) (cdr (lazy-list))))

In each case, you run the thunk, getting a cons-box, and then you take
either its car or cdr.  

But this won't get us far.  Remember that in an ordinary list, we do
the computation of its pieces once, when we do the cons (this may be hard);
but taking the pieces apart with car or cdr is easy.  In a lazy list, we've
reversed this:  we don't do ANY computation when we build the list-- all the
computation comes when we try to take the list apart by invoking the thunk.

So our definition of lazy-car and lazy-cdr are at best wasteful, because they
do all the computation in the thunk over and over again, every time you call
them.  Worse yet, if the computation involves side-effects (as in
make-input-stream), you may get different answers each time!

So we need to make sure that we invoke each thunk at most once.  Most likely,
you'll want to take both the car and cdr of this lazy list.  The only
reasonable way to do this is:

(let ((temp (lazy-list)))
  (let ((the-car (car temp))
        (the-cdr (cdr temp)))
    (..do something with the-car and the-cdr...)))

Here we run the thunk once by saying (lazy-list).  We then give names
to its pieces, and do whatever it is we really wanted to the pieces.

For example:

(define stream->list
  (lambda (stream end-marker-test)
    (let ((temp (stream)))
      (let ((head (car stream))
            (tail (cdr stream)))
        (if (end-marker-test head)
          '()
          (cons head (stream->list tail end-marker-test)))))))

If we write code using lazy lists, we will write this pattern of code
over and over again.  So we write a PROCEDURE that encapsulates it.

To do this we observe the following important fact:

(let ((var1 Exp1) (var2 Exp2) ...) Body)
is PRECISELY THE SAME as
((lambda (var1 var2 ...) Body)
 Exp1 Exp2 ...)

In both cases, we evaluate Exp1, Exp2, etc., and then we evaluate Body
in an environment in which var1, var2, etc., are bound to the values
of Exp1, Exp2, etc.

Think about this.  It is important.

For the case of streams, this says we can replace 

(let ((temp (lazy-list)))
  (let ((the-car (car temp))
        (the-cdr (cdr temp)))
    (..do something with the-car and the-cdr...)))

by 

(let ((temp (lazy-list)))
  ((lambda (the-car the-cdr)
     (..do something with the-car and the-cdr...))
   (car temp)
   (cdr temp)))

You can check that here, too, we run the thunk, bind its pieces to
the-car and the-cdr, and then do something with the-car and the-cdr.

This form can be abstracted as:

(let ((temp (lazy-list)))
  (some-function (car temp) (cdr temp)))

So we write

(define decompose-lazy-list
  (lambda (lazy-list fcn)
    (let ((temp (lazy-list)))
      (fcn (car temp) (cdr temp)))))

Using analyze-lazy-list, we can write stream->list as:

(define stream->list
  (lambda (stream end-marker-test)
    (decompose-lazy-list
      stream
      (lambda (head tail)
        (if (end-marker-test head)
          '()
          (cons head (stream->list tail end-marker-test)))))))

We can write stream transducers.  Here is a procedure that maps a function
down the elements of a stream (like "map" does on lists):

(define map-stream
  (lambda (fcn stream)
    ;; don't do anything now, just build the lazy list of answers:
    (lambda ()
      ;; if somebody asks, then do some computation
      (decompose-lazy-list stream
        (lambda (first rest)
          (cons first
                (map-stream fcn rest)))))))

Of course, the things we've built here are exactly the same as the
streams we built before:  make-lazy-stream is the identity function,
so it was just a marker reminding the reader that this thunk is
intended as a stream.  And stream-get is just the same as
decompose-lazy-list. 

[Digression:  The style of doing decompose-lazy-list is not restricted
  to streams.  We could just as easily write things like:

(define decompose-list
  (lambda (list fcn)
    (fcn (car list) (cdr list))))

(define remove1
  (lambda (a list)
    (if (null? list) '()
      (decompose-list list
        (lambda (the-car the-cdr)
          (if (eq? the-car 'a) the-cdr
            (remove1 a the-cdr)))))))

This automates the taking apart of the list into its car and cdr.  We
could even automate the testing for null:

(define list-case
  (lambda (list value-if-nil fcn)
    (if (null? list)
      value-if-nil
      (fcn (car list) (cdr list)))))

(define remove1
  (lambda (a list)
    (list-case list
      '()                               ; if it null, return nil
      (lambda (the-car the-cdr)         ; otherwise take it apart
        (if (eq? the-car 'a) the-cdr
            (remove1 a the-cdr))))))

But this is a different story....]