Notes
2026/07/31
Let's assume we have a unified bytecode representation that allows us to represent nested lists flat on the stack in a functional language. Can we support Koka/Perceus-style “functional-but-in-place” mutation, in other words mutate lists directly if there's only a single observer, so that the mutation doesn't violate referential transparency?
Existing approaches like Perceus or Mutable Value Semantics (MVS) depend on a combination of static analysis and reference counting. Reference counting (well, precise reference counting in the Perceus sense) tells us how many observers a value has: If it has a ref count of 1, we can safely mutate it because no one else is around to witness our shameful act of direct bit twiddling. In functional programming, we keep our perversions confined to our own bedroom, safe from prying eyes.
Can we get functional-but-in-place mutation even without full ref counting? Yes, if we can maintain the invariant that all of our references only point backwards on the stack, to values older than the references. If that's the case, we can safely mutate any values on top of the stack, because no one else can hold a reference to them. This is how we can trivially push / pop / set an element in a list.
That's trivial, but not very powerful. What if we want to pass a nested list to a function, together with some other arguments, mutate the list in the function and then return it? If nobody else holds a reference to that nested list, we'd like to mutate it in place. We would also like to guarantee that all function arguments are passed by reference (to make it cheap to shift around and reorder function arguments, some of which might come from a closure). But now we have a problem: If everything is passed by reference and we don't ref count, we need to assume that our ref to the nested list isn't the only one and we thus can't safely mutate through it.
Can we do better, without full ref counting? Yes, if we're willing to explicitly distinguish between shared values (which support borrowing through an arbitrary number of refs and need to be copied-on-write) and unique values (which can only have a single ref that supports mutation). If we want to efficiently mutate a value that we own, we need to mark it as unique in the code:
f = (l, i) => {
l[i] = 10
}
// x is shared
x = [1, 2, 3]
f(x, 0) // x gets copied-on-write
// y is unique
y = uniq([1, 2, 3])
f(y, 0) // y is mutated in place
Instead of storing the exact number of refs (as we would with ref counting), we just store whether a value is unique or not, as a single bit on a value. In contrast to ref counting, we don't need to update this information on any read or write, we merely need to set the bit once: uniq(...) only sets the bit to mark a value as unique if the value sits at the top of the stack (at which point it's guaranteed to be unique), deep copying the value onto the top of the stack if the value isn't already there. The result of uniq(...) on the stack is an owning ref, which safely allows mutation, because only one ref can ever exist for a unique value. If we try to create a borrowed ref to a value that has the uniqueness bit set, the ref instead defensively deep-copies the uniquely owned value (turning the copy into a normal value), preserving the invariant that only one ref to it can ever exist.
An owning ref can be passed directly into a function, effectively giving us move semantics. What happens if we try to use y after it has been moved into the function? In a fully dynamic language the only option would be to throw an error on access. Or we could add a very simple ownership system (without tracking lifetimes).
When is the uniqueness bit unset? We have several options: We can make all mutating operations return the owning ref once they're done, and add an explicit share(...) operation that turns an owning ref back into a regular shared value. Or we can make use of the fact that every compaction knows which values are still referenced, so we could update the uniqueness bits of compacted data on every return.
There are a few ways in which we can further improve on this little ownership system: Whenever uniq(...) is applied to a value that is not at the top of the stack (and thus would naively need to be deep-copied), we can walk from the top of the stack downwards until we reach the value. If we don't find a borrowed ref pointing to it along the way, we know that the value is still unique and we can safely set its uniqueness bit to 1 without deep-copying it. We can further improve on it by only walking down the stack if the distance to the value is smaller than the full extent of the value (because deep-copying isn't a big deal when the value's size is small).
This brings up the question of how explicit we want our ownership system to be. We could just deep-copy whenever it is necessary, but perhaps there's value in exposing uniqueness in the surface syntax? We could then for example decide that we only want to mutate a value if it's truly unique (if it is an owning ref), otherwise (if it is a borrowed ref) we choose something that's more efficient than a full deep copy. All we need is a way to branch depending on whether a ref is an owning ref instead of a borrowed ref:
if is_owning(x) {
x[0] = 10
} else {
// do something more efficient here
}
We could also imagine an operation that combines the walk that checks whether the current borrowed ref is the only ref (in which case we can turn it into an owning ref) with the check above, allowing us to try to get an owning ref in the then branch, or a regular borrowed ref in the else branch:
if try_uniq(x) {
x[0] = 10
} else {
// do something with the borrowed ref here
}
Where should the line between implicit and explicit behavior be drawn? Should a push/pop/set operation implicitly deep-copy if the operand isn't unique? Should uniq(...) implicitly walk the stack to check that there's no existing borrowed ref instead of immediately deep-copying? Is this maybe where a simple static ownership system makes sense, by only distinguishing between unique and shared values (while keeping lifetimes implicit, thus making it more ergonomic than Rust's borrow checker)? I'm not sure I have a good answer here yet...
One pathological case that stretches this uniqueness system to its limits is the following:
x = uniq([])
// let's imagine a loop for simplicity, but this could also be tail recursive
for _ in 0..10000 {
x = push(x, [1, 2]) // each time we push a _pair_, not just an atom
}
The important part is that while x is unique and thus can be easily mutated, the element that we push (a new list [1, 2] in every iteration) is not atomic. We thus need to store a reference per pair in our accumulator x, but the problem is that a pair [1, 2] lives higher up on the stack than x, so a reference from within an element of x to a pair [1, 2] would violate our invariant that refs always point down the stack, never higher up. The result is that the entire list needs to be copied (not deep-copied, just the list of refs storing the elements) on each iteration.
Is this a problem? Maybe that's fine in practice? The constant factors would probably still be pretty good, because it's effectively just an array with pointers on the stack that needs to be copied each time. And if it turns out to be a problem, there are potentially still ways in which we could address this, for example by allocating a larger area for the list x than we need, which would allow us to allocation its elements before the list (effectively turning x into a little arena). Not sure that's worth the implementation complexity, but it could be worth a shot.