Design examples in SICP

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


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