Notes
2026/07/30
This is a continuation of the bytecode idea explored previously for flat lists on the stack and flat closures on the stack.
Let's assume we have the following bytecode that encodes lists on the stack:
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 | +
=======+
____|
In Rust, the above representation of lists as an enum variant MAKE_LIST { elems: usize, adopted: usize } would force every instruction to occupy at least 24 bytes. Worse, it also assumes that the number of elements and the size of the adopted area are encoded as part of the instruction. This is fine for an (output) data representation, but if we want to use the same bytecode instruction set as both input and output representation, this implies that we need another (input) instruction that can create a list dynamically with a size based on an int that has been pushed onto the stack (assuming we want lists with a dynamic length) and without necessarily knowing the size of the arguments on the stack.
There's more to this observation, because this duality of “static” vs. “dynamic” instructions is a pattern that we can see in multiple places, notably for lists, references, and function calls:
There are two slightly different notions of “static” vs. “dynamic” here and it's worth briefly calling out the distinction: An instruction can be static or dynamic in terms of where the operand comes from (is it statically fixed in the bytecode or dynamically supplied on the stack), and also what the operand counts (is it an extent in terms of stack slots or a number of values whose size needs to be dynamically computed).
The first static/dynamic distinction (“where an operand comes from”) does not require separate instructions, we can instead unify them by encoding operands differently. To do that, let's sketch out a concrete bytecode representation (and provide a separate instruction for the dynamically computed size). First of all, we would like instructions to always have the same constant size, so that we can easily map from nth stack element to a concrete stack offset. Let's also assume that we want to store ints with close to 64 bit precision on the stack. What are our options?
This is what for example Lua does (for values, not instructions), and it's the simplest option. If we choose 16 bytes, we still do better than Rust's 24 bytes, and we have enough space to store 64 bit ints without losing precision. But it's still 16 bytes, so can we do better?
What if we split each instruction into a data part (always 64 bits) + an instruction tags (always one byte, for a total of 256 different instructions) and pad the bytecode so that 8 data parts (each 64 bits) are followed by 8 instruction tags.
Only ints take up the full 64 bits of the data part, whereas code pointers, string pointers, and list sizes/indexes are limited to a lower number of bits, with the remaining bits deciding whether the number is to be interpreted as an absolute int or a relative reference to a value on the stack (which could then be a full 64 bit int). The threshold at which a number grows too large to be stored directly in the data part then depends on the instruction: Ints always store the full value, while operations with one potentially static operand (like LIST_GET or LIST_SET) can store up to 63 bits directly, for example, and operations with multiple operands (like MAKE_LIST's { elems: usize, adopted: usize}) only store 23 bits per operand directly, etc.
This would give us full precision ints, but at the cost of interleaving data and tags, as well as making addressing slightly more cumbersome. We could store data and tags separately to get rid of the interleaving issue, but that would worsen the cache locality, which destroys one of the advantages of storing everything on the stack.
A much simpler and probably better alternative is to just accept that ints are 63 bits, which gives us one bit to distinguish between ints and everything else, with “everything else” than holding both data and tags. We would still need to support both “static” (absolute int) and “dynamic” sizes (through refs), but we would be free to decide how to encode them independently from our int representation.
This also seems to be what OCaml is doing, and it simplifies the implementation slightly compared to interleaving data and tags, so this seems like something that's probably good enough for applications that aren't numerically heavy.
With either 64 or 63 bit ints, we might still need a sort of “escape hatch” for large blobs of binary data that we'd like to represent as one contiguous chunk. We could store these blobs out of band, as heap-allocated memory with just a pointer to them on the stack, but (while this might be a good addition later on) this would destroy the guarantee that everything can be represented and manipulated as a flat sequence of bytecode instructions.
Just putting the blob on the stack and then adding a tag either before or after it marking it as a blob wouldn't be enough, because the 4-pass algorithm needs to walk the stack both from the bottom and the top. (We would also want to maintain the invariant that entries on the stack can be read either starting at the top or the bottom for things like comptime.) But we can treat blobs as a special data structure that needs “bracket” instructions before and after it, each 64 bits wide. Not exactly cheap if we want to store 64 bits as a blob, but fine the larger the blob gets.
Let's briefly return to the second static/dynamic distinction (“what an operand counts”). We could have separate instructions, for example MAKE_LIST (expecting stack offsets) vs MAKE_LIST_DYN (expecting a number of elements, whose size is dynamically computed). Same for CALL vs. CALL_DYN for computing the size of arguments. But there's an easier alternative: We just need to provide a single NORMALIZE instruction that normalizes the top N values on the stack by turning them into atomic values or refs, which is then what MAKE_LIST and CALL can operate on.
So this is what I'm leaning towards: 63 bit ints + blobs that can be stored fully on the stack (and potentially on the heap later) + a dedicated NORMALIZE instruction. Would this actually lead to an efficient bytecode? I'm not sure, but it sounds like something that's worth a try.