# 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?

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

- Create a list of all odd Fibonnacci numbers smaller than (or equal to) the
k
^{th}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.

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

- Create a list of all odd Fibonnacci numbers smaller than (or equal to) the
k
^{th}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$ , find all pairs $0<j<i\leq N$ s.t. $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.