One Queue, Three Languages

00 — description

What this session is for

A persistent data structure is one in which every operation returns a new version and no existing version is ever modified. The lab asks what that costs, what it buys, and how much of the answer depends on the language in which it is written.

The vehicle is the classic two-list queue: a FIFO queue built from two singly-linked lists, in which the expensive step — reversing one list into the other — is rare enough to be paid for in advance. We derive its cost with an amortised argument, implement it three times, and then deliberately construct the case in which that argument fails. The failure is not a defect in the implementation; it is a genuine and well-known tension between amortisation and persistence, and meeting it here is the point of the session.

Three things generalise well beyond queues, and are the reason the lab is built this way. First, a specification can be language-independent while its implementation is not: one page of pseudocode yields three programs that agree on every observable number and disagree on almost everything else. Second, immutability turns version history from an expensive feature into a free consequence — the same property behind undo stacks, git's object model, and time-travelling debuggers. Third, an amortised bound is a claim about a sequence of operations, and therefore a claim that persistence is uniquely able to invalidate.

01 — before any language

The structure, what it drives, and why it is persistent

A queue is represented by two lists. Three lines and four equations fix everything else in the lab: the search we are about to watch run, and the reason the containers had to be persistent in the first place.

The structure, specified once

representation:   (front, back)
abstraction:      contents  =  front ++ reverse(back)
invariant:        front is empty  ⟹  back is empty

enqueue(x, (front, back)) = make(front, x·back)      -- cons onto back, O(1)
dequeue((x·front', back)) = (x, make(front', back))  -- take head of front
dequeue((∅, _))           = nothing

make(∅, back)     = (reverse(back), ∅)               -- restore the invariant
make(front, back) = (front, back)

Every operation returns a new queue and no version is ever modified. The invariant guarantees that the oldest element is always the head of front, so peek and dequeue are one pointer away — except when front is exhausted and make performs a single O(n) reversal.

The demo — same code, same maze, different search

Both panels below run identical search code over an identical maze. The only difference is which structure supplied the frontier. Drag the slider, or press play.

The outlined cells are the frontier — the contents of the queue or the stack at that instant — and they are the only mechanical difference between the two runs. What that difference produces is the shape of the pale region behind them. BFS spreads outwards evenly, so by the time it first reaches the exit it has necessarily arrived by a shortest route. DFS follows a single thread, commits to a corridor, and returns the first path it finds rather than the best one.

Run the slider to the end and compare the two. DFS leaves whole regions of the maze white — never visited at all — and still comes back with a path 28 steps longer than it needed to be. BFS looks at 66 more cells and is repaid in the guarantee. Neither behaviour is better; they are different guarantees, and we select between them by choosing a data structure.

Why the containers had to be persistent

A mutable queue would drive this solver perfectly well, and faster. The honest question is therefore not whether persistence works here, but what it is for. There are three answers, in increasing order of how much they matter.

1. For the search itself, it was not necessary

This is worth stating plainly, because it is the honest starting point. An ordinary mutable queue would run the solver correctly and with less allocation. Persistence is not a performance argument and it is not required by breadth-first search. If finding a path were the only goal, the whole design would be unjustified.

2. It makes the version history free

Because take returns a value and a new frontier rather than modifying one in place, every intermediate frontier remains valid indefinitely. The solver therefore keeps all of them, in a list, at the cost of one pointer per step:

versions = [frontier]
...
    versions.append(frontier)   # no copy — the old version persists

With a mutable queue, answering "show me the frontier as it was at step 40" costs either a deep copy at every step — O(n) space per step, so O(n²) overall — or a replay of the search from the beginning. With a persistent structure it costs a single append, because each new version shares almost all of its structure with the previous one and nothing in the language can reach in and alter what is shared.

The list itself is the same list either way — an array of references, and any language can build one. Persistence is what makes versions[40] a different value from versions[41], rather than another alias for one mutating object. Keep the same list against a mutable queue and every entry in it reads the same, because there is only ever one queue to read.

