コンパイラ自作に挑戦したい？必読の神論文はこの2本だけで十分だ（2008年）

コンパイラを自作してみたいけれど、何から手をつければいいか分からないという人は、この2つの論文を読んでください。コンパイラの基礎を最短ルートで理解できるベストな資料です。

最近だと『Crafting Interpreters』（https://craftinginterpreters.com ）がおすすめってよく聞くね。Nanopassの論文リンクは切れてるみたい。

Nanopassの論文はもう更新が止まってるっぽいけど、とりあえずここから見られるよ：https://stanleymiracle.github.io/blogs/compiler/docs/extra/n... (https://stanleymiracle.github.io/blogs/compiler/docs/extra/nanopass-framework.pdf)

*ドナルド・クヌース（Donald Ervin Knuth）は『The Art of Computer Programming』の著者ね。（何十年も執筆が続いていて、今は第4巻cを書いてる最中）。かなり高度な内容だし、もうコンパイラについては扱わないだろうな（昔は博士論文の候補としてAddison-Wesleyからコンパイラの本を依頼されていたけど、引退した今はシリーズの目標が変わったって言ってるし）。

著者の意見にはちょっと同意できないかな。「ドラゴンブック」（Aho他著『Compilers: Principles, Techniques, and Tools』）の第2章は、それだけでコンパイラの最初から最後までを網羅した自律的な入門編になってるから、本の他の部分は無視してそこだけ読むのもアリだよ。

あと、コンパイラ作成の素晴らしい入門書といえば、Niklaus Wirthによる薄い本『Compilers』も最高。コンパイラの全ソースコードが驚くほど簡潔に載ってて、本全体がすごく分かりやすい（本当に明快！）。合計100ページ以下（99ページ）で収まってるしね。

（自分は高校生の時、この2つの資料でコンパイラを自作できるくらいには学べたよ）

最近、趣味でおもちゃのコンパイラを作ってるよ。

構文解析の理論とか、パーサー生成器、カスタムDSL、形式文法とかの面倒な話は全部すっ飛ばして、代わりに素晴らしいパーサーコンビネータライブラリの『Megaparsec』を使ってる。構文解析のロジックを追いやすいし、曖昧さがない（意図した通りじゃないかもしれないけど、少なくともパースに成功するか失敗するかのどちらかだし）。パーサー関数の合成や再利用が簡単（空白に敏感なパースや行の折り返し処理には特に役立った）だし、従来の解析手法につきものの退屈な字句解析と構文解析の分離作業がいらないのがいいよ。

『An Incremental Approach to Compiler Construction』（Abdulaziz Ghuloum著）
http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf

【概要】
コンパイラは、魔法使いが丹念に作り上げた、凡人には到底理解できない魔法の成果物だと思われがちだ。コンパイラ関連の書籍は、いわば「魔法使いの専門用語」で書かれていて、知識ある者の仲間内だけで共有されている。現実のコンパイラは複雑すぎて教育用ツールには向かないし、一方で教育用のおもちゃコンパイラとの間には大きな溝がある。初心者コンパイラ作者はその厚い壁を前に困惑して「いっそインタプリタでも作るか」となってしまう。

この論文の目的は、その壁を打ち破ることだ。コンパイラを作ることは、インタプリタを作るのと同じくらい簡単だということを示す。ここで作るコンパイラは、Schemeプログラミング言語の大きなサブセットを受け取り、パーソナルコンピューティングで主流のIntel-x86アーキテクチャのアセンブリコードを出力する。コンパイラの開発は、小さなステップに小分けされている。各ステップで、徐々に拡張されるSchemeのサブセットに対して、完全に動作するコンパイラが完成する。各ステップで生成されるのは実際のアセンブリコードで、それをアセンブルすればハードウェア上で直接実行できる。読者が基本的なコンピュータアーキテクチャのコンポーネントや実行モデルを知っているという前提で書かれているが、Intel-x86アーキテクチャの深い知識は不要だ。

コンパイラの開発過程は、拡張チュートリアルとして詳しく解説されている。チュートリアルには、自動テスト機能や包括的なテストスイートなどのサポート資料も付属している。Schemeの実装を目指す現在および未来の開発者が、この論文から高性能なコンパイラを作るモチベーションと、それを達成するための手段を見出してくれることを願っている。

コンパイラ作成はかなり進歩してるね。特に、数百行のコードで書けるメタコンパイラ[1]や、適応型コンパイル[3]、JITコンパイラなんかは顕著だ。
Alan Kay率いるVPRiの研究グループは、（コンパイラ作成における）複雑性の問題に取り組んでいたね[4]。

[1] Ometa: https://tinlizzie.org/VPRIPapers/tr2007003_ometa.pdf
[2] その他のOmeta論文: https://tinlizzie.org/IA/index.php/Papers_from_Viewpoints_Research_Institute
[3] 適応型コンパイル: https://youtu.be/CfYnzVxdwZE?t=4575
博士論文: https://www.researchgate.net/publication/309254446_Adaptive_compilation_for_an_object-oriented_and_reconfigurable_architecture
[4] 本当に「Complex（複雑）」なのか？それともただ「Complicated（難解）」にしただけなのか？（Alan Kay）: https://youtu.be/ubaX1Smg6pY?t=3605

いいアドバイスをもらったことがあるんだけど、本はRAMみたいなもので、順番通りに通しで読む必要はなくて、必要な箇所をランダムアクセスすればいいんだって。そう考えると、分厚い本を一冊手に入れて、自分のタスクに必要な部分だけを読むっていうやり方は全然アリだと思える。

ただ、公平を期すために言うと、自分が何を知らないのかすら分からない状態だと、そのランダムアクセスのやり方は通用しない。だからこそ、軽くて分かりやすい入門書が重要なんだと思うし、著者が指摘したいのもそういうことなんじゃないかな。

この記事のNanopassに対する構成は少し過小評価されてる気がするな。本当の洞察はパスの数じゃなくて、各パスが明示的な入力言語と出力言語を持っていることで、それによって各段階でどんな不変条件（invariant）が守られるべきかを強制的に考えさせられる点にあるんだ。その規律だけでも、コンパイラを実行する前に驚くほど多くのバグを見つけられる。Crenshawの資料も素晴らしいけど、こうした構造的な思考こそが、おもちゃのコンパイラと実際に拡張可能なコンパイラを隔てるものだと思う。

自分がコンパイラの作り方を学んだのは、1978年8月と9月の『BYTE』誌に載ってたTiny Pascalコンパイラのソースコードリストからだった。あのリストを読み解いたのは魔法のような体験だったよ。

オプティマイザの作り方は、UllmanとHennessyが教えてたスタンフォードの夏期講習で学んだ。

コードジェネレータは自分で捏造したものだけど、他のどこにもない変わった代物になってるみたいだね！

ドラゴンブックは持ってるけど、実際には読んだことがない。文句があるなら訴えてくれ。

Niklaus Wirthの教え子だったMichael Franz教授が教えていたCS241コンパイラコースで、最適化コンパイラを実装した時の思い出は懐かしいな。UC Irvine時代で一番刺激的な授業だったよ。2009年のことだから記憶は曖昧だけど、DLXというシンプルなアーキテクチャ用の仮想マシンが提供されていて、そこで動くバイトコードをコンパイラで生成するという課題だったはず。

Google検索してみると、アーキテクチャの解説がこれ（https://github.com/cesarghali/PL241-Compiler/blob/master/DLX.pdf ）で、レジスタ割り当てアルゴリズムについては多分これ（https://bernsteinbear.com/assets/img/linear-scan-ra-context-ssa.pdf ）だったかな。