Systems with generic operations

Lesson 07 took one family — complex numbers — and let it wear many representations, dispatched through an operation/type table by apply_generic. It deliberately dodged one question: what does add mean when its two arguments carry different tags? This lesson builds the answer into a whole layered arithmetic system: ordinary numbers, rational numbers, and complex numbers stacked on the same dispatcher, with one generic add/mul that works across them. Mixing types forces coercion and a type tower, and raises the question of where that cross-type logic should live. Underneath it all sits the structural tension that will haunt every large system you build: adding a new type versus adding a new operation — the expression problem, in embryo.

1 · A layered arithmetic on one dispatcher

We reuse Lesson 07's machinery verbatim — attach_tag/type_tag/contents, the put/get table, and apply_generic. Now the operations are arithmetic, and the types are kinds of number. The user-facing generic operations are one line each:

const add = (x, y) => apply_generic("add", x, y);
const mul = (x, y) => apply_generic("mul", x, y);
const equ = (x, y) => apply_generic("equ", x, y);

Each number kind is an install package that registers its column, mentioning no other type — exactly the discipline from Lesson 07. Note apply_generic dispatches on the tags of all arguments here (the key includes every operand's tag), because arithmetic is binary.

// --- integers: the tower's bottom rung (a "real" package mirrors this one rung up) ---
const install_integer = () => {
  const tag = x => attach_tag("integer", x);
  put("add", ["integer","integer"], (a, b) => tag(a + b));
  put("mul", ["integer","integer"], (a, b) => tag(a * b));
  put("equ", ["integer","integer"], (a, b) => a === b);
};
// --- rational numbers: contents is [n, d] ---
const install_rational = () => {
  const tag = (n, d) => attach_tag("rational", [n, d]);
  put("add", ["rational","rational"], ([n1,d1],[n2,d2]) => tag(n1*d2 + n2*d1, d1*d2));
  put("mul", ["rational","rational"], ([n1,d1],[n2,d2]) => tag(n1*n2, d1*d2));
};
// --- complex numbers: reuses Lesson 07's selectors internally ---
const install_complex = () => {
  const tag = z => attach_tag("complex", z);
  put("add", ["complex","complex"], (z1, z2) => tag(/* add components */ z1));
  put("mul", ["complex","complex"], (z1, z2) => tag(/* mul mags, add angles */ z1));
};

Here apply_generic("add", ...) keys on the tuple of argument tags. We must generalize the dispatcher slightly so the key reflects every operand:

const apply_generic = (op, ...args) => {
  const tags = args.map(type_tag);
  const fn   = get(op, tags);              // key = op + tuple of tags
  if (fn) return fn(...args.map(contents));
  // ...the interesting case (different tags) handled in §3
  throw new Error(`no method ${op} for [${tags}]`);
};

So far this is just Lesson 07 with more types. add(rational, rational) and add(complex, complex) each find their cell. The system is layered: complex numbers can even contain rational parts, because their parts are themselves manipulated by the generic add/mul — the recursion the dispatcher enables.

2 · The wall — mixed types have no cell

3 · Coercion — and why pairwise coercion is not enough

Coercion is converting a value of one type into an equivalent value of another, so that a mixed call collapses to a same-type call. The first idea is a coercion table keyed by (from-type, to-type):

const _coerce = new Map();
const put_coercion = (from, to, fn) => _coerce.set(from + "->" + to, fn);
const get_coercion = (from, to)     => _coerce.get(from + "->" + to);

put_coercion("integer", "complex", x => make_complex(x, 0));     // 5 -> 5+0i
put_coercion("rational", "real", ([n,d]) => make_real(n/d));      // 1/2 -> 0.5

Then apply_generic, on a two-argument miss, tries to coerce one operand to the other's type and retry:

// inside apply_generic, when get(op, [t1, t2]) misses and t1 !== t2:
const t1c = get_coercion(t1, t2);
if (t1c) return apply_generic(op, t1c(contents(a1)), a2);  // lift a1 to t2, retry
const t2c = get_coercion(t2, t1);
if (t2c) return apply_generic(op, a1, t2c(contents(a2)));  // lift a2 to t1, retry

4 · The type tower — and where coercion belongs

The number types are not an unstructured set; they form a chain by inclusion. Every integer is a rational; every rational is a real; every real is a complex number:

  complex          (most general — sits at the top)
     ^  raise
  real
     ^
  rational
     ^
  integer          (most specific — sits at the bottom)

Instead of t² pairwise coercions we define just one step per level: raise, which lifts a value to the type one rung above it. Any coercion is then a composition of single steps along the tower — to add operands of different levels, repeatedly raise the lower one until the two tags match, then dispatch to the same-type cell that already exists.

const install_raise = () => {
  put("raise", ["integer"],  n => make_rational(n, 1));
  put("raise", ["rational"], ([n,d]) => make_real(n / d));
  put("raise", ["real"],     x => make_complex(x, 0));
  // complex has no raise — it is the top
};
const raise = x => apply_generic("raise", x);

// level maps a tag to its rung index in the tower (0 = bottom, integer):
const level = t => ["integer","rational","real","complex"].indexOf(t);

// the new mixed-type rule, replacing the pairwise block in apply_generic:
const apply_generic_with_tower = (op, a, b) => {
  const [ta, tb] = [type_tag(a), type_tag(b)];
  if (ta === tb) return get(op, [ta,tb])(contents(a), contents(b));
  if (level(ta) < level(tb)) return apply_generic_with_tower(op, raise(a), b);
  else                       return apply_generic_with_tower(op, a, raise(b));
};

add(int 3, complex 2+1i)
  tags differ; level(integer)=0 < level(complex)=3  -> raise the integer
  raise(int 3)      -> rational 3/1
  add(rational 3/1, complex 2+1i)
    raise(rational 3/1) -> real 3.0
    add(real 3.0, complex 2+1i)
      raise(real 3.0)   -> complex 3+0i
      add(complex 3+0i, complex 2+1i)
        tags match -> get("add",["complex","complex"]) -> complex 5+1i
  = complex 5+1i

Where does coercion live? Not inside any arithmetic package — a package must mention only its own type, or additivity from Lesson 07 dies. Not hard-wired pairwise into each operation. It lives in one place: the dispatcher's mixed-type rule, parameterized by the raise table. That keeps each type's package self-contained and makes "how types relate" a single, separately-maintained concern. (Symmetrically, drop / lowering simplifies results back down — 5+0i can become the integer 5 — but only the raising direction is needed to dispatch.)

5 · Generic coefficients, and the expression problem

Because the operations are generic, the layer can be stacked again. A polynomial is a list of terms, and its arithmetic uses generic add/mul on the coefficients — which can therefore be ordinary numbers, rationals, complex numbers, or polynomials themselves. Polynomials become just another type registered in the table:

const install_polynomial = () => {
  // term-by-term, using GENERIC add/mul on coefficients — they may be any type
  put("add", ["poly","poly"], (p1, p2) => tag(add_terms(p1, p2)));  // add_terms calls add(...)
  put("mul", ["poly","poly"], (p1, p2) => tag(mul_terms(p1, p2)));
};
// a polynomial whose coefficients are complex numbers "just works" —
// each coefficient add bottoms out in the complex "add" cell via apply_generic.

Now stand back at the whole table — operations down the side, types across the top. There are exactly two ways to grow it, and they pull against each other:

This is the expression problem: no single decomposition makes both "add a type" and "add an operation" free without editing existing code. The operation/type table makes types cheap (a new column slots in) but operations costly (a new row touches every column); the message-passing dual flips it. Every architecture you meet later — interpreters, the visitor pattern, type classes — is one more answer to this same tension. SICP does not "solve" it; it shows you the two poles and that the table at least makes the costs explicit and additive in one direction.

Common mistakes / failure modes

Checkpoint exercise

// (a) Add a generic operation `negate(x)` to the WHOLE system.
//     How many existing packages must you edit? Which axis of the
//     expression problem is this?
// (b) Add a new TYPE "gaussian" (integers a+bi) that sits between
//     real and complex. How many cells/rungs, and what existing code
//     changes?

Where this points next

We now have a richly layered system — generic operations, coercion, a tower, recursive coefficients — and it is built entirely from the tools of Parts I and II: functions, pairs, tags, and tables. Crucially, everything so far is purely functional. Every value means one fixed thing; make_rational(1,2) denotes the same rational forever; the substitution model from Lesson 01 still explains every program by replacing expressions with their values. But real systems model objects — a bank account, a counter, a circuit — whose identity persists while their state changes over time. You cannot express "the same account, now with less money" with values that never change. To model identity-through-change you must add assignment — and assignment detonates the substitution model, because a name no longer denotes a single value. Lesson 09 introduces local state and assignment, watches substitution break on a specific step, and thereby creates the pressure for an entirely new model of evaluation.

Interview prompts

• How does a generic-arithmetic system reuse a single dispatcher across many number types? (§1 — each type is an install package registering same-tag cells in the operation/type table; user-facing add/mul route through apply_generic, which keys on the tuple of all operand tags.)
• What breaks when you add operands of different types? (§2 — there is no table cell for the tag tuple; enumerating every cross-type cell is O(m·t²) and adding a type means O(2·m·t) new mixed cells — quadratic explosion.)
• What is coercion, and why is a flat pairwise coercion table insufficient? (§3 — converting one type to another so a mixed call collapses to same-type; pairwise tables are again O(t²), and flat entries don't enforce transitive consistency.)
• Explain the type tower and how raise resolves a mixed call. (§4 — types form an inclusion chain; one raise per rung (O(t)); the dispatcher repeatedly raises the lower operand until tags match, then dispatches to the same-type cell; coercions compose consistently along the chain.)
• Where should coercion live, and why not in a package? (§4 — in the dispatcher's mixed-type rule, parameterized by the raise table; putting it in a package couples that package to others and destroys additivity.)
• State the expression problem using this system. (§5 — the table makes a new type (column) cheap but a new operation (row) costly, touching every type; message passing flips the costs; no single decomposition makes both extensions free without editing existing code.)
• Why does this system stay purely functional, and what forces that to end? (§ where-next — every value denotes one fixed thing and the substitution model still holds; modeling objects with identity that persists through change requires assignment, which makes a name no longer denote a single value and breaks substitution → Lesson 09.)