Notes
2026/08/15
Over the past two weeks, I was busy building a simple bytecode VM that extends the idea of representing lists as flat data on the stack to closures. In addition to storing lists and closures on the main VM stack, the VM has two other interesting properties:
Here's what the (decoded) bytecode looks like:
// Ops are atomic integers/variables/references or dynamically sized operations
pub enum Op {
Int(i64),
Var { elem: usize },
Ref { offset: usize },
Sized(SizedOp, usize), // the size field allows O(1) access as output
}
pub enum SizedOp {
BlobStart,
BlobEnd,
FuncStart,
FuncEnd { args: usize },
Call { args: usize },
List { elems: usize },
Push { elems: usize },
Set,
Get,
If,
Len,
Bin(BinOp),
}
pub enum BinOp {
Eq,
Add,
Sub,
Mul,
}
The crucial detail is that all operations track their size on the stack, which makes the representation suitable as a fast O(1) output value representation on the stack in addition to being an input bytecode representation. It's possible to read the stack starting at the top and know immediately how many stack slots the topmost element takes up.
This is usually not true for bytecode representations: Think about an AST such as (3 - 2) + 1, which might normally be represented as a bytecode of the form 3 2 - 1 +. Just looking at the topmost stack slot, +, it's not clear how far the operands to the addition extend. In the above example they extend all the way to the bottom of the stack, but that's only clear by scanning through the stack from the bottom.
By tracking the size of operations + operands, the bytecode representation becomes an AST/bytecode hybrid, making it possible to manipulate and rewrite parts of the AST without being a dumb input-only tape. Since the output stack that is being manipulated uses the same representation as the input stack (in fact, the program being executed is simply a fixed prefix of the “output” stack), the result of running the VM is another stack of bytecode, which can be executed again, opening the door for staged evaluation.
One interesting detail is that while the representation is the same for input and output, some of the operations undergo a transformation as they are being executed: For example, the operation Ref { offset: usize } is used to reference/borrow an element earlier on the stack, with its offset referring to a position in the input bytecode (relative to the current instruction pointer) when the operation is executed, but is stored on the output stack with its offset referring to a position on the output stack (relative to its own position on the output stack). Depending on whether it is an input instruction or output data, the offset thus takes on a different meaning.
The same is true for Call { args: usize } and List { elems: usize } instructions, which both store a logical number of operands (each of which can take up multiple stack slots) in addition to the usize field of stack slots that each Op::Sized tracks. When used as input instructions, there's no requirement that the args/elems are atomic. But for lists or call frames on the stack, the requirement is that each argument or element is atomic (which means complex values need to be stored lower on the stack and then referenced) so that knowing the logical number of elements allows accessing the atomic elements in O(1).
Here's the stack layout of [[1, 2], 3, 4] as input bytecode:
Int(1) \ \
Int(2) | |
List { elems: 2 } / |
Int(3) |
Int(4) |
List { elems: 3 } /
Executing it turns the first argument into an atomic reference and copies the other two:
Int(1) \
Int(2) |
List { elems: 2 } / <--+
Int(3) | // garbage
Int(4) | // garbage
Ref { offset: 3 } -----+ \
Int(3) |
Int(4) |
List { elems: 3 } /
Note how Int(3) and Int(4) just get copied and thus leave garbage on the stack, which will be reclaimed by the mark-and-compact algorithm that runs on return. So let's look at that next.
I previously built a 4-pass mark-and-compact algorithm running on every function return that would rewrite references and compact all the data being returned from a function. The new 2-pass algorithm is much simpler, but follows the same idea and still runs on return. It simply manages to merge 3 of the passes by using a bit more space on the stack. Here are the 2 phases of the new algorithm:
Note how we need to keep track of how far data has been shifted after we have shifted it, because we will encounter refs to it later on the stack as we move closer to the top. This means that moving data down the stack must not overwrite this meta information. The solution is to split each stack slot into a fixed part for the Op (e.g. 8 bytes) and a separate fixed part for the meta information (e.g. 4 bytes), holding the tag that identifies an operation as well as a mark bit (for reachability during the first pass) and the amount by which an operation has been shifted during compaction:
1 2 3 4 5 6 7 8 9 10 11 12
+----+----+----+----+----+----+----+----+----+----+----+----+
| op | t | shift |
+---------------------------------------+----+--------------+
\____________________________________________/
moved during compaction
\_____________/
fixed
In the above encoding scheme, the maximum shift would be 2^24 * 12 B == ~200 MB. Nothing breaks if we clamp the gap to that maximum shift and the garbage exceeds this threshold, it would simply take the next compaction (triggered by the next function return) to reclaim more space. If 3 bytes for shift turn out to be too little, other options would be to use 8 bytes for the meta information or to encode the shift in powers of two (which would leave unused space on the stack that could potentially be re-used for direct mutation).
Storing the tag outside of the 8 bytes for the op also nicely solves the problem of how to store 64 bit ints on the stack.
All of this makes garbage collection trivial. It runs on return (whenever the size of the threatened area minus return value exceeds the size of the return value, leading to amortized compaction for incremental garbage) and the entire function is short enough to fit in less than 50 lines of code:
fn compact(&mut self, floor: usize) -> Result<(), &'static str> {
// resolve the return value first
let ret = self.resolve_slot(self.sp())?;
match self.op(ret)? {
Sized(List { elems: n } | Call { args: n }, _) => {
for sp in ret - n..=ret {
self.stack.get_mut(sp).ok_or(ERR_UNDERFLOW)?.meta.mark = true;
}
}
_ => self.mark(ret)?,
}
// pass 1: mark (bottom <- top)
for sp in (floor..=ret).rev() {
if self.stack[sp].meta.mark {
let r = self.resolve_slot(sp)?;
if r >= floor && r < sp {
self.mark(r)?;
}
}
}
// pass 2: compact (bottom -> top)
let mut gap = 0;
for sp in floor..=ret {
let mut slot = self.stack[sp];
if slot.meta.mark {
if let Ref { offset } = slot.op {
let shift = if sp - offset >= floor {
self.stack.get(sp - offset).ok_or(ERR_UNDERFLOW)?.meta.shift
} else {
0
};
let src = sp - gap;
let dst = sp - offset - shift;
slot.op = Ref { offset: src - dst };
}
self.stack[sp].meta.shift = gap;
self.stack[sp - gap].op = slot.op;
self.stack[sp - gap].meta.mark = false;
} else {
gap += 1;
}
}
self.stack.truncate(ret + 1 - gap);
if let Slot { op: Sized(_, slots), .. } = self.stack.last_mut().ok_or(ERR_UNDERFLOW)? {
*slots = (ret - gap) - floor;
}
Ok(())
}
So how do closures fit in? Given the above bytecode + mark-and-compact on return there's barely anything else needed in the VM, because closures end up being just a combination of lists and functions. The calling convention for functions on the stack is function first, then arguments from left to right, so that f(a, b, c) on the stack would be represented as f, a, b, c, Call { args: 3 }, with f and its arguments standing in for one or more stack slots.
The compiler is expected to do closure conversion, so that a function that is identical to f but with the first argument coming from an outer scope is first converted into a three argument f(a, b, c). At the point where the closure f(a, _, _) is returned, we then simply store f and a together in a list, with f as the first element and a as the second.
When the closure is applied to its remaining two arguments b and c, we encounter a stack of the following form, with f and its arguments again standing in for one or more stack slots:
f, a, List { elems: 2 }, b, c, Call { args: 2 }
This is almost like the non-closure call f, a, b, c, Call { args: 3 }, except for the List { elems: 2 } and the different args count. So all we need to turn the closure into a regular call is to move around the arguments on the stack before treating it like a call with 3 arguments. And here's where the requirement that both Call and List store arguments as atomic elements comes in, because we can always trivially and cheaply move around atomic elements without moving the underlying data of references.
The result is a regular function call. And since the captured arguments of a closure are just stored in a list, the mark-and-compact that happens on return ensures that garbage is compacted by the time the closure leaves its frame. The closure remains stored on the stack, as a flat list.
So that's it. The VM is still in its early stages and whether the design works will depend on whether I can get comptime to play nicely with it. But I think the combination of flat data on the stack (for both closures and lists), a unified input/output bytecode representation, and a really simple 2-pass mark-and-compact algorithm is promising.