Decide Before Running What Can Be Decided — Bytecode

In one line

Instead of walking the tree every time, you move the tree once into a flat list of instructions (bytecode) and run that list with a single loop — that is a bytecode VM. Values are pushed onto and popped from a single stack, names are turned into slot numbers at compile time, and if and while become jump offsets that are filled in later.

Why this was needed

A tree interpreter, even to compute a single a + b, compares node names, descends recursively, and finds names in the environment chain. If it runs a million times in a loop, it does this work a million times. But a good part of it is already decided before the program runs. Which declaration x is, which local variable of the function that declaration is, where the end of the while is — all of it can be known just by looking at the code.

A bytecode compiler makes these decisions once and bakes them into the instructions. GET_LOCAL 2 is not "climb the chain and find x" but "push slot 2 of the frame." CPython, the JVM, and Lua all have this structure (for CPython, you can see it with python3 -m dis).

How it works

Chunks and the constant pool. The code of one function is called a chunk. An instruction is [이름, 인자, 줄, 칸] (name, argument, line, column), and numbers, booleans, global names, and function chunks are put into the constant pool once each, and instructions use that index. The same value is put in only once, but in Python, True == 1 and the hashes are the same, so if you use only the value as the key, true and 1 share one slot — you must put the type in the key too.

A single stack. This VM has one stack. A script's local variables, the called function value and its arguments, and temporaries being computed all pile up on the same stack. A frame is (chunk, next instruction position, base), and the base is the stack position where that frame's slot 0 is.

fn f(a, b) { let c = a * b; return c + 1; }     print f(3, 4);

스크립트: GET_GLOBAL f · CONST 3 · CONST 4 · CALL 2 · PRINT
스택      [ … | <fn f> | 3 | 4 ]   CALL 2 → 새 프레임의 바닥 = 스택 길이 − 2 = 'a' 칸
f:        GET_LOCAL 0 · GET_LOCAL 1 · MUL        [ … | <fn f> | 3 | 4 | 12 ]  ← 12 가 곧 c(슬롯 2)
          GET_LOCAL 2 · CONST 1 · ADD · RETURN    RETURN: 결과를 내리고 바닥 − 1(함수 값)까지 걷고 결과를 올림
          CONST 0 · RETURN                        return 없이 끝날 때를 위한 꼬리(여기서는 닿지 않는다)

For a local variable made with let, the position where the value is already pushed is the slot itself. Nothing is moved. Instead, when leaving a block, you must POP as many times as that block has local variables for the stack to return to where it was. The value of an expression statement (f(1);) must also be discarded with POP. If either is missing, the stack grows by one slot on every loop iteration — the result is right but memory leaks. That is why this lab compares the maximum stack depth against the reference down to one slot.

Jump patching. When translating if (c) { A } else { B }, at the moment you emit JUMP_IF_FALSE you do not know where the else will start. You emit it with the argument slot left empty (emit_jump), and after translating all of A, you come back and fill it in (patch_jump). The offset is counted from the instruction after the jump — destination = jump position + 1 + offset. A one-slot difference between counting from the jump position and from the next position is the most common bug, and that bug usually shows up as "it sometimes skips a line."

if 없이 else:   조건 · JUMP_IF_FALSE →끝 · then
else 가 있으면: 조건 · JUMP_IF_FALSE →else · then · JUMP →끝 · else
while:          [처음] 조건 · JUMP_IF_FALSE →끝 · 몸체 · JUMP →처음(음수 오프셋)
&&:             왼쪽 · JUMP_IF_FALSE_OR_POP →끝 · 오른쪽        (거짓이면 값을 남긴 채 건너뛴다)
||:             왼쪽 · JUMP_IF_TRUE_OR_POP  →끝 · 오른쪽

This VM lets functions be declared only at the outermost level. For a function inside a function to hold on to the outer local variables (a closure), you need a device that takes those variables off the stack and moves them to the heap (the upvalue of Lua and clox), but this course leaves that story as reading only, and the VM handles global functions and recursion.

What it looks like in the field

• python3 -m dis. If you disassemble a Python function, you see LOAD_FAST 0 (a local slot), LOAD_CONST, and POP_JUMP_IF_FALSE. The shape is nearly the same as what you build in this module. You also see the POP_TOP after a one-line expression statement.
• The JVM's stack maps. The Java bytecode verifier checks at every jump destination that the stack depth and types match. A class produced by a compiler that left out the POP at the end of a block or of an expression statement is rejected at the loading stage — stack depth is a contract as important as the "result."
• Register VMs. Lua 5 and Dalvik are VMs that use virtual registers instead of a stack. The instruction count drops but each instruction gets larger. Either way, the idea of "decide in advance what can be decided before running" is the same.

What you will do in the next lab

You grow compiler.py and vm.py in alternation — the constant pool and expression instructions (and a human-readable disassemble), the arithmetic VM, global and local slots, jump patching, jump execution, functions with CALL/RETURN, and the pipeline that ties source to VM. The grader compares the compiler side instruction by instruction and the VM side by output, executed instruction count, and maximum stack depth against the reference. Finally, you run four fixed programs on your VM and leave the numbers in a report.