Immutability is not enough

Immutable data structures – also known as persistent or purely functional data structures – are a key part of modern functional programming. Once created, immutable data structures cannot be modified. Instead, they support operations which efficiently produce a new copy of the structure with the desired changes applied.

As I’ve gotten more experience working with immutable data structures, I’ve found that they can be beneficial in many ways. However, most programs that interact with the outside world must model state changes somehow. In these cases, I’ve noticed that I still need to be careful about state updates – even though I’m using immutable data structures. Surprisingly, many of the state update bugs that are rife in imperative programs can also occur in purely functional code.

To make it easier to discuss some of these issues, let’s use a concrete example. I’ve implemented a simple retro-style platform game¹ in JavaScript where you control a tiny carpenter named Manuel:

Here’s the code for an initial implementation which uses mutable state updates:

var canvasEl = document.querySelector('canvas');
var ctx = canvasEl.getContext('2d');

var state = {
  pos: {x: 200, y: 220}  // Manuel's position.
};

window.requestAnimationFrame(function render() {
  var pos = state.pos;

  // Clear the canvas
  canvasEl.width = 500;
  canvasEl.height = 300;

  // Draw the background
  ctx.fillStyle = '#008A00';
  ctx.fillRect(0, 250, 500, 50);

  // Process input
  if (dpad.right) {
    pos.x += 3;
  } else if (dpad.left) {
    pos.x -= 3;
  }

  // Draw Manuel
  ctx.fillStyle = '#AF8452';
  ctx.fillRect(pos.x + 5, pos.y - 10, 10, 10);
  ctx.fillStyle = '#C91B13';
  ctx.fillRect(pos.x, pos.y, 20, 20);
  ctx.fillRect(pos.x, pos.y + 20, 8, 10);
  ctx.fillRect(pos.x + 12, pos.y + 20, 8, 10);

  window.requestAnimationFrame(render);
});

For simplicity, I’ve left out the event handling implementation – it’s enough to know that dpad.left and dpad.right are boolean properties that indicate whether the left and right arrow keys are currently pressed.

As you can see, this code is not functional: the input handling code is updating the state object’s pos.x property in-place. You’ll also see that there are a few other places in the code where we refer to pos. At first glance, it’s hard to see all the spots where we’re reading and writing the state object. We can improve this a bit by factoring out the different concerns into separate functions:

var state = {
  pos: {x: 200, y: 220}  // Manuel's position.
};

window.requestAnimationFrame(function render() {
  clearCanvas();
  drawBackground(state);
  processInput(state);
  drawManuel(state);
  window.requestAnimationFrame(render);
});

That’s better. Now we can see which functions are state-dependent. However, we still don’t know what they do with the state. Do they modify it, or do they only read it? And are there ordering dependencies between the two operations?

Going functional

A purely functional approach will help us address some these problems. First, let’s make the state object immutable, and rename the variable to initialState. The root of the state becomes an immutable map with a single entry named ‘pos’, whose value is another map:

var initialState = Immutable.Map({
  pos: Immutable.Map({x: 200, y: 220})  // Manuel's position.
});

Since JavaScript doesn’t support immutable data structures by default, I’m using Immutable.js, a library which provides efficient, purely-functional versions of commonly-used data structures. The root of the state becomes an immutable map with a single entry named ‘pos’, whose value is another map.

Rather than updating the state directly (which is now impossible), the simplest change we can make to the helper functions is to have them return a new state value. This makes them side-effect free, and moves the burden of maintaining state into the higher-level code. For example, here’s what processInput looks like now:

function processInput(state) {
  var currX = state.getIn(['pos', 'x']);
  if (dpad.right) {
    return state.setIn(['pos', 'x'], currX + 3);
  } else if (dpad.left) {
    return state.setIn(['pos', 'x'], currX - 3);
  }
  return state;
}

Note that state.setIn(['pos', 'x'], <value>) is analogous to calling state.pos.x = <value>, except that it doesn’t modify the object. Instead, it returns a new copy of the state object with the pos.x field set to the desired value.

The next step is to compose the functions into a pipeline, so that state value returned from one function will be passed as an argument to the next:

var newState =
    drawManuel(
    drawBackground(
    processInput(state)));

The final step is to actually do something with the new state object. We can use a technique similar to tail recursion by adding a state parameter to the render function:

window.requestAnimationFrame(function render(state) {
...
});

…and using Function.prototype.bind to ensure that the state is passed as an argument when render is invoked on each animation frame:

window.requestAnimationFrame(function render(state) {
  var newState = ...;
  window.requestAnimationFrame(render.bind(null, newState));
}.bind(null, initialState));

