Immutability
A Socratic walk-through of immutability — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why does forbidding a value to change make code that runs in parallel correct by construction?
Concurrency is famously the hardest thing in ordinary programming: locks, race conditions, deadlocks, bugs that appear once a fortnight on one machine. And the standard advice for taming it is a restriction that sounds unrelated and faintly puritanical — do not let values change after they are created.
That is not a synchronisation mechanism. It adds no ordering, no mutual exclusion, no communication. So how can removing an operation make a whole category of bug disappear? And is "correct by construction" honest, or a slogan?
Reasoning it through
REASONING #Start with what a data race actually requires. Two threads touch the same memory, at least one of them writes, and nothing orders the two accesses. Notice the middle clause. If every access is a read, there is no race — not because reads are fast or safe by convention, but because there is no moment at which the memory holds a partial or inconsistent value. Nothing is in the middle of becoming something else.
So the restriction is aimed precisely at the clause that makes races possible. Remove writes-after-publication and the definition stops applying. That is why it feels like it comes from nowhere: it is not a better way to coordinate, it is the removal of the thing that needed coordinating.
Now test that against a concrete failure. A configuration object holds a hostname and a port, and one thread updates both while another reads both. The reader can read the old host and the new port — each field read is fine individually, and the combination never existed as a valid configuration. No amount of care in the reader helps, because the object it was handed changed underneath it. This is the deep problem with shared mutable state: an object's identity stays the same while its value changes, so holding a reference is not the same as holding a value.
Immutability separates those. If the object cannot change, then a reference to it is as good as a copy: whatever you saw when you got it is what you will see forever. Updates do not disappear — you build a new object with the new host and port, complete and consistent, and then swap which object the shared reference points to. The reader either sees the whole old value or the whole new one, and never a mixture.
Follow that carefully, because it locates exactly what synchronisation is still needed. The swap is a single write to a single reference, so it is the only thing requiring atomicity, and it is the smallest thing that could. All the compound structure — however many fields, however deeply nested — was assembled privately by one thread before anyone else could see it. The hard part shrank to one pointer.
But is anything left? Yes, and this is where "correct by construction" overreaches. Three things survive.
First, safe publication. It is not enough that the object never changes after construction; other threads must be guaranteed to see it fully constructed. Compilers and processors reorder writes, so a reader can in principle see a reference before the fields it points to. Language memory models address this specifically — Java's final fields carry a guarantee for exactly this case — but it is a real rule, not an automatic consequence of not writing again.
Second, immutability removes data races, not race conditions in the broader sense. Two threads can each read the same value, each compute a new one, and each swap it in; one update is simply lost. Nothing was corrupted and nothing was unsynchronised, yet the outcome is wrong. That needs a compare-and-swap, a transaction, or a single owner — immutability makes the update atomic, not the read-modify-write.
Third, there is a cost. Every change allocates, and naively copying a large structure per update is quadratic misery. The practical answer is persistent data structures, which share the unchanged parts between versions — a tree where a new version reuses every subtree it did not touch, so an update copies a path rather than the whole. That is what makes the discipline affordable rather than merely elegant, and it is worth knowing it does not come free with the keyword.
The analogy
THE ANALOGY #Think of a printed edition of a timetable rather than a whiteboard. A whiteboard is amended in place, so somebody reading it while a change is half-written gets a schedule that was never true. Editions are never amended: a new one is printed complete, and the notice board is switched to it. Anyone mid-read simply finishes reading a coherent old edition, and nobody ever holds a page that is partly Tuesday's and partly Wednesday's.
two editors can each take yesterday's edition away, revise it, and print — and the second printing quietly erases the first one's changes, which is precisely the lost-update problem that immutability leaves for some other mechanism to solve.
Clarifying the model
THE MODEL #Three refinements.
First, "immutable" has to be deep to help. An object whose fields cannot be reassigned but which holds a mutable list is not immutable; readers can still observe it changing through that list. Shallow immutability is the most common way the guarantee is claimed and not delivered.
Second, immutability is a property of values, and programs still need identity — something that means "the current configuration". The useful decomposition is Rich Hickey's: keep values immutable and give change a single, explicitly managed reference cell. Then the only place that needs concurrency reasoning is that cell, and it is one line of the design rather than diffused through every object.
Third, the benefit is not only concurrency. Immutable values can be cached, memoised, hashed once, compared by reference as a fast path, sent to another thread without defensive copying, and reasoned about locally — a function handed one cannot have it changed mid-call by anything. Concurrency is the case where the alternative is most obviously unmanageable, which is why it dominates the argument, but the local-reasoning gain applies to entirely sequential code too.
A picture of it
THE PICTURE #How to readTime runs downward and each arrow is one memory access. In the upper half the reader's two accesses straddle the writer's update, so it assembles a configuration from two different eras — the classic torn read, and note that the reader did nothing wrong. In the lower half everything the writer does happens on its own lifeline until the single swap arrow, which is the only shared write in the whole exchange; the reader touches the shared reference exactly once and then works from a value nobody can alter.
What became clearer
WHAT CLEARED #Forbidding change does not add coordination — it deletes the precondition that made coordination necessary, since a race needs a write and there is none. What remains to synchronise shrinks to a single reference swap, which is the smallest atomic operation a machine offers. "Correct by construction" is the right instinct but slightly too strong: safe publication is still a real requirement, and lost updates are still possible because immutability makes each new value atomic without making read-modify-write atomic. What it genuinely buys is that holding a reference becomes as trustworthy as holding a copy, and that is what makes parallel code readable rather than merely lucky.
Where to go next
ONWARD #- How persistent data structures share subtrees so that an update copies a path rather than the whole structure.
- Where compare-and-swap loops and software transactional memory pick up the lost-update problem immutability leaves behind.
Key terms
TERMS #| Term | What it means |
|---|---|
| Data race | two unordered accesses to the same location where at least one is a write; undefined behaviour in most memory models. |
| Safe publication | the guarantee that a thread seeing a reference also sees the fully constructed object behind it. |
| Persistent data structure | an immutable structure whose new versions share unchanged parts with the old, making updates cheap. |
| Compare-and-swap | an atomic instruction that writes only if the current value matches an expected one, used to detect lost updates. |
Every term the collection defines is gathered in the glossary.