6.001/Recitation 24
Rob Speer
Three ways to be lazy
It may not have been clear from the lecture, but there are three different ways we can talk about doing lazy evaluation in Scheme.
- 1. Using plain vanilla Scheme
You don't need extra evaluation rules to do the things you do with lazy evaluation. You can make thunks and force them in ordinary Scheme. You just don't get to be particularly lazy about it.
- Every time you need to delay an argument, write
(lambda () arg)in place ofarg. -
(define force (λ (thunk) (thunk)))
If you have delay defined as a special form (MzScheme and MIT Scheme do), you can use that too, and it will be prettier.
But then it's your job to keep track of everything that's delayed and force it before you use it. Icky.
- 2. Using an incompatible version of Scheme
Change the evaluation order around so that everything is evaluated lazily. (This will involve some big decisions about memoization, making side-effects work, and how much compatibility to break.)
- 3. Using extra syntax
This is the thing where you add lazy and lazy-memo flags to lambda arguments. (I believe this actually works in MIT Scheme.)
So if we wanted to define a pair where the cdr is lazy:
(define (stream-cons x (y lazy-memo)) (cons x y)) (define stream-car car) (define stream-cdr cdr)
Streams
Why would we want pairs like that? So we can have lists that aren't computed until we go down them. They can even be infinitely long!
Regardless of implementation, we'll be using stream-cons to construct streams, and stream-car and stream-cdr to extract things from them.
So let's generate some streams.
1. (repeat n) should return an infinite stream with the number n over and over. We can use this to describe the useful streams zeros and ones.
2. To build up more interesting streams, we'll want to be able to combine entire infinite streams. Write map2-stream so that we can define these:
(define (add-streams s1 s2) (map2-stream + s1 s2)) (define (sub-streams s1 s2) (map2-stream - s1 s2)) (define (mul-streams s1 s2) (map2-stream * s1 s2)) (define (div-streams s1 s2) (map2-stream / s1 s2))