The new, purely-functional render loop now looks like this:

window.requestAnimationFrame(function render(state) {
  clearCanvas();

  var newState =
      drawManuel(
      drawBackground(
      processInput(state)));

  window.requestAnimationFrame(render.bind(null, newState));
}.bind(null, initialState));

This is probably the most straightforward way to transform stateful code into a purely functional style. The old (mutable) state object is now an immutable object called initialState. On each invocation of render, the current state is passed through a function pipeline – each function takes the state as an argument, and returns a new state object to be passed to the next function. A function that only needs to read the state (like drawManuel) can simply return the same object it was passed. A function that needs to update the state can do so by returning a new object with the updated values.

Let’s take a moment to appreciate a few of the things we’ve gained by rewriting this code in a functional style:

• At a glance, we can now see exactly which functions can read and write the state: only the ones in the pipeline that returns newState. A function like clearCanvas becomes easier to reason about, because we know that it can’t affect (or be affected by) the state.
• The main components of the game now have a clearly-defined interface: the state object. This makes the components easier to test.

You can try the purely functional version here.

Adding collisions

Now, let’s make things a bit more interesting: let’s give Manuel an obstacle, and do some simple collision detection to prevent him from running into it. Here’s what the new world looks like with a boulder in it:

To prevent Manuel from colliding with the boulder, let’s write a simple collision detection function:

function handleCollisions(state) {
  var pos = state.get('pos');
  var boulderPos = state.get('boulderPos');
  // If Manuel is overlapping the boulder, move him.
  if (pos.get('x') + 20 > boulderPos.get('x')) {
    return state.setIn(['pos', 'x'], boulderPos.get('x') - 20);
  }
  return state;
}

…and add it to the pipeline:

var newState =
    drawManuel(
    drawBackground(
    processInput(
    handleCollisions(state))));

A bug

If you try this out, it appears to work. But when we write tests for it, we’ll discover that it’s still possible to render a frame where Manuel is occupying the same space as the boulder. Uh oh, what’s going on?

After a bit of debugging, we’ll probably figure out the problem: we’re doing collision detection first, and then moving Manuel into his new position based on the user’s input. It should be the other way around. By changing the order of the functions in the pipeline, we can ensure that collision detection runs after input processing, thus preventing the bug.

It turns out that our purely functional rendering code is sensitive to ordering in non-obvious ways. The first time I encountered this kind of bug, it felt strangely familiar – it’s something that often occurs in imperative programs. This is exactly the kind of problem that functional programming was supposed to help us avoid!

You could argue that the dependency between input handling and collision detection should be obvious. Yes, someone who has developed games before will probably catch this bug before it’s even written. But this is only a simple example – it’s easy to avoid state problems in small imperative examples too. The real problem comes when the codebase grows large enough that there are too many different dependencies to keep track of in any one programmer’s head. And as this example shows, the same problem can happen in purely functional programs as well.

Functional Design, Take 2

A savvy functional programmer will point out that there’s another way to write the rendering loop that would prevent this kind of ordering issue. Instead of each component passing along a new state value to the next component in the sequence, we could instead invoke every component with the same state value as an argument, as if they are all executing simultaneously. It would look something like this:

var updatedStates = [
  processInput(state),
  handleCollisions(state),
  drawBackground(state),
  drawManuel(state)
];
var newState = ...;

With this approach, we’ll quickly run into a problem. Both processInput and handleCollisions can modify Manuel’s position. If they each return a new state object, we’ll have to merge the two states somehow. It’s difficult to figure out how we could do that in a general way, because at this level, we have no idea what part of the structure each function has changed.

A solution to this is that instead of returning a new state object, each component could return a piece of data representing a desired state change. In terms of types, the functions would have type State -> [StateUpdate] instead of State -> State. Here’s what handleCollisions would look like:

function handleCollisions(state) {
  var pos = state.get('pos');
  var boulderPos = state.get('boulderPos');
  // If Manuel is overlapping the boulder, move him.
  if (pos.get('x') + 20 > boulderPos.get('x')) {
    return [{op: 'setIn', path: ['pos', 'x'], value: boulderPos.get('x') - 20}];
  }
  return [];  // No update.
}

Then, at the end of the render function, we can process the list of updates to produce the new state object to be passed to the next render call:

var updates = []
    .concat(processInput(state))
    .concat(handleCollisions(state))
    .concat(drawBackground(state))
    .concat(drawManuel(state));
var newState = applyUpdates(state, updates);

In applyUpdates, we simply need to go through the list of updates, and apply each one in turn to produce a new state object:

