SICP 6a
Streams I

Table of Contents

Maybe the real reason that we pay such a price to mirror our new view of reality, is that we have the wrong view of reality. Maybe time is just an illusion, and nothing ever changes.

Stream processing is another method we can wield to decompose systems. To show why adding yet another method of decomposition is useful, let's contrast and compare two procedures.

1 Why?

  1. Calculate the sum of the square of odd numbers in the leaves of a tree.
(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)))))
  1. Create a list of all odd Fibonnacci numbers smaller than (or equal to) the kth Fibonacci number.
(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))

To better visualise what is happening in the above two procedures, draw the diagrams. 

enumerate —> filter —> map —> accumulate
 leaves       odd?    square    + 0 

enumerate —> map —> filter —> accumulate
interval  fibonacci  odd?      cons ()

From the diagrams, it is blatant that the two procedures are structurally similar; in the code, this similarity is nowhere to be found.

2 Streams

To represent the way of thinking demonstrated in the diagrams, invent a new language. The arrows in the diagrams will be called streams. A stream is a data abstraction.

2.1 Earth, water, air, fire

Four minimal elements are required. 

the-empty-stream
(cons-stream x y)
(head s)
(tail s)

For any x and y (in exactly the same way as lists with cons car cdr): 

(head (cons-stream x y))
x
(tail (cons-stream x y))
y

2.2 Map, filter, etc.

On top of these building blocks, build the basic pieces.

map-stream (essentially identical to map) 

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

filter 

(define (filter pred s)
  (cond
   ((empty-stream? s) the-empty-stream)
   ((pred (head s))
    (cons-stream (head s)
                 (filter pred
                         (tail s))))
   (else (filter pred (tail s)))))

accumulate 

(define (accumulate combiner init-val s)
  (if (empty-stream? s)
      init-val
      (combiner (head s)
                (accumulate combiner
                            init-val
                            (tail s)))))

enumerate-tree 

(define (enumerate-tree tree)
  (if (leaf-node? tree)
      (cons-stream tree
                   the-empty-stream)
      (append-streams
       (enumerate-tree
        (left-branch tree))
       (enumerate-tree
        (right-branch tree))))))

append-streams 

(define (append-streams s1 s2)
  (if (empty-stream? s1)
      s2
      (cons-stream
       (head s1)
       (append-streams (tail s1)
                       s2))))

enum-interval 

(define (enum-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream
       low
       (enum-interval (1+ low) high))))

3 Procedures reimplemented

Let's rewrite the two procedures using the newly invented streams.

  1. Calculate the sum of the square of odd numbers in the leaves of a tree.
(define (sum-odd-squares-tree)
  (accumulate
   +
   0
   (map
    square
    (filter odd
            (enumerate-tree tree)))))
  1. Create a list of all odd Fibonnacci numbers smaller than (or equal to) the kth Fibonacci number.
(define (odd-fibs n)
  (accumulate
   cons
   '()
   (filter
    odd
    (map fib
         (enum-interval 1 n)))))

Much better. Conventional interfaces act as glue, allowing us to easily piece procedures together.

4 Flex

Take a look at two more complicated examples. Will first need to be able to flatten a stream of streams. 

(define (flatten st-of-st)
  (accumulate append-streams
              the-empty-stream
              st-of-st))

(define (flatmap f s)
  (flatten (map f s)))

4.1 Prime sum pairs

Given N 𝑁 N , find all pairs 0 < j < i ≤ N 0 𝑗 𝑖 𝑁 0<j<i\leq N s.t. i + j 𝑖 𝑗 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))
            (enum-interval 1 (-1+ i))))
         (enum-interval 1 n)))))

Flatmaps replace the functionality provided by nested loops in other languages.

It is also possible to write the above procedure using collect (synctatic sugar). 

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

4.2 Eight queens problem

Place eight queens on a chessboard, so that no queen more take another queen. 

(safe? <row> <column> <rest-of-positions>)

Back-tracking is the traditional method to solve this problem. First place the first queen on the first column, first row square and check for safeness. Take the second queen and place it on the first column, first row square and check for safeness, and keep repeating until the second queen is safe. Then take the third queen…

Back-tracking is convoluted because of time. If we disregard time, the problem becomes a lot simpler. Assume k-1 columns have been filled, then only look at the safe spaces. 

(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 (enum-interval 1 size)))
      (safe? try-row k rest-queens))))
  (fill-cols size))

The above procedure provides all the solutions to the eight queens problem.

5 Catch?

So what's the catch?

Find the second prime between 10,000 and 1,000,000. 

(head
 (tail (filter
        prime?
        (enum-interval 10000 1000000))))

Ridiculous.

In traditional programming, the very thing that makes it conceptually ugly, makes it efficient.

It seems that all I've done this morning so far is just confuse you. I showed you this wonderful way that programming might work, except that it doesn't.

6 Promises

But we can have our cake and eat it. The key is that streams ≠ lists.

(cons-stream x y) (cons x (delay y))
(head s) (car s)
(tail s) (force (cdr s))

delay takes an expression and produces a promise to compute the expression when you ask for it.

force calls on that promise.

How on earth do we implement delay and force? Quite simply.

(delay <exp>) (lambda () <exp>)
(force p) (p)

Promises allow the decouplement of the apparent order of events in programs from the actual order of events in the computer.

7 Memoisation

delay is actually an abbrevation for 

(memo-proc (lambda () <exp>))

memo-proc takes a procedure of no arguments and transforms it into a procedure which is only ever run once. The result of memo-proc is a new procedure, which runs the original procedure the first time it is called, remembers the outcome, and from then on, will provide the cached outcome. 

(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))))

This hack is called memoisation.

Since data ≈ procedure, iteration control can be built into streams.

Christian Christiansen