Shared NAND Mutable

This post is about computer science. Specifically, it discusses a way of designing programming languages to make them safer and easier for people and the computer to understand.

Mutating shared data

A recently fashionable discipline in programming says that it's bad to mutate a value that is shared, i.e. that can be accessed by more than one path. Here's an example (in Python) of something that this discipline forbids:

    a = [0]
    b = a
    a[0] = 1 # Also affects `b[0]`.

Here are some alternative approaches that are allowed:

    # Approach 1: always access the list as `a`.
    a = [0]
    a[0] = 1

    # Approach 2: `b` is an unaffected copy of the list.
    a = [0]
    b = list(a)
    a[0] = 1

This discipline is sometimes known as "shared XOR mutable". However, this terminology is dumb, because there's nothing wrong with a value that is neither shared nor mutable. I prefer to say "shared NAND mutable". And because that's quite a mouthful, I usually abbreviate it to "shnam". It's an adjective.

Rappers don't...

Programs aren't shnam; languages are. There's very little point in trying to write programs in a shnam way in a non-shnam language. You would find it difficult and error-prone, and you will not get the benefits.

Shnam benefits

So what are those benefits? There are many; it's an idea that pays off at multiple levels of the software stack. I have written about these benefits in the past, so here I'll just summarise.

At the level of human society (teams, ecosystem, etc.) shnam libraries have clearer API contracts. Whenever a value crosses a module boundary (e.g. is passed to or returned from a function), it will always do so with a clearly defined "mode", e.g. one of the following:

Contracts like these exist in every library in every language, but only in shnam languages are they explicitly written, automatically checked, and universally obeyed.

Shnam programs are therefore more correct, and therefore more secure. After memory allocation bugs and incorrect escaping, one of the most common kinds of bug, and security flaw, in real programs is one part of a program mutating a value which another part is assuming will be constant. This is simply impossible in a shnam language.

At the level of the programming language, shnam semantics are much clearer. Pure functional languages boast that they are "referentially transparent", meaning that any reference to a value can be replaced by the value. Shnam semantics are a generalisation of referentially transparent semantics in which mutation is permitted when it is harmless. In both programming styles, it does not matter whether a value is passed by reference or by value; the meaning is exactly the same. This eliminates lots of difficult concepts and some asssociated syntax, and shifts some mental burden from programmers to their tools.

The compiler finds shnam information very useful. The fundamental benefit is that when you store a value in a location, and later read it back from the same location, the compiler can be sure that you will get back the same value, no matter what instructions occur in between. This allows optimisations that are invalid in a non-shnam language.

The same benefit accrues to virtual machines. Much of the inefficiency of an interpreted or JIT-compiled language (e.g. Javascript, Python, Lua) is due to the loss of shnam information in the process of encoding the program into virtual code. Many virtual machines spend significant complexity on mitigating this problem, but treating the symptoms is never as good as curing the disease. In a shnam language values values stored in memory are just as tractable as values stored in registers or on the stack, making these latter concepts unnecessary. My unproven hunch is that a shnam virtual machine can be significantly more efficient.

And what is true for virtual machines is also true for real hardware. Registers, store-to-load hazards, cache coherency, and loose memory models are all problems/solutions caused by a lack of shnam information or by mitigations invented to treat the symptoms thereof. Eventually I hope we will include accurate shnam information in machine code, and build simpler, better CPUs.

Existing shnam languages

The poster model of shnam programming languages is Rust. It is a statically checked language with an ahead-of-time compiler. When a program is compiled, its adherence to the shnam discipline is checked at compile time, after which the program is optimised and compiled to machine code. The part of the compiler that does the checking is called the "borrow checker". Learning how to appease Rust's borrow checker is a famously frustrating process; it is an expert skill which typically requires at least six months of practice. Which is a Bad Thing. However, if you do manage to persuade the compiler to accept your program, then it is likely to behave correctly and to run efficiently.

Before Rust appeared in about 2014, there were pure functional programming languages, which are trivially shnam to the extent that they forbid mutating any value, shared or otherwise. Languages with copy-on-write semantics belong in this group. However, pure functional languages are popular despite forbidding mutation, not because of it. A blog post about shnam languages should focus on languages that allow in-place mutation.

After Rust, imitators are gradually appearing, but in 2025 such languages are still quite uncommon. I know of the following examples:

If you know of other shnam languages I would love to hear about them.

The design space

With the exception of Pony, which is quite weird, the existing languages are all taking a similar approach, with Rust pushing the ideas furthest. I see many unexplored alternatives. I will try to avoid describing a particular language, and I will instead try to speak in general about all possible shnam languages.

