You Might not Need Immutability - Safe In-Place Updates

[Editor's note: see edit at the bottom]

What makes destructive/in-place updates of mutable values like Array or Map harmful? First of all, they represent a side effect, that is an implicit process not directly evident from the code. We should always strive for expressing our intentions explicitly.

Moreover reference values can be shared by copying the reference with the consequence that side effects may pop up throughout the application, causing race conditions and other unexpected behavior.

So why bother using in-place updates at all? Well, they can lead to quite performant and intuitive algorithms in certain scenarios. The question is rather whether there is a way to benefit from these attributes without jeopardizing the application's predictability and maintainability.

As it turns out we can. All it takes is a special data type which decouples mutable values from the global scope and rules out reference sharing. Here is a first implementation of such a generic type:

const record = (type, o) =>
  (o[Symbol.toStringTag] = type.name || type, o);

const app = f => x => f(x);

const Mutable = clone => refType =>
//     clonable ^^^^^ constraint
  record(Mutable, app(([o, refType]) => {
    o.mutable = {
      run: k => {
//         ^ continuation (A)

        // rule subsequent calls out
        o.mutable.run = _ => {
          throw new TypeError("illegal subsequent inspection");
        };

        // rule subsequent calls out
        o.mutable.set = _ => {
          throw new TypeError("illegal subsequent mutation");
        };

        return k(refType);
//             ^^^^^^^^^^ call-at-most-once semantics (B)
      },

      set: k => {
//         ^ continuation (A)
        k(refType);
//      ^^^^^^^^^^ call-any-number-of-times semantics (B)
// but discard the result (C)
        return o;
      }
    }

    return o;
  }) ([{}, clone(refType)]));

Mutable takes two arguments, the mutable value refType we want to perform in-place operations on and a function clone that knows how to create a shallow copy of this value. A shallow copy is necessary to decouple refType from the parent scope, which narrows the scope where the mutations are actually observable.

Next we create two closures run and set wrapped in an object, which each hold the mutable value as a free variable and expect a continuation (B), which is the only means to interact with this value. The first closure allows us to inspect refType, whereas the second one merely performs mutations on it while discarding the result, because it is only interested in the side effects.

By the way, a continuation is just a partially applied function with a function argument as its last formal paramter:

const inck = x => k => k(x + 1);
//                ^^^^^^^^^^^^^ this is the continuation

By using continuations we turn the usual call mechanism upsite down: Instead of passing a value to a function we pass it the other way around. By relying on this mechanism the run/set closures are able to completely control how k is applied to the mutable value and what happens with the result. It is the prerequisite for modelling functions with call-at-most-once (run) and call-any-number-of-times (set) semantics respectively in Javascript.

Now we can perform as many in-place updates as we want (via set), but only until a function in our application inspects the mutable value (via run). Once inspected the value is owned by this function and can neither be inspected again nor be further updated. I borrowed the ownership concept from the extraordinary Rust language, where it is implemented on the language level in a way more sophisticated manner.

Enough with the theory though. Let's take a look at two examples to see how Mutable works in practice:

const reduce = f => init => xs =>
  xs.reduce((acc, x) => f(acc) (x), init);

const concat = xs => ys => // performs in-place updates
  (xs.push.apply(xs, ys), xs);

const flatten = reduce(
  acc => xs => concat(acc) (xs)) ([]);

const xss = [[1], [2, 3], [4], [5]];

flatten(xss); // [1, 2, 3, 4, 5]
flatten(xss); // [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]

run code

This is a contrived, simple example and yet it is not easy for the untrained eye to pick up the side effect leak. Let's see what happens if we encode this computation with our new Mutable type:

// Mutable combinators
const mutRun = k => o =>
  o.mutable.run(k);

const mutSet = k => o =>
  o.mutable.set(k);

const arrClone = xs =>
  xs.concat();

const MutableArr = Mutable(arrClone);

// adapted computation from the first example

const reduce = f => init => xs =>
  mutRun(id)
//^^^^^^ inspect the mutable value once (C)
    (xs.reduce((acc, x) =>
      f(acc) (x), MutableArr(init)));
//  make in-place ^^^^^^^^^^ updates explicit (A)

const concat = xs => ys =>
  mutSet(xs_ =>
//^^^^^^ perform any number of in-place updates on the mutable value (B)
    (xs_.push.apply(xs_, ys), xs_)) (xs);

const flatten = reduce(concat) ([]);

// MAIN

const xss = [[1], [2, 3], [4], [5]];

flatten(xss); // [1, 2, 3, 4, 5]
flatten(xss); // [1, 2, 3, 4, 5]

run code

As you can see the problem just vanished and this holds not only for this specific case but for the entire error class. Let's go through the necessary transformation. It is a pretty mechanical process:

1. identify the mutable value and wrap it with Mutable (A)
2. use the mutSet combinator to perform as many in-place updates on this mutable value as you need (B)
3. use the mutRun combinator to inspect the mutable value once at the boundary of your impure computation (C)

Inspecting the mutable value with mutRun(id) just means that we are only interested in the reference itself, instead of looking up an element or retrieving the length.

The seasoned functional programmer might be concerned why the in-place updates rely on strict evaluation? They are right, it should be non-strict but for the sake of simplicity I leave it as is at this point.

With the next exmaple we are going to trigger a couple of error messages which may give an insight of Mutable's proper use:

// Map instance

const mapClone = m =>
  new Map(m);

const MutableMap = Mutable(mapClone);

const mapSet = k => v => m =>
  mutSet(m_ => m_.set(k, v)) (m);

const mapUpd = k => f => m =>
  mutSet(m_ =>
    m_.has(k)
      ? m_.set(k, f(m_.get(k)))
      : m_) (m);

const mapGet = k => m => m.get(k);

// MAIN

const m = MutableMap(new Map());

mapSet("foo") (1) (m); // in-place update
mapSet("bar") (5) (m); // in-place update
mapUpd("bar") (x => x * x) (m); // in-place update

const m_ = mutRun(id) (m); // inspection

console.log(m_); // Map(foo: 1, bar: 25)

// you must not perform further mutations from now on

try {mapSet("foo") (1) (m)}
catch (e) {console.log(e.message)}

// you must not perform further inspections from now on

try {mutRun(m => m.size) (m)}
catch (e) {console.log(e.message)}

run code

The principles should be clear now.

We haven't covered race conditions yet. Let's see how Mutable can help alleviating the problem:

// auxiliary functions

const delayf = f => ms => x =>
  new Promise((res, rej) => setTimeout(x => {
    try {return comp(res) (f) (x)}
    catch (e) {return rej(e.message)}
  }, ms, x));

const comp = f => g => x => f(g(x));

const id = x => x;

const arrClear = xs =>
  xs.length = 0;

const arrHead = ([x]) => x;

const sqr = x => x * x;

// MAIN

const xs = [3, 4, 5],
  ms = Math.round(Math.random() * 100);

const foo = delayf(comp(sqr) (arrHead)) (25);

const bar = delayf(arrClear) (ms); // unsafe in-place update

foo(xs).then(x =>
  console.log(
    `foo retrieved head from [${xs}] and evaluated to ${x} after 25ms`));
//    will eventually log [] ^^^^^^^          and NaN ^^^^
bar(xs).then(x =>
  console.log(`bar cleared array after ${ms}ms`));

run code

If you run the program often enough you will eventually reproduce the race condition. Imagine what a nightmare race conditions may evolve into in larger codebases.

Here is the same application encoded with Mutable:

// auxiliary functions

const delayf = f => ms => x =>
  new Promise((res, rej) => setTimeout(y => {
    try{comp(res) (f) (y)}
    catch (e) {rej(e.message)}
  }, ms, x));

const sqr = x => x * x;

// MAIN

const xs = MutableArr([3, 4, 5]),
  ms = Math.round(Math.random() * 100);

const foo = delayf(comp(sqr) (mutRun(arrHead))) (25);

const bar = delayf(arrClear) (ms); // safe in-place update

foo(xs).then(x =>
  console.log(`foo retrieved head from MutableArr
  and evaluated to ${x} after 25ms`));
//                 ^^^^ will either log NaN...

bar(xs)
  .then(x => console.log(`bar cleared array after ${ms}ms`))
  .catch(e => console.log(`bar triggered exception "${e}"`));
//   ...or trigger an "illegal subsequent mutation" ^^^^ error

run code

How is this any different from the previous example? Unfortunately Mutable doesn't provide a strong enough guarantee to avoid race conditions from occurring in the first place. This isn't Rust after all. But at least the type produces immediate errors, either NaN or TypeErro("illegal subsequent mutation") in the example above. While Mutable doesn't save us from race conditions altogether, it helps us detecting them.

You can think of Mutable as kind of interpreter that assists you in creating exclusively safe in-place updates. It is a bit of a pain in the neck to be honest. But if you think it over you might come to the conclusion that a type yelling at you on unsafe mutations is way better than pinpointing subtle bugs caused by unleashed side effects.

[EDIT]
Mutable's implementation is too strict. It has a copy-exactly-once-then-write semantics but should have copy-at-most-once-on-first-write. Additionally a variant is needed that only copies if the mutable value is actually needed, i.e. consumed.

You can see the current implementation as part of the scriptum library on Github.