インタプリタと C backend：クロージャを手で作る

前回は、インタプリタがプログラムの意味を定め、コード生成器はそれを byte 単位で再現せねば ならないと論じた。今回は四つのうち最初の二つ —— 基準を据えるインタプリタと、まずそれに一致 せねばならない C backend —— を、そして両者の隔たりを具体にする一つの問題を見る：クロージャを 持たない言語で、クロージャをどう表現するか？

インタプリタと、無料のクロージャ

インタプリタはツリーウォーカーだ：パーサが作った構文木を取り、各ノードを直接、再帰的に評価し、 名前を値に対応づける環境を携える。x + 1 を評価するとは、x を評価し、1 を評価し、足す ことだ。関数呼び出しを評価するとは、関数を評価し、引数を評価し、一方を他方に適用することだ。 ここに巧妙なものは何もなく、それが要点だ：インタプリタは言語の明らかに正しい読みであるべく、 目視で信じられるほど単純な版であるべく作られる。だからこそ、それが他の三つを測る基準になれる。

それをここまで単純にしているのは、以前の決定が静かに払っている負債だ。クロージャ —— それが 書かれたスコープから変数を捕捉する関数 —— は、ここではほとんど実装するものがない。ホスト言語の OCaml がすでにクロージャを持つからだ。インタプリタが fn x -> x + n を評価するとき、n が 住む環境を握るホストのクロージャをただ作ればよい；捕捉も、記憶域も、寿命も、ホストのランタイムが 面倒を見る。この連載の初めの、OCaml を選ぶ回は、まさにこの賭けをした —— 代数的データ型、 パターンマッチ、そしてホスト自身のクロージャと GC を持つホストなら、インタプリタと型検査器が 素直にこぼれ落ちる、と。ここがその賭けの報われるところだ：クロージャの難しい機構は丸ごとホスト から借りられ、インタプリタにはほとんど何のコストもかからない。

C backend は現金で払わねばならない

C backend はそのどれも借りられない。C にはクロージャも、GC も、振る舞いを持つタグ付き共用体も ない —— あるのはトップレベルで定義される関数と、構造体と、ポインタだ。だからインタプリタが OCaml から無料で得たすべてを、C backend はそれらの部品から、明示的に作らねばならない。その 隔たり —— 豊かなホストが手渡すものと、素のターゲットが構築を強いるものとの間 —— こそ、コンパイルが 実のところ何であるかの大半だ。

その構築は、プロジェクト全体が働くやり方でなされた：一度に一つの言語 feature、それぞれが、次が 始まる前にインタプリタと照合される小さなスライスとして。まず整数、次に文字列、次にタプル（C の 構造体になる）、次にレコード（typedef）、次に variant（match をタグ検査の連鎖にコンパイルした タグ付き共用体）。各ステップは自己完結した翻訳で、それぞれが前回の差分テストで検証される —— コンパイルし、走らせ、バイトをインタプリタの言ったものと比べる。そして、機械的でない一つが来る。

構造体とポインタからクロージャを作る

クロージャは融合した二つのものだ：あるコードと、そのコードが参照する捕捉された変数。OCaml では、 つまりインタプリタでは、その二つは単一の値として届き、継ぎ目を考える必要はない。C にはそんな値が ないから、backend はクロージャを二つの部分へ割り戻し、それらを明示的に運ばねばならない —— クロージャ変換と呼ばれる技法だ。

それはいくつかの手で起きる。別の関数の内側に書かれた関数は、トップレベルへ持ち上げられる。 C にはトップレベルの関数しかないからだ。その捕捉された変数は、かつては単に名指しで届いたが、 持ち上げられた後はもうそのやり方では届かない —— だから heap 確保の環境構造体へ集められ、 捕捉変数への参照はすべて、その構造体から読み出すよう書き換えられる。持ち回されるクロージャの値は、 すると小さな対になる：持ち上げられた関数へのポインタと、その環境へのポインタだ。それを 呼ぶとは、環境ポインタを隠れた第一引数として関数ポインタを呼ぶことだ —— c.fn(c.env, x)。何も 捕捉しない素のトップレベル関数も、値として渡せる必要があるから、些細なアダプタと空の環境をもらい、 同じ対の形に収まる。コンパイラがどの関数が呼ばれているかを正確に見えるところでは、対を丸ごと 飛ばして直接呼び出しを速い経路として吐く —— 速度を変え、出力は決して変えない最適化だから、 parity は保たれる。

ここには言語自身の思想の静かな谺がある。クロージャの捕捉された環境は、たいていの言語で、暗黙的な ものの定義そのものだ —— 関数が黙って引きずる、周囲の状態の見えない袋。クロージャ変換はその袋を 明示的にする：具体的な構造体、どこか定まった場所に確保され、普通の引数として渡され、中身は 名づけられ届く。コンパイラはクロージャに、言語がエフェクトとメモリにするのとまさに同じことを している —— 環境的で不可視なものを取り、指させる値に変える。違うのはただ、ここではそれが、 そうでないふりを拒む C ターゲットのために、フードの下で起きることだけだ。

二つの backend、一つの意味

これが終わる頃、二つの backend は、この Part 全体が依存する関係に立つ。インタプリタは言語の 短く信頼できる定義で、難しい部分をホストに寄りかかる。C backend は、同じその意味の、より長く より字義通りの再構築で、インタプリタが借りたすべてを —— 持ち上げられた関数、環境構造体、タグ付き 共用体として —— 手で綴り出す。そして各スライスが落ちるたびインタプリタと照合されたから、二つは 同じバイトを出す：まったく異なる二つの実装が、一つの意味に保たれる。

その再構築は可搬な C で、C コンパイラのあるところならどこでも走る。だが C は、コンパイルする 価値のある唯一のターゲットではなく、最適化について最良の物語を持つターゲットでもない。次回： LLVM backend —— C ソースの代わりに LLVM の中間表現を吐くこと、そしてターゲットが、人のため に設計された言語ではなく、コンパイラのために設計された IR であるとき、何が変わるか。