In what follows I illustrate some concepts in Rust, which is the most ambitious example of a shnam language so far, and which has appropriate syntax for all of them. It is also probably the most familiar language. These Rust snippets may be ignored, and in any case should not be taken too seriously, because Rust's model does not always align cleanly with mine.

Dynamic

I have yet to see a dynamic shnam language, though it is a simple concept. In such a language, values could be reference-counted to detect sharing, and mutation of a value would be permitted only if its reference count is 1. It surely cannot be long until somebody invents such a language. Note that in such a language mutating a shared value is an error that is detected at run time.

Two modes

The next level of sophistication is a static checker that distinguishes two modes:

Knowing this information statically is very useful. It eliminates the cost of run-time checks, and the possibility of the corresponding run-time errors. Explicitly writing and checking modes is also useful as concise, regular, reliable documentation, complementing any type information.

The language would need "mode operators" to change the mode of a value:

* is partial: not all values can be deep-copied. Indeed, it is precisely the non-clonable values that benefit most from the mutable mode, as a copy-on-write strategy won't work for them. Examples include I/O channels, large values that are too expensive to copy, and values that represent a unique privilege.

$ can also be partial. When you discard a share of a value, you cannot know whether your share is the last. If it is, the value is implicitly destroyed, without your involvement. For some values that might not be appropriate. Examples include I/O channels, valuable unsaved data, and values that represent a unique responsibility.

In a language with these two modes, the typical life-cycle of a value starts with a mutable phase, which ends when the value is first shared, after which it remains shared, until the last reference to it is discarded. Cloning a value makes a fresh value, with its own life-cycle.

Mode-generic operations

An operation that only reads a value and that does not share it can be applied irrespective of the mode of the value. In a language with two modes, such an operation needs to be defined twice: once for each mode:

This repetition could be avoided if the language allows the function to be defined to be mode-generic, i.e. to accept a value of either mode. A caller of the function can pass either a mutable value or a shared value, and the same code will be run either way. A function that respects the limitations of both modes does not need to know the actual mode of the borrowed value. When the function returns, the caller can resume accessing the value with its original mode.

In the next section I describe a better idea.

Three modes

The next level of sophistication introduces the concept of borrowing: receiving a value with the understanding that it belongs to some other owner, in the sense that you have a limited time to use the value before the owner resumes using it with its original mode. The time limit is an unavoidable feature of a loan; if the lifetime does not end then the concept of a loan is unmotivated.

The additional mode is:

Cloning a loan with * makes a mutable value. Sharing it with $ must not increment its reference count, and could be forbidden, or defined to make another loan.

The language would need an additional mode operator:

A loan is strictly more powerful than a mode-generic function parameter, in at least the following ways:

Five modes

A shnam language inspired by Rust might consider two additional modes:

The language would need mode operators for making these new kinds of loan. They could be called &* and &$.

It might be worth including these two extra modes in a language, depending on its design priorities. However, I feel that their motivation is weaker than for the other three:

Pointless modes

Note that Rust can express additional uselessly complicated things:

If we make such simplifications wherever possible, then the closure of the various mode operators imagined so far is the set of five modes that I have enumerated. The set is in that sense complete.

Related design spaces

So far, every shnam language has conflated its shnam aspects with other aspects of its design. This makes sense, as a way of exploiting the benefits of a shnam language. However, it is confusing and distracting if we are trying to understand what makes a language shnam.

Here are some shanm-adjacent considerations which I want to mention but which I don't want to discuss further.

Lifetimes

In OCaml and Hylo, the lifetime of a loan is a function call. The next level of sophistication relaxes this connection, and instead parameterises loan modes by a "lifetime": an abstract compile-time concept which indicates the time interval within which the loan must be used. Of all the shnam languages I've seen, Rust is the only one which goes so far.

The upshot of this design decision is that Rust is the only language of the three in which a function can return a loan. Where Rust would return a loan, the other languages must pass the loan to a callback. This makes Rust more capable, and the other languages simpler.

Memory

Shnam features are useful for enforcing correct use of memory allocation primitives. For example, discarding a mutable value implies a responsibility to free the memory it occupies. For another example, a value that is stack-allocated cannot be lent with a lifetime that exceeds its stack frame.

Rust and OCaml both tie their shnam primitives tightly to their memory allocation primitives, and make proud claims about the problems that this solves. I think this says much about the seriousness of memory allocation bugs, but fundamentally shnam concepts are separable from memory allocation concepts. There is no need to tie them together.

Panic

Like other languages, Rust handles some rare situations by panicking: irrecoverably stopping part of the program. For example, this resort is used if memory allocation fails.

Panicking in Rust interacts with mutable loans; it is forbidden to panic if doing so would discard a mutable loan. The reasoning is that a mutable loan confers a responsibility to give back a value. Since it is in practice not feasible to determine which parts of a program might panic, the burden in practice is that a mutable loan must always have a valid value. For example, it is impossible to implement swap() safely; it must be defined outside the language.

