Build a Bytecode Compiler and a Stack VM

Goal

You build a compiler that translates the AST into a stack VM's instruction list (a chunk), and a VM that executes that chunk. While producing the same output as the tree interpreter (module 5), the executed instruction count and the maximum stack depth must also match the reference.

Why it matters

Bytecode decides "what can be decided before running" — the slot numbers of names and the jump destinations — once and bakes it into the instructions. In exchange, there appear places where it is easy to go wrong. If a jump offset is off by one slot, it sometimes skips a line, and if you leave out the POP at the end of a block or of an expression statement, the result is right but the stack leaks on every repetition.

Chunks and instructions

청크      {"name": "<script>" 또는 함수 이름, "arity": n, "code": [[op, arg, line, col], …], "consts": […]}
          명령의 줄·칸 = 그 명령을 만든 노드의 위치
상수 풀   int·bool·전역 이름(str)·함수 청크(dict). 같은 (타입, 값)은 한 번만, 함수 청크는 늘 새 칸
명령      CONST k · POP · PRINT · NEG · NOT · ADD SUB MUL DIV MOD POW · EQ NE LT LE GT GE
          DEF_GLOBAL k · GET_GLOBAL k · SET_GLOBAL k(값을 남긴다) · GET_LOCAL s · SET_LOCAL s(값을 남긴다)
          JUMP o · JUMP_IF_FALSE o(조건을 내림) · JUMP_IF_FALSE_OR_POP o · JUMP_IF_TRUE_OR_POP o
          CALL n · RETURN            오프셋 o: 목적지 = 이 명령의 자리 + 1 + o
옮기는 법 리터럴 CONST · 이름 GET_LOCAL/GET_GLOBAL · 대입 값 → SET_* · 단항 피연산자 → NEG/NOT
          두 항 왼쪽 → 오른쪽 → 연산 · 호출 callee → 인자들 → CALL n
          print 식 → PRINT · 식 문장 식 → POP · let 전역(깊이 0) 식 → DEF_GLOBAL, 지역 식(그 자리가 슬롯)
          블록 안의 문장들 → 이 블록의 지역 변수 수만큼 POP(블록 노드 위치)
          if·while·&&·|| 는 읽기의 표 그대로 · fn 은 맨 바깥에서만: 함수 청크 CONST → DEF_GLOBAL
          함수 몸체: 매개변수가 슬롯 0.., 몸체 맨 바깥은 매개변수와 같은 깊이(블록 POP 없음),
          끝에 늘 CONST 0 · RETURN(Fn 노드 위치). return 식 → RETURN, return; 은 CONST 0 → RETURN
          함수 안의 fn 이나 맨 바깥 블록 안의 fn 은 CompileError "nested functions are not supported by the VM"
VM        프레임 [청크, 다음 자리, 바닥]. 스크립트 프레임의 바닥 0. CALL n: 스택[-n-1] 이 함수인지·인자 수·
          깊이(스크립트를 뺀 프레임 200개까지)를 본 뒤 바닥 = 길이 − n 인 프레임을 쌓는다.
          RETURN: 결과를 내리고 바닥 − 1 부터 끝까지 걷은 뒤 결과를 올린다. 스크립트 코드 끝에서 멈춘다.
          executed = 실행을 마친 명령 수, max_stack = 명령 하나를 마친 직후 스택 길이의 최댓값
          실행 오류 글자는 5모듈과 같다(명령의 줄·칸으로). 조건 점프의 비 bool 은 condition must be bool …

Steps

1. Fill in new_chunk, const_key, and disassemble in /root/mini/compiler.py, and emit, add_const, expr (literals, unary, binary), and stmt (print, expression statements) of Compiler. Hand names, logic, and calls over to expr_more and the remaining statements to stmt_more.
2. Fill in VMError, vm_type, and vm_show in /root/mini/vm.py, and run, step, arith, need, and fail of VM.
3. Fill in the compiler's resolve_local, expr_more, and stmt_more (globals, locals, block POP) and the VM's step_more (the global and local instructions).
4. Fill in the compiler's emit_jump, patch_jump, emit_loop, expr_control, and stmt_control — the grader compares down to a single offset.
5. Fill in the VM's step_jump.
6. Fill in the compiler's expr_call and stmt_function and the VM's step_call.
7. Fill in compile_program and compile_source (→ (청크, 오류), the chunk and the error), and run_chunk and run_source (→ {"output", "error", "executed", "max_stack"}).
8. Run the four programs fib, loops, primes, and gcd (/opt/fixtures/mini/programs/) on your VM and write {이름: {"executed", "max_stack", "same_as_interp"}} (a mapping from each program name) into /root/mini/vm_report.json.

Notes

• python3 /root/mini/mini.py dis 파일.mini shows the chunk and python3 /root/mini/mini.py vm 파일.mini shows the execution result and the instruction count (the placeholder is the file).
• The files up to the interpreter are laid out when you start the lab.
• Common mistakes: removing constant duplicates by value alone so that true and 1 get mixed, leaving out the POP at the end of expression statements and blocks, counting offsets from the jump position, RETURN leaving the function value behind, and setting the frame base off by one.
• The session starts at 60 minutes and you can extend it with the +time button, and when it ends /root/mini disappears. This lab easily runs past 60 minutes, so extend the time if needed.

Chunks, the constant pool, and expression instructions

emit appends [op, arg, node.line, node.col] and returns that position. add_const removes duplicates with a dictionary keyed by (type(value).name, value) — if you use only the value, True and 1 become one slot. Binary operations are in the order left → right → operation.

A loop that executes instructions one at a time

run takes an instruction from the top frame, moves the next position first, calls step, raises executed, and updates max_stack with the stack length. For a binary operation, pop the right side first (b, a = pop(), pop()). For the arithmetic rules, borrow div, mod, power, and wrap from interp.

Global and local slots

If depth is 0, it is global (DEF_GLOBAL, with the name in the constant pool); otherwise just append (name, depth) to the locals list — the value is already at that position. When looking up a name, you must look at locals from the back so the inner name wins. When leaving a block, POP once for each local variable with a larger depth.

Jumps left empty and filled in later

emit_jump emits a jump whose argument is None and returns that position. patch_jump(at) fills in the current code length minus (at + 1). A backward JUMP is negative, the start position - (that JUMP's position + 1). If there is an else, one more JUMP to the end is needed after then.

Execute the jumps

frame[1] already points to the next instruction, so add the offset to it. JUMP_IF_FALSE pops the condition, and if it is not a bool, it is a condition must be bool error. The two OR_POP instructions jump while leaving the value if the result is decided, and otherwise pop the value so that the right side takes its place.

CALL and RETURN

fn translates the body with a new Compiler (parameters as slots 0.., depth 1) and appends CONST 0 and RETURN at the end. CALL n looks at stack[-n-1], checks it, and then pushes a [function chunk, 0, len(stack) - n] frame. RETURN pops the result and clears up to the function value with del stack[base - 1:] (where base is the frame base).

From source to the VM

compile_source goes in the order parse_program → check → compile_program, and if there is a first error, it is (None, error). It also catches CompileError and returns it as error text. run_chunk keeps the output, the instruction count, and the depth up to that point even if it catches a VMError.

A report of instruction count and stack depth

Write the executed and max_stack that run_source returned as they are, and write whether the output equals that of interp.run_source as same_as_interp. Do not write the numbers by hand; produce them with code — the grader runs it again.