Mutable references

For six modules we have written OCaml without using mutation. Every value has been immutable; whenever we needed a new state, we made a new value, with let shadowing the old name or building a fresh list, record, or tuple. This is the functional style and it has real benefits: any expression f x produces the same answer regardless of when in the program you run it, so reasoning about code reduces to substituting values for names, and the compiler can inline and reorder freely.

But mutation is, sometimes, the right tool. A web server counts how many requests it has handled across calls. A memoization table caches results across calls. A long-lived event loop keeps a connection pool that wakes up, shrinks, and grows. None of these are impossible to express without mutation, but threading the state through every call by hand makes the code longer and noisier than it needs to be. OCaml, unlike a purely-functional language such as Haskell, takes the position that mutation should be available when you want it but should not be the default. The simplest mechanism the language offers for opting in is the mutable reference cell, or ref for short. This module is about ref and the other mutable building blocks (mutable record fields, arrays), and about when reaching for them is worth what you give up.

Mutation is one of several kinds of side effect a program can have. A side effect is anything an expression does besides return a value: changing the value stored in some cell, printing to the screen, raising an exception, looping forever, sending a packet over the network. This module covers the first three. We focus on state (mutable cells, mutable fields, arrays) this lecture and the next; we cover exceptions in their own lecture. I/O has been with us implicitly since print_endline in the very first programs; non-termination is whatever recursion you write that does not stop. The general lesson is the same for all four: they let you do things pure functions cannot, but they cost you equational reasoning.

What "costs you equational reasoning" means at full scale: on 1 August 2012, the trading firm Knight Capital deployed new code to seven of its eight servers. The eighth still ran an old code path guarded by a reused feature flag, and the new deployment flipped that flag on. Stale state plus live flag reactivated code that had been dead for years, and in 45 minutes the firm lost about 440 million dollars and nearly ceased to exist. The SEC's account reads like a parable about mutable state: nothing in any one server's code was wrong; the combination of mutations across machines was. Pure values cannot disagree with each other; mutable state can, and at scale it eventually does.

A ref is a mutable box

Three operators, three roles. ref x creates a fresh mutable cell holding the value x; the expression evaluates to a reference to that cell, of type int ref. The operator := writes a new value into the cell. The operator ! reads the current value out: the contents left by the last write.

The unusual thing for a programmer arriving from C or Python is that creation, read, and write each get their own syntax. In C you write int counter = 0 to create and counter = 1 to update; in Python counter = 0 does both, with the second = deciding from context that it is an update. OCaml separates the three because, under the hood, they really are three different operations: ref allocates a cell on the heap, := mutates a cell that already exists, and ! reads from a cell. C makes the same distinction implicitly with pointers (malloc allocates, *p = 1 writes, *p reads), and OCaml's ref is essentially a heap-allocated single-cell pointer with named operations.

One small note about syntax: the ! in !counter is the dereference operator, not boolean negation. Boolean negation is the function not, not a symbol. This is the same !/not split that ML-family languages have shared since Standard ML, and the choice is deliberate: the dereference is the more common operation by far on a ref, so it gets the short symbol.

The cost of mutation: equational reasoning

Here is the price you pay when you reach for a ref.

The same expression get_next () produces three different answers in succession. There is no way to predict the answer of a call to get_next () without knowing how many times it has been called before.

Contrast with a pure function. If let f x = x + 1, then f 3 is always 4. You can replace any occurrence of f 3 in the program with 4 and nothing changes: the behaviour is the same, the performance is the same. This equational property is what makes pure code easy to reason about. You think of a function call as naming a value, the way pi names 3.14159, and you can substitute freely.

Mutation gives that up. get_next () is not the name of a value; it is the name of an action. The action consults a shared mutable state, modifies it, and returns the new state. Two textually identical calls can produce different results. You can no longer inline a call to get_next () without thinking about whether the inlining changes how many times the function is called.

This is why OCaml is functional-first. The default discipline is to write pure code, where equational reasoning holds, and to isolate mutation behind a small surface area when it is needed. We will come back to "what surface area" at the end of the lecture.

When ref is the right tool

A non-exhaustive list of cases where reaching for a ref is defensible.

Counters and accumulators. When you are stepping through a sequence and the natural shape of the algorithm is "for each element, update this variable," a ref is fine. We will see in the next lecture that for loops in OCaml usually go hand in hand with refs and arrays: this is the imperative corner of the language, and you use it where the algorithm wants it.

