メタ循環評価器：Mere が Mere を走らせる

フロントエンドはいま Mere を読み書きし直せる、二つのやり方で検証されて。明白な次の願い、そして ブラウザデモが具体にしたもの —— パースが動くなら、走らせてほしい —— は、評価器だ。評価器を Mere で 書くと、名前と小さなめまいの付いた何かが生まれる：メタ循環インタプリタ、その同じ言語で書かれた、 ある言語のためのインタプリタ、それゆえ自分自身を走らせられる。

型検査の前に評価する

このセルフホストの取り組みのより大きなビジョンは二つの部品、評価器と型検査器だった。評価器が先に 行った、いまや馴染みのパターンの理由で：二つのうち、より単純で、より即座に説得的な方だからだ。評価は 動的だ —— プログラムを、その木を歩いて計算することで走らせ、型を先に知る必要がない —— だから 型検査器がまだ存在することに依存しない。そして目に見えて報われる：評価器は、ブラウザデモを「コードを 貼って整形し直されるのを見る」から「コードを貼って走るのを見る」に変える。型検査器はより難しい機械で、 unification と一般化を建てねばならないから、難しい部分の前に地面を固めるべく、評価器が先に行く。

インタプリタの大半はインタプリタではない

OCaml 評価器は二千行近く、それは Mere で再現するのに手強く聞こえる —— 行がどこへ行くかを見るまでは。 その約五分の四が組み込み関数だ：print、文字列操作、list と vector と map の操作、ファイルの 入出力、その他数十。それらはインタプリタではない。それらは標準ライブラリで、まったくセルフホストを 要さない —— それらはランタイムがすでに提供する primitive で、どの Mere プログラムもそうするのと同じ やり方で、セルフホスト評価器から届く。

それらを剥ぎ取ると、実際に Mere で書かねばならないものは小さい：走るプログラムの値がどう見えるかを 記述する値の型、名前を値に対応づける環境、パターンマッチャ、そしてツリーウォーカーの心臓に あるディスパッチ —— 式と環境を与えられて値を生む、再帰関数だ。OCaml の二千行に対しておそらく二百行。 書き直さなくてよいものを知ることが、セルフホストを扱いやすくすることの半分だ：インタプリタのコアは 本当に小さく、そしてそれが小さいのは、それが解釈する言語が小さいからだ —— 連載の初めの最小 ML コアが、 いま小さな評価器として報われる。

コア、そしていまや馴染みのクロージャ

形は教科書的なツリーウォーカーが、Mere 自身の型で表現されたものだ。値は variant —— 整数、真偽値、 文字列、クロージャ、など。環境は名前と値の対のリストで、歩いて引かれる。そして評価器は、式の種類で マッチする単一の再帰関数だ：変数は環境で自分を引き；二項演算は両辺を評価して組み合わせ；if は条件を 評価して枝を取り；関数適用は関数と引数を評価して一方を他方に適用する。

立ち止まる価値のある一片はクロージャだ。それは、この連載がいまや四つの異なる層で出会った同じアイデア だからだ。評価器が関数式に出会うと、関数の本体とその時点で有効な環境を運ぶクロージャ値を作る —— 捕捉された束縛が、クロージャ値のフィールドとして直接格納される。それはまたしてもクロージャ変換だが、 ここでは巧妙さをまったく要さない：捕捉された環境はただの値、クロージャの中に保持された束縛のリストだ。 リファレンスインタプリタはクロージャを OCaml から無料で得た；C backend はそれを heap の env struct として 建てた；Wasm backend はそれをメモリ offset とテーブルインデックスに割った；そしてセルフホスト評価器は 捕捉された環境を普通の variant フィールドとして保持する。一つの概念 —— コードとそれが閉じ込めた環境 —— の四つの表現、そのそれぞれが自分の層に合わされ、この最後のものが最も直接的だ：環境がデータの中にそこに ある。

「メタ循環」が実際に買うもの

セルフホスト評価器は、他のどれとも同じ Mere プログラムだ。同じ四つの backend でコンパイルされ、同じ byte 単位の parity に保たれ、プログラムのコーパスの上で OCaml 評価器に対して cross-validate される —— 前回のハーネスが、いま Mere で評価した結果が OCaml で評価したものと一致するかをチェックする。それは、 それが Wasm にコンパイルされてブラウザで走れることを意味し、デモは dogfood signal が求めたものになる： Mere プログラムを貼ると、Mere のインタプリタ —— それ自身 Mere からコンパイルされた —— がそれを走らせ 結果を示す。Mere のための REPL、ブラウザで、Mere によって動く。

「メタ循環」という語はただの飾りではない。自分の言語を解釈できるインタプリタは、原理的に自分自身を 解釈できる —— 評価器にそれ自身のソースを手渡せる。好奇の対象以上に、それは言語のコアについての証だ： Part I と II で選ばれた feature —— variant、再帰、パターンマッチ、クロージャ —— は、まさに評価それ 自体、言語が持つ最も根本的な操作を表現するのに要る feature だった。言語は、自分自身の実行を記述する のに十分表現力があると判った。それは、小さなコアが正しいコアだったと確認する静かなやり方だ。

評価器は、プログラムの型を気にせず走らせる。型を気にする部品 —— 型の付かないものを、走る前に拒む もの —— はより難しく、それが次だ。それは Hindley–Milner 推論を Mere で建て直すことを意味する： unification、一般化、その静かなアルゴリズム丸ごと。次回：型検査器。