Building with boxes

Add one third to one third, holding each fraction as a pair of whole numbers, and a naive program prints 6/9. That answer is not wrong, because six ninths equals two thirds, and nothing in the addition misfired. The addition computed one times three plus one times three over three times three, which is the schoolbook rule.

A representation is a way of storing a value together with the rules for reading it back, and this one merely admitted two names for a single number. Only the constructor, the procedure that builds a fraction out of two whole numbers, needed to change. The source records the consequence exactly: the modification was accomplished by changing the constructor without changing any of the procedures that implement the actual operations [S:13:146]. !The same scorer above the barrier, two representations below it. The scorer asks only for the size, the elapsed seconds of an item and the recorded minutes of an item. Below the line, one implementation stores twelve rows and the other stores two columns; both answer the three questions, so the scorer's text stays the same and the scores stay 1/3 and 1/4. Status: schematic.

That sentence answers the question this section asks: how do you use a part without reading its insides? Suppose you want to use the fraction code without reading it, which is the ordinary condition of anybody employing a part written by somebody else. What protects you is not the code but the collection of operations it exposes, together with the meaning of each one. !One line crosses the barrier. With the table stored as two columns, table(0)(1) is 40, the second elapsed time, so a count of seconds is charged against a recorded answer; table(1)(1) is 0, which happens to be the right answer for that row; item 2 asks for table(2), and the program stops with an index error. The crossing is legal in the language and silent for two rows. Status: schematic.

An interface describes what a data structure does, while an implementation describes how the data structure does it [S:10:18]. A data structure is a way of holding a collection of values in a program, together with the operations that read and change it. The line separating the two is an abstraction barrier, and the horizontal lines in the source's diagram represent barriers that isolate different levels of the system [S:13:147].

An interface is therefore a set of operations together with the meaning of each: what it may be handed, and what it returns. The meaning is not commentary on the operations, it is part of them, because two implementations that disagree about what an operation returns are not implementations of the same interface. Two that agree are indistinguishable from above the barrier, and choosing between them then becomes a question about cost rather than about correctness.

Worked example. The minutes table of the first section can be stored in two obvious ways. The first holds twelve rows, each row a pair with the seconds first and the recorded minutes second. The second holds two columns of twelve numbers, held as the pair (seconds column, minutes column).

Everything written against the table so far takes a row apart as it goes and expects twelve of them. Handed the columns it sees two items instead of twelve, and it reads numbers out of the wrong level.

Do not rewrite the programs that use the table, and do not widen its interface to expose the columns. Instead name three operations: how many items the table holds, the elapsed seconds of a given item, and the recorded minutes of a given item.

The scorer then asks rather than indexes. It requests the size, walks the indices from zero upward, and for each index requests the input and the recorded answer. Run it against the rows, and round down scores 1/3 while round to nearest scores 1/4. Run the identical scorer against the two columns and the two scores are 1/3 and 1/4 again. Between those two runs the text of the scorer is byte for byte the same, and the only thing that changed is which implementation of the three operations is in scope.

That is what a box buys you, and the comparison to a physical box breaks in one place. A box hides its contents because the cardboard is opaque, while a barrier hides a representation because everybody above it agreed to name only the operations. Nothing in the language enforces the agreement. The source is candid that the barrier is a discipline rather than a mechanism, and the discipline has exactly one failure mode.

The failure is worth seeing, because it is quiet. Write the charge inside the scorer as a direct index: the loop asks for item i, takes table[i] as the row, reads its second entry as the recorded answer. It asks the rule for its answer on the first entry, and compares the two. Against the rows this works, and it works because the row is a pair.

Against the columns it stays legal, because table[i][1] is still an index into something. For the first item the loop picks up the whole seconds column, so table[0][1] is 40, the second elapsed time. A count of seconds is charged against an answer recorded in minutes, and nothing is printed. For the second item table[1] is the whole minutes column, so table[1][1] is 0, which happens to be the right recorded answer for that row, and the mistake stays hidden one step longer. Only at the third index does the table run out of columns, and the program stops with an error that names an index rather than the mistake.

The first line crosses the barrier. Of the other two, one is right and one is wrong. Which one is wrong, and what does it charge for the first item stored as two columns?

The cost is small and it is paid once. The scorer makes two extra procedure calls per row, and each new representation must supply the operations again, so a wide interface is more work to implement than no interface at all. The benefit is that the choice of representation can be deferred, revisited and measured, and that the measurement is a count of operations rather than an argument about taste. One thing the barrier does not do is tell you which representation is correct, and the next section shows that sometimes the representation itself is the bug.

