バイトコードコンパイラとスタック VM を作る

目標

ASTをスタックVMの命令の並び(チャンク)に移すコンパイラーと、そのチャンクを実行するVMを作ります。木をたどるインタプリター(モジュール5)と同じ出力を出しながら、実行した命令数とスタックの最大の深さまで、基準と同じである必要があります。

なぜ重要なのか

バイトコードは、「実行前に決められるもの」、すなわち名前のスロット番号とジャンプの目的地を、1回だけ決めて命令に埋め込みます。その代わり、間違えやすい場所が生まれます。ジャンプのオフセットが1つずれるとときどき1行を飛ばし、ブロックの終わりや式文の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を埋めます。採点ツールがオフセット1つ1つまで突き合わせます。
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の4つのプログラム(/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が関数の値を残す、フレームの底を1つずらして取る、の5つです。
セッションは60分で始まり、＋時間で延ばせます。終わると/root/miniが消えます。このラボは60分を超えやすいので、必要なら時間を延ばしてください。

チャンクと定数プール、式の命令

emitは[op, arg, node.line, node.col]を追加して、その位置を返します。add_constは、(type(value).name, value)をキーにした辞書で重複を除きます。値だけを使うと、Trueと1が1つの欄になります。二項は、左 → 右 → 演算の順序です。

命令を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がもう1つ必要です。

ジャンプを実行する

frame[1]はすでに次の命令を指しているので、そこにオフセットを足します。JUMP_IF_FALSEは、条件を降ろして、boolでなければcondition must be boolエラーです。OR_POPの2つの命令は、結果が決まっていれば値を残したまま飛び、そうでなければ値を降ろして、右がその位置を引き継ぎます。

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に書きます。数字を手で書かずに、コードで作って書いてください。採点ツールが、もう一度動かして確認します。