ハクソク

世界を動かす技術を、日本語で。

コンパイラを書きたいですか？この2本の論文を読んでみてください（2008年）

25日前原文(prog21.dadgum.com)

概要

  • プログラミング初心者がコンパイラ本に直面する難しさの指摘
  • 多くの入門書が難解で実践的な知識に繋がりにくい現状
  • Jack Crenshawの「Let’s Build a Compiler!」シリーズの紹介
  • 内部表現（抽象構文木）の重要性と高水準言語の利点
  • Nanopass Frameworkの考え方と学習への活用提案

コンパイラ本の難しさと神話

  • プログラミング初心者 がAmazonで高評価の本「The Art of Computer Programming」を購入する状況の例示
  • 全ての入門書が高度すぎる というコンパイラ本の現状
  • 内容が広範囲すぎて どこから始めるべきかわからない問題
  • 正規表現から状態機械、文法理論まで 分厚い章 が続く構成
  • 読破しても 実際のコンパイラ作成 には結びつきにくい現実
  • この難解さが「 コンパイラは難しい」という 神話 を生む原因

Jack Crenshawの「Let’s Build a Compiler!」シリーズ

  • Jack Crenshaw による1988年開始の連載「Let’s Build a Compiler!」の紹介
  • Turbo Pascalクラス のシンプルなコンパイラを題材
  • シングルパスで パースとコード生成を一体化、最小限の最適化のみ実装
  • Pascal での実装例が中心だが、 CやForth版 も存在
  • Forth版 は対話的で実験しやすく、理解が容易
  • このシリーズの大きな欠点は 抽象構文木（AST） などの内部表現がない点

抽象構文木（AST）と高水準言語

  • 内部表現を省略することで 柔軟性を犠牲 にしている問題
  • Pascalでは 木構造操作が煩雑 なため、チュートリアルでは省略
  • Python, Ruby, Erlang, Haskell, Lisp などの高水準言語では 木構造の扱いが容易
  • 特に Lisp, Erlang, Haskell は 木構造データの操作 を得意とする設計

Nanopass Frameworkの提案

  • Sarkar, Waddell, Dybvig による「A Nanopass Framework for Compiler Education」の紹介
  • 重要なコンセプトは 「コンパイラ＝内部表現の変換の連続」 という発想
  • 1パスごとに 単純な変換処理 を行い、 複雑な変換は分割 して独立させる方針
  • 各パスの 入出力仕様を明確化 するフレームワーク
  • Scheme で実装され、動的型付けによる 実行時検証 が特徴

学習ステップの提案

  • 1～2本のコンパイラ を自作して基礎を体得
  • その後で「 Dragon Book」などの有名専門書に挑戦する選択肢
  • 場合によっては 専門書が不要 になる可能性も示唆

Hackerたちの意見

コンパイラのコースを受けてから約4年経ったけど、今でも震える... 本当に、今まで受けた中で一番難しかった（でもやりがいのあった）授業だったよ。

└

それで、ベネチアンブラインドみたいに飲んじゃった。

└

このコメントには同意したいけど、全然やりがいを感じなかったな。純粋に苦痛だった。

└

別の返信を見て、もしかして見逃してるウィンドウに関するしゃれがあるのかな？ もしそうじゃないなら、ここでは「shudder」じゃなくて「shutter」って言いたいんだと思うよ。もしジョークを台無しにしちゃったらごめんね。

└

コンパイラについて、他のプログラミングと比べて何が一番辛かった？

