Notes
2026/07/29

Flat closures (that fully live on the stack)

Going back to the idea of keeping immutable lists/tuples on the stack, I've been thinking about how to extend this idea. Briefly, the idea of that earlier exploration was to store (dynamic) lists fully on the stack, by using lightweight stack-internal pointers that could only point backwards, thus encoding a sort of borrowing concept. The hard part is returning these lists from functions without ending up with dangling pointers, which is why the return instruction ended up implementing a 4-pass mark-and-compact algorithm that looks suspiciously like GC.

(There was one correctness issue in the 4-pass algorithm as described previously, which is not relevant for the following discussion though, so I'm just mentioning it for completeness. I previously wrote that “An unmarked tuple below inside_floor is garbage, we skip past its elements”, but that's unsound: Pass 1 must not skip past a garbage list's extent, because a garbage list's adopted area can contain child data that is still referenced by the return value, so we need to check that child's children in pass 1.)

This might sound vaguely reminiscent of another idea, namely escape analysis in the context of closures. That's no coincidence, because one of my main motivations for the whole experiment was to find a bytecode that could store and manipulate closures on the stack (so that I can eventually evaluate the bytecode at comptime and get back more flat bytecode).

Closures, if you squint a bit, look a lot like lists, because both “wrap around” some data that they need to hold onto if the entire closure or list is returned from a function. Let's say that our lists store the number of their elements (each with a fixed size of one stack slot, because compound data structures are stored on the stack before the list and being pointed to) + the total size of “adopted” or “ghost data”.

00: PUSH_INT(1)
01: PUSH_INT(2)
02: MAKE_LIST { elems: 2, adopted: 0 }
03: PUSH_INT(3)
04: PUSH_INT(4)
05: REF(02)
06: MAKE_LIST { elems: 3, adopted: 3 }

Conceptually:

1 |
2 |
__| <==+
3   |  +
4   |  +
=======+
____|

Let's say that we also have an instruction to push a non-closure function onto the stack, like PUSH_FUNC { code_pointer: usize }. We can now extend this to closures by merging both of these instructions together, so that we get a function that also stores some partially applied arguments:

00: PUSH_INT(1)
01: PUSH_INT(2)
02: PUSH_CLOSURE { args: 2, adopted: 0, code_pointer: ... }

Instead of ints, the closed-over arguments could be refs to arbitrarily large data on the stack. The same 4-pass mark-and-compact algorithm that takes care of returning lists would then also compact and return just the closed-over data, cleaning up anything that is not held onto by the closure.

How do we refer to positional arguments on the (runtime) stack from (within the bytecode of) a function? (This applies equally to normal functions and closures.) Since lists can grow arbitrarily large and are stored fully on the stack, we need a way to map from the static notion of nth function argument to position on the stack. The easiest way is probably to resolve variables relative to a function's call frame, by introducing an instruction like VAR(usize), in contrast to the absolute stack position of REF(usize).

Is a separate instruction even needed for closures? Or are closures just a combination of a MAKE_LIST instruction and PUSH_FUNC instruction? The easiest way would be to define a closure as a list wrapped around a function as its last (or first, depending on the calling convention) element, in which case the CALL instruction needs to recognize a list in a function position (or a ref to one) as a closure. An alternative would be to treat “normal” functions as a special case for closures with 0 captured arguments and to only provide a single instruction for closures and functions.

Function calling convention

How are function pointers and function arguments positioned on the stack? Let's say we want to call f(a, b, c), with f being translated to the bytecode instructions f_0, ..., f_n or f... for short, a being translated to a_0, ..., a_n or a... for short, etc. Let's also say that we have a CALL { args: usize } instruction that applies a function to the specified number of arguments. What calling convention should we use? There are several options:

We can choose relatively freely if our language is pure, but in the presence of side effects the order of arguments on the stack will also determine the order of side effects. I want my function arguments (and their side effects) to be evaluated according to their left-to-right reading order, which leaves the options a... b... c... f... CALL and f... a... b... c... CALL. For choosing between these two options, we are less restricted by the order of side effects: Evaluating a function itself (before applying it to any arguments) rarely has a side effect and we could even add a restriction to the language that disallows something like (f(a, b))(c, d) and instead enforces a normal form like g = f(a, b); g(c, d) that makes the order of side effects clear, for example A-normal form.

How do closures fit into either of these two calling conventions? A closure effectively carries around partially applied arguments, which need to be accessible on the stack as if they were regular arguments. So instead of f... just being a bunch of bytecode instructions for the function f, the closure needs to wrap around the partially applied f(a, b, _).

If our calling convention is f... a... b... c... CALL and our closure is a list that wraps around f... a... b... and follows them with a MAKE_LIST instruction, our stack before our call looks like the following:

f... a... b... MAKE_LIST c... CALL
\______________________/
       closure

Similar to what our calling convention expects, but with a MAKE_LIST instruction in the way, which CALL needs to remove before being able to apply the function. This requires us to move around the arguments so that we end up with f... a... b... c... CALL, which could be expensive unless we require all function arguments to be of atomic size.

Luckily, this is already a requirement for lists (and thus also closures, which only store atomic values / refs as their direct elements), so it's not a stretch to extend this requirement to our CALL instruction. If we can assume that all arguments are just atomic (and any adopted data lives in a bulk area before the actual arguments), we can just pick a calling convention arbitrarily, and thus go with f... a... b... c... for the ordering of side effects that it gives us.

But how would the compiler be able to emit refs to arguments in situations like f(g(x), h(y)), where the size of g(x) or h(y) at the point of calling f cannot be determined statically during compilation? We need a separate call instruction with the semantics of calling a function for the “top N elements” (whatever size they might have), which dynamically creates the right atomic refs at runtime and then acts like a regular CALL instruction.

This is a pattern that we can see in multiple places, notably for lists and references: To be able to represent data efficiently on the stack (as a runtime representation), we need lists with an explicit size in terms of stack slots + adopted data. But to be able to emit bytecode (and consume it as part of running the VM), we need an instruction that can just say “turn the N topmost values into a list”. Same for references, which need to exist as absolute refs into the stack (the efficient runtime representation) as well as relative references that look up variables relative to a call frame (the input bytecode for the VM that's emitted by the compiler).

There's more to say about this duality when it comes to an efficient bytecode representation, but I'll leave that for another time.