When code becomes data

A fourth reader of the notebook refuses to guess how the recorder rounded. She copies the notebook instead: twelve elapsed times, twelve recorded answers, stored side by side, plus a procedure that takes the seconds it is handed, finds that number among the twelve, and returns what was written beside it. When the number is not among the twelve, it returns 0. Score it and it is wrong zero times out of twelve, against four for round down and three for round to nearest.

That candidate raises a question the other three do not. Is the thing a program or a piece of data? The question sounds philosophical and it has a practical answer, which begins with a distinction already in use in this chapter. A program is a description of what to do, written as text: the text is the thing you can copy, store, compare and hand to somebody else. !A pair built without storage. The constructor receives 20 and 0, the first row of the minutes table, and returns a procedure that answers 0 with 20 and 1 with 0. The first selector applies that procedure to 0 and gets 20; the second applies it to 1 and gets 0. Both selector laws hold, and there is no structure to index. Status: schematic.

The thing it runs is a process, with a state and a duration, and the process exists only while the text executes. An object is a value a program can hold and pass around without caring what it is made of. Because text is an object like any other, a piece of text that describes steps can be stored, passed and returned. Then it is data in every sense the surrounding machinery cares about, because every operation that accepts data accepts it too.

So the boundary between code and data is a design choice rather than a fact about what things are made of, and the choice is made by whoever supplies the operations. The source states what data is with unusual economy: data is defined by some collection of selectors and constructors, together with specified conditions that these procedures must fulfil in order to be a valid representation [S:13:151]. A constructor builds an object out of other objects, and a selector takes one apart. The conditions are the third and least obvious part, and they are what turn three procedures with the right names into a representation of something.

Worked example. A pair glues two objects together so that both can be recovered. The condition is the whole of what a pair is: for any objects x and y, if z is built from x and y, then the first selector applied to z returns x and the second returns y [S:13:151]. Notice what that sentence does not mention: storage, memory, fields, or any arrangement of boxes.

Here is a pair built without any of those, and the construction uses a procedure in place of storage. The constructor hands back a procedure, and that procedure answers zero with the first object and one with the second. The first selector applies the returned procedure to zero, and the second applies it to one.

Take the first row of the minutes table, whose elapsed time is 20 and whose recorded answer is 0. The constructor receives 20 and 0 and returns a procedure that has remembered both numbers. The first selector applies that procedure to zero and receives 20. The second applies it to one and receives 0. Both halves of the condition hold, and nothing was stored in a structure that could be indexed, because there is no structure to index.

The source draws the conclusion in one sentence: access pairs using only the constructor and the two selectors, and you cannot distinguish this implementation from one that uses real data structures [S:13:152]. That claim is exact, and it holds for a reason rather than by luck. Everything above the barrier is entitled to ask only the two questions the condition names, and both implementations answer those two questions identically.

The cost is that a reader can no longer tell what a value is by looking at it, and the fourth reader's candidate shows why that matters, because the value's type no longer announces what operations it supports. It scores zero on the twelve rows because it copies them, and its answer on a thirteenth task is a default nobody chose. Whether that counts as a kept promise or an evasion depends on the fourth line of its contract, which the next section asks you to write.

The pair argument also leans on a rule about names that this chapter states without proof. A free name is a name a procedure uses but does not create. The procedure handed back keeps the values those names had where it was written, not where it is called, because the text does not mention the caller. If a language looked a free name up at the point of call, the argument would fail while all four rights of a first-class procedure survived intact.

The formal statement. Data is a collection of constructors and selectors together with the conditions those procedures must satisfy to be a valid representation [S:13:151]. For a pair the conditions are two equations: for any objects x and y, if z is built from x and y by the constructor, then the first selector applied to z returns x and the second returns y [S:13:151].

Write the constructor as a procedure that accepts a selector m and answers with x when m is zero and with y when m is one. Write the first selector as the procedure that applies its argument to zero, and the second as the procedure that applies its argument to one.

The derivation. Both conditions hold by substitution. Build z from x and y, apply the first selector, and the expression reduces to the body of the constructor with m replaced by zero, which is x. The second selector gives the body with m replaced by one, which is y. The two lines are the whole proof, and they use one rule: the returned procedure keeps the values its free names had where it was written.

Now the claim that no client can tell the difference. Take any expression built from the constructor and the two selectors, and evaluate it under both implementations. The operations agree on every argument pair, so by induction on the size of the expression the two values agree. The induction has one case per operation and no interesting step, which is why the claim looks stronger than it is. The step I omit is the substitution rule itself, and with it the assumption that the client uses only these three operations.

An edge case. The equivalence is indexed by the operation set, and by immutability. SICP states the second condition plainly: while nothing modifies a data object you may regard a compound object as the totality of its pieces, and that view fails once change enters [S:13:345]. Add a procedure that changes a pair in place, and the two implementations stop agreeing unless the procedural one gains a matching mutator, which requires a boxed cell rather than a closure over two values.

So the correct statement of L1's conclusion is narrower than it sounds: access pairs using only the constructor and the two selectors and you cannot distinguish the implementations [S:13:152], and the qualification is doing the work.

What L1 hid, and why that was safe there. L1 called the free-name rule a detail it stated without proof. The refinement is that the rule is the load-bearing step, not a footnote: without it the returned procedure would look up x and y where it is called, and both equations would fail. The worked example applied the selectors immediately, in the same scope, so a language with the other lookup rule would have passed it.

Where the analogy breaks. The phrase "code becomes data" suggests a conversion, and nothing converts. The text was an object before and after; what changes is which operations you permit on it, and who is allowed to supply them.

Where the idea comes from. Structure and Interpretation of Computer Programs asks what data is meant to be, and answers that it is a collection of selectors and constructors together with the conditions those procedures must fulfil [S:13:151]. It then implements pairs three ways with no data structure at all, and observes that a client using only the constructor and the two selectors cannot tell the implementations apart [S:13:152]. The implementation cost of that freedom is stated in the previous section: returning a procedure as a value requires reserving storage for its free variables while it is not executing [S:13:131].

The immutability condition has its own page. SICP notes that while nothing modifies a data object, a compound object may be regarded as the totality of its pieces, and that the view fails once change enters [S:13:345]. That remark is the boundary of the claim in this section, written by the same authors nine chapters later.

What the field has not settled. How complete a condition set must be. The axioms for a pair mention only the two selectors, and the claim of indistinguishability is relative to that list. SICP remarks that the underlying idea is difficult to formulate rigorously and names two approaches to doing it, Hoare's abstract models and algebraic specification [S:13:151]. What remains open in practice is deciding when a list of equations is long enough, since any finite list can be satisfied by two implementations that differ on an observation nobody wrote down. The evidence that settles a particular case is a pair of implementations that satisfies every stated condition and differs on one unstated observation, which shows the list was incomplete.

What depends on it. Automatic differentiation runs on the same trick at scale. A computation graph is a representation of a mathematical computation as data, which lets a program build a network, evaluate it, and later walk the same structure backwards to obtain gradients [S:88:28]. A model defined by a list of modules is another instance: the list is data, the modules are procedures, and the forward pass is the interpretation.

What to read next. Read SICP sections 2.1.1 to 2.1.3 in order, and stop at the footnote on abstract models, which is the corpus's clearest statement that this idea is hard to pin down [S:13:151]. Then read section 1.3 on procedures as returned values, because the closure rule is stated there and used here [S:13:131]. Finish with the computation graph section of Goldberg's primer, where a recorded program is the ordinary object of the system [S:88:28].