With hindsight, this is an unforced design error in Rust. Panicking could instead have been defined to have the same semantics as non-termination, i.e. the responsibility to give back a value could be deferred forever. Fundamentally, shnam concepts are separable from panic concepts.

Input and Output

Pure functional languages famously struggle to model I/O, because the real world must be mutated in-place, and cannot meaningfully be shared. Non-shnam languages struggle too, though the problems are less obvious. For example, if two unsynchronised programs both read from the same input stream, or both write to the same output stream, your operating system will define a behaviour, but it will not be a useful one. This is particularly the case for buffered I/O. If ever that behaviour actually occurs, it is probably a bug.

In contrast, a shnam language can model the real world as a mutable value. In fact, it can model individual objects in the real world as mutable values: peripherals, storage devices, users, and other computers. A program that attempts I/O on a shared object will simply be rejected; there is no need to implement such a nonsense concept.

Existing shnam languages have to run on non-shnam operating systems, which do implement a lot of nonsense concepts. It is easy to forget that the familiar POSIX-like abstractions are an early attempt using antiquated technology, and that things don't have to be that way. I don't feel we've yet seen a serious attempt to define a shnam I/O library.

Structures

In this section I will discuss a puzzle that every shnam language must solve: how to define data structures, by which I mean values that have internal structure. Examples include tuples, arrays, closures and objects. Some languages even allow the programmer to define new kinds of structure. Structures can contain other structures. In the absence of sharing, data structures form a tree. With sharing they form a directed graph.

In a shnam language, the directed graph is acyclic. There is no way of constructing a cyclic structure without mutating a value that you share with the value you are trying to store into it; and mutating a shared value is forbidden! Consequently, recursion on a shnam data structure always terminates, and a common bug is impossible. Moreover, shnam reference counting cannot leak memory.

The restriction to acyclic structures disallows a number of well-known data structures, such as a doubly linked list, but experience suggests that alternatives generally exist. An interesting example is the represention of code. In a shnam language you can easily represent structured programming primitives, such as a "while" loop. However, to represent an arbitrary "goto" you have to invent a way of labelling the destination.

Another non-obvious feature of shnam data structures is that you cannot reliably detect sharing using pointer equality. Since there is no semantic difference between passing by value and passing by reference, there is no guarantee that a pointer even exists. If the identity of a structure is important, it must include some sort of primary key.

How deep is a Copy?

For a language with modes, I described the "clone" operator (*) as making a "deep copy" of a value, so that its reference count is 1. For simple values, including integers and pointers to static constants, it suffices to allocate some memory for the copy and to copy the bits of the value into that memory. Things get more interesting for structures.

There is no objectively correct way to define how to copy a value. At the shallow end of the design spectrum it might copy just the topmost layer of the structure, such that the copy shares its immediate contents with the original. At the deep end, it might recursively copy every reachable part of the structure, removing all sharing. Most existing languages allow the programmer in some way to declare how deep the copy goes.

In non-shnam languages, a single definition "deep copy" is sometimes frustratingly inadequate. The depth of a copy determines how much of the program is affected by mutating the copy in-place: a semantic question that grapples with external requirements. In a shnam language there is no such concern: no other part of the program is affected by in-place mutation. Instead, the principal concern is the compromise between:

Since the shallowest copy limits the benefits, any deeper copy operation is unnecessarily costly. Thus, we can define * just once for each data type.

The effect of this is that individual fields of a structure acquire modes. Fields through which * recurses are known always to have a reference count of 1, if the structure as a whole does, and can be mutated in place. Conversely, fields at which * terminates might be shared even if the structure as a whole is mutable. We recognise these cases as the two modes "mutable" and "shared". Declaring the fields of a structure with one of these modes effectively defines the behaviour of *.

In a language with loans, some fields of a structure might be loans. * terminates at such fields. Loans have a limited lifetime, and since the structure cannot exist without its fields, it too has a limited lifetime. Note that this gives an example of a non-loan value with a limited lifetime. To avoid that complexity, a language could forbid structures that contain loans.

Tuples

The simplest data structure is perhaps a tuple: a way of treating a group of zero or more values as a single value. A tuple type consists of the types and modes of its fields. Constructing a tuple merely involves providing values for its fields, and destroying the (mutable) tuple returns those values with their original modes.

Given a share of a tuple, you can non-destructively obtain shares of its fields. Given a loan of a tuple, you can non-destructively obtain loans of its fields. Given a mutable loan of a tuple, you can mutate its fields by first destroying the tuple and later reconstructing it. In Rust these operations are built into the language. I can imagine instead providing them as part of the standard library.

