Hierarchical data and conventional interfaces

Lesson 04 built a single pair behind an abstraction barrier and, at the end, named the property that makes it explosive: the closure property — a pair may contain a pair. This lesson cashes that in. Because pairs nest, the one mechanism from Lesson 04 builds unbounded structure: lists, then trees, then arbitrary hierarchies. But unbounded structure is useless if every program that walks it is a bespoke recursive loop. So the second, bigger idea: process all of it through a small set of conventional interfaces — map, filter, accumulate — viewed as a signal-flow pipeline (enumerate → filter → map → accumulate). That view makes programs snap together like plumbing instead of tangling into nested loops.

1 · Lists are nested pairs

Carry over pair/head/tail from Lesson 04. A list is just a right-nested chain of pairs ending in a marker, null (the empty list). The list 1, 2, 3 is pair(1, pair(2, pair(3, null))): each pair's head is an element, its tail is the rest of the list. The closure property is doing all the work — the tail slot holds another pair.

const nil = null;
function list(...xs) {                     // sugar: build a chain of pairs
  let acc = nil;
  for (let i = xs.length - 1; i >= 0; i--) acc = pair(xs[i], acc);
  return acc;                              // list(1,2,3) === pair(1,pair(2,pair(3,nil)))
}
function isEmpty(s) { return s === nil; }

// walking a list is structural recursion: do head, recurse on tail
function length(s) { return isEmpty(s) ? 0 : 1 + length(tail(s)); }

list(1,2,3)  =   [ 1 | *-]--->[ 2 | *-]--->[ 3 | / ]
                   ^   ^                          ^
                 head tail(->rest)             tail = nil

2 · Three conventional interfaces

Almost every list program does one of three things, so we name them once and reuse them everywhere. A conventional interface is a small, fixed vocabulary that many operations are expressed in — instead of each program inventing its own recursion.

// map: transform every element (same length out)
function map(f, s) {
  return isEmpty(s) ? nil : pair(f(head(s)), map(f, tail(s)));
}
// filter: keep elements passing a predicate (shorter out)
function filter(pred, s) {
  if (isEmpty(s)) return nil;
  return pred(head(s)) ? pair(head(s), filter(pred, tail(s)))
                       : filter(pred, tail(s));
}
// accumulate (fold): collapse the whole list to one value with a binary op
function accumulate(op, init, s) {
  return isEmpty(s) ? init : op(head(s), accumulate(op, init, tail(s)));
}
// e.g. accumulate((a,b)=>a+b, 0, list(1,2,3)) === 6

The crucial property: each takes a sequence and returns a sequence (or a summary), so their output type matches the next one's input type. That single uniformity is what lets them chain — and chaining is the whole game.

3 · The signal-flow view — why pipelines compose

SICP's metaphor: think of a list program as a signal-processing pipeline, like wiring electrical components. Data flows left to right through independent stages, each with one job:

  source ──> ENUMERATE ──> FILTER ──> MAP ──> ACCUMULATE ──> answer
            (make signal) (keep some) (transform) (combine to one)
              a tree        a pred      a fn        op + init

Because every stage's output is a sequence (until the final accumulate), you can reorder, insert, or delete stages without rewriting the others — exactly as you re-plumb pipe segments. Each stage is testable in isolation and reusable across programs. A hand-rolled recursive loop fuses enumerate-filter-map-accumulate into one tangled function where the four concerns are interleaved and inseparable; the pipeline keeps them as four independent boxes. That modularity is the payoff, and it is bought by the uniform sequence interface.

4 · Worked example — loop rewritten as a pipeline

function sumSqEven(s) {
  if (isEmpty(s)) return 0;
  const x = head(s);
  if (x % 2 === 0) return x * x + sumSqEven(tail(s));   // filter+map+accum fused
  return sumSqEven(tail(s));                              // filter (drop) fused in
}

function sumSqEven(s) {
  return accumulate((a, b) => a + b, 0,           // ACCUMULATE: sum
           map(x => x * x,                          // MAP: square
             filter(x => x % 2 === 0, s)));         // FILTER: keep evens
}
// trace on list(1,2,3,4):
//   filter even  -> list(2,4)
//   map square   -> list(4,16)
//   accumulate + -> 0 + 4 + 16 = 20

5 · Trees, nested mappings, and the picture language

The closure property does not stop at lists — a list element can itself be a list, giving a tree. Operations recur into both head and tail (assume a primitive isPair(x) that reports whether x is a pair rather than a leaf value):

// count leaves of a tree (nested lists), recurring into sublists
function countLeaves(t) {
  if (isEmpty(t)) return 0;
  if (!isPair(head(t))) return 1 + countLeaves(tail(t));   // a leaf
  return countLeaves(head(t)) + countLeaves(tail(t));      // a subtree
}

Nested mappings express "for each i, for each j" as a pipeline of maps whose results are flattened by accumulate — e.g. all pairs (i, j) with i > j up to n become map over i of (map over j), accumulated together, then filtered. The double loop becomes nested signal flow. The capstone of 2.2 is the picture language: a tiny set of operations on painters (beside, above, flip) that are themselves closed — the result of combining two painters is a painter you can combine again. It is the closure property applied to operations, not just data, and it is why a handful of primitives generates infinitely elaborate images. Same idea, one level up.

Common mistakes / failure modes

Checkpoint exercise

Where this points next

Look at everything we have processed: numbers in, numbers out. Lists of integers, sums of squares, products — the leaves of every structure so far have been values to be evaluated. But a program that does algebra, or compresses text, or manipulates expressions, needs to treat a name as data — to hold the symbol x itself, not the number x stands for. Lesson 06 lifts exactly that hidden rule "data must be evaluated to a value": with quotation we can refer to a symbol instead of its value, and suddenly the same pairs and the same conventional interfaces process representations — differentiating an expression by rewriting its tree, building sets, encoding Huffman trees. Dropping the must-evaluate rule is the pressure that forces symbolic data.

Interview prompts

• How is a list built from pairs, and why does the closure property matter? (§1 — a list is right-nested pairs ending in nil; the closure property (a pair's tail may be a pair) is what lets one mechanism build arbitrary-length structure.)
• Define map, filter, and accumulate and say what makes them "conventional." (§2 — transform each / keep some / collapse to one; they are conventional because their sequence-in/sequence-out uniformity lets many programs share the same vocabulary instead of inventing recursion.)
• Explain the signal-flow metaphor and why it yields composability. (§3 — enumerate → filter → map → accumulate as pipe stages; each stage's output is a sequence matching the next's input, so stages can be reordered/inserted/tested independently like plumbing.)
• Rewrite a recursive "sum of squares of evens" loop as a pipeline; what is gained? (§4 — accumulate(+,0, map(square, filter(even, s))); the gain is four reusable, separately testable boxes vs one fused loop — changing the rule becomes local edits, no recursion touched.)
• What is the right seed for accumulate and why does it matter? (§Common mistakes — the operation's identity (0 for +, 1 for ×); a wrong seed (0 for ×) silently corrupts every result.)
• How does the picture language demonstrate the closure property? (§5 — its painter operations (beside/above) return painters, so combinations are themselves combinable — closure applied to operations, letting a few primitives generate infinite images.)
• In general, why is filter-then-map not the same as map-then-filter? (§Checkpoint — map can change whether the predicate holds, so applying it before the filter tests different values; keep the conventional enumerate→filter→map→accumulate order.)