Caches. A memoization table that maps inputs to previously computed outputs grows across calls. A Hashtbl.t is itself mutable; you reach for it directly without wrapping in a ref. A small inline cache, on the other hand, is often a ref of an option or a list.

Shared mutable structure. Building a structure where several pointers see the same updates: a graph with cycles, a doubly-linked list, an AST node whose forward reference is filled in after the surrounding tree is built (this last is called backpatching in compiler pipelines). Each of these needs a ref as the shared cell or as the backpatch point. We will not write one of these in this course, but they are part of what ref makes possible.

Interop. Code that talks to GUI toolkits, network callbacks, or any C library expects to push state into the world rather than return it from a function. A ref (or a mutable record field, or a hash table) is how OCaml participates in that world.

For most everyday OCaml code, none of these apply, and the function you are writing has no refs at all. Reach for ref when the alternative is awkward, not as a default.

A small example: a one-shot

Here is a pattern where mutation is genuinely the cleanest expression: a closure that does something the first time it is called and nothing thereafter.

The mutable state used is hidden inside the closure: there is no way to reach it from the outside. Each call to make_once produces a fresh, independent one-shot.

The pattern is private mutable state inside a closure. The state is invisible to callers; they can only observe its effects through the function's behaviour. From the outside, f () looks like a function that happens to return None on the second and later calls. The fact that it does so via a mutable flag is an implementation detail.

This same pattern, scaled up, is how many imperative languages build objects: an object is essentially a record of closures that share some private mutable state. Smalltalk and JavaScript make the connection explicit; in OCaml, the building blocks are exposed and you put them together as needed.

Sequencing side effects with ;

We met ; in the hello-world lecture as the way to sequence two unit-typed expressions: e1; e2 evaluates e1 (which must be unit), then e2, and returns e2's value. With refs, ; becomes the everyday tool for threading several updates in a row:

There is no syntactic limit on the chain: e1; e2; e3; e4 evaluates each in order and returns the last. As before, every expression except the last must produce unit, or the compiler warns that you are throwing a value away; wrap the offender in ignore if the discard is intentional.

The begin ... end and (...) brackets group a sequence into one expression, which we sometimes need when a sequence appears in the branch of an if. We saw this when writing count_down.

incr and decr

A ref of int is so common that the standard library gives you two shortcuts:

incr r is shorthand for r := !r + 1; decr r is shorthand for r := !r - 1. They are mildly more readable in counter-style code. Otherwise the difference is cosmetic.

A quick check

Aliasing: two names for one cell

Because a ref is a heap-allocated cell, you can have two names that refer to the same cell. Mutating through one name mutates what the other name sees.

The let y = x did not copy the cell; it bound a new name to the same cell. Both names refer to the same place in memory, so the write through x is visible through y.

If you actually want two independent cells with the same initial value, you have to create two cells:

Each ref 42 evaluation is a fresh allocation, so the write through x leaves y's cell untouched.

This aliasing is the source of much of the difficulty of imperative programming. Anywhere a ref (or any mutable value) escapes a function, there is now a question of "who else has a handle on this cell, and what might they do to it?" In a pure functional setting, the question does not arise because there is nothing to share. With mutation, every API has to decide what its caller is allowed to do with the values it returns.

Structural and physical equality

Aliasing immediately raises a question: given two refs, how do you ask whether they are the same cell versus cells that happen to hold equal contents? OCaml has two operators for this. = is structural equality: it walks the two values comparing them piece by piece. == is physical equality: it asks whether the two operands are the exact same heap-allocated object.

The rule on refs is:

• r1 = r2 (structural) iff !r1 = !r2. Two refs are structurally equal exactly when their contents are.
• r1 == r2 (physical) iff r1 and r2 name the same cell, i.e., the two are aliases.

So ref 5 = ref 5 is true even though the two ref 5s are separate allocations, but ref 5 == ref 5 is false.

A richer worked example that exercises both axes (aliasing of refs and sharing of list contents) at once:

The heap layout that results:

With this picture in mind:

• l1 = l2 and l1 = l3 are both true: structural equality walks the contents, and all three lists are [1; 2; 3].
• l1 == l2 is true (same allocation) but l1 == l3 is false (two separate allocations with equal contents).
• r1 = r2 and r1 = r3 are both true: structural equality on refs compares contents, and both cells hold an equal list.
• r1 == r2 is true (aliased to the same cell) but r1 == r3 is false (two different cells).