Like all structures, destroying one share of a tuple merely decrements its reference count. Destroying the last share of the tuple recursively destroys its fields; there is no opportunity to recover their values.

Arrays

An array is a data structure that contains zero or more values of the same type and mode. If the length of the array is constant, then the array is a special case of a tuple, but in general the length is not part of the array type. Constructing and destroying an array is broadly analogous to the same operations on tuples, though an unknown length complicates things. The unique feature of arrays is that they provide random access to their elements.

Constructing an array involves providing values for each of its elements. The initial values for the elements of a fixed-size array ([Type; length] in Rust) could be computed by cloning a default value, by applying a function to each array index, or by drawing values from an iterator. Alternatively, a growable array (a stack, Vec<Type> in Rust) could be constructed by pushing values onto an initially zero-length array (pushing and popping are forms of mutation).

To destroy a mutable array it is necessary to do something with its elements. For example, you could pass them one by one to a drop() function. A growable (mutable) array can be emptied by popping its values, and then destroyed.

Rust's into_iter() method turns an array into an iterator that yields the values one by one. Turning a share of an array into an iterator yields one share of each of its elements. Turning a loan of an array into an iterator yields loans of its elements, if the language allows it.

Random read access to an array requires sharing or borrowing it. Given a share of an array, and an array index, you can obtain a share of one element. Given a loan of an array, and an array index, you can obtain a loan of one element. Some languages have the concept of a "slice", which behaves like a loan of a contiguous subarray (&[Type] in Rust). A loan of an array can be turned into a slice of the whole array. A slice can be broken into shorter slices, and permits random access to its elements.

Random write access to an array is analogous. Given a mutable loan of an array and an array index, you can obtain a mutable loan of one element. Equivalently (e.g. in a language without mutable loans) given an array index and a closure that takes and returns one element, you can obtain a closure that takes and returns an array.

Note that these primitives do not allow simultaneous mutation of more than one element of an array. For example, to safely swap two elements of an array, you would have to swap the a dummy value in place of the first element, swap that in place of the second, and finally swap that in place of the dummy value. One can imagine more sophisticated primitives for accessing array elements, but here I am content to show existence.

Rust has the concept of a mutable slice (&mut [Type]), but puts restrictions on what you can do with it. For example, you cannot swap two mutable slices (partial work-around), nor assign a slice to a mutable slice (partial work-around). Therefore, a mutable slice in Rust is not just a mutable loan of a contiguous subarray. A hypothetical language which does allow a mutable loan of a contiguous subarray would be quite powerful, but difficult to implement efficiently.

Closures

Nearly all modern programming languages have closures: functions that mention free variables. Terminology:

Each time the function definition is evaluated, the values of its free variables are "captured" and become part of the closure.

In a non-shnam language, the type of a closure depends only on the types of its arguments and of its return values. The types of the captured variables have no effect on the type of the closure, meaning that it is possible to call the closure without knowing about them.

In a shnam language, all this remains true. However, the captured variables have modes as well as types, and the modes cannot be entirely hidden within the closure. Mode information leaks out and affects the type of the closure, so as to impose on every caller the responsibility to treat the captured values properly.

To be specific, a shnam function type must answer the following questions:

Supposing just two possible lifetimes (as in Hylo and OCaml) these three questions make eight different kinds of closure. Rust's design does not align perfectly with my analysis, but it does distinguish closures according to what traits they implement: one of FnOnce, FnMut and Fn; maybe Clone; and their lifetimes.

A language can choose to place restrictions on closures to reduce the variety of concepts. Obviously this makes closures less useful. Examples of sensible restrictions include:

Objects

Many programming languages have objects. Rust does not, but it does allow methods to be defined for types, which is all that I require in this section.

A method of an object typically has a special argument called self (Python, Rust, Hylo) or this (Java, Javascript, C++) which is bound to the object when the method is called. In a shnam language, this special argument has a mode, like all function arguments do. Depending on the mode of self, the experience of calling the method is quite different:

A closure can be imagined as an object with a method called call(). It is interesting to compare the different kinds of closure to the different kinds of method that call() might be. The correspondence is not trivial. Closures that capture a mutable loan also need a method that destroys the closure and repays the loan.

A tuple can be imagined as an object with automatically-generated methods for accessing its fields.

Summary

I think shnam languages are probably The Future, and that we have yet to see a typical example. Rust will no doubt remain popular for decades, but it will never replace Python, for example, whereas some other shnam language eventually will. We have only recently solved some of the puzzles necessary to make a shnam language, and it is not yet clear that we have found the best solutions; people inventing shnam languages today (including me!) are still fumbling around the design space. We have barely started exploiting the benefits of shnam languages, especially in virtual machines and in hardware. I expect this to be a fruitful area of research for many years.

Last updated 2025/05/23