Mere で Scheme を

別の言語の小さなインタプリタを書くのは、自分の言語が何でできているかを知る最も古い方法の一つだ。 再帰、パターンマッチ、環境を一度に働かせ、Mere の probe がこれまで避けてきた二つを問う。再帰的多相 variant は抽象構文木かつ実行時値として仕えられるか、そして値は捕捉した環境を運べて closure が動くか。 Scheme は自然な題材だ —— そのコードはすでにデータだ —— なので一つ書いた。s 式を parse する reader、 木を歩く評価器、printer、約 260 行。

コードとデータと値の、一つの variant

インタプリタ全体が一つの再帰 variant を軸に回る。s 式は nil、整数、真偽値、シンボル、pair、closure、 または primitive —— そしてその一つの型が、reader の生む構文であり、プログラムの操るデータであり、 評価器の返す値でもある、同時に。これは Lisp の定義的な特徴で、それを綺麗に表現することは variant の 本当のテストだ。評価器は「head が シンボル if の pair」のような深く入れ子の形をマッチして special form を認識し、パターンマッチャは網羅性検査を保ったままそれら入れ子ケースを扱った。自己言及的な 構文＝値の型を表現することは言語に何の負荷もかけず、どんな ML でもそうであるように読めた。

自分のスコープを閉じ込める値

より難しい問いは closure だった。lambda が評価されると、その結果は定義された環境を覚えていなければ ならない。別の関数から返された関数が、捕捉した変数を依然見えるように。Mere はこれまで環境を値の中に 入れよと問われたことがなかった。s 式 variant の closure ケースは三つを持つ —— 引数リスト、本体、 そして捕捉した local 環境、これ自体もただの s 式連想リストだ —— そしてそれで足りた。捕捉した数を 足す lambda を返す関数 make-adder、二つから新しい関数を組む compose、どちらも lexical スコープが 求めるとおりに振る舞った。返された closure は、生まれたフレームの正しい束縛を見た。global 定義は 再帰が動くよう可変テーブルを通り —— 関数は自分を呼ぶ頃にはスコープにいる —— local 束縛は lexical スコープのために捕捉した alist を辿った。

測定と、摩擦

どのテストプログラムも正しい答えを出した。interp でも C backend でも同一に。10 の階乗、range 上の 二乗の map、和の fold、closure の例、コードをデータに保つ quote、短絡する and と or。同じ日の 別の probe —— 二次元の最長共通部分列テーブルの上に backtrack で edit script を復元する行レベル diff —— も同じ話を語った。system の diff ツールに照らして正しく、新バグゼロ。これが、物を建てて 測ったときの言語の成熟の見え方だ。Scheme インタプリタと diff ツール、どちらも非自明で、どちらも コンパイラを変えずに書けた。唯一の摩擦は言語のバグでなく言語との衝突だった —— run という名の関数が 二つの backend で違う振る舞いをした。run も組み込みだからだ。その糸を辿るのが次回で、バグの一例 でなく一つの種類を終わらせる。