You Might not Need Immutability - Safe In-Place Updates
Tags: javascript, node, functional
Published: 2020-12-25 19:59:10

---
title: You Might not Need Immutability - Safe In-Place Updates
published: true
description: 
tags: #javascript #nodejs #functional
//cover_image: https://direct_url_to_image.jpg
---

[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:

```javascript
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:

```javascript
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:

```javascript
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](https://repl.it/@scriptum/GrowlingUniqueSource#index.js)

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:

```javascript
// 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](https://repl.it/@scriptum/LoyalDarkkhakiUnix#index.js)

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:

```javascript
// 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](https://repl.it/@scriptum/EnragedReflectingEquation#index.js)

The principles should be clear now.

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

```javascript
// 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](https://repl.it/@scriptum/MellowStridentVendor#index.js)

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`:

```javascript
// 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](https://repl.it/@scriptum/DependentFuzzyPixels#index.js)

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](https://github.com/kongware/scriptum/blob/7fda63a2392e417ddd83bae7467612fc9a69702b/index.js#L4424) on Github.