最近は「Crafting Interpreters」がおすすめって聞いたよ。(https://craftinginterpreters.com) Nanopassの論文のリンクは使えないみたい。

└

すごいコースだね！最終学年のCSの授業を受けてるときに終わらせたよ。たくさんの授業を待たなきゃいけなかったから（正直、授業前に話す相手もいなかったし）。ナノパスは試してないけど、他にも使えるリンクがあるから、やってみるつもり。

└

自習に最適な本だね！

└

コンパイラって幅広いから、誰かが「コンパイラの本」を勧めると、だいたい自分が欲しかった内容とはちょっと違うことが多いんだよね。だから、「Crafting Interpreters」のために実行可能なチートシートを作ったんだ。デモ用のパースは続けてて、ASTは本のよりちょっとLispっぽいかな。注意点として、これは学べることの本質を伝えるためのもので、決して本の代わりにはならないよ。むしろ、この本はコンパイラのマニュアルというより、Nystromが明らかに楽しんでいたような体験（ビジターパターンとか）を含むものだと思う。興味があれば、ビジターパターンのチートシートもPythonで作れるよ。プライベートなスクリプトからAIエージェントを使って「公に見えるアーティファクト」にしたんだ。[0] https://ouatu.ro/blog/crafting-interpreters-cheat-sheet/

└

「Crafting Interpreters」は素晴らしいけど、次のことをカバーしたサブ本があればいいなと思う：- 型と型付け - 最適化パス - オブジェクトファイル、実行可能ファイル、ライブラリ、リンク これがあれば、コンパイラを書くのに十分だと思う。

Nanopassの論文はもうダメみたいだけど、ここで見つけられるよ：https://stanleymiracle.github.io/blogs/compiler/docs/extra/n...

└

あと、こちらも：https://www.cambridge.org/core/journals/journal-of-functiona...

└

それから、Andy Keepのサイトにも行けるよ。https://nanopass.org/

同じようなテーマの本シリーズに「AIゲームプログラミングの知恵」ってのがあって、ゲームで実際に使えるさまざまなアルゴリズムに焦点を当てた多くの章が含まれてるよ。

*ドナルド・クヌース -> ドナルド・アーヴィン・クヌースは「コンピュータプログラミングの芸術」という本の著者です（数十年かけて進行中で、現在は第4巻のcを書いています）。かなり高度な内容で、もうコンパイラについては触れないかもしれません（アディソン・ウェスリーは、彼が博士課程の学生だった頃にコンパイラの本を依頼しましたが、今は引退してシリーズの目標が変わったと彼は言っています）。著者の意見には賛成できません。「ドラゴンブック」（アホらによる「コンパイラ：原則、技術、ツール」）の第2章は、コンパイラについての自給自足の導入で、他の素晴らしい本を無視しても単独で読めます。もう一つ素晴らしいコンパイラ作成の入門書は、ニクラウス・ウィルトの「コンパイラ」という短い本で、完全なコンパイラの驚くほど短いソースコードが含まれています（全体の本が非常に理解しやすくて、本当に明瞭です）し、合計で100ページ未満（99ページ）です。この2つの資料から学んだことを使って、高校でコンパイラを書けるようになりました。

└

「コンパイラ」ニクラウス・ウィルトのこれ？ https://people.inf.ethz.ch/wirth/CompilerConstruction/Compil...

└

コンパイラの本にはまだ希望があるよ。Knuthのウェブサイトから:

「第1巻から第5巻が終わったら、神の御意のもとに、第6巻（文脈自由言語の理論）と第7巻（コンパイラ技術）を出版する予定だけど、私がそのトピックについて言いたいことがまだ関連性があって、まだ言われていない場合のみだ。」 https://www-cs-faculty.stanford.edu/~knuth/taocp.html

└

ドラゴンブックは、コンパイラを書くのを諦めさせるくらいの説得力があった。なんでみんなこれを勧めるのか分からないよ。たぶん、君は僕よりずっと頭がいいんだろうね。素晴らしい本は他にもたくさんあるし、ドラゴンブックも独自の良さがあるけど、スタート地点としては最悪だと思う。OPと同じくらいの年代の参考文献をいくつか挙げるね。実際にコンパイラを作るプロセスを詳しく解説している本から始めるのをおすすめするよ。理論だけに時間を使ってる本じゃなくてね。

└

「ドラゴンブック」にはパースに関することがたくさん書いてあるけど、最適化パスやバックエンドを作りたいならおすすめしないな。90年代に高校生の時に初版を買ったけど、それが僕の最初のCSの教科書だったし、若いプログラマーとしてたくさん学んだよ。数年前に現代のコンパイラのバックエンドに取り組み始めたんだけど、知識をかなり更新する必要があった。第二版ではデータフロー分析がカバーされていて、これはすごく重要なんだ。でも、現代のコンパイラ（GCC、LLVM、Cranelift）は静的単一割り当て形式の中間表現を中心に構築されていて、第二版ではそれについてはたった1ページしか触れてない。実際に使うには、その特性についての理論もたくさん学ぶ必要があるよ。

最近、遊びでおもちゃのコンパイラを作ってるんだ。パース理論やパーサージェネレーター、カスタムDSL、形式文法とかは全部無視して、素晴らしいメガパーセックのパーサーコンビネータライブラリを使ってる。パースのロジックが簡単に追えるし、あいまいさがない（成功するパースは一つだけだから、意図したものじゃないかもしれないけど）、パーサー関数を組み合わせたり再利用したりするのも簡単だし（特にホワイトスペースに敏感なパースや行折り処理に役立った）、従来のパースアプローチでの面倒なレキサー/パーサーの分割をなくしてくれる。

└

ちょっと反論させてもらうけど、レキサーとパーサーを分けるのは本当に価値があるよ。パーサーコンビネータのアプローチの一番の良いところは、それぞれが一種のパーサーで、例えば、type Lexer = ParsecT e ByteString m [Token] type Parser = ParsecT e [Token] Exprみたいに書けること。多くのヘルパー関数（manyやsepByなど）は、レキシングとパースの両方のフェーズで同じようにうまく機能するんだ。括弧や割り算の順序に関わる段階に達して、「ここでホワイトスペースをすでにトリムしたかどうか考えなきゃいけない」ってのは本当に面倒だよね。

└

LLとLRのパーサージェネレーターは過大評価されてる気がするし、手書きの再帰下降が実際には一番良いと思う。学者がそれを教える理由は分かるけど、なぜ趣味でおもちゃの言語をコンパイルしたい人たちがそれに時間をかけるのかは理解できない。私はプログラミング言語の分野で働いていて、初めてのコンパイラから今まで、再帰下降が一番簡単で効果的（バグが少なく、エラーダイアグノスティクスが良くて、十分速い）で直感的だと感じてる。多くの人気のある言語コンパイラは再帰下降を使ってるよ。C#（Roslyn）やRustは知ってるけど、Haskell（GHC）やOCamlを除いてほとんどがそうだと思う。LRアルゴリズムは一度学べば簡単だったし、yaccのようなLR（やantlrのようなLL）パーサージェネレーターも、コンフリクトの解決方法を学べばすぐに分かりやすかった。でも、再帰下降は（少なくとも私には）もっとシンプルでストレートだよ。LRがLLより表現力があるってのは、私には関係なかった。手書きの再帰下降パーサーは最も表現力が高い：無限の先読みができて、パースしたASTノードを変更できる（例えば、優先順位のために再配置したり、ifをif-elseに変えたり）。近い解決策はtree-sitterだけど、GLRを実装していて、役立つコンフリクトメッセージを提供して、基本的なIDEサポート（例えば、構文ハイライト）をほぼ無料で提供してくれる。でも、ビルド依存関係があるから、再帰下降パーサーはほとんどの言語でゼロ依存関係で最小限のボイラープレートで書けるんだ。

コンパイラ構築への漸進的アプローチ アブドゥルアジズ・グルーム http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf 概要 コンパイラは魔法のようなアーティファクトと見なされていて、魔法使いによって慎重に作られ、一般人には理解できないものとされています。コンパイラに関する本は、魔法使いの言葉で書かれたものとして説明されることが多いです：全知の実践者のために書かれたものです。実際のコンパイラは教育ツールとしてはあまりにも複雑です。そして、実際のコンパイラと教育用のおもちゃのコンパイラとの間には大きなギャップがあります。初心者のコンパイラ作成者は、不可解な障壁に直面して困惑し、「代わりにインタプリタを書いた方がいい」と思うことが多いです。この論文の目的は、その障壁を打破することです。コンパイラを構築するのはインタプリタを作るのと同じくらい簡単であることを示します。私たちが構築するコンパイラは、Schemeプログラミング言語の大きなサブセットを受け入れ、パーソナルコンピューティングの主要なアーキテクチャであるIntel-x86アーキテクチャのアセンブリコードを生成します。コンパイラの開発は、多くの小さな漸進的なステップに分けられています。各ステップは、徐々に拡大するSchemeのサブセットに対して完全に動作するコンパイラを生成します。すべてのコンパイラステップは、実際のアセンブリコードを生成し、それをハードウェアで直接アセンブルして実行できます。読者は基本的なコンピュータアーキテクチャ：その構成要素と実行モデルに慣れていることを前提としています。Intel-x86アーキテクチャの詳細な知識は必要ありません。コンパイラの開発は、拡張チュートリアルで詳細に説明されています。チュートリアルのための自動テスト機能や包括的なテストスイートなどのサポート資料も提供されています。この論文が、現在および将来のSchemeの実装者に高性能コンパイラの開発への動機とその目標を達成する手段を見つけてもらえることを願っています。

└

Ghuloumの本に触発されて、Nora Sandlerの素敵な本があるよ。「Writing a C Compiler」ってやつ。https://norasandler.com/book/

コンパイラ作成はかなり進化してるよ。特にメタコンパイラ[1]は数百行のコードで書かれていて、適応コンパイル[3]やジャストインタイムコンパイラもある。アラン・ケイの研究グループVPRiは、コンパイラを書く際の複雑さの問題に取り組んだんだ[4]。 [1] Ometa https://tinlizzie.org/VPRIPapers/tr2007003_ometa.pdf [2] 他のometaの論文 https://tinlizzie.org/IA/index.php/Papers_from_Viewpoints_Re... [3] 適応コンパイル https://youtu.be/CfYnzVxdwZE?t=4575 博士論文 https://www.researchgate.net/publication/309254446_Adaptive_... [4] 本当に「複雑」なのか？それともただ「複雑にした」だけなのか？アラン・ケイ https://youtu.be/ubaX1Smg6pY?t=3605

もらったいいアドバイスの一つは、本はRAMみたいなもので、順番に読む必要はなくて、自分が必要な部分にランダムアクセスできるってこと。そう考えると、分厚い本を一冊手に入れて、自分のタスクに必要な部分だけ読むのもできると思う。でも、正直言うと、何を知らないかが分からないときにはこのランダムアクセス法は通用しないんだよね。だから、軽くて良い導入があることが重要なのは理解できるし、作者がそれを指摘しているのも納得だよ。

└

何年も前からそういう提案を見たけど、僕には全然うまくいかなかった。印刷された本から何か意味のあるものを得るには、最初から最後まで読まなきゃいけなかった。昔は価値のある参考書もあったけど、今はそれがインターネットに移っちゃったね。

ナノパスに関する記事の枠組みはあまり評価されてないけど、実際のポイントはパスの数じゃなくて、各パスに明確な入力と出力の言語があることなんだよね。これがあるから、各ステージでどんな不変条件が成り立つかを考えさせられる。これだけでも、コンパイラを実行する前に驚くほど多くのバグを見つけられるよ。クレンショーは素晴らしいけど、この構造的な考え方が、トイコンパイラと実際に拡張できるコンパイラを分けるんだ。