6A Streams, Part 1⁠

# Part 1

# Recap

• We’ve learned about assignment and its frightening implications.
• The substitution model of evaluation breaks down; we have to use the much more complicated environment model.
• Worry about: assignment, state, change, time, identity, objects, sharing.
• Suddenly a variable doesn’t just stand for a value; it specifies a place that holds a value.
• Our goal was modularity, writing programs that mirror reality.
• Maybe we have the wrong view of reality; maybe time is an illusion and nothing changes.

# Motivation

• We’re going to look at another way to decompose systems: stream processing.
• Consider summing the odd squares in a binary tree of integers:

(define (sum-odd-squares tree)
  (if (leaf-node? tree)
      (if (odd? tree)
          (square tree)
          0)
      (+ (sum-odd-squares (left-branch tree))
         (sum-odd-squares (right-branch tree)))))

• And contrast with collecting the odd Fibonacci numbers:

(define (odd-fibs n)
  (define (next k)
    (if (> k n)
        '()
        (let ((f (fib k)))
          (if (odd? f)
              (cons f (next (1+ k)))
              (next (1+ k))))))
  (next 1))

• sum-odd-squares: enumerate leaves → filter odd? → map square → accumulate +, 0.
• odd-fibs: enumerate interval → map fib → filter odd? → accumulate cons, '().
• These are similar, but the commonality is obscured by how we wrote the procedures.

# Defining streams

• The arrows between the boxes represent data structures called streams.
• (cons-stream x y) and the-empty-stream construct streams.
• For any x and y, (head (cons-stream x y)) is x.
• For any x and y, (tail (cons-stream x y)) is y.
• We can define higher-order procedures like we did for lists:

(define (map-stream proc s)
  (if (empty-stream? s)
      the-empty-stream
      (cons-stream (proc (head s))
                   (map-stream proc (tail se)))))

# Using the language

• Now we can reimplement those problems with explicit stream processing:

(define (sum-odd-squares tree)
  (accumulate +
              0
              (map square
                   (filter odd
                           (enumerate-tree tree)))))
(define (odd-fibs n)
  (accumulate cons
              '()
              (filter odd
                      (map fib
                           (enumerate-interval 1 n)))))

• This reveals their commonality, and makes it easy to mix and match boxes.
• The advantage of stream processing is that it establishes conventional interfaces.
• Conventional interfaces are powerful because we can easily glue things together.

# Part 2

# More complicated stream processing

• Suppose we have a stream of streams $\{\{1,2,3,\dots\},\{10,20,30,\dots\},\dots\}\htmlClass{math-punctuation}{\text{.}}$
• We can define a procedure flatten to accumulate them into a single flat stream.
• Problem: Given $N\htmlClass{math-punctuation}{\text{,}}$ find all pairs $0<j<i≤N$ such that $i+j$ is prime.

(define (prime-sum-pairs n)
  (map
   (lambda (p)
     (list (car p) (cadr p) (+ (car p) (cadr p))))
   (filter
    (lambda (p)
      (prime (+ (car p) (cadr p))))
    (flatmap
     (lambda (i)
       (map
        (lambda (j) (list i j))
        (enumerate-interval 1 (-1+ i))))
     (enumerate-interval 1 n)))))

• flatmap takes the place of nested loops in most other languages.
• We can simplify it with syntactic sugar collect:

(define (prime-sum-pairs n)
  (collect
   (list i j (+ i j))
   ((i (enumerate-interval 1 n))
    (j (enumerate-interval 1 (-1+ i))))
   (prime? (+ i j))))

# Eight queens puzzle

• Solving this typically uses a backtracking search, navigating up and down the tree of possibilities until we get to the bottom (all queens placed).
• This is unnecessary—it’s inordinately concerned with time.
• A simpler way is to employ wishful thinking and go from $k$ columns to $k+1$ columns.

(define (queens size)
  (define (fill-cols k)
    (if (= k 0)
        (singleton empty-board)
        (collect (adjoin-position try-row k rest-queens)
                 ((rest-queens (fill-cols (-1+ k)))
                  (try-row (enumerate-interval 1 size)))
                 (safe? try-row k rest-queens))))
  (fill-cols size))

• This gives us all solutions to the $k$-queens puzzle.
• We changed our view from things that evolve in time and have state to a global view where we’re not concerned with time.

# Part 3

# Streams are not lists

• By now you should be suspicious—what’s the catch?
• Problem: Find the second prime between 10,000 and 1,000,000.
• Stream solution: enumerate 10,000 to 1,000,000 → filter prime? → take 2nd.
• This is ridiculously inefficient. Our earlier programs (before streams) were ugly because they mixed all the operations up, but because of this they were efficient.
• But we can have our cake and eat it too! We can make it just as efficient.
• The key to this is that streams are not lists.

# Implementing streams

• We want the stream to compute itself incrementally, to be an “on demand” data structure.
  • (cons-stream x y) is an abbreviation for (cons x (delay y))
  • (head s) is (car s)
  • (tail s) is (force (cdr s))
• delay creates a promise to compute something when force d.
  • (delay expr) is an abbreviation for (lambda () expr)
  • (force p) is (p)
• delay decouples the apparent order of events from the actual order of events that happen in the machine. We give up the idea that our procedures mirror some clear notion of time.
• One little hack: to be efficient, (delay expr) is (memo-proc (lambda () expr)).

(define (memo-proc proc)
  (let ((already-run? nil) (result nil))
    (lambda ()
      (if (not already-run?)
          (sequence (set! result (proc))
                    (set! already-run? (not nil))
                    result)
          result))))

• Streams blur the line between data structures and procedures.