The Timeless Allure of Immutability

Every programmer — whether your first hello world came in BASIC, in C, or in JavaScript — is bound to encounter next a concept called the “variable.” Variables are mutable. The equation x = x + 1, forever impossible in mathematics, takes on new meaning in a programming language: assignment. Over the course of a variable’s lifetime, its value may change at any time the need arises — whether through iteration or through a shift in state. On this foundation, the code a programmer writes is essentially the ceaseless mutation of internal state in response to various external and internal events. This is true of a running process, of a disk’s file system, of a database, and of the DOM pages under JavaScript’s control. The “variable” brought us mutable state, and this mutation is everywhere in the world of computing.

Mutability is a headache. Unless you painstakingly replay every action encountered along the way of state transitions, you cannot easily restore something to a previous state (undo) or redo a given step. In a multitasking environment, the contention and synchronization between readers and writers (or producers and consumers) is a disaster. Even this simple scenario has been dissected by academia and industry into single-producer single-consumer, single-producer multi-consumer, and multi-producer multi-consumer variants, compounded further by lock-free and wait-free combinations — complexity that has already grown considerable.

Complexity is the nemesis of software. When something grows complex, it means more complexity will sprout up around it. Consider testing: unit tests for a single function or class are usually simple, because they cover the fewest states; functional tests involving the interaction of multiple classes are more complex, because states begin to interweave and entangle. Those who have worked on networking equipment have probably all heard of a testing method called stress test: place the device in a complex network-traffic environment, enable every feature, and run it for 72 hours. Engineers pray nothing goes wrong — because in such a scenario, where countless states are woven into a plate of spaghetti, the odds of finding the root cause when something does break are slim.

Since mutable state is so elusive, why not simply forbid x = x + 1 altogether and make all state immutable?

Just thinking about it is frightening — how many problems would that introduce! Do I really have to copy every existing element each time I modify one in an array or hash table? Can the GC even keep up? How would I write a for loop — how, for that matter, would I write code happily at all?

Hold on. Set these questions aside for now, and let’s look at a few real-world product examples.

Start with git (or any SCM). Every time you commit to the repository, you forfeit the right to alter that commit again footnote:[git commit –amend counts as a small, harmless compromise], and any later modification never touches a prior commit. The system stores data incrementally by computing the diff between two commits. On this foundation, you can undo/redo at will, switching your codebase to any commit in history. And that commit remains forever fixed. In multi-person collaboration, no one else can corrupt your commit either.

Docker learned a great deal from git. It wrapped lxc — hardly anything new — into a deployment-management tool reminiscent of git. Software deployment has long been a headache: because the file system is writable, the only way to reconstruct a running system is to replay every step it went through — precisely what earlier deployment-management tools like puppet and ansible did. Replay is time-consuming: it repeatedly mutates an initial state until the desired state is reached, a quintessentially mutation-oriented mindset.

Docker took a different path: what if the runtime environment, like a git commit, were immutable once each environmental change is committed?

That bold idea made Docker what it is today. Whereas diffs between git versions are mostly text, Docker’s are file-system diffs. Using the existing UnionFS (perhaps something newer these days?), it continually produces new layers through copy-on-write, with each new layer retaining only what differs from the layers already there; a software runtime environment becomes a series of commits (layer after layer). Combined with powerful caching, Docker achieved “git for deployment” — administrators can, in production, conveniently undo/redo/checkin/checkout runtime environments of any version.

React, meanwhile, was a great attempt to bring immutability into the UI domain. When contemporary JavaScript libraries were still mired in the early stages of MVC, fighting to be its flagship, React had already set its sights further: was there some conceptual leap that could produce a far more formidable V(iew)?

React’s answer was to reduce change. It has two principal ideas: unidirectional information flow, and isolating change — the latter manifested in two ways:

1. Separating immutable props from mutable state

2. Inserting a VDOM between the DOM and its manipulators. Rather than operating on the DOM directly and keeping state in a mess, why not build an intermediary layer, onto which every new modification is piled layer by layer, from which a diff can be obtained — just like git? On this basis, React needn’t painstakingly record exactly which bindings the user set up (as ember/angular do); instead, on each change it computes a fresh diff through the VDOM and makes only the most necessary modifications to the DOM.

Of course, React still uses mutable state, as everyone does, which keeps its diff-computation performance from being optimal. om, built on React and leveraging clojurescript’s language-level immutability, pushes React’s capabilities to the limit (state changes are themselves recorded as diffs, hence the exceptional efficiency). When the UI can be expressed with a simple data structure like EDN, everything seems so simple. Want time travel (undo/redo) in the UI? It’s as easy as git checkout of a commit! Want to test any state of the UI? It couldn’t be easier — construct in advance the EDN of some intermediate UI state, then take specific steps and test whether the constructed EDN equals the actual UI’s EDN!

The pixel editor below delivers a complete undo/redo capability in just 66 lines of code:

This is immutability — the timeless allure of the unchanging!

Which brings us back to the problems that immutability introduces. The question of how to write code happily has already been solved by functional programming languages; the programmer need only invest time and effort adapting to this unfamiliar world.

The remaining question is: how do we copy state happily?

Mathematicians long ago provided the solution, and Clojure brought it into practical application: the persistent vector. The array in the figures below uses a persistent vector — 4 bits by 4 bits (32 bits in practice) to build an index tree. Suppose we want to change the element at index 106 (0b01101010): first take (01), i.e. 1, to find the second index of the second level, and so on:

At last we reach the leaf node; after locating the element to modify, we create a new node and copy every index along the path we traversed, completing one “modification” of an element within the array.

Someone is surely thinking: you’ve turned an O(1) problem into O(logN) — isn’t that taking off your trousers to fart, a needless extra step?

Don’t forget: this is not merely about “changing” content — it also records history, preserving the right to travel through time with your data. And the most beautiful part is that, at the cost of some speed and memory, your code is immutable, and complexity is pared down to simplicity.

And immutability is what today’s programming world dreams of. I know that whenever people discuss the benefits of immutability, they inevitably bring up concurrency — so I won’t dwell on those here.