做一个字节码编译器和栈式虚拟机

目标

做出一个把 AST 翻译成栈 VM 指令列表（chunk）的编译器，以及一个执行该 chunk 的 VM。它要给出与树解释器（第 5 个模块）相同的输出，同时执行的指令数和栈的最大深度也必须与参考一致。

为什么重要

字节码把“运行前就能确定的东西”——名字的槽位编号、跳转目的地——只确定一次，写死在指令里。作为代价，会出现容易出错的地方。跳转偏移量差一格，就会偶尔跳过一行；漏掉块末尾或表达式语句的 POP，结果虽然正确，每循环一次栈就会泄漏一格。

chunk 与指令

청크      {"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 …

步骤

补全 /root/mini/compiler.py 的 new_chunk、const_key 和 disassemble，以及 Compiler 的 emit、add_const、expr（字面量、一元、二元）和 stmt（print、表达式语句）。名字、逻辑和调用交给 expr_more，其余语句交给 stmt_more。
补全 /root/mini/vm.py 的 VMError、vm_type 和 vm_show，以及 VM 的 run、step、arith、need 和 fail。
补全编译器的 resolve_local、expr_more、stmt_more（全局、局部、块 POP）和 VM 的 step_more（全局、局部指令）。
补全编译器的 emit_jump、patch_jump、emit_loop、expr_control 和 stmt_control——评分器会对照到每一个偏移量。
补全 VM 的 step_jump。
补全编译器的 expr_call 和 stmt_function，以及 VM 的 step_call。
补全 compile_program、compile_source、run_chunk 和 run_source。compile_source 返回 (청크, 오류)（占位符依次为 chunk 和错误），run_chunk 和 run_source 返回 {"output", "error", "executed", "max_stack"}。
用你的 VM 运行 fib、loops、primes、gcd 四个程序（/opt/fixtures/mini/programs/），把 {이름: {"executed", "max_stack", "same_as_interp"}}（占位符为程序名）写入 /root/mini/vm_report.json。

参考

python3 /root/mini/mini.py dis 파일.mini（占位符为文件名）会显示 chunk，python3 /root/mini/mini.py vm 파일.mini（占位符为文件名）会显示运行结果和指令数。
直到解释器为止的文件，在实验开始时已经铺好。
常见错误：只靠值去掉常量重复，导致 true 和 1 混在一起，漏掉表达式语句或块末尾的 POP，从跳转位置开始数偏移量，RETURN 把函数值留了下来，帧的栈底差了一格。
会话从 60 分钟开始，可以用＋时间延长，结束后 /root/mini 会消失。本实验很容易超过 60 分钟，需要的话请延长时间。

chunk、常量池与表达式指令

emit 追加 [op, arg, node.line, node.col]，并返回它的位置。add_const 用以 (type(value).name, value) 为键的字典去重——只用值的话，True 和 1 会变成一个格子。二元运算的顺序是左边 → 右边 → 运算。

逐条执行指令的循环

run 从最上面的帧里取出指令，先移动下一条指令的位置，再调用 step，增加 executed，并用栈长度更新 max_stack。二元运算先弹出右边（b, a = pop(), pop()）。算术规则取用 interp 的 div、mod、power 和 wrap。

全局与局部槽位

depth 为 0 就是全局（DEF_GLOBAL，名字放进常量池），否则只往 locals 列表里追加 (名字, 深度)——值已经在那个位置上了。查找名字时要从 locals 的后面往前看，内层的名字才会获胜。离开块时，对每个深度更大的局部变量执行 POP。

先留空、稍后回填的跳转

emit_jump 发出参数为 None 的跳转，并返回它的位置。patch_jump(at) 填入当前代码长度减去 (at + 1) 的值。向后的 JUMP 是起点位置 - (该 JUMP 的位置 + 1)，是负数。如果有 else，then 后面还需要再多一个跳到结尾的 JUMP。

执行跳转

frame[1] 已经指向下一条指令，把偏移量加到它上面。JUMP_IF_FALSE 弹出条件，如果不是 bool，就是 condition must be bool 错误。两条 OR_POP 指令在结果已经确定时，保留值并跳转；否则把值弹出，让右边接替那个位置。

CALL 与 RETURN

fn 用新的 Compiler 翻译函数体（形参放在槽位 0.. 上，深度 1），并在末尾加上 CONST 0 · RETURN。CALL n 查看 stack[-n-1] 并做检查，然后压入 [函数 chunk, 0, len(stack) - n] 帧。RETURN 弹出结果，并用 del stack[栈底 - 1:] 一直清理到函数值。

从源码到 VM

compile_source 的顺序是 parse_program → check → compile_program，如果有第一个错误就是（None，错误）。CompileError 也要捕获，转成错误文字返回。run_chunk 即使捕获了 VMError，也要保留此前的输出、指令数和深度。

把指令数与栈深度写成报告

把 run_source 返回的 executed 和 max_stack 原样写入，并用 same_as_interp 写下它是否与 interp.run_source 的输出相同。不要手写数字，而要用代码生成再写入——评分器会重新运行一遍。