Streams

Streams

Lazy Evaluation in Scheme

Lazy evaluation

- In Python, iterators and generators allowed for lazy evaluation

- Scheme doesn't have iterators. How about a list?

Streams

: Instead of iterators, Scheme uses streams

-   Stream : (linked) list whose rest is lazily evaluated

: A promise to compute

-   cdr returns the rest of a list

: For normal lists, the rest is another list

: The rest of a stream is a promise to compute the list

-   cdr-stream forces Scheme to compute the rest

- Remember, a stream is just a regular Scheme pair whose second element is a promise

Promises : an object that delays evaluation of an expression

-   delay : The delay special form creates promises

-   force : The force procedure evaluates the expression inside the promise

- cons-stream and cdr-stream are syntactic sugar. Achieve the same effect with delay and force

Examples

Recursively Defined Streams _ Constant Stream

1. Let’s start with the constant stream. A constant stream is an infinitely long stream with a number repeated.

2. Why does this work ?

3. We know cons-stream takes in a value and a stream, and we know constant-s returns a constant stream. Thus we will have an infinitely long constant stream. Why doesn’t this error ?

Natural Number Stream

1. Why does this work ?

2. We know cons-stream takes in a value and a stream, and we know nats returns a stream. 

3. We know a function call to ( nats ( + start 1 ) ) will return us a naturals streams starting at start + 1, so what value is left? Start, which we place in the stream constructor before the recursive call.

Add-Stream and Ints-Stream

1. Let’s write a function that will add two infinite streams together and return a new stream.

2. Let’s see it in action! Let’s first define the ones stream again.

3. This is the same as (constant-stream 1).

4. Let’s use the ones stream and our new add-stream function to define the ints stream. This is the same as (nats 1). How do we do this ?

Ints-Stream Solution

: We can use infinite streams to build other infinite streams. This is the power of lazy evaluation, our current stream stays one step ahead of itself !

Streams Exam Problems

map-stream

- Implement (map-stream fn s)

 : fn is a one-argument function

 : s is a stream

- Returns a new stream with fn applied to elements of s

stream-to-list

- Implement (stream-to-list s num-elements):

 : s is a stream

 : num-elements is a non-negative integer

- Returns a Scheme list containing the first num-elements elements of s

Streams : Streams are how we implement lazy evaluation in Scheme.

- We use cons-stream to create streams and cdr-stream to evaluate the promise.