GoKawiilI encountered this problem while working through the challenges in chapter 14 of Robert Nystrom’s Crafting Interpreters.
Note: Production VMs are more sophisticated, though I’ll share how this is similar to other VMs like JVM and Lua at the end of this post.
Background
The first half of the book implements a toy language, jlox, from the top down, starting with lexing and parsing to build an AST and then interpreting it. The second half re-implements the same language but from the bottom up, beginning with the bytecode structure.
It stores bytecode in a chunk, which contains a sequence of bytes. Each byte is either an opcode or an operand belonging to an opcode. Instructions can therefore occupy different numbers of bytes. For example, OP_RETURN is a single byte, while OP_CONSTANT is followed by an operand containing an index into the chunk’s constant pool:
offset 0 1 2 byte OP_CONSTANT constant index OP_RETURN \___________________/ | one instruction another instruction
When an instruction causes a runtime error, the VM needs a way to translate the bytecode offset back to the source line that produced it. So the chunk needs to store the line numbers.
A straightforward solution is to store a second array, lines , in parallel with the bytecode so that every byte gets a corresponding source line:
offset: 0 1 2 3 4 5 6 7 code: 00 01 00 02 01 00 03 01 line: 1 1 1 1 1 2 2 2
This design is simple and gives us O(1) lookup. However, it takes up O(n) memory for n bytes of bytecode.
... continue reading