Notes
2026/09/27
(This is even more of a sketch than most other notes, see later notes for viable options.)
Let's say we have a compiler that does last-use analysis so that we know when a variable is used for the last time in a lexical scope. Is it safe to mutate that variable (so that no other observers can see the effects of mutation) at the point when it is last used? Not unless we know more about the lifetimes of all of the usages of that variable. Here's an example:
{
l = [1, 2, 3] // l goes into scope
m = f(l) // l is first used here
g(m, l) // l is last used here, but m could still depend on l
}
Just knowing that l is last used in g(m, l) is not enough to know whether l can be safely mutated by g. We need to know more about the lifetime of l in f(l): Does f just read from l? Then it's safe for g to mutate l. Does f return l or store l so that it outlives f? Then it's not safe for g to mutate l. In code:
{
k = []
{
l = [1, 2, 3]
f(x) = { len(x) }
m = f(l) // m does not keep l alive
g(m, l) // safe for g to mutate
}
{
l = [1, 2, 3]
f(x) = { x }
m = f(l) // m keeps l alive
g(m, l) // cannot mutate l
}
{
l = [1, 2, 3]
f(x) = { push(k, x) }
k2 = f(l) // l outlives f
g([], l) // cannot mutate l
}
}
How can we figure out whether l still has active observers at the point when g wants to mutate it?
The first option is to simply track the number of active observers on the target, in our case the underlying list of l. Whenever we create a reference to l, we increment the reference count. Whenever a reference is destroyed, we decrement the reference count. When we want to mutate l through a reference, we simply check whether the reference count is exactly 1, which would mean that we're the only observer and can safely mutate the underlying list.
This sounds easy enough, but only works well if reference counting is precise. Many languages are imprecise and only decrement the reference count when a reference goes out of scope, not immediately when a reference is last used. In our first example above (where f(x) = { len(x) }) it would be safe for g to mutate l, but if the reference to l is only destroyed when it goes out of scope then we would still have a reference count of 2 at the point of g(m, l) and g would be forced to copy l instead of mutating it.
Perceus as implemented in the Koka language is the classic example of precise reference counting in a functional language.
Another option is to check at the point of mutation whether there are any remaining active references, by walking through any regions in memory that could contain references to the value we want to mutate. The phrase “any regions in memory” is potentially doing a lot of work here, because a completely unstructured language runtime that allows pointers from anywhere to anywhere would have to walk the entire stack and everything allocated by the language on the heap, on every mutation.
This is obviously not practical, so we have to guarantee that the relevant region remains bounded, for example by only allowing references to point backwards in the stack and disallowing those references to be stored on the heap. This then restricts the region that we need to walk on the stack to the range between where the value first appeared (in our example where the underlying list l is first allocated on the stack) and where the mutation happens. Everything that has been allocated on the stack between these two points in time could potentially contain references to the value that we want to mutate.
This is better, but would still lead to a uniqueness analysis whose cost grows linearly in a lot of cases. For example, let's say we want to pop elements from a list l and push them onto a list m, both stored as elements on the stack. The list l sits at the bottom of the stack, the list m at the top. Whenever we want to pop from l, we need to walk over all of m and check that it doesn't contain any references to l, but m grows with each iteration and so does our uniqueness analysis walk.
If we want to be able to do uniqueness analysis in constant time per iteration, we need to be able to skip over the parts of the stack that grow but that we can safely ignore for our analysis, so that the parts to be checked remain of a constant size. This is easy enough to do for specific cases, but hard to generalize. For our two-list example, we could store a bit that indicates whether a list contains any references to a value that might be mutated later in the scope, which would allow us to hop over m, but such a bit is necessarily conservative and can't keep track of different mutable references. (For example, what if m doesn't store a reference to l, but to some other mutable list n?)
The more general observation is that we need to keep track of lists that have already been visited. By recording previous visits, we can potentially avoid doing the same work again, thus trading space for time.
For now, this is still a vague idea that I need to explore more.
The last option is to stop worrying about whether there are any other observers when we mutate and simply mutate optimistically and then fail later with a runtime error whenever a remaining observer tries to read or write the (now mutated) value. While reference counting has to do work both when reading and mutating through references, and tracing the stack tries to do the work when we finally want to mutate the value (but keeps reading simple), mutating optimistically makes mutating simple but requires the readers to do the work, since every read has to ensure that the reference hasn't gone stale.
While the easiest implementation strategy is to just set a bit after a value has been mutated, this would mean that any read after it would fail, even if the reference was borrowed after the value was originally mutated. A better option might be to store a monotonically increasing version number on lists and increment it whenever a mutable reference is first written through. Any read-only borrow would then record which version it was borrowed against and fail at runtime on a read if the underlying value has a different version.
The resulting language would effectively have a Rust-like ownership system, but one that is checked at runtime instead of statically.
The big problem is that such a language would not be a purely functional language anymore because it would effectively give up referential transparency: A function that simply reads the same borrowed value could fail or succeed for the same function arguments depending on whether some other observer has mutated the underlying value somewhere else. Even worse, the effects of such a violation would not be raised at the write site where it first happens and instead only be caught later at the read site.
What's the takeaway? Reference counting seems to be the only proven strategy for functional languages here. Perhaps it's not worth spending innovation tokens on other approaches, especially since trying to trace-and-record uniqueness walks seems far trickier to get right, and mutating optimistically means giving up functional purity.