Data abstraction

Lesson 03 made functions first-class so we could name a pattern of behavior — pass a function in, return one out, capture a general method like sum or Newton's method. But real programs do not just transform numbers; they manipulate compound objects — a rational number, a point, a line segment, an interval. We need a way to glue parts into a whole and then forget how the glue works. This lesson builds that wall: a data abstraction is a contract between constructors and selectors separated by an abstraction barrier, and the punchline — the procedural representation of pairs — shows that the glue itself can be made out of nothing but the first-class functions from Lesson 03. Data turns out to be behavior in disguise.

1 · Rational numbers from a constructor and two selectors

A rational number is two integers — a numerator and a denominator — treated as one thing. Suppose JavaScript gives us a primitive glue, pair(a, b), with two extractors head and tail (these are SICP's cons/car/cdr renamed). We define three operations and pretend, for now, the glue is given:

// constructor: build a rational from a numerator and denominator
function make_rat(n, d) { return pair(n, d); }
// selectors: read the parts back out
function numer(x) { return head(x); }
function denom(x) { return tail(x); }

// operations defined ENTIRELY in terms of the three above — never head/tail directly
function add_rat(x, y) {
  return make_rat(numer(x) * denom(y) + numer(y) * denom(x),
                  denom(x) * denom(y));
}
function mul_rat(x, y) {
  return make_rat(numer(x) * numer(y), denom(x) * denom(y));
}
function print_rat(x) { return numer(x) + "/" + denom(x); }

The discipline is the whole point: add_rat never says head(x), only numer(x). It is written against the names of the operations, not their implementation. That separation is an abstraction barrier — an imaginary horizontal line. Above it live programs that use rationals (they know only make_rat, numer, denom); below it lives the representation (today, a pair). Each layer talks only to the layer directly beneath it.

2 · The barrier diagram and the contract

       programs that use rationals      (add_rat, mul_rat, print_rat)
   ----------- rationals in problem domain -----------   <-- barrier 1
       make_rat   numer   denom            (the abstract data type)
   ----------- rationals as pairs --------------------   <-- barrier 2
       pair   head   tail                  (the chosen representation)
   ----------- however pairs are implemented ---------

The barrier is enforced by a single contract that constructor and selectors jointly promise: whatever make_rat packs in, numer and denom get back out. Formally, for all integers n, d (with d ≠ 0):

Any pair of implementations that honors this contract is a valid rational. Clients above barrier 1 cannot tell which one you picked — and that is exactly the freedom we cash in next. The contract is what the client depends on; the representation is what it is forbidden to depend on.

3 · Worked example — change the representation, touch zero clients

Our current rationals do not reduce to lowest terms: add_rat of 1/2 and 1/2 yields 4/4, not 1/1. Reduction by the greatest common divisor belongs below the barrier, and there are two places to put it. Both honor the contract, so both are invisible to clients.

function make_rat(n, d) {
  const g = gcd(Math.abs(n), Math.abs(d));   // gcd from Lesson 02 (Euclid)
  return pair(n / g, d / g);                  // stored already reduced
}
function numer(x) { return head(x); }
function denom(x) { return tail(x); }

function make_rat(n, d) { return pair(n, d); }  // store raw
function numer(x) { return head(x) / gcd(head(x), tail(x)); }
function denom(x) { return tail(x) / gcd(head(x), tail(x)); }

print_rat(add_rat(make_rat(1,2), make_rat(1,2)))

  Choice A:  make_rat(1,2)->1/2 ; make_rat(1,2)->1/2
             add_rat -> make_rat(1*2+1*2, 2*2)=make_rat(4,4)
             make_rat reduces 4/4 (gcd 4) -> stored 1/1   ->  "1/1"
  Choice B:  make_rat stores 1/2, 1/2 raw
             add_rat -> make_rat(4,4) stored raw
             numer reduces 4/4 -> 1 ; denom -> 1          ->  "1/1"

4 · What is data? — the procedural representation of pairs

We leaned on a primitive pair. But what is a pair, really? Here is the move that Lesson 03 set up: we can build pair, head, and tail out of nothing but functions. A pair is the only thing it needs to be — something that, given a way to ask, will hand back the right part.

// a pair is a FUNCTION that, given a selector index, returns the chosen part
function pair(a, b) {
  return function dispatch(i) {        // closes over a and b
    if (i === 0) return a;
    if (i === 1) return b;
    throw new Error("pair: bad index " + i);
  };
}
function head(p) { return p(0); }       // ask for part 0
function tail(p) { return p(1); }       // ask for part 1

There is no record, no array, no field anywhere — a and b live only as captured variables inside the closure dispatch. Trace it: head(pair(3, 4)) = pair(3,4)(0) = dispatch(0) with a=3, b=4 = 3. The contract head(pair(a,b)) === a holds purely by how the closure behaves. This is the deep claim: data is defined by the operations that act on it, not by any storage layout. "Pair-ness" is the contract head(pair(a,b))===a and tail(pair(a,b))===b — and behavior alone satisfies it. Above the barrier nothing can tell this implementation from the primitive one; the abstraction is total. Data and procedures are the same kind of thing seen from two sides.

5 · A second example — interval arithmetic and a subtle trap

An interval models a quantity known only within bounds, e.g. a resistor of 10 ohms ± 5%. Constructor and selectors:

function make_interval(lo, hi) { return pair(lo, hi); }
function lower(i) { return head(i); }
function upper(i) { return tail(i); }
function add_interval(x, y) {
  return make_interval(lower(x) + lower(y), upper(x) + upper(y));
}
function mul_interval(x, y) {          // widest product of the four corner cases
  const ps = [lower(x)*lower(y), lower(x)*upper(y),
              upper(x)*lower(y), upper(x)*upper(y)];
  return make_interval(Math.min(...ps), Math.max(...ps));
}

Common mistakes / failure modes

Checkpoint exercise

Where this points next

A pair is one barrier wrapping two parts — but notice we never said the parts had to be numbers. A part can itself be a pair. That single observation, the closure property (the result of combining things can itself be combined the same way — pairs of pairs of pairs), is what turns one tiny gluing mechanism into the power to build structures of unbounded size and shape: lists, trees, arbitrary hierarchies. Lesson 05 takes that pressure head-on: with the closure property, the single pair we just built becomes the foundation for all hierarchical data, processed through conventional interfaces (map/filter/accumulate) that make programs compose like plumbing. One mechanism, unbounded structure — that is what forces the next lesson.

Interview prompts

• What is an abstraction barrier, and what does it let you change? (§2 — a line separating clients (which know only constructors/selectors) from the representation; you may swap the representation freely as long as the constructor/selector contract holds, touching no client.)
• State the contract between make_rat, numer, and denom. (§2 — numer(make_rat(n,d))/denom(make_rat(n,d)) equals n/d; any pair of implementations honoring it is a valid rational.)
• Show the same client works whether you reduce at construction or at selection. (§3 — both honor the contract, so add_rat/print_rat are unchanged; only the cost moves — once per build vs once per read.)
• Implement a pair using only functions. What does it prove? (§4 — pair returns a dispatch closure over a,b; head=p(0), tail=p(1); it proves data is defined by its operations, not by storage — data is behavior.)
• Why is reducing fractions a representation concern, not a client concern? (§3 — it depends on how rationals are stored/read; lift it above the barrier and every client must repeat it, and you lose freedom to change the policy.)
• Why does sub_interval(A, A) not yield zero? (§5 — the abstraction treats the two operands as independent uncertainties, so it widens; a correct contract can still encode a model whose independence assumption is wrong.)
• How does the closure property turn one pair into unbounded structure? (§Where next — because a pair's part may itself be a pair, the same mechanism nests arbitrarily, giving lists and trees of any size — the basis of hierarchical data in Lesson 05.)