プログラミング言語に対する私の考えを変えた文章たち
(bernsteinbear.com)- プログラミング言語とコンパイラに対する見方を根本から変えてくれた、さまざまな記事・論文・動画を紹介する
- 実用的なGC実装、オプティマイザ設計、レジスタ割り当て、正規表現エンジンなどへの理解を大きく広げてくれた資料群
- Z3と抽象ドメイン、SSA形式、E-Graphs など、実務的なアルゴリズムや構造が実際のコード例とともにわかりやすく説明されている
- 各資料は複雑な概念を簡潔かつ拡張可能で理解しやすい形にほどいている
プログラミング言語とコンパイラに関する認識を変えた文章たちの紹介
- ときどき、プログラミング言語やコンパイラに関する話題について、自分の考えを完全に変えてしまう論文やブログ記事、動画などに出会う
- いくつかの文章については、読む前に自分がどう考えていたのかすら思い出せないほど強烈な影響を受けた。
- 以下はそうした資料の紹介（順不同）
GC、オプティマイザ、抽象ドメイン、レジスタ割り当て関連
- Andy Wingoの a simple semi-space collector は、Cheney/コピー/コンパクティング・ガベージコレクタの概念を理論から実際に適用するまでの流れをうまく示している
- 本文中のGCの中核実装は非常に簡潔で、拡張しやすく、半日あれば理解できる
- CF Bolz-Tereickの Implementing a Toy Optimizer は、オプティマイザにおける命令 rewrite方式への認識を変えてくれる
- 単純な検索・置換ではなく、forwarding pointer の利用を重視し、union-find の概念を紹介している
- toy optimizer シリーズ全体を通して、各記事に新しく興味深い内容が含まれている
- A Knownbits Abstract Domain for the Toy Optimizer, Correctly は、新しい抽象ドメインとZ3の活用法を同時に紹介している
- Z3がさまざまな数値演算の証明に使われるだけでなく、Pythonコードの検証エンジンとして活用される例も示している
- Z3が反例を見つけられなければコードの正当性を保証できるという発想を紹介している
- Chris Fallinの Cranelift, Part 3: Correctness in Register Allocation では、入力ごとに正しいレジスタ割り当てを直接証明する方法を説明している
- 本番環境では、正しい割り当てか、意味のあるクラッシュのどちらかが得られる
- ファジング手法で状態空間を探索し、バグを検出するアプローチを導入している
パース、インタプリタ、JIT、抽象構造関連
- Russ Coxの Regular Expression Matching: the Virtual Machine Approach は、正規表現エンジンの実装をおよそ50行の読みやすいコードで示している
- その過程で、コルーチン、ファイバー、スケジューラなどの原理もわかりやすく説明している
- Andrej Karpathyの micrograd は、外部ライブラリなしでニューラルネットワークを動かす極小実装の例で、機械学習の基本構造や原理を学ぶのに役立つ
- Fil Pizloの How I implement SSA form は、union-find構造を改良する新しい方法を紹介している
- SSA変換で追加ポインタをオブジェクト内部のIdentity tagとして管理する方式である
- このほかにも Phi/Upsilon form、TBAAスタイルのheap effectなど、さらに考える材料を与えてくれる
- Fil Pizloの Speculation in JavaScriptCore は、JavaScriptCoreのさまざまなオプティマイザ実装方式を詳しく扱っている
- 読み返すたびに新しいインサイトが得られる
コンパイラ設計、パーサ、IR構造、E-Graphs
- Chandler Carruthの Modernizing Compiler Design for Carbon Toolchain の発表（29分ごろ）では、圧倒的に高速なコンパイル時間目標の設定と全体構造の設計過程を説明している
- 40分ごろからは各層ごとに構造をほどいて説明している
- Allison Kapturの A Python Interpreter Written in Python は、CPython内部のバイトコードインタプリタの動作原理を簡単に理解させてくれる
- Eli Benderskyの Parsing expressions by precedence climbing は、従来の再帰下降パーサより理解しやすく、実装負担も小さいPrecedence Climbingによる構文解析を紹介している
- Takashi Kokubunの Ruby JIT Challenge は、コード生成と新しいレジスタ割り当て手法（stack folding at compile-time）を示している
- Abdulaziz Ghuloumの [An Incremental Approach to Compiler Construction (PDF)(https://bernsteinbear.com/assets/img/11-ghuloum.pdf) は、従来の多段階コンパイラ設計を一度に理解できる単一パス実装方式を説明している
- 各機能をエンドツーエンドで少しずつ追加していく方式を取っている
- Fernando Borrettiの Lessons from Writing a Compiler は、コンパイラ実装戦略を明快に言語化して説明している
- egg: Fast and extensible equality saturation 論文は、オプティマイザとパス順序に対する認識を根本から変えてくれる
- 式のあらゆる可能なバージョンを圧縮されたハイパーグラフとして保持し、その中から最適なバージョンを選ぶという考え方を提示している
- Chris Fallinの Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations は、実際の商用コンパイラでも e-graphs が効果的に機能することを示している
- Phil Zuckerの Acyclic Egraphs and Smart Constructors は、非循環 e-graph構造とスマートコンストラクタの活用を探究している
- 最初は理解が難しかったが、時間がたつにつれて徐々に理解が深まる文章だ
AST保存、大規模並列動的解析などその他
- Bob Nystromの この Reddit comment と Adrian Sampsonの Flattening ASTs は
- ASTをほとんどバイトコードのようにコンパクトに保存する方法と、
- IRノードをこのように保存すれば大規模な並列ロックフリー解析も可能になるという大きな議論につながった
- Cliff Clickのバッファ割り当て速度に関する言及も、こうした考え方に影響を与えた
1件のコメント
Hacker Newsの意見
この投稿は本当に気に入った。最近かなりコンピュータサイエンスの研究を読んでいるが、ここで言及されているものの中にもまだ触れていないものがあった。自分が好きなのにここには入っていない論文をいくつか紹介したい。Ian Piumarta の “Open, Extensible Object Models” は、プログラマに最大限の自由を与える最小限のオブジェクト指向メタオブジェクトシステムを扱っている。基本的にはメッセージ送信演算だけを定義し、それ以外のすべてはランタイムで変更可能だ。“Art of the Metaobject Protocol” の実用版という感じ。John Ousterhout の “Scripting: Higher-Level Programming for the 21st Century” は、システムプログラミング言語とスクリプティング言語の二分法を扱っている。私たちは何でも高速かつ生産的にできる完璧なマルチパラダイム言語をいつも求めがちだが、コンパイルされる高速で複雑なシステム言語と、便利で柔軟なインタプリタ型フロントエンドを組み合わせたほうが良いことも多い。実際、単に C と Tcl を一緒に使うだけで十分な場合も多い。プログラミング言語を作る人なら必読の文章だ。Niklaus Wirth の Project Oberon は、高水準 UI からカーネル、コンパイラ、RISC に似た CPU アーキテクチャまで、コンピュータシステム全体を実装した事例だ。彼は “lean software” を力強く提唱し、実際にそれを実践した。依存関係地獄と過剰な抽象化があふれる今の時代では、失われた職人芸のように感じる
この投稿は本当に気に入った。プログラミング言語についての文章が、私のプログラミングそのものの見方を変えてくれた。TAPL(Types and Programming Languages) の「安全性」についての一節をよく思い出す。安全な言語とは、プログラマが自分で自分の足を撃ち抜くのを防ぎ、自分自身の抽象化を守れる言語のことだ。つまり、言語が提供する抽象化と、プログラマが作り出す上位の抽象化の完全性を保証する能力が重要だ。たとえば配列という抽象化があるなら、明示的に更新したときにだけ変更可能であるべきで、別のデータ構造を誤って壊してしまうようなことがあってはならない、ということだ
興味深い開発習慣の話でいうと……APL で有名な Aaron Hsu は、考えを整理するときに万年筆でカリグラフィーのようにコードを書く。私は似た感じで、安いボールペンで Python オブジェクトのフローチャートのようなものを描きながら考えを整理する。いわば格安 UML だ
私も一番難しい問題に取り組むときは万年筆を手に取りたくなる。万年筆を使うと、まったく別の思考空間に入る感じがする。編集の自由度が低いので、より一貫した線形の思考に導かれる一方で、英語、コード、数学、図を自由に行き来できるので創造性が開く
手書きと記憶力の向上には、実際に関連があることが示されている。コンピュータでメモを取るのは、取っ手に指紋を残すのと大差ないレベルだ。OCR 技術が本当に進歩して、完全に手書きだけで記録しても保存や検索ができるようになってほしい
Rich Hickey の講演、特に初期の講演はぜひ観ることを勧めたい。私もそれを観て、プログラミングそのものの見方が完全に変わった
私にとって最も影響が大きかったのは、Larry Wall の “Programming Perl” と Rich Hickey の講演群だった
“Simple made easy” は、この10年ほぼすべてのカンファレンス登壇者が引用しすぎて今やクリシェになっているので飛ばせ、と冗談めかして言いたくもなる。個人的には “Hammock driven development” のほうが好きだが、会社で勧めるには少し向かない
Abdulaziz がクウェートに戻ってから静かになってしまったのが残念だ。彼は 2009 年に Maxine VM のインターンで、本当に良い人だった。あの論文はまさに宝石のような一本だ
最近、インタプリタを高速化する closure ベースのインタプリタについての良い投稿 があった。私はその手法を使って簡単な brainfuck インタプリタ を作ってみたが、かなり速かった。他で使う機会はなさそうだが、実験としてやってみたのは有益だった
JavaScript や .NET のような、より高水準の言語についてもこういう文章が出てきてほしい。この著者は非常に賢い人だが、たいていの利用者よりもっと低レベル（あるいは高レベル？）のところで活動している
彼のブログの他の記事も本当に素晴らしい
micrograd 関連でいうと、GitHub リポジトリのソースコード以外に、もっと文書化された資料があるのか気になる
この人のことは好きだからこそ言うが、ここにある文章は PL（プログラミング言語）そのものについてではなく、ほとんどがコンパイラについての話だ（ガベージコレクタを除けば）。もちろんコンパイラも好きだが、PL の話題とは別物だ