Notes
2026/09/12
Let's assume a functional programming language that keeps all lists on the stack, as flat arrays that either store atomic values like ints directly or store (stack-internal) pointers to more complex data structures. Let's also assume that pointers are only ever allowed to point to older items (that are sitting lower) on the stack, which effectively enforces a simple (but also restrictive) form of lifetime system where the stack layout + backwards refs guarantee that anything pointed to will go out of scope after anything that holds a pointer to it.
We can then support more complex lifetime patterns (such as returning a closure, or returning a list holding data that would outlive the current function) by using a 2-pass mark-and-compact GC algorithm that lets returned lists “adopt” data that needs to outlive the current function.
This gives us array-backed lists with good data locality and efficient O(1) random access for reads, but it does not (on its own) give us efficient mutation with “observationally pure” mutable value semantics, where multiple observers cannot interfere with each other. To guarantee that existing observers don't see a mutation, we would have to naively copy the entire array on every set / push / pop and thus get O(n) complexity.
Can we do better? Yes, if we do a last-use analysis for variables, additionally identify which values are unique (== have a single observer), and also figure out how to efficiently mutate unique values that are buried deep in the stack. Let's look at these issues in turn:
The first thing to do is analyzing when a variable is last used, because variables that are used again later in a lexical scope are never safe to mutate. This is a simple syntactic check and can be done by the compiler, which saves us from having to look ahead into later bytecode at runtime.
Conceptually, we want to annotate variables, so that in a call like f(len(x), x) and with left-to-right call-by-value and no further mention of x later in the scope we know that the second occurrence of x can be safely mutated. The compiler would then emit something like f(len(x), mut x). A mut in front of a variable signifies move semantics, since the argument is conceptually moved into f and the variable x is then empty for the remainder of the enclosing scope.
While last-use analysis conceptually talks about variables, it might be better to make a mut annotation a property of an operand, so that in f(len(x), mut x) we annotate the second operand of the call as mutable (and emit a regular variable op for x as the second argument in the bytecode). The reason for this is that in an expression like f(mut l, len(l)) the ownership-move must only happen as part of the call of f, after len(l) has been evaluated. A move thus doesn't happen as part of the evaluation of an argument, it happens as soon as an operation accesses its operand. Only then can set(mut l, 0, get(l, 1)) mutate the list in place by setting l[0] = l[1].
If we want to preserve referential transparency / observational purity in a functional language, we must do “functional-but-in-place” mutation only when a value is uniquely held by a single observer. There are at least three viable options:
The simplest of these, a linear scan to determine uniqueness, works in the language sketched out here because all values are allocated on the stack and references can only point backwards (to older entries on the stack). Any observers of a value must thus show up as references higher on the stack than the value being pointed to. If we want to mutate a list of 1000 elements that is sitting 10 elements from the top of the stack, it makes sense to walk the 10 elements if it means potentially being able to mutate the 1000 element list directly instead of copying all of it to the top of the stack to be mutated.
We thus get a simple heuristic: If the distance from the top of the stack to the list is shorter than the length of the list, we walk the stack to check for uniqueness. Otherwise, we simply copy the stack and skip the uniqueness walk. This gives us better asymptotic complexity for accumulator patterns where long lists are manipulated with a constant stack overhead on top (because the uniqueness walk is bounded by a constant factor) but mutation still ends up being O(n) in cases where the list is buried deep in the stack or the part above it also grows linearly (such as when we're mutating two lists in a loop).
The alternative chosen by Perceus and mutable value semantics is reference counting: Before mutating a value, we check if its refcount is exactly 1. If so, we're the only observer and can safely mutate it directly. Otherwise, we copy-on-write.
The disadvantage is that this adds refcounting overhead and effectively adds an entirely new garbage collection machinery to the language. But if we already have 2-pass mark-and-compact GC in the VM, why pay for precise refcounting, when all we want to know is whether there is a single observer or more than one?
We can instead track uniqueness as a single bit, trading preciseness for a more conservative analysis with less overhead: All non-atomic values start with a uniqueness bit set and can be referenced with a single owning ref which allows us to mutate the value directly as long as its uniqueness bit remains set. We guarantee by construction that only a single owning ref can ever exist, by restricting the creation of owning refs to values that are at the top of the stack (thus guaranteeing that no other refs exist). Whenever an owning ref is created from a variable, the variable is tombstoned so that no further reads can reach the target of the owning ref (and any mistaken reads will error with a use-after-move when encountering a tombstone).
The uniqueness bit is set to false if a borrowed ref to the value is stored in a list (because storing the borrowed ref makes it observable beyond its current call frame). Both a mutation through a borrowed ref and a mutation through an owning ref of a value with its uniqueness bit set to false turn into a copy-on-write.
This uniqueness bit strategy is only sound if we guarantee that in a call such as f(l, g(mut l)) the borrowed first argument cannot observe the mutation of l happening as a result of g(mut l). In other words, the function f must see its first argument l as it was before the mutation, which requires copy-on-writing l as part of g(mut l). We can guarantee this by scanning the operands when one of them wants to mutably take a ref such as g(mut l). In this case, we then see at runtime that the first argument borrows l and we need to copy-on-write. In a case like f(len(l), g(mut l)) however, no other reference to l would exist at the point of g(mut l), so we can safely mutate in place.
The nice property here is that since we guarantee that storing a borrowed ref in a list will already have set the uniqueness bit to false, the scan can hop over lists and only needs to look at the current call frame. We still need a dynamic scan though, which checks whether there are any pending borrows that point to the list (or anywhere in its extent, in other words its directly owned children), because of a case such as the following:
l = [[1]]
f(l) = g(get(l, 0), h(mut l)) // f(l) = g(l[0], h(l))
h(l) = set(get(mut l, 0), 0, 42) // h(l) = l[0][0] = 42
Here, the argument get(l, 0) is a pending borrow and must conflict with h's mutation of l. But get(l, 0) in itself shouldn't mark l as non-unique, because otherwise every read through a borrow, such as len(get(l, 0)) would lead to copy-on-write on l. This is where the dynamic scan comes in at runtime: h(mut l) finds an owning ref to l with its uniqueness bit set to true, then walks the current call frame to check for any refs that point to l or inside of l, at which point the pending ref returned from get(l, 0) is found. Since there's a pending ref, h(mut l) downgrades mut l to a borrowed ref (which will then default to copy-on-write).
Now that we know which values are unique and can be mutated, there's still the question of how to actually mutate them. For some cases, it's easy enough to mutate a value in place: Setting an element in a list to an atomic value such as an int is always guaranteed to work, no matter where on the stack the list is, because we're merely writing a single atomic value into an existing slot. But pushing values or setting an index to a complex value is trickier, because the list needs to grow and the new element needs to be stored somewhere.
One special case where this is less of an issue is if the value to be mutated is sitting as a physical value at the top of the stack, because we can then simply shrink and grow the value as needed. But if the value is buried deep in the stack, we'd like to be able to mutate it without having to shrink/grow the entire stack above it.
So let's give lists the ability to have spare capacity and let's double a list's capacity whenever we mutate it deep in the stack and there are no free slots, thus giving us amortized O(1) mutations.
One problem though: Where do we add the spare capacity? If we add it at the end of a list, we can push new atomic elements in amortized O(1), but if we want to store an element that is younger than the list by reference, the reference would point upward in the stack, which breaks our invariant that references always point to older data on the stack. We thus have to add the data before the list's element references. But if we add the spare capacity at the beginning of the list, we can't add a new element at the end of the list.
A simple solution is to adopt the classic “heap + stack” model and put the spare capacity in the middle. We then let the “heap” (the data of non-atomic list elements) grow from left to right, while the “stack” (the atomic elements or element pointers) grow from right to left, reversed. Reversing the elements of a list still safely allows us to store elements that point to earlier elements of the list, because list elements never directly point to other list elements, only ever to the “heap” section of a list.
However, it would not only be annoying if all list literals had to be emitted in reverse order, it would mean that a list like [f(), g()] would evaluate the effect of g() before f(), which breaks the expectation of left-to-right effectful evaluation. An easy solution is to introduce two separate lists, one for literals and one for reversed elements with capacity: A literal list is always laid out left-to-right, whereas any reversed list is laid out right-to-left and tracks its capacity.
Now that our lists have some slack and allow us to push elements onto a list even if it's buried deep in the stack, why not use these lists for arena allocation (also known as region-based memory management, e.g. with a letregion primitive)? The idea is simply that we treat a list with some spare capacity deep in the stack as the arena/region where we can allocate values that are meant to outlive their current frame higher up in the stack. All elements in the arena are then deallocated all at once when the arena goes out of scope.
The one subtlety is that allocations must not be observable by other users of the arena, otherwise referential transparency / observational purity would break. This is why we can't just use push to push values to a list: A push would be observable by a len, get, or pop somewhere else, and it could be overwritten by another observer's set.
The solution is to add another operation on lists, adopt(l, x), which stores the element x in the “heap” part of a list with capacity without adding an element pointer, instead returning the pointer to x as the result of adopt(l, x). Anything younger than l that x points to will transitively be adopted by the arena. Since adopt operation never touches a list's elements, len / get / set / push / pop never observe its effects, so we can safely mutate using adopt(l, x) even through a borrowed ref, because the mutation is not observable.
Adopting an element in an arena only makes sense if adopt's l argument is a ref to a list (instead of a physical list) and if x is a non-atomic value (because there's nothing to store for an atom), but adopt degrades gracefully even if these conditions aren't met. If we call adopt(l, x) on a physical list at the top of the stack, it simply throws away the list and returns x (after all, there's no other place to store it). If we call adopt(l, x) with an atomic x, it merely returns x without storing it deeper in the stack.
If l is full, there are two choices: We could either grow l in place by doubling its capacity, moving the entire stack above it and shifting references accordingly, or we could simply keep x at the top of the stack, degrading to the normal mark-and-compact on return.
(One fun thought experiment is to think of the entire available memory as being such an arena, with the heap being the actual heap, which would simply never be garbage collected since the top level arena never goes out of scope, and the elements as the growing stack.)