That list is what --inspect=40 reads: it prints versions[40], a structure that is still there to be asked. The slider is a different case, and instructive for being so — a browser cannot hold references into the solver's heap, so --html walks each frontier with to_list and exports the contents. The slider therefore moves between several hundred recordings; --inspect moves between several hundred live structures. Only the second is free, and it is the one that matters: immutability converts "keep the history" from an expensive feature into a free consequence — for any consumer that can hold a reference, which a web page cannot and the rest of our program can.

3. It is what breaks the amortised bound

This is the reason the containers had to be persistent, rather than merely could be.

Recall the banker's argument from the start of this section: each element is pushed onto back once, reversed into front once, and taken once, so the O(n) reversal is paid for by the n cheap operations that preceded it. That argument contains a silent premise — each version is used at most once, so operations form a single line and the deposited coins are spent exactly once.

Persistence is precisely the power to violate that premise. Retain one version whose front holds a single element and whose back holds a thousand, then call dequeue on that same version a thousand times. Every call triggers the full reversal, because no call can see the work done by the others, and each has an equal right to the coins. The amortised bound collapses to O(n) per operation.

So the containers had to be persistent because the lab is not really about mazes. The maze is a vehicle: first for making the version history observable, then for making the amortised bound visibly fail. Neither is possible with a mutable queue.

02 — before any language

The architecture, also specified once

The queue is not an exercise in isolation. It is dropped into a maze solver that was written without knowing it would exist, and the seam between them is five names.

Two properties of the frontier interface do all the work, and both are visible in the name take.

• take returns a value and a new frontier. Nothing is modified in place. This is what makes the whole history of the search available for free — see §01 — and it is why the interface cannot be satisfied by an ordinary mutable queue without wrapping one.
• Nothing else about the container is assumed. Not its representation, not its cost, not its ordering. Substituting FIFO for LIFO therefore cannot break the search: the search never had an opinion to break.
• The graph is a separate layer again. It reports adjacency and lets the caller sequence the results, which is why the same maze file drives both searches and why neither search can tell which maze generator produced it.session 7

From here the lab is that one seam, three times over. We write a single file, and a program we did not write changes its behaviour.

03 — in class

What we build, and in what orderassignment

One structure, built once by hand and then twice at the keyboard. The code parts are guarded by tests; make them pass in order, because the test classes are named so that they run in teaching order and the ones about persistence come last — a correct ephemeral queue passes everything before them.

First, away from the keyboard

Fifteen minutes with a pen, before an editor is opened. This is the difference between implementing make from understanding and implementing it from guesswork.

The handout queue-on-paper.pdf walks the structure by hand: enqueue five elements, dequeue until the reversal fires, and draw the cons cells that two versions share. Bring it along — the pseudocode is projected during the introduction, and every implementation that follows goes faster if the reversal has already been traced once by hand.

Then, at the keyboard

Python first, because it has the fewest obstacles between us and the structure; then the same queue in OCaml, against an interface file that states the specification in the type system. The third implementation, in Java, is homework — §05.

cd python
python3 -m unittest test_pqueue -v
M=../mazes/medium.txt
python3 solver.py $M --bfs
python3 solver.py $M --dfs
python3 bench.py

cd ocaml
dune runtest
M=../mazes/medium.txt
dune exec bin/solver.exe -- $M --bfs
dune exec bin/solver.exe -- $M --dfs

Two flags worth trying in every implementation

• --inspect=40 prints the frontier as it was at step 40. Nothing is replayed and nothing is logged; the solver retained every version. If this seems unremarkable, work out what it would have cost with a mutable queue.
• --html=bfs.html writes the page dragged in §01. All three languages emit a byte-identical file, because the page is HTML and JavaScript in every case — a small reminder that the interesting differences between these three programs are not in what they can produce.

The check — three implementations, one set of numbers

