実行前に決められることは決めておく — バイトコード

一言でいうと

木を毎回たどる代わりに、木を1回だけ平らな命令の並び(バイトコード)に移しておき、その並びを1つのループで回すのが、バイトコードVMです。値はスタック1つに積んだり降ろしたりし、名前はコンパイル時にスロット番号に置き換えておき、if・whileはあとから埋めるジャンプオフセットになります。

なぜ必要なのか

木をたどるインタプリターは、a + bを1つ計算するだけでも、ノードの名前を比べ、再帰で降り、名前を環境の連鎖から探します。ループの中で100万回回れば、これを100万回行います。ところが、そのうちかなりの部分は、プログラムが動く前にすでに決まっています。xがどの宣言なのか、その宣言が関数の何番目のローカル変数なのか、whileの終わりがどこなのか。すべて、コードだけを見てわかります。

バイトコードコンパイラーは、こうした決定を1回だけ行い、命令に埋め込んでおきます。GET_LOCAL 2は「連鎖を上がってxを探せ」ではなく「フレームのスロット2を積め」です。CPython・JVM・Luaは、どれもこの構造です(CPythonはpython3 -m disで見られます)。

どう動くのか

チャンクと定数プール。関数1つのコードをチャンクと呼びます。命令は[이름, 인자, 줄, 칸]で(プレースホルダーは名前、引数、行、桁です)、数値・真偽値・グローバル名・関数チャンクを定数プールに1回ずつ入れ、命令はその番号を使います。同じ値は1回だけ入れますが、PythonではTrue == 1でハッシュも同じなので、値だけをキーにすると、trueと1が1つの欄を共有してしまいます。型までキーに入れる必要があります。

スタックは1つです。このVMはスタックが1つです。スクリプトのローカル変数、呼ばれた関数の値と引数、計算途中の一時値が、すべて同じスタックに積まれます。フレームは(チャンク、次の命令の位置、底)で、底はそのフレームのスロット0があるスタック上の位置です。

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 없이 끝날 때를 위한 꼬리(여기서는 닿지 않는다)

letで作ったローカル変数は、値がすでに積まれたその位置が、そのままスロットです。別に移しません。その代わり、ブロックを出るときに、そのブロックのローカル変数の数だけPOPする必要があり、そうしてはじめてスタックが元に戻ります。式文(f(1);)の値も、POPで捨てる必要があります。どちらか1つでも抜けると、ループが回るたびにスタックが1つずつ伸びます。結果は合っているのに、メモリが漏れます。そのため、このラボはスタックの最大の深さを、基準と1つ単位まで突き合わせます。

ジャンプのパッチ。if (c) { A } else { B }を移すとき、JUMP_IF_FALSEを出す時点では、elseがどこから始まるかわかりません。引数の位置を空けたまま出しておき(emit_jump)、Aを移し終えたあとで戻って埋めます(patch_jump)。オフセットはジャンプの次の命令から数えます。目的地 = ジャンプの位置 + 1 + オフセットです。ジャンプの位置から数えるか、次の位置から数えるかという1つ分の違いが、いちばんよくあるバグで、そのバグは、たいてい「ときどき1行を飛ばす」という形で現れます。

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  →끝 · 오른쪽

このVMは、関数をいちばん外側でだけ宣言できるようにしています。関数の中の関数が外側のローカル変数をつかむには(クロージャ)、その変数をスタックから取り出してヒープへ移す仕組み(Luaやcloxのupvalue)が必要ですが、このコースはその話を読み物としてだけ扱い、VMはグローバル関数と再帰までを扱います。

現場での姿

python3 -m disコマンド。Pythonの関数を逆アセンブルすると、LOAD_FAST 0(ローカルスロット)、LOAD_CONST、POP_JUMP_IF_FALSEが見えます。このモジュールで作るものと、ほとんど同じ形です。1行だけの式文のあとのPOP_TOPも見えます。
JVMのスタックマップ。Javaのバイトコード検証器は、すべてのジャンプの目的地で、スタックの深さと型が合っているかを確認します。ブロックの終わりのPOPや式文のPOPを忘れたコンパイラーが作ったクラスは、ロード段階で拒否されます。スタックの深さが「結果」と同じくらい大切な約束事だということです。
レジスターVM。Lua 5とDalvikは、スタックの代わりに仮想レジスターを使うVMです。命令の数が減る代わりに、命令が大きくなります。どちらの場合も、「実行前に決められるものは決めておく」という考え方は同じです。

次のラボですること

compiler.pyとvm.pyを交互に育てます。定数プールと式の命令(と、人が読む逆アセンブル)、算術VM、グローバルとローカルのスロット、ジャンプのパッチ、ジャンプの実行、関数とCALL/RETURN、そしてソースからVMまでをつなぐパイプラインです。採点ツールは、コンパイラー側は命令1つ1つを、VM側は出力・実行した命令数・スタックの最大の深さを、基準と突き合わせます。最後に、固定プログラム4つを自分のVMで動かして、数字をレポートに残します。