コンパイラにジャンプを教える

前の Part は診断で終わった：self-hosted なコード生成器はあらゆる関数呼び出しを同じやり方で、フレームを 積む普通の call として lower し、だから tail-recursive なコード —— スタックを育てずにループするはずの 規律あるやつ —— がそれにコンパイルされるとそれでもスタックを育てた。リファレンスの生成器、ホスト言語で 書かれたやつ、はその位置で保証された末尾呼び出しを emit することを知っていた。Mere で書かれたやつは しなかった。behavioral な fixpoint まるごとが一つの欠けた命令を待っていて、この Part はそれを入れることに ついてだ。

「末尾位置」が実際に要すること

末尾呼び出しとは、その結果が囲む関数の結果である call だ —— それが return した後に何も起きないので、 呼び出し元のフレームを取っておく理由がなく、call はジャンプになれる。それを認識するのはローカルなチェック に聞こえるが、そうでない：末尾位置はプログラムの構造を通して内へ流れる性質だ。関数が最後にすることは if かもしれず、するとその両分岐が末尾位置にある。match かもしれず、すると全 arm がそう。本当の末尾が その body である let かもしれない。だからコード生成器は単に call を見て決められない；プログラムを歩き ながら、一ビットの文脈 —— いま末尾位置にいるか？ —— を運び、そのビットを関数を終えうるあらゆる構文の 分岐へ正しく伝播させ、他のどこでもそれをクリアせねばならない、なぜなら式の途中に埋まった call は断固として 末尾呼び出しでなく、そのフレームを保たねばならないから。

だから変更は、そのビットを生成器を通して threaded することだった。生成器が歩きながら運ぶ状態が、現在の式が 末尾位置にあるかのフラグを得た。関数 body に入るとそれがセットされ；if の分岐、match の arm、let の body がそれを継承し；普通の部分式がそれをクリアする。そして call がついに emit される唯一の点で、フラグが 二つの命令の間を決める：フレームを積む普通の call か、ジャンプする保証された末尾呼び出しか。仕事の大部分は この辛抱強い伝播で、一度に一つの構文、ビットをちょうど正しい場所に、他のどこでもなく届かせる。

何かを明かした反対

一つの引っかかりがあり、それが要したものでなく露呈したもののゆえに語る価値がある。末尾位置フラグを反転 させる自然なやり方は、生成器の状態を取りその一フィールドを変えたコピーを生むこと —— 普通の record 更新 だった。だが型推論器がそれを拒んだ、生成器の関数がみな互いを参照しその型がまだ一緒に割り出されている 文脈で。更新される値がその時点でまだ具体的な record 型に固定されておらず、正確な型がまだ開いている値の フィールドを更新することは、まさに厳格な推論器が通せない類のことだ、なぜなら更新が well-formed だとまだ 知れないから。修正は小さかった —— フラグを、inline 更新でなく関数呼び出しとして変更を適用する小さな ヘルパを通して反転させ、それが推論器に必要な具体的な型を与えた。だが反対はノイズでなかった。それは言語が 自分自身をコンパイルするよう求められたまさにその瞬間に型システムがその仕事をしていたことで、ときに衒学的 に感じる厳格さが、保証を実にする同じ厳格さだという正直な思い出させだった。

二十万フレーム、平らに

命令が threaded されて、重要だったテストは深さが入力と共に育つ再帰 —— overflow していた形。二十万レベル 深く駆動された tail-recursive なカウンタが、self-hosted な生成器にコンパイルされ WebAssembly バイナリ として走り、いまやスタック制限に触れずに完走した、以前はクラッシュしたところで。末尾呼び出しはジャンプに なった；フレームはもう積み上がらなかった；再帰の深さはもう問題でなかった。fixpoint を塞いでいた overflow は単に消えた。生成器は決して知らなかった命令を emit することを学び、interpreter の寛大なスタックが隠して いた資源限界が、いまやソースで、コンパイルされたコード自身の中で扱われた。

向こう側の、もっと悪いもの

そしてコンパイルされたコンパイラは、もうスタック枯渇でクラッシュせず、これまでより先に走った —— そして また止まった、違うふうに。今度は overflow しなかった；明示的な失敗にぶつかり exit した、静かに、コンパイル すべき入力で。これの意味は最初は明白でなく、末尾呼び出しの仕事の退行と読むのは容易だった。逆だった。 末尾呼び出しはまさにその仕事をした：再帰をあまりに徹底的に平らにしたので、コンパイルされたコンパイラが いまや初めて自分自身の logic を最後まで走った —— overflow が触れる前に常にクラッシュしていた欠陥に 届くほど遠くまで。構造的 self-hosting はコンパイラが valid なバイナリを emit できることを証明しただけ； バイナリは自分自身の logic を端から端まで実行したことがなかった。いまやした、そして初めて端から端まで 走ることは、プログラムの深くに住むバグが出てきてあなたに会うまさにその時だ。

だから一つの欠けた命令は易しいほうの半分と判明した。それはコンパイルされたコンパイラを早くに止めていた 壁を取り除き、そうすることで、コンパイラがその存在で初めて、決して実際には走ったことのない自分自身の部分に 届くのを許した。それがそこで見つけたのは一つのバグでなく三つで、そのそれぞれが、プログラムが自分自身に コンパイルされたときにだけ現れる類だった。次の Part は、その狩りだ。