One specification should produce one behaviour. On mazes/medium.txt all three solvers must agree exactly — including the Java row, which can only be filled in after the homework in §05.

solver mazes/medium.txt --bfs | --dfs

implementation	bfs explored	bfs path	dfs explored	dfs path
Python	306	75	240	103
OCaml	306	75	240	103
Java	306	75	240	103

The mazes themselves are generated by randomised Kruskal over a union–find structure — an imperative one, deliberately. We implement it persistently, and regenerate these same mazes from the same seeds, in a later session.session 7

04 — three languages

What survives the translation

The specification in §01 is identical in all three languages, and so is every number in the check above. Almost nothing else survives the translation.

Each language embodies the frontier interface of §02 differently — a bag of functions, a record of functions, or an interface with implementing classes. The table below lays the three side by side; the per-language architecture pages take one apart in detail.

Read the last row first, because the hole count is the language difference. OCaml supplies List.rev, so there is no reversal to write and the lab is three holes; Python and Java require it to be built out of cons cells. The two rows above it are the same observation running in the opposite direction: OCaml needs no stack module at all, because a list already is one, while Java needs a wrapper class around a queue that the other two use bare. Same architecture, three different amounts of boilerplate — and the boilerplate is not distributed evenly.

05 — at home

What to finish at homeassignment

One more implementation, in the language that checks the most and provides the least. Start it once the Python and OCaml queues are passing their tests: the third pass is instructive only once the first two are complete.

cd java
javac *.java && java Tests
M=../mazes/medium.txt
java MazeSolver $M
java MazeSolver $M --dfs

A set of OCaml exercises extends Part C beyond the queue itself: nine short problems on lists, recursion, match and option, each starting as a hole, with a self-check that reports what is still to do. They are homework too — and tour.ml is the worked tour they follow.

06 — reference

Related work and further reading

The two-list queue is not folklore; it has a literature, a known repair, and industrial descendants. None of the following is required reading for the lab.

• Chris Okasaki, Purely Functional Data Structures (CUP, 1998; thesis 1996). The standard reference. Chapter 5 is the queue we are building; chapter 6 is the repair for the problem met in Part D, using lazy evaluation and memoisation. His short retrospective ten years on, Ten Years of Purely Functional Data Structures, is worth the five minutes it takes. the amortisation/persistence tension is §5.6 and §6.1
• Eric Lippert, “Immutability in C#” (2007–08). Eleven posts building immutable stacks, queues and trees. Part Four is this very queue, in a fourth language and twenty years earlier — including the observation that a stack is a backwards queue, and the warning that one dequeue can cost O(n). Part One separates the several different things the word immutable is used to mean, which is the distinction the Java column of §04 turns on. read Part One, then jump to Part Four
• Hood & Melville (1981); Kaplan & Tarjan (1995). Queues with worst-case O(1) bounds rather than amortised ones, obtained by incremental rebuilding rather than laziness — the other way out of the same problem.
• Driscoll, Sarnak, Sleator & Tarjan, "Making data structures persistent" (1986). Where the vocabulary comes from: partial persistence (old versions readable) versus full persistence (old versions writable). The --inspect flag in this lab uses the partial kind.
• Git's object model. A production persistent data structure: a commit is a new version of a whole tree that shares every unchanged subtree with its parent. The reason git checkout of an old commit is cheap is the reason --inspect is cheap here.
• Clojure's persistent vectors; Scala's immutable collections; React's state discipline. The same idea at industrial scale, and the reason "don't mutate, return a new one" is now ordinary advice rather than an academic position.
• “Understanding Clojure's Persistent Vectors” (hyPiRion, 2013). Three heavily illustrated posts on the bit-partitioned trie behind the vectors named above: how a persistent structure gets effectively constant-time indexing and update once cons cells are no longer enough. The companion post on transients covers the escape hatch — mutation that no one is able to observe — which is the other half of the amortisation story. the natural sequel to this lab