Immutability

Immutability is the rule that a value, once made, never changes. It sounds like a restriction and turns out to be a superpower: if nothing can change under you, an entire family of bugs simply cannot happen.

The problem it removes

Share a mutable thing between two parts of a program and you have signed up for trouble. One holder mutates it; another, holding the same reference, is surprised. To defend yourself you copy defensively (slow, and easy to forget) or reach for locks (hard, and easy to get wrong). Aliasing bugs, and most concurrency bugs, are really this one problem in different clothes.

If values cannot change, the problem evaporates. Sharing is free and safe, because there is nothing anyone can do to a value to hurt you.

The people who saw it

The root is the Lambda Calculus and pure functions: given the same inputs, a function always returns the same output, because nothing lurks that can change out from under it (referential transparency). Lisp and the functional tradition carried the idea, but always under a cloud.

The cloud was efficiency. If “change” means copy-the-whole-thing, immutable data is too slow to be anyone’s default. Chris Okasaki, a graduate student in the mid-1990s, was irritated that every data-structures textbook quietly assumed you could mutate, leaving functional programmers with no proper toolbox; his 1998 book Purely Functional Data Structures built them one from the ground up. Phil Bagwell then devised the hash array mapped trie (2000), which lets an immutable map or vector share almost all of its structure with its previous version, so “change” is cheap. Rich Hickey took the gamble few dared: he made those structures the default in Clojure, so everyday code is immutable and nobody has to think about it. The decades-old objection — “too slow” — had finally been answered.

Side by side

• C — mutable by default, no safety in sharing. Pass a pointer and the callee can change your data underneath you; to be safe you copy.
• Erlang — every term is immutable. That is exactly what lets processes share nothing and communicate by copying messages, with no locks anywhere.
• Clojure — immutable by default, yet “changing” a big map or vector is cheap: you get a new value that shares almost all of its structure with the old one, and the old one stays valid forever.

Why it endures, and its twin

Immutability is the engine under State: because values never change, an identity can be a reference that simply swaps from one immutable value to the next, and time becomes a clean succession instead of a race. It is why functional code is easy to test (no hidden state to set up), why undo and time-travel are trivial, and why immutable infrastructure, event logs, and value-oriented databases work at all. In your dynamical-systems terms: the immutable values are the fixed frames, and State is which frame an identity points at right now.

Try it

“Changing” an immutable value returns a new one and leaves the original untouched:

;; conj / assoc return NEW values; the originals are untouched (and share
;; structure under the hood, so this stays cheap even for big collections).
(def v1 [1 2 3])
(def v2 (conj v1 4))
(println "v1:" v1)            ; [1 2 3]  - unchanged
(println "v2:" v2)            ; [1 2 3 4]

(def m1 {:a 1 :b 2})
(def m2 (assoc m1 :c 3))
(println "m1:" m1 "m2:" m2)   ; m1 is still {:a 1, :b 2}

[!recall] Immutability sounds limiting. What does making values unchangeable actually buy you, and how is “change” handled? It removes aliasing and most concurrency bugs at a stroke: if a value cannot change, sharing it is always safe and you never need defensive copies or read locks. “Change” is handled by returning a new value; persistent data structures make that cheap by sharing the unchanged parts. This is precisely what makes the State model (an identity as a succession of immutable values over time) and lock-free concurrency possible.

Sources

• Okasaki, “Purely Functional Data Structures” (1996 PhD thesis) — the toolbox that made immutable structures practical.
• Bagwell, “Ideal Hash Trees” (2001) — the HAMT behind Clojure’s fast immutable maps and vectors.

See also: State, Clojure, Erlang, Lisp, Lambda Calculus, C.