The formal statement. An interface is a set of operation names with the type of each, together with the meaning of each: what it accepts and what it returns [S:10:18]. Write the set of operations as the signature and the collection of conditions as the axioms. An implementation is any collection of procedures that interprets the signature and satisfies the axioms. The interface is the pair, and a bare list of names is not one, because two implementations that disagree about a return value are not implementations of the same thing [S:10:18].

An abstraction barrier is the line between the code that may use only the signature and the code that supplies an interpretation of it [S:13:147].

The derivation. Write the scorer as a term built from three operations: a size, a seconds selector and a minutes selector. The claim is that the term returns the same number under any two implementations that satisfy the axioms. Prove it by induction on the index. At index zero the charge is computed from the first row, which both implementations return identically. Assume the totals agree after k steps. Step k+1 adds one charge computed from the same two selected values, so the totals agree after k+1. At the end the total is divided by the same size, so the scores agree.

That argument is the content of the claim that the scorer's text is unchanged across representations, and it uses the axioms and nothing else. The step I omit is the induction principle itself, which Chapter 3 supplies.

An edge case. Consider the illegal line that indexes the row directly, taking the second entry as the recorded answer. Against the pair of columns this line is legal, because an index into an index is still a legal expression. At the first index the loop picks up the whole seconds column, so table[0][1] is 40, the second elapsed time, and a count of seconds is charged against an answer recorded in minutes. At the second index table[1][1] is 0, the first recorded answer, which happens to be right for that row. Nothing raises an error, because the expression has the right type and the value has the right shape. The failure appears at the third index as a complaint about a missing column, which names the symptom rather than the cause.

The case generalises. Axioms are universally quantified over indices, and a run checks finitely many of them, so no test suite establishes that an implementation is an implementation.

What L1 hid, and why that was safe there. L1 said the barrier is a promise between two pieces of your own program. The refinement is that the promise has to be written as conditions before it can be kept, and that its scope is every index, not the ones you tried. The worked example changed one implementation for another that agreed everywhere, so the universal reading and the tested reading gave the same answer.

Where the analogy breaks. Cardboard is opaque because of what it is made of. A barrier is opaque because everyone above it agreed to name only the operations, and nothing in the language enforces the agreement [S:13:147]. A box also hides its contents from its owner, while a barrier hides them only from the code above, which is why the implementer can still open the lid.

Where the idea comes from. The abstraction barrier is drawn in Structure and Interpretation of Computer Programs, section 2.1.2, using the rational-number package, with the two representations differing only in when the greatest common divisor is computed [S:13:149]. The section that follows asks what data is, and answers with selectors, constructors and conditions [S:13:151]. Open Data Structures states the same distinction in a sentence that this book borrows: an interface describes what a structure does, and an implementation describes how [S:10:18].

The footnote at the end of that section is the honest part. SICP remarks that the idea is difficult to formulate rigorously, and names two approaches: Hoare's abstract models, and algebraic specification, which treats the procedures as elements of an algebraic system whose behaviour is fixed by axioms [S:13:151]. The four-line contract of the first section and the axioms here are the same instrument used at two levels.

What the field has not settled. Whether a barrier can be enforced by a machine rather than by discipline. SICP notes that the choice of representation influences the programs above it, and that confinement to a few interface procedures is what makes a change cheap [S:13:149]. A type system or a module system can make some crossings fail to compile, and no mainstream system makes all of them fail. The open question is how much of the barrier a checker can hold. The evidence that would settle it is narrow and concrete: a module system in which the illegal direct index is rejected at compile time, while the same scorer text still runs unchanged against two representations.

What depends on it. Every deep learning framework uses the device. A module in PyTorch defines a forward propagation method that turns its input into output and stores its parameters, and modules combine into larger modules recursively [S:69:248]. The backward pass is supplied by automatic differentiation, so the author writes the forward pass and the parameters only [S:69:249]. A reader who has written a custom module has used an abstraction barrier, and has probably also reached through one to read a tensor's internals.

What to read next. Read SICP sections 2.1.1 and 2.1.2 in order, because the barrier becomes visible once the rational-number package has been built twice [S:13:149]. Read the interfaces section of Open Data Structures for the queue, stack and deque as three interfaces with many implementations [S:10:18]. Then read the footnote on abstract models, which is the shortest honest account in the corpus of why this idea resisted formalisation [S:13:151].