Session 2
Structures that keep their past: what they cost, what they buy, and how to spot one from its interface.
An algorithm can be read two ways. As a recipe: do this, then that, and the pot changes as we stir. Or as a definition: this value is that function of those values, and nothing is stirred at all. Most data structures we have written follow the recipe. Push onto an array-backed stack and the previous stack is gone.
That is fine until we need the past. Backtracking needs the state before the wrong turn. Undo needs every state. A search needs the frontier as it was at step 40. The recipe answer is to copy, or to log and replay, and both are expensive enough that we usually give up and redesign around the limitation.
There is another answer. If no one may modify a structure, then everyone may share it — and a “new version” can be a few new cells pointing into the old one. The past stays alive because nothing ever overwrote it. Structures that work this way are called persistent, and this session is about what they cost, what they buy, and how to recognise one from across the room.
An operation returning unit or void has
changed something we cannot see. One returning a new t
hands us the next version and leaves the old one standing. We can read
a module’s interface and know which world we are in, before
seeing a single line of implementation.
A chain of implications, and the middle link carries the weight: sharing is safe when no version can be changed through another version’s pointer. Immutability buys that outright. It is not the only way to buy it — ownership and undetectable mutation also work — but it is the one a compiler checks.
OCaml ships a mutable Stack and Hashtbl next
to its immutable List and Map. Python hides
a persistent map inside the standard library. Java gets there with
final fields and records. Languages set defaults; we
choose the paradigm.
oldsp = sp — and the
pop-then-push case where that trick quietly returns the wrong
answer.private and final.
Java enforcing by compiler what Python asks for politely; the
tuples-as-cons construction and the frozen-object trick.::
shares, match, records, option in place of
null, and how to compile and run. It closes on the same
stack written with a mutable record — same language,
same data, and the whole difference visible in one type.The OCaml half is also a program.
tour.ml
walks the same ten steps in the same order, so the claims made on the
slides can be checked instead of believed — structural sharing,
for instance, is demonstrated with physical equality rather than drawn.
It stops short of the queue itself, which is the lab’s work.
Run it with ocaml tour.ml.
Its companion is
homework.ml,
which follows the same order and asks us to write the code instead:
nine short exercises on lists, recursion, match and
option, each starting as a hole. Running the file reports
which are still to do, which pass and which are wrong, so we can work one
at a time. There is nothing to collect — the point is that the
lab’s OCaml part should be typing rather than puzzling.
One data structure, specified once, built three times: the
two-list persistent queue. The stack was straightforward because
push shares everything. A queue adds at one end and removes
at the other, so persistence has to be earned.
B and D have nothing to implement — they are the two we run and watch, and they are where the point of the session lands. They are shaded below. Everything happens in order, A through D on the day, E at home. Nothing is handed in.
| A0 | On paper, before any code. The representation, the abstraction function, the invariant, and a hand-executed trace. Nine exercises; the proofs in the last four are for afterwards. |
| A | Python. Four holes in
pqueue.py, guarded by fourteen tests in three groups:
basics, the FIFO contract, then persistence and structural
sharing. |
| B | The payoff.
Our queue drives a maze solver. Swapping it for the lecture’s
stack turns breadth-first search into depth-first, without touching
the search: the algorithm never mentions queue or stack, only a
frontier. A slider then scrubs through every frontier the search ever
had, and --inspect=40 asks what the frontier held at
step 40 — without the solver having recorded it. |
| C | OCaml. The same queue
against a given .mli. Worth noticing what the compiler
now checks for us, and what got shorter. |
| D | Breaking the bank. The amortised bound has an assumption hidden inside it, and persistence violates it: a benchmark makes an “O(1)” operation cost O(n) every single time. Which assumption? We answer it out loud before we leave. This is the case Okasaki constructs in §5.6; the repair is his chapter 6, and needs tools we meet in session 5. |
| E | Java. At home. The same four
operations a third time, in a language that can enforce what Python
only asks for politely: final fields,
record nodes, a final class. |
What “free history” means, exactly. Two things in Part B look alike and are not.
| Feature | Reads | Recorded? |
|---|---|---|
--inspect=40 |
versions[40] — the frontier value itself |
nothing recorded |
| the HTML slider | a trace exported to JSON | one snapshot per step |
versions is an ordinary list the solver appends to
at every step. That is bookkeeping — but it copies nothing. Each
entry is a reference to a value that already exists, and consecutive
values share all but one or two cells, so keeping every version costs one
pointer per step and not a single extra cons cell: the search allocated
those cells anyway, and the list merely declines to forget them. The
slider is the other case, and has no choice: a browser cannot hold
references into the solver’s heap, so the frontier is walked and
serialised at each step. On mazes/medium.txt that is 1306
cells against the search’s own 612.
| Language | Role |
|---|---|
| C | read the ephemeral array stack, and the checkpoint that fails |
| Java | read in the lecture, write for homework |
| Python | write the queue, the solver, the benchmark |
| OCaml | read first, then write — the language is introduced here, gently |
No OCaml is needed beforehand. The lecture spends a minute on how to read it, and the lab supplies a signature to fill in.
None of this is required. It is the list from the lab page, where each entry is annotated at more length.
--inspect flag in the lab is the
partial kind.--inspect is cheap here.