# Design examples in SICP

*Structure and Interpretation of Computer Programs* (SICP), by
Harold Abelson and Gerald Jay Sussman, is packed with good software
designs.
## Streams

Many computations can be viewed as streams of information passing through
computational units. Each component is simple and general but their
combinations are limitless.
Suppose we want to write a function which sums the squares of the odd
leaves in a tree. Here's a first implementation:

;; For each leaf of the tree, pick the ones that are odd,
;; square them, and add the results.
(define (sum-odd-squares tree)
(if (leaf? tree)
(if (odd? tree) (square tree) 0)
(+ (sum-odd-squares (left-branch tree))
(sum-odd-squares (right-branch tree)))))

Here's what it looks like using streams:

(define (sum-odd-squares tree)
(accumulate + 0
(map square
(filter odd
(leaves tree)))))

Note that the code is now its own documentation. Only a graphical language
could make it clearer. The computational primitives
`accumulate`

, `map`

, `filter`

, and
`leaves`

are general enough to construct many other functions.
For example, multiplying the odd Fibonacci numbers Fib(k), where k ranges
over the leaves of a tree:
(define (mul-odd-fibs tree)
(accumulate * 1
(filter odd
(map fib
(leaves tree)))))

PLE used this example to demonstrate functional programming.
Entire languages (e.g. APL, FP) have been built around this pattern.

The UNIX shell is good example of this approach. It points out another
benefit: the computational units are independent enough to be implemented
by different people or even in different languages. It is commonplace and
natural to pipe a shell command into a C program into a Perl script into
Tcl/Tk. This approach puts the value in the design, not the
implementation.

Thomas Minka
Last modified: Tue Apr 25 09:54:07 GMT 2006