1 of 7

Streams

Shayna Kothari

2 of 7

Streams

  • Remember: why are generators useful?
    • Allow you to read in infinite sequences!
    • Helpful for getting data line-by-line from a very large file, for example
  • How can we do that in Scheme?
    • No such thing as an iterator!
    • Trying to construct an infinitely long linked list will… fail

(define (naturals n)

(cons n (naturals (+ n 1)))

3 of 7

Streams

However… Scheme does support streams!

  • Lazy evaluation -- Scheme doesn’t evaluate the next value unless you tell it to!
    • Represented as a promise -- aka Scheme telling you that it will calculate the value when it needs to
  • Constructed like normal Scheme lists, except using cons-stream
    • Tells Scheme not to evaluate the rest until it has to!
    • cdr can be either a Scheme list or a stream
  • cdr will always give you a promise -- to evaluate, use cdr-stream

(define (naturals n)

(cons-stream n (naturals (+ n 1)))

4 of 7

Streams

Evaluation steps:

  • Evaluate the first operand
  • Construct a promise containing the second operand
  • Return a pair with the first operand as the first value, promise as second value

Promises aren’t evaluated until you call cdr-stream!

  • “Forced” promise means that it’s already been evaluated
  • “Not forced” means Scheme hasn’t evaluated it yet

5 of 7

6 of 7

Streams

  • You can construct streams recursively! We can define a stream of all 1s:

(define s (cons-stream 1 s))

  • You can also make the second element of a Stream a list:

(cons-stream 1 (cons 2 nil))

7 of 7

Why the Dot?

  • Dot indicates that the second element of the Pair isn’t another Pair!
    • Used to be more stuff with dots in 61A, but we removed it from our Scheme implementation because it was confusing :^)
    • We still use dots for this, though, since the second element of a stream is a promise and not another pair!