フォーマッタ、そしてセルフホストがセルフホストをパースする

前回はフロントエンドを建てた —— Mere のレキサとパーサ、共有された構文木を生む —— そして、プリティ プリンタが先に来てその木を定義したことに触れた。今回はプリティプリンタそのものの話だ：なぜそれが 最初にセルフホストする正しい部品だったか、そして「動くように見える」を「元のものに対して、そして 自分自身に対して検証されている」に変える二層のチェックだ。

なぜフォーマッタが先に行ったか

コンパイラをセルフホストするのは大きな仕事で、部品の順序は本物の決定だ。フォーマッタ —— 構文木を 取り、きれいなソーステキストに描き戻すツール —— が最初の一片に選ばれ、その理由はすべて検証可能性に ついてだ。

それは純粋だ：構文木から文字列への関数、入力なし、出力なし、状態なし。モックするものも、順序づける ものもなく —— ただ値が入り値が出る。それは言語がすでに持っていたもので表現できる：再帰、variant 上のパターンマッチ、文字列構築、そのすべてを Mere はできた。そして最も重要なことに、それはチェック しやすい。出力が文字列であり、基準となる文字列を生む OCaml フォーマッタがすでにあるからだ。代替と 比べよ：パーサは大きく、型検査器は unification を要し、評価器とコード生成器は状態が重く四つの backend に またがる。フォーマッタは、本物のコンパイラの真の一片でありながら、正確に検証するのに十分小さく純粋な、 唯一の部品だ。最も検証可能な部品でセルフホストを始めることは、言語自身の第一原則 —— 確信できるものを 最適化する —— を、ブートストラップ計画そのものに適用したものだ。

作業は OCaml フォーマッタの忠実な翻訳だった：十いくつの段にわたる同じ precedence 駆動の括弧挿入、 block 形の同じ改行とインデント、構文糖（range、cons リスト、lambda 短縮形）の同じ復元、中置演算子と record リテラルと match arm の同じレイアウト。OCaml の Buffer は Mere の文字列ビルダになり、その List.map は prelude のものになり、フォーマッタは決して raise しないので、移植すべき例外はなかった。 結果は、六百行の OCaml がしたことを、五百行ほどの Mere がするものだった。

チェック一：基準に忠実

最初の検証は parity 規則、backend から変わらない：Mere フォーマッタの出力は、テストコーパス全体に わたって、OCaml フォーマッタの出力に byte 単位で等しくなければならない。OCaml フォーマッタが 「Mere コードはどう見えるべきか」の基準の定義で、セルフホスト版はそれをちょうど再現する義務を負う —— 等価な整形でも、近いのでもなく、同じバイトだ。全スイートにわたって走らせると、二つは一致し、それは 移植がただコンパイルして走っただけでなく —— 最後のスペースまで元の挙動を再現したことを意味する。これは 翻訳が忠実だと証す：Mere フォーマッタは、書き直された OCaml フォーマッタであり、単に似たツールでは ない。

チェック二：基準を要さない round-trip

二つ目のチェックはより面白い。フロントエンドをそれ自身に対して検証し、OCaml 基準をまったく要さない からだ。パーサとフォーマッタが両方存在すれば、それらはループに合成される：ソーステキストを取り、 木にパースし、木をソースに整形し戻す。正しいフォーマッタは冪等だ —— すでに整形されたコードを 整形しても何も変わらない —— だからループを二度回せば不動点に達するはずだ：パースし、整形し、その 結果をパースし、また整形して、出力は最初の整形と同一でなければならない。もしそうでなければ、パーサと フォーマッタは木について食い違っている —— パーサが、ソースが含意したのとフォーマッタが違って描く 構造を組んだ —— そして round-trip がそれを外部のオラクルなしに捕らえる。二つの部品が互いをチェック するからだ。これは Part IV で四つの backend が互いを検証したのと同じアイデアで、いまフロントエンドの 二つの半分の間にある。

セルフホストがセルフホストをパースする

そのチェックの最も鋭い形は、フロントエンドを手に入る最も厳しい入力に向けることだ：それ自身の ソースコード。 セルフホストパーサが fmt.mere とパーサ自身のソースをパースし；セルフホスト フォーマッタがそれらを整形し；round-trip が保たれねばならない。これは、セルフホストと dogfood が一つの 行為に融合するマイルストーンだ —— フロントエンドはそれ自身が実質的な Mere プログラムだから、フロント エンドをフロントエンドの上で走らせることは、同時に、それが直面しうる最も現実的なテストであり、ツールが ツールを処理する文字通りの実例だ。セルフホストフロントエンドが自分自身のソースをパースし整形し直して 不動点に達したとき、「Mere は Mere を処理できる」は、この層について、願望であることをやめ、実証的に 起きたことになる。

そしてそれをすべて行うハーネスは、一度きりのチェックではない；それは恒久的なインフラだ。OCaml 基準に 対する cross-validation と、自分自身に対する round-trip が、セルフホストの取り組みの残り全体が走る、 立ち続けるテストになる。この後に建てられるあらゆる部品 —— 評価器、型検査器、コード生成器 —— が同じ 規律を継ぐ：Mere で書かれ、OCaml の双子に対して cross-validate され、一致を要求される。フォーマッタは 一つのツールを移植しただけではない；後のあらゆるツールがどう信頼されるかを確立した。

フロントエンドはいま Mere を読み書きし直せる、二つのやり方で検証されて。まだできないのは、それを走らせる こと —— パースされた木を取り、その結果を計算すること —— だ。それが評価器で、それを Mere で書くと特有の 奇物が生まれる：Mere のためのインタプリタ、Mere で書かれ、自分自身を解釈できる。次回：メタ循環 評価器。