Time Travel in Programs

Nor Time, nor Place, nor Chance, nor Death can bow. My least desires unto the least remove. — “The Time Traveler’s Wife”

Three years ago, when I wrote that callow essay “The Enduring Charm of Immutability,” I was just a beginner in Elixir and Clojure. I hungrily absorbed ideas and energy from Bret Victor, Rich Hickey, and others, pouring them into the foundation of my faith in functional programming. Functional programming languages contain many design ideas worthy of praise, but immutability is clearly the jewel in the crown. It lets us use concurrency without restraint, with no need to think about locks, because there is no critical section to speak of; it frees us from wandering, lamenting, even flagellating ourselves all day over segfaults caused by dangling pointers or exceptions caused by bad references. When we use a product, determinism makes us feel safe and happy—on WeChat, if the little spinning flower that represents sending a message to a friend stops without an exclamation mark, then it has definitely succeeded; that is determinism. The determinism immutability gives programmers is this: I give you a reference, and as long as you hold it—until the end of time, until the seas run dry and the rocks crumble—it remains accessible and still guards the original value.

Have you ever wondered why, if it is so good, our predecessors did not use it?

It was not that they would not; it was that they could not. Immutability is good, but it “wastes” memory.

When machine memory was measured in kilobytes, programs describing complex states could barely cope; naturally, they could only reuse every bit as much as possible, hoping to get the most out of it. Copy-on-write? Get out of here.

In the 1980s and 1990s, memory reached the megabyte level, but DOS, constrained by the addressing capability of real mode, still divided memory into inside the Fifth Ring (the low 1 MB) and outside the Fifth Ring (expanded memory above 1 MB). So programmers of that era were still famous for scrimping on memory.

After the turn of the millennium, memory transitioned from sub-gigabyte to gigabyte levels; operating systems had long since fully adopted 32-bit protected mode and were moving toward 64-bit. Most application developers gradually no longer had to worry about a memory ceiling. Even if they accidentally exceeded physical memory, swap would catch them, and there was plenty. But Newton tells us that programmers are lazy: without an external force, they develop inertia—path dependence.

Path dependence means everyone applauds the idea of immutability, yet it is still used only in a handful of contexts—Git, Docker, React, and, of course, blockchain.

There is another reason: the way we see the world. Is the world we operate in a mutable system or an immutable system? Let us first examine our own brains. Most people’s first reaction might be that the brain is a mutable system, but think carefully: it is immutable. Our memories are like onion rings, continually layered, never modified. Take my family’s phone numbers: several numbers immediately pop into my head—four-digit ones, from the first telephone installed at home when I was a child; numbers from Guangdong, Beijing, San Jose, Seattle, and so on. So the brain is an immutable system; once data is generated, the brain only connects it, never modifies it. Consider the events that happen every day—today’s temperature, news from around the world, the child playing piano downstairs: all of these are immutable. The temperature seems to change, but that depends on how we model it. What if temperature is not a value but a vector indexed by time?

So when we view the world as a series of points that have only a final state, it is constantly changing; but add the dimension of time and it is immutable—from a genesis state, a series of immutable events occurs, ultimately producing the present state. That is how our world works. Unfortunately, most of the time it is not how we write programs—even though our programs either deal with the real world or simulate it.

Bret Victor, in his famous talk Inventing on Principle, showed how changing our mental model can give us one “voilà” moment after another—for example, this screenshot of time travel in a game:

Time travel in programs is nothing new. The Git we use every day lets us move freely to any commit, tag, or branch in history:

Goya, a pixel editor written in Clojure, also uses time travel for undo/redo—very simply:

To do all this, we first need to introduce the idea of immutability and describe the world inside the application using genesis state + events. In Git, each commit is an event; in Goya, each stroke of the brush is an event.

Next, we need a suitable data structure to hold state—Chris Okasaki’s Purely Functional Data Structures reveals the strange magic of persistent data structures—and Robert Virding, one of Erlang’s inventors, is said to have written Erlang’s data-structure support by following the examples in PFDS.

A persistent data structure is a tree:

Here, data is stored at the leaf nodes, and a tree is built keyed by indexes of the data. When some data in the whole structure changes, we only need to create the new data and then a new tree that indexes that data together with the unchanged data, thereby avoiding, in space, the copies that immutability would otherwise produce. In functional programming languages, if no one uses the old tree anymore, the GC will reclaim it; but if we link or record each event’s new tree to the old tree, we gain the ability to travel through time.

Git uses a Merkle tree—more precisely, a Merkle DAG—to store all objects of all commits. The idea is similar to persistent data structures: the data (the objects in a commit) are at the leaf nodes, except that the index connecting the leaves is their hash rather than an ordinary key. Merkle DAGs are used widely—from Plan 9 OS to BitTorrent, from Git to Bitcoin/Ethereum, and so on:

As we know, by starting from an initial genesis state and successively appending events, we can construct the state at any moment; this design idea is event sourcing. Use event sourcing, manage and persist the current state with a Merkle DAG, and then use public-key cryptography to make all events and states publicly verifiable, and you have what we know as Ethereum.

In Ethereum, the event is a transaction, and state is stored in a Merkle Patricia Tree. If we regard Ethereum as a self-contained world, then its forks are other worlds of this world in parallel universes, and we humans are like the five-dimensional beings in Interstellar: we can travel through time within the Ethereum world. For example, to return to January 13, 2017 and explore the state of all accounts in that world at that moment, we only need to find the state root in block 4904084, locate the corresponding tree under that hash, and then dig down through the tree for information.

What if we need Ethereum’s state at an arbitrary moment? Within Ethereum’s world, what exactly is time? Time is block height. So time travel within Ethereum means fetching the state at different block heights. However, Ethereum’s own time is obscure, so we first need to map human-society time to Ethereum block heights, then find the block height closest to a given human time, and we obtain time travel to any time within Ethereum.