Elixir's Immutability is Not Magic

Elixir is an immutable programming language. But what does that actually mean?

Let's start with what it doesn't mean. Here's some JavaScript.

    
      const a = 100;
// This is an error
a = 'foo';

The variable a here is an immutable variable, better known as a "constant". A variable declared as a constant cannot be rebound, but this says nothing of the immutability of what it points to.

Observe.

    
      const a = [100];
const b = a;
b[0] = 'foo';
console.log(a); // => ['foo']

Even though a is a constant and cannot be rebound, the object it points to is entirely mutable! This is unfortunate, because it means we cannot reason about the value of a after passing it somewhere.

There is a way around this. Every time we want to change the object, we can copy it first. This technique is called copy-on-write. The problem is that if we have a large, complex object, we need to copy the entire thing just to change a small part of it.

    
      const a = [...Array(1000).keys()].map(i => [i]);
const b = structuredClone(a);
b[0][0] = 'foo';
console.log(a); // => [[0], [1], [2], ...]
console.log(b); // => [['foo'], [1], [2], ...]

Here we have an array with 1000 more arrays nested inside of it. We only wanted to change a single array, but we had to copy the other 999 arrays just to do it.

Elixir does not have this problem.

    
      # Tuples are Elixir's equivalent to arrays
a = Enum.map(0...999, fn i -> {i} end) |> List.to_tuple()
b = put_elem(a, 0, {"foo"})
dbg(a) # => {{0}, {1}, {2}, ...}
dbg(b) # => {{"foo"}, {1}, {2}, ...}

This Elixir code is equivalent to the JavaScript code above, but with one key difference: the outer tuple is copied, and the first inner tuple is replaced, but the other 999 tuples are not copied. All 999 of them point to the same locations in memory as they did before.

This sounds like magic. How does Elixir know which parts to copy and which parts to keep the same? What if I go back and change another one of those inner tuples? It sounds like you would need some sort of fancy persistent data structure to make this work.

I am going to try to convince you of two things:

It's not magic
It's actually very, very simple

The Power of Guarantees

Let's go back to that JavaScript code. We had to deep-copy all of the nested arrays just to preserve the immutability of the outer array. Why is that?

Well, in languages like JavaScript an "array" is an object which exists somewhere in memory (on the heap). When we assign the "array" to a variable, the variable actually contains a pointer to the array. And when we access an element of the array, like a[0], the program will follow that pointer to the actual object in memory and return the value.

In languages like C you're allowed to manipulate these pointers freely, but JavaScript is much more restrictive in this regard. They can only reference a known object.

Where JavaScript is not restrictive, however, is in regard to mutating the object itself. By manipulating the contents of the array, you are allowed to change the bytes of the object that pointer is pointing to. This is mutability, and it's the cause of our problems.

But hold on a minute. What if we all just agreed to never do that?

    
      const inner = [100];
const a = [inner];
// This shallow copy is perfectly safe, as long as we
// pinky-promise to *never* mutate `inner`
const b = Array.from(a);
b.push(['foo']);
console.log(a); // => [[100]]
console.log(b); // => [[100], ['foo']]

    
  

That's funny. As long as we uphold our promise to never mutate the inner array, it's safe for any other shallow-copied data structure to leave its pointers intact. There's no need to waste memory with deep copies of every little thing.

That's the power of making a guarantee. As long as we can be absolutely sure no mutations will take place, we never have to worry about it.

The Elixir Guarantee

Here's something that may surprise you: Elixir's memory layout is not meaningfully different from that of JavaScript.

If you create a tuple, Elixir's equivalent to an array, it's just a pointer to a location in memory. And if you create another tuple with that tuple inside of it, the outer tuple will hold a pointer to the inner tuple on the heap, just like in JavaScript.

The difference between Elixir and JavaScript is that in Elixir the API to mutate a tuple simply does not exist. Have a look at put_elem/3.

    
      a = {1, 2, 3}
b = put_elem(a, 1, "foo")
dbg a # => {1, 2, 3}
dbg b # => {1, "foo", 3}

That's right, a call to put_elem/3 always shallow-copies the tuple. There is no API to mutate the tuple, or any other term, in-place. Which means it's perfectly safe to hold on to pointers to other terms.

    
      enormous_list = Enum.to_list(1..1_000_000)
a = {enormous_list, enormous_list}
b = put_elem(a, 0, "foo")
dbg a # => {[1, 2, 3, ...], [1, 2, 3, ...]}
dbg b # => {"foo", [1, 2, 3, ...]}

Naively, you might expect this code to produce three copies of enormous_list, taking up three times as much memory. But, actually, both tuple a and tuple b are only holding pointers to the list. So the memory used by this program is effectively that used by enormous_list, plus the two (negligible) tuples.

Notice that we didn't even add anything to JavaScript's model to get this functionality. All we did was take something away.

Not magic, very simple.

Bonus Round: Escape Hatches

Elixir has several mutable "escape hatches" which are useful for edge cases where mutability is actually what you want. However, none of them actually violate the guarantee above, because none of them are terms.

The Process Dictionary stores references to terms on the process's heap. The terms themselves are just the same Elixir terms, and they remain fully immutable. Only the process dictionary itself is mutable, and it cannot be referenced within another term, so it cannot break our guarantee.
An ETS Table is a mutable in-memory key/value data structure that can be shared between processes. Like with the Process Dictionary, terms stored within an ETS table are immutable, and it's only the table itself which is mutable. Unlike the Process Dictionary, terms are deep-copied in and out of the ETS table, but that's because it's shared between processes. An ETS table is referred to by a reference term, which is a standard (immutable) term.
The persistent_term module is conceptually similar to the previous two, except that the table itself is actually globally immutable (across processes) and copied on write. Terms are copied into persistent_term from a process but are not copied out. Old terms and old copies of the table are (globally) garbage-collected. These properties are useful for global data that is rarely updated but frequently read.
The atomics module allows Elixir programs to take advantage of a CPU's native atomic instructions for efficient synchronization across processes. An atomics array is referred to by a reference term, similar to an ETS table.

Of these, the Process Dictionary and persistent_term cannot be referenced at all as they are (contextually) global. An ETS table can be referenced by its reference, but an ETS table is better thought of as a database than a data structure.

An :atomics array is the closest thing Elixir has to a truly mutable term, and they're rarely used in practice. Of course technically the reference term is immutable and access is regulated by functions like :atomics.get(), but conceptually they are mutable objects. It's hard to get around this as atomic instructions are an inherently mutable paradigm, and for certain situations they can be a very handy performance trick.

Elixir's Immutability is Not Magic

It's just a matter of providing strong guarantees.

The Power of Guarantees

The Elixir Guarantee

Bonus Round: Escape Hatches