function applyUpdates(state, updates) {
  return updates.reduce(function(prevState, update) {
    switch (update.op) {
      case 'setIn':
        return prevState.setIn(update.path, update.value);
      default:
        throw new Error("Unknown op '" + update.op + "'");
    }
  }, state);
}

More bugs

Unfortunately, this solution has some other subtle bugs. Since all of the components are now seeing a consistent state value, it means they can’t observe each other’s changes until the next frame. This means if processInput puts Manuel into the same space as the boulder, it won’t be seen by handleCollisions until the next frame, after we’ve rendered an inconsistent state. Try this version out and you’ll see what I mean.

Additionally, this code is once again sensitive to subtle ordering issues. If two components will modify the same part of the state (e.g., Manuel’s position), then the final result will depend on the order in which we process the changes. Whichever component is processed last will overwrite any previous updates.

This is known as the “lost update” problem. It’s another issue that’s commonly encountered in imperative code with mutable state updates – and once again, we see that it does not automatically go away when we use immutable data structures.

What’s going on?

When I first encountered these kinds of bugs, I was confused – isn’t functional programming supposed to prevent these kinds of errors? How could I have state update bugs in a program without mutable state? After thinking about it for a while, I realized what was happening.

Programming is largely about building models – abstractions that have certain properties and obey a particular set of laws. Immutable data structures are one such abstraction. We use this abstraction (and others) to model the higher-level concepts which make up Manuel’s world.

Each level of the model has its own set of properties, and the properties at one level do not automatically extend to other levels. Our higher level model includes identity: there is a stable, logical entity that we refer to as Manuel, whose position changes from frame to frame. In a sense, we are modelling a mutable object. Implementing that model with immutable data structures does not eliminate the difficulties of dealing with state updates – it just shifts them to a different conceptual level.

As another example, imagine implementing a simple accounting ledger using a grow-only set. A grow-only set is an unordered set to which elements can be added, but never removed. This has the nice property that the order of operations doesn’t matter – if we have a $500 asset and a $200 liability, the balance is the same no matter what order the entries are added.

At this point, both the low-level model (the grow-only set) and the higher-level model (assets and liabilities) share the property that operations are commutative. But what happens if we decide to model asset depreciation? Naively, we might try just adding a new “depreciation” entry to the ledger once a month – but this would not be correct, because the meaning of the depreciation operation is dependent on the state of the ledger when the depreciation occurs. If we add a $1000 asset, then 12 months of depreciation, the final balance should be different than if the asset was acquired yesterday. The operations in the higher-level model are no longer commutative – it doesn’t matter that it’s implemented using a grow-only set.

What now?

After experiencing the kinds of bugs I described above, it became clear to me that – despite their merits – immutable data structures are not a silver bullet. Many programs still need additional support to safely and easily model state updates.

In the first version of the code, we had a bug that was caused by incorrect ordering between two of our components. In that case, all of our components were run in sequence, even when there was no ordering dependency between them. This is actually very similar to the problem with imperative languages – since everything runs sequentially, it’s hard to see what parts of the code have a true sequential dependency (as with our collision detection and input handling) and which parts do not.

In the second approach, we eliminated the sequential dependencies between components. But as we saw, this opened us a new class of errors. Some components do need to be run in sequence, and we had no easy way to detect that. Also, since each component saw the same version of the state, it was as if they were running in parallel. This made the code vulnerable to “lost update” errors, which (again) we had no easy way to detect.

A powerful idea: effect systems

Despite its downsides, the second solution has one big thing going for it: by representing our side effects as plain data, we have more flexibility in how to apply them. For example, we could detect lost updates by raising an error if there is more than one update for a particular location. This would show that there is an ordering dependency between two components that should be addressed by the programmer. This very similar to detecting serializability in databases.

Representing side effects as data is the core idea behind effect systems. In much the same way that type systems manage values, effect systems manage side effects. Most of the work on effect systems has been in pure functional languages, but the idea is more widely useful. Just like with types, you can imagine different kinds of effect systems. The system I hinted at in the previous paragraph could be considered a basic dynamic effect system. That is, we can’t tell what the effects are without executing the program. Most existing effect systems are static, in that effects can be determined at compile time. Other kinds of effect systems could be strong or weak, structural or nominal.

Although there’s a lot to be gained from purely functional techniques, state updates still pose a problem. Immutability is not enough: as I discovered, even purely functional programs are susceptible to state-related errors. Experienced programmers know how to avoid these problems, but it’s important enough to deserve a built-in language solution. I think that effect systems offer a promising approach.

Further reading

• Eff: a functional programming language based on algebraic effects and their handlers
• Effects, a library for side-effect management in Idris
• Lambda the Ultimate: When will we all have effect systems?