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

한국어 원문으로 표시합니다.

목표

AST 를 스택 VM 의 명령 목록(청크)으로 옮기는 컴파일러와, 그 청크를 실행하는 VM 을 만듭니다. 트리 인터프리터(5모듈)와 같은 출력을 내면서, 실행한 명령 수와 스택 최대 깊이까지 기준과 같아야 합니다.

왜 중요한가

바이트코드는 '실행 전에 정할 수 있는 것' — 이름의 슬롯 번호, 점프 목적지 — 을 한 번만 정해 명령에 박아 둡니다. 그 대신 틀리기 쉬운 곳이 생깁니다. 점프 오프셋이 한 칸 어긋나면 가끔 한 줄을 건너뛰고, 블록 끝이나 식 문장의 POP 을 빠뜨리면 결과는 맞는데 반복할 때마다 스택이 샙니다.

청크와 명령

청크      {"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(→ {"output", "error", "executed", "max_stack"})를 채웁니다.
fib·loops·primes·gcd 네 프로그램(/opt/fixtures/mini/programs/)을 여러분의 VM 으로 돌려 /root/mini/vm_report.json 에 {이름: {"executed", "max_stack", "same_as_interp"}} 를 적습니다.

참고

python3 /root/mini/mini.py dis 파일.mini 는 청크를, python3 /root/mini/mini.py vm 파일.mini 는 실행 결과와 명령 수를 보여 줍니다.
인터프리터까지의 파일은 실습을 시작할 때 깔려 있습니다.
흔한 실수: 값만으로 상수 중복을 없애 true 와 1 이 섞이는 것, 식 문장·블록 끝의 POP 을 빠뜨리는 것, 오프셋을 점프 자리에서 세는 것, RETURN 이 함수 값을 남기는 것, 프레임 바닥을 하나 어긋나게 잡는 것.
세션은 60분에 시작해 ＋시간으로 늘릴 수 있고, 끝나면 /root/mini 가 사라집니다. 이 실습은 60분을 넘기기 쉬우니 필요하면 시간을 늘리세요.

청크와 상수 풀, 식 명령

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] 을 보고 검사한 뒤 [함수 청크, 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 을 그대로 적고, interp.run_source 의 출력과 같은지를 same_as_interp 로 적습니다. 숫자를 손으로 적지 말고 코드로 만들어 쓰세요 — 채점기가 다시 돌려 봅니다.