セルフホスト始動：レキサ、パーサ、そして共有された木

前の Part は小さな自己参照で終わった：Mere についてのドキュメントを生成する Mere プログラム。 Part V は、この連載全体が向かってきた大きなもの —— Mere 自身を処理する Mere プログラム —— の話だ。 これまでのコンパイラは OCaml で書かれている：OCaml のレキサ、OCaml のパーサ、OCaml の型検査器、 評価器、コード生成器。セルフホストとは、そのすべてを Mere で書き直し、言語が自分自身のソースを コンパイルできるようになるまでやることだ。今回はフロントエンド：ソーステキストの文字列を、構造化 された構文木に変える部分だ。

プリティプリンタが先に来て、的を据えた

コンパイラのフロントエンドを建てる明白な順序がある —— レキサ、それからパーサ、それからパーサの 出力を消費するすべて。このプロジェクトは意図してそれを逆にやり、その理由は理解する価値がある。 以後のすべてを形づくったからだ。

最初のセルフホスト部品はパーサではなかった；それはプリティプリンタ —— 構文木を取り、きれいな ソーステキストに整形し戻すツール —— だった。それは順序が外れて見える：木を作るパーサをまだ持たない うちに、どう木を整形するのか？ 答えは、プリティプリンタが最初は手書きの木を与えられ、そして 書かれる中で、下流のすべてが依存する一つのものを宣言せねばならなかった、ということだ：構文木 そのものの形。 木を整形するには、まず木が何であるかを言わねばならない —— let ノードがどう 見えるか、if が何を持つか、関数適用がどう表現されるか。プリティプリンタがそのデータ型を定義した。

つまり、パーサが書かれる段になったとき、それは自分の出力を発明する自由を持たなかった。固定された的が あった：プリティプリンタがすでに消費する木を、ちょうど作れ。契約はパーサが存在する前に据えられて いた。そして見返りは各ステップで具体的だった —— プリティプリンタが動くので、フロントエンドの各段が 目に見える結果を持った。フォーマッタはすでにブラウザで手書きの木の上で走っていた；パーサは、 プロジェクト自身の言葉で、手で組んだ木ではなく打ち込まれたソースを受け付ける本物のブラウザ内 フォーマッタへの、最後の障害だった。

共有された木が背骨だ

その構文木 —— 抽象構文木、AST —— は、セルフホストコンパイラ全体で最も重要なオブジェクトだ。それが あらゆるフェーズ間の契約だからだ。パーサがそれを作る。プリティプリンタがそれを消費する。型 検査器、評価器、コード生成器 —— みなこの Part の後に来る —— もそれを消費する。一度定義すれば、 あらゆる部品が互いに同じ言語を話す。それを先に、プリティプリンタを通して定義したことは、パーサが 動く点ではなく固定された点を狙ったことを意味し、後に建てられたすべてが同じ固定点を継いだ。

そしてここで、連載のまさに初めの決定が再び報われる。AST は、構造的には、ノード形の和だ：式はリテラル か変数か if か適用か match で、各形は自分のフィールドを運ぶ。それはまさに代数的データ型 —— レコードの variant —— であり、それこそ Mere が、小さな ML 系言語として、きれいに表現するために 建てられたものだ。初めの方の OCaml を選ぶ回は、代数的データ型を持つホストがコンパイラを書くのを 自然にするという賭けをした；セルフホストコンパイラは、同じ賭けを言語自身の言葉で回収する。Mere が Mere の構文木を記述することは、言語を自分自身に向けたものであり、それが嵌まるのは、構文木こそ和型が そのためにある正典的なものだからだ。

レキサ、それからパーサ、基準に保たれて

木が定義されて、フロントエンドは二つの部品だ。レキサは生のソース文字列を、平らなトークンの リスト —— キーワード、演算子、リテラル、識別子 —— に変える。言語の小さな語彙を認識し、切り分ける。 パーサは、そのトークンリストを再帰下降で歩き、言語の十いくつの演算子優先順位の段を登り、プリティ プリンタが定義した木を組み立てる。どちらも概念的に新しくはない；どちらも手書きフロントエンドの標準的な 形が、いま Mere で表現されたものだ。

それらを正直に保つのは、backend を統べたのと同じ規律だ。すでに OCaml のレキサと OCaml のパーサ —— 元のフロントエンド —— があり、それらが基準を務める。セルフホストパーサはそれらに対して cross- validate される：同じソースを与えられたら、OCaml パーサが作るのと同じ木を作らねばならない。これは Part IV の parity 規則を、一段上げたものだ。四つの backend がインタプリタのバイトに保たれたところ、 セルフホストフロントエンドは OCaml フロントエンドの木に保たれる —— 「このソースをパースせよ」の二つの 実装が、一致することを要求され、乖離が信頼で見逃されるのでなく自動で捕まる。

フロントエンドはまた、基準より小さくありえた。それは、セルフホストコンパイラ自身が書かれている Mere の部分集合だけをパースすればよいからだ。コンパイラが自分自身にまだ使わない構文は、先送りできた —— プロジェクト全体が回る、同じ最小の正直な版の規律が、いまコンパイラが自分の同類をパースすることに 適用された。あなたが実際に書いた言語を読むのに、ちょうど足りるだけの言語を建てる。

フロントエンドはいま Mere に存在する：ソーステキストが入り、共有された構文木が出て、それは基準に 一致する。だが、作者しか走らせていないパーサは、まだ証されていない。最も鋭いテストは、それを手に入る 最も厳しい入力に向けることだ —— それ自身のソースコード、そして他のセルフホスト部品のソース。次回： フォーマッタと cross-validation ハーネス、そして、セルフホストフロントエンドがセルフホスト フロントエンドをパースする瞬間。