Graydon HoareのCompiler講義資料が面白かった話
Graydon Hoareが2019年にカナダのブリティッシュ・コロンビア大学でコンパイラ関連のゲスト講義した時の資料21 compilers and 3 orders of magnitude in 60 minutes - a wander through a weird landscape to the heart of compilationを読んだら大変面白かったのでメモ。
作者
Graydon HoareはMozillaでRustを開発したことで有名。その後Rustの開発もMozillaも離れて（というかRustの開発からは2013年に離れたようだ）、一時期AppleでSwift開発チームに所属していたらしい。（ソース：Reddit: I wonder, why Graydon Hoare, the author of Rust, stopped contributing into it and switched to Swift?）
概要
そういった作者のプログラミング言語開発の経験を元に、学生に実在のコンパイラについていろいろ解説した講義。
話の流れとしては：
の二点を豊富な実例（タイトルにもあるとおり21個のコンパイラ）を紹介しつつ解説している。特に最後の部分に重きを置いているので、例えばRustコンパイラ開発秘話のような内容は入っていない。
巨大コンパイラ
巨大なコンパイラの実例として挙げられているのは以下の四つ：
- clang
- swiftc
- rustc
- gcc
最初の三つはLLVMを使っており、コンパイラの大きさとしては
（ちなみにLLVMは120万行）となるようだ。ただし言語がまちまちなので行数で比較できるものでもないかもしれないが・・・。
一番気になったのはGCCに含まれているという60万行のAdaコードだ・・・。何に使われているのだろうか。
巨大さの理由
上記のコンパイラがなぜここまで巨大になったか、について４つの原因を挙げている：
これらのコンパイラに関しては巨大であることは合理的だとした上で、しかしコンパイラは必ずしも大きくなる必要はない、プロジェクトが置かれているコンテキストに拠る部分が大きいとのこと。違うコンテキストではどのような技術的選択がありえるのかについて実例とともに見ていく。
コンパイラ開発における技術的選択
資料の後半（というかスライド数では全体の2/3）ではコンパイラをそこまで大きくしない７つの手法が紹介されている：
軽く個別に見ていく。
最適化手法の限定採用
いろんな最適化を頑張ってもそこまで劇的なパフォーマンス改善は見られない（特にCのような低レベルな言語になると）、というわけで1971年（！）に出たA Catalogue of Optimizing Transformationsという論文に載っている８つほどの最適化を実装して終わるのがいいんじゃないか、という話。多くのコンパイラは最適化はこの８つだけ（あるいはそのサブセット）。それだけで、カリカリに最適化するのに比べて大体８割ぐらいのパフォーマンスが出るとのこと。
コンパイラに合った開発言語の選択
MLやLisp（特にSchemeやRacket）を使いましょう。ASTを直接表したりパターンマッチができる言語だと木構造に対する処理が直接コードに書き表せるので、コンパイラが非常に書きやすい。
メタコンパイラ
パーサだとLex/Yaccがあるが、それをコンパイラ全体に拡張したような「言語仕様を記述するDSLからコンパイラを出力する」メタコンパイラが存在するらしい。そういうツールを使ってしまえば非常に簡単に（かつ少量のコードで）コンパイラが得られる。
IR・バイトコードへのコンパイル
バイトコードインタプリタの話。OCamlの開発者Leroyの「バイトコードインタプリタはちゃんとしたコンパイラの1/4くらいのパフォーマンスだけど、実装コストは1/20くらいだ」という言葉を紹介している。OCaml（というかその前身であるCaml Light）は元々Zinc抽象機械というバイトコードインタプリタだけで開発されて、その後Nativeコンパイルもサポートされた経緯があるので、その経験からくる発言と考えると面白い。
プログラムのサブセットをコンパイル
パフォーマンスに影響が大きそうで、コンパイルがしやすい関数だけコンパイル。それ以外の部分はインタプリタに任せる。この手法はJITとの相性もいいらしい。
インタプリタの部分評価
二村射影の話。インタプリタを書いて、それを部分評価して静的に解決し得る部分を解決してしまうとコンパイラになる。Graal/Truffleで実用化しているという話も紹介されている。
IRやASTを省略
IR（コンパイラの中間表現）がなく、ASTから直接アセンブリ言語を出力するのはそれなりに事例がある（@rui314さんの8ccも紹介されている）。それをさらに進めてPascalではAST自体も必要ないように構文がデザインされていて、シングル・パスで行単位で処理・コード出力されるようになっていたとのこと。後者は本当にコンパイラを簡単にするようなメリットがあるのだろうか？
まとめ
RustとSwiftという現代的な言語の開発経験がある作者の「技術的な多様性を紹介することを主眼に置いたおもしろコンパイラ探訪」といったところで、自作言語のコンパイラに関する技術的なアイデアを得るのもよし、よもやま話的に興味本位で読むのもよしである。
個人的にはA Catalogue of Optimizing TransformationsとGraal/Truffleについての論文One VM to Rule Them Allがとても読みたくなった。