The structural check = says "the contents match." The physical check == says "they are the same cell." Aliasing is exactly the property == detects.

A useful rule of thumb: == is rarely what you want. Most code asks "do these values represent the same thing?", which is structural equality (=). Reach for == when you genuinely need to know "are these two names for the same mutable cell?", which happens in aliasing-aware code (caches keyed by identity, cycle detection, breaking circular print). For everything else, use =.

Value restriction: a subtle interaction with polymorphism

Mutation and polymorphism do not quite get on. Consider:

The toplevel reports '_weak1 list ref, not 'a list ref. The underscore in '_weak1 marks this as a weakly polymorphic type: r may be used at one element type, not many, and OCaml will infer which one from the first use.

After r := [1], the type of r is locked to int list ref. A subsequent attempt to push a string in would be rejected at compile time. This rule is called the value restriction, and it exists to plug a hole in type safety.

The hole, if there were no value restriction: a single cell could be used at two different types at once, and the type system would let you read out an int as a string.

r_int and r_str are aliases for the same cell. Writing an int list through one alias and reading a string list through the other would print arbitrary bytes as a string, or segfault. The value restriction is the type system's way of refusing to compile the program in the first place: by demoting 'a to '_weak1 when a polymorphic type is created by something other than a value, it forces every use of r to agree on one element type.

The restriction can occasionally bite when it does not need to. A common case is a partial application that would be safely polymorphic, but the syntactic check that implements the rule does not see that. For example:

map_id is morally fun xs -> List.map (fun x -> x) xs, which would be safely polymorphic. But the RHS of the let is a function application (List.map applied_to_one_arg), not a syntactic function value, so the restriction kicks in and 'a collapses to '_weak1.

The standard workaround is to add an explicit parameter, restoring the right-hand side to the form of a function value:

Now the RHS is a function value (let f x = e desugars to let f = fun x -> e), and map_id gets its full polymorphism back. Lifting an argument out like this is called eta-expansion. We will not need it again in this course; it is enough to recognise '_weak1 and know what it means.

Where you put let ref matters

A small bug whose shape recurs constantly in larger code.

Suppose we want a ticket dispenser: a zero-argument function whose first call returns 1, second returns 2, and so on. A first attempt:

Expected: 1, 2, 3. Actual: 1 every time.

Trace through one call. The body runs as a fresh evaluation: let n = ref 0 allocates a new ref cell with value 0; incr n bumps that cell to 1; !n reads 1 back. The cell was local to this call, so it has nothing to do with any cell from a previous call. Each call starts over from zero.

The fix is to hoist the let n = ref 0 out of the function so that the cell is allocated once, when the function is defined, and the function value closes over it:

Now there is one cell, allocated at definition time, captured by the closure. Successive calls hit the same cell.

The lesson generalises: a let inside a function body runs on every call; a let outside, captured by closure, runs once. With immutable bindings the distinction rarely matters; with ref it decides whether your state survives between calls.

Activity

let add = make_running_total ()
add 5    (* = 5  *)
add 3    (* = 8  *)
add 10   (* = 18 *)

Each call to make_running_total () is a fresh allocation of total, captured by a fresh closure. The two accumulators a and b are independent: a's total and b's total are different cells. This is the same closure machinery from functions-as-values, with the captured value happening to be a mutable cell rather than an integer.

What's next

The next lecture extends the mutation toolkit: mutable record fields (the general form ref is the one-field special case of) and arrays, the fixed-size random-access mutable sequence. Lecture 3 covers exceptions, the other major form of "side effect" in OCaml. Together these three (refs, arrays, exceptions) give you the imperative subset of the language. Lectures 4 and 5 take a small detour: streams (infinite data, built lazily) and memoization (caching function results for speed), two techniques that build on the ref / exception machinery. Lectures 6 through 8 then turn to modules, the unit of program structure: how OCaml organizes code at scale, hides representation, and writes generic data structures via functors. Lecture 9 is the tutorial.

Reading

• Cornell CS3110, References: https://cs3110.github.io/textbook/chapters/mut/refs.html
• Real World OCaml, Imperative Programming: https://dev.realworldocaml.org/imperative-programming.html

Sources

This lecture's prose, worked examples, and quizzes are original to this course. Materials referenced during preparation are listed in the Reading section above; Cornell CS3110 and Real World OCaml are CC BY-NC-ND-licensed and have not been derivatively reused. See LICENSES.md at the repository root for the full source posture.