CS 22
Clab 27: Introduction to Streams
I want to briefly introduce you to a possible solution to the
deque problem. Then we will turn our attention to streams. A possible
solution to the deque problem is in my pub directory at:
/home/cfk/pub/cs22/week9/deque2.scm. We'll look at this code for a
few minutes.
Now let's look at streams, an example
of lazy evaluation..
We have studied a number of different programming styles in this
course; functional (e.g. just about anything in chapter 1), data
driven (e.g. the generic arithmetic package), and
object oriented (e.g. the circuit simulator). Today we want to look
at demand-driven programming. The idea is that we want to set
up processes that will deliver some appropriate item when that
item is needed but not before it is needed. Suppose we have some
process P that needs a sequence of integers starting at 1. Sometimes
P needs just the first couple of integers. Other times P needs all of
the first 20 integers. One approach to this problem would be to
construct a list of the first 20 integers. Then let P use this list.
Whenever P needs all 20 integers, this would be just fine. But if P
needed only the first 3 integers then this approach would waste the
effort of constructing 17 integers. In contrast, the
demand-driven solution to this problem would be to set up a procedure
that will promise to deliver the next integer when asked for
it.
Our first attempt to construct a sequence of integers might
look like:
<![CDATA[
;;; not a good move
;;; intsfrom is a procedure that when invoked will recurse
;;; for a long time trying to construct a list of every integer
;;; after n.
(define (intsfrom n)
(cons n (intsfrom (+ 1 n))))
]]>
Remember the break button, save anything that is important and try:
<![CDATA[
;;; with above intsfrom procedure, this tries to define a list
;;; of all integers starting from 1. Unfortunately (intsfrom 1)
;;; never terminates
(define ints (intsfrom 1))
]]>
The problem with the above intsfrom procedure is that it actually
tries to construct the list rather than promising to give an integer
when asked. Attempting to construct an infinite list in a finite
machine causes problems.
In order to construct and deliver on promises, we need the Scheme
primitives delay and force. Here is part of what r5rs says
about delay and force.
<![CDATA[
Syntax: (delay <expression>)
The delay construct is used together with the procedure force to
implement lazy evaluation or call by need. (delay <expression>)
returns an object called a promise which at some point in the future
may be asked (by the force procedure) to evaluate <expression>, and
deliver the resulting value. The effect of <expression> returning
multiple values is unspecified.
Procedure: (force promise)
Forces the value of promise (see delay, section 4.2.5). If no value
has been computed for the promise, then a value is computed and
returned. The value of the promise is cached (or "memoized") so that
if it is forced a second time, the previously computed value is
returned.
(force (delay (+ 1 2))) => 3
(let ((p (delay (+ 1 2))))
(list (force p) (force p))) => (3 3)
(define a-stream
(letrec ((next
(lambda (n)
(cons n (delay (next (+ n 1)))))))
(next 0)))
(define head car)
(define tail
(lambda (stream) (force (cdr stream))))
(head (tail (tail a-stream))) => 2
Force and delay are mainly intended for programs written in functional style.
]]>
Now, in your definitions window, define, save and execute:
<![CDATA[
;;; This intsfrom is a procedure that when invoked will create
;;; a stream that consists of the interger n followed by a promise
;;; to construct subsequent integers if forced.
(define (intsfrom n)
(cons n (delay (intsfrom (+ 1 n)))))
]]>
Then in the interaction window,evaluate:
<![CDATA[
(define ints (intsfrom 1))
]]>
There was no infinite recursion here because ints is really a finite structure
consisting of 1 followed by a promise. Now try:
<![CDATA[
> ints
(1 . #<promise>)
> (car ints)
1
> (cdr ints)
#<promise>
> (force (cdr ints))
(2 . #<promise>)
]]>
There is a promise to deliver all of them. But we don't want to wait to
see them all.
It is correct to think about ints as being an infinite stream.
This allows for a very
powerful way of thinking and programming.
Drscheme does have force and delay built in. It does not have cons-stream.
On the top of page 321, sicp tells
how to
construct cons-stream in terms of cons and delay. BUT, if we just
(define (cons-stream a b) (cons a (delay b))), we will fail. The
reason is that in
Scheme, ordinary functions are applied to evaluated arguments. But the whole
idea here is not to evaluate b until needed. So cons-stream must be
a special form
(like cond for example) that only evaluates its arguments when needed.
We cannot define special forms in drscheme. There is a work
around, however. Since delay is a special form, we can replace any
occurence of
(cons-stream a b) by (cons a (delay b)) by hand. So do this when working
with sicp material.
Let's develop a few tools for handling streams. Define, try out, and think
about:
<![CDATA[
(define (stream-car stream) (car stream))
(define (stream-cdr stream) (force (cdr stream)))
(define the-empty-stream '())
(define stream-null? null?)
;;; If s has at least n+1 elements, returns element n in stream s
;;; counting from zero. If s has fewer elements returns ().
(define (stream-ref s n)
(cond
((stream-null? s) '())
((= n 0) (stream-car s))
(#t (stream-ref (stream-cdr s) (- n 1)))))
]]>
Continue with:
<![CDATA[
;;; returns a list containing the first n elements of stream s
;;; if s contains substreams, at most n top-level elements of a
;;; a substream are converted
(define (stream->list n s)
(cond
((stream-null? s) '())
((not (pair? s)) s)
((= n 0) '())
(else (cons (stream->list n (stream-car s))
(stream->list (- n 1) (stream-cdr s))))))
(define square (lambda (x) (* x x)))
(define (stream-map proc s)
(if (stream-null? s)
the-empty-stream
(cons (proc (stream-car s))
(delay (stream-map proc (stream-cdr s))))))
]]>
Then test them by evaluating:
<![CDATA[
> ints
(1 . #<promise>)
> (define f10 (stream->list 10 ints))
> f10
(1 2 3 4 5 6 7 8 9 10)
> (define intssq (stream-map square ints))
> intssq
(1 . #<promise>)
> (stream->list 15 intssq)
(1 4 9 16 25 36 49 64 81 100 121 144 169 196 225)
]]>
This is pretty awesome stuff. intssq is an infinite stream
of the integers squared. We can use stream->list to see as
many of them as we have the patience to look at.
Now define, save, and execute:
<![CDATA[
(define (stream-for-each proc s)
(if (stream-null? s)
'done
(begin (proc (stream-car s))
(stream-for-each proc (stream-cdr s)))))
(define (display-stream s)
(stream-for-each display-line s))
(define (display-line x)
(newline)
(display x))
]]>
Make sure you have saved anything important, remember where the
break button is, and then try the following in the interactions window:
<![CDATA[
> ints
> (display-stream ints)
]]>
You knew that was coming. Right?
As discussed in the text pp. 321-322, we will frequently want to filter
streams. The text gives the following general filter defintion for streams:
<![CDATA[
(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)))))
]]>
This uses cons-stream so it won't work in drscheme. Using our
work-around, define a stream-filter that works, then use it to define
a procedure filter-odd such that (filter-odd str) returns a stream of
all those integers in str that are odd. You may assume that str
is a stream of integers. The stream returned should consist of the
first odd integer in str and a promise to deliver subsequent odd
integers if forced. Test your filter by:
<![CDATA[
> (define oddints (filter-odd ints))
> ints
(1 . #<promise>)
> oddints
(1 . #<promise>)
> (stream-car (stream-cdr (stream-cdr ints)))
3
> (stream-car (stream-cdr (stream-cdr oddints)))
5
> (stream->list 30 oddints)
(1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59)
> (stream->list 30 ints)
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30)
]]>
Call me over to show off your definition of filter-odd or to ask
questions.
As we said, the idea behind lazy evaluation is to set
up processes that will deliver some appropriate item when that
item is needed but not before it is needed.
We used delay and force to build a small library of useful procedures.
We could obtain even integers by defining filter-even and filtering the
stream of all integers as above.
Do that and test filter-even. What will happen if you apply filter-even
to oddints? Why?
Ask any questions you may have.
<![CDATA[
]]>