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

プログラミング言語に対する考え方を変えた文章

概要

  • プログラミング言語やコンパイラに関する画期的な記事や論文を紹介する内容
  • 各記事が筆者の考え方や理解を大きく変えた事例を列挙
  • ガベージコレクション、最適化、レジスタ割り当て、正規表現エンジンなど多岐にわたるトピック
  • 各記事の要点や学びを簡潔に解説
  • 読者に新たな視点や知識の獲得を提案

プログラミング言語・コンパイラ分野で思考を一変させた記事リスト

ガベージコレクションとメモリ管理

  • Andy Wingo による「a simple semi-space collector」は、 Cheney式/コピー/圧縮型GC の理論を実装レベルで理解可能にすること
    • コア部分が小さく、拡張性があり、短時間で把握できることを確認
  • is_forwarded関数 のバグ修正提案
    • int is_forwarded(struct gc_obj *obj) { return (obj->tag & NOT_FORWARDED_BIT) == 0; }とすること

最適化手法と抽象領域

  • CF Bolz-Tereick の「Implementing a Toy Optimizer」は、命令書き換えの考え方を 転送ポインタ利用 へ刷新
    • find-and-replaceからforwarding pointer活用への転換を提案
  • 「A Knownbits Abstract Domain for the Toy Optimizer, Correctly」では、 新たな抽象領域Z3の役割 を再認識
    • Z3を証明エンジン・Pythonコードの検証ツールとして活用すること

レジスタ割り当てと検証

  • Chris Fallin の「Cranelift, Part 3: Correctness in Register Allocation」は、 入力ごとの正しさ証明 を提案
    • 本番環境で正しい割り当てか有意義なクラッシュを保証すること
    • ファジング を状態空間探索・バグ発見に活用すること

正規表現と仮想マシン

  • Russ Cox の「Regular Expression Matching: the Virtual Machine Approach」は、 50行未満の正規表現エンジン 実装を提示
    • 実装を通じて コルーチン/ファイバー/スケジューラ の理解を深めること

機械学習の基礎理解

  • Andrej Karpathy の「micrograd」は、 ライブラリ未使用のニューラルネット実装 を体験
    • 機械学習の仕組みを自作コードで理解すること

SSA形式とヒープ効果

  • Fil Pizlo の「How I implement SSA form」は、 union-findの新しい実装法 を提案
    • Identityタグを活用し、破壊的だが省スペースなアプローチを採用すること
    • Phi/Upsilon形式やTBAAスタイルのヒープ効果も導入

JITとコード生成

  • Takashi Kokubun の「Ruby JIT Challenge」は、 仮想スタック上でのレジスタ割り当て という新手法を紹介
    • スタック操作をコンパイル時に物理レジスタへ畳み込むこと

単一パス設計と実装戦略

  • Abdulaziz Ghuloum の「An Incremental Approach to Compiler Construction」は、 機能ごとに逐次実装 するシンプルな設計を提示
    • Fernando Borretti の「Lessons from Writing a Compiler」も同様の実装戦略を言語化

イコリティサチュレーションとe-graph

  • 「egg: Fast and extensible equality saturation」は、 全ての式の最適版を圧縮ハイパーグラフで生成 し最良を選択する発想を提案
  • Chris Fallin の「Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations」は、 e-graphの実用性 を証明
  • Phil Zucker の「Acyclic Egraphs and Smart Constructors」は、 非巡回e-graph の可能性を探求

抽象構文木(AST)と並列解釈

  • Bob Nystrom のRedditコメントおよび Adrian Sampson の「Flattening ASTs」は、 ASTのコンパクト化と並列ロックフリー抽象解釈 を議論
    • Cliff Click による「bump-allocationは数クロックで済む」との言及も新たな視点を提供

その他の注目記事・講演

  • Chandler Carruth の「Modernizing Compiler Design for Carbon Toolchain」は、 厳格なコンパイルタイム予算内での設計 を解説
  • Allison Kaptur の「A Python Interpreter Written in Python」は、 CPythonのバイトコードインタプリタ内部 を理解
  • Eli Bendersky の「Parsing expressions by precedence climbing」は、 優先順位付きパーサ の簡潔な実装法を提示

  • これらの記事・論文は、 プログラミング言語・コンパイラの理解や設計思想 を根本から刷新する内容であり、読者に新たな知見や発想を提供することを提案

Hackerたちの意見

マイクログラッドについてなんだけど、GitHubのリポジトリにあるソースコード以外にドキュメントってもっとあるの?

彼(アンドレイ・カーパシー)は、どうやってそれを作ったかを解説するYouTubeのシリーズを持ってるよ! https://www.youtube.com/watch?v=VMj-3S1tku0&list=PLAqhIrjkxb...

これ大好き!最近、たくさんのCS研究をしてきたけど、ここに載ってないものもいくつかあるよ。思いつくままに、私のお気に入りをいくつかシェアするね: - イアン・ピウマルタの「オープンで拡張可能なオブジェクトモデル」(https://www.piumarta.com/software/id-objmodel/objmodel2.pdf)は、プログラマーに最大限の自由を与える最小限のオブジェクト指向メタオブジェクトシステムを作ることについて。基本的にはメッセージ送信操作だけを定義していて、他は実行時に変更可能。濃密な「メタオブジェクトプロトコルの技法」の実用的な対比。 - ジョン・アウスターハウトの「スクリプティング:21世紀の高水準プログラミング」(https://web.stanford.edu/~ouster/cgi-bin/papers/scripting.pd...) - これは論文じゃなくて、Tclの創始者によるシステムプログラミング言語とスクリプト言語の二項対立についての記事。最初は明白に見えるけど、そこにある教訓は広範な影響があると思う。私たちは常に、何でも高パフォーマンスで生産性高くできる完璧なマルチパラダイム言語を求めているけど、実際にはコンパイルされた速くてガタガタのシステム言語と、エルゴノミックで柔軟なインタープリタフロントエンドを組み合わせるのがベストかも。アプリ内でC+Tclがあれば十分なことが多い。新しいプログラミング言語を書く人には必読だよ。 - ニクラウス・ウィルトのプロジェクトオベロン(https://people.inf.ethz.ch/wirth/ProjectOberon/)は、ハイレベルのUIからカーネル、コンパイラ、RISCのようなCPUアーキテクチャまで、コンピュータシステム全体の実装。彼は「スリムなソフトウェアのお願い」という重要な著作を書いて、実際にそれを実行した。依存関係地獄や平凡なコーダーからの高い抽象化の時代において、長らく失われた技術だね。

うーん、アウスターハウトの二項対立と結論には同意できないな。まず、彼のポイントの理解として - 言語はCのようなシステム言語か、TCLやPythonのようなスクリプト言語のどちらかだってこと。システム言語は「強い」型を持ち、データ構造やアルゴリズムに使われ、スクリプト言語は「型なし」で「ものをつなげる」ためのもの。主張は、スクリプト言語はより簡潔で、型なしの性質のおかげでつなげるのが早くできるってこと。彼の例では、Tclでボタンを作る。button .b -text Hello! -font {Times 16} -command {puts hello} 彼は続けて言う。「C++とMicrosoft Foundation Classes(MFC)では、3つの手続きで約25行のコードが必要です。フォントを設定するだけでもMFCでは数行のコードが必要です:CFont *fontPtr = new CFont(); fontPtr->CreateFont(16, 0, 0, 0, 700, 0, 0, 0, ANSI_CHARSET, OUT_DEFAULT_PRECIS, CLIP_DEFAULT_PRECIS, DEFAULT_QUALITY, DEFAULT_PITCH|FF_DONTCARE, “Times New Roman”); buttonPtr->SetFont(fontPtr); このコードの多くは強い型付けの結果です[...] Tclでは、フォントの本質的な特性(フォント名Times、サイズ16ポイント)を宣言や変換なしですぐに使える。さらに、Tclではボタンの動作をボタンを作成するコマンドに直接含めることができるが、C++やJavaでは別に宣言されたメソッドに置かなければならない。引用終了。私たちは長い道のりを歩んできたし、例はこの二項対立が間違っていることを明らかにしている。アウスターハウトの見解は彼の限られた経験に影響されていて、彼が実際にTclの何を好きなのかを誤解している。構文について話そう。彼が提示した正確なTclコードは、静的型解析を行う言語によって解析され、コンパイルされることができる。そうではないのは、彼が実行時にのみ型をチェックするインタープリタで実行しているからだ。でも、コードがコンパイルされるかインタープリタであるかは、構文とはほとんど関係のない実装の詳細だ。彼は自分の構文がC++より明らかに優れているから好きなだけで、それ以上のことはない。そして型について:彼は「型なし」言語が制約が少ないから開発が早くできると主張している。これは、もちろんナンセンスだ。制約の量は問題の関数であって、言語の関数ではない。動的型付けが開発を早くしているように感じるのは、制約に直面するのを後回しにしているからだ。プログラムが実行される前にすべての型エラーに遭遇することを保証するほうがいい。でも、どの言語でも静的型解析を行えるのに、なぜすべての言語がそれを行わないのか?それは難しいからだ。型理論は複雑だ。すべての型システムが決定可能なわけではないし、実用的な理由から決定可能なものを選ぶ必要がある。決定可能なものは、注釈や複雑なアルゴリズム/セマンティクスの制約が必要な場合がある。PLデザイナーとしては、静的型チェックを実行時にのみ行うことをあきらめるほうがずっと簡単だ。そして、すぐに使える言語を埋め込むことが最優先なら、それは理にかなっている。でも、それが実際に良いからだとは思わないでおこう。

コメントするのは、コメントにお気に入りができないからだよ。

リッチ・ヒッキーのトークの一つを観ることを強く勧めるよ(特に初期のやつ)。あれを観ることで、プログラミング全般についての考え方が変わったから。

「シンプルを簡単に」はスキップしたほうがいいよ。過去10年間、ほぼすべてのカンファレンススピーカーがそのトークを引用してるのを聞くのに耐えられないから。もうそれ自体がクリシェになっちゃった。(もちろん冗談だよ。「ハンモック駆動開発」のほうが好きだけど、あまり企業向きじゃないね)

ラリー・ウォールの「Programming Perl」と並んで、俺にとって最も影響力のある本だね。

誰かがこれを高水準言語向けに書いてくれたらいいのに:JavaScriptや.NET。きっとその人は天才なんだろうけど、私たちのほとんどよりもずっと低い(高い?)レベルで活動してるみたい。

興味深い変わった開発方法について...APLのアーロン・ヒューが、考えを整理するために万年筆でカリグラフィーのようにコードを書くことが多いんだ。私は似たようなことをするけど、印刷でクソみたいなビックペンとPythonオブジェクトのフローチャート(貧乏人のUMLみたいな)を使ってるよ。

難しい問題には万年筆を使うことにしてる。全然違う思考空間に入れるんだよね。限られた編集能力が、より一貫した線形的な思考を強いるけど、英語、コード、数学、図の間をシームレスに切り替えられる自由が創造性を広げてくれるんだ。

手書きと記憶の保持には証明された関連性があるんだよね。コンピュータでメモを取るのは、手すりに指紋を残すようなもの。OCR技術がもっと進化して、手書きだけで完璧に保存・検索できるようになったらいいのにな。

この人は好きだけど、彼に対して何も言うことはないよ。ただ、これらは全部PLについてじゃなくて、コンパイラについての話ばかりなんだよね(GCの話を除いて)。それはそれでいいんだけど(コンパイラは好きだし)、PLに関しては全く関係ないんだよね。

プログラミング言語(実装)? :)

アブドゥラジズがクウェートに戻ってから静かになっちゃったのは残念だね。彼は2009年にMaxine VMのインターンだったんだ。すごくいい人で、その論文は宝物だよ!

わかるよ :( でも、彼はパン屋を開いて、そのビジネスがうまくいってるみたいだね。だから、ある意味では夢を叶えてるのかも。

この投稿大好き。プログラミング言語について書くことで、プログラミング全般に対する考え方が変わったんだ。TAPLのこの引用をよく思い出すよ。「非公式には、安全な言語はプログラミング中に自分の足を撃つことが不可能なものとして定義できる。」この「安全性」の枠組みが、システムの設計方法を変えたんだ。安全な言語は「自分の抽象を守るもの」と言えるかもしれない。安全性は、言語がこれらの抽象やプログラマが言語の定義機能を使って導入した高レベルの抽象の整合性を保証する能力を指すんだ。例えば、ある言語は配列を提供していて、アクセスや更新操作ができるようになっている。だから、この言語を使うプログラマは、配列は明示的に更新操作を使ってのみ変更できると期待するんだよね—例えば、他のデータ構造の終わりを越えて書くことではなくて。 https://www.cis.upenn.edu/~bcpierce/tapl/

最近、クロージャベースのインタプリタでインタプリタを高速化する良い投稿があったよ: https://news.ycombinator.com/item?id=43595283 その技術を使っておもちゃのbrainfuckインタプリタを作ってみたけど、結構速かったよ。他の場所で使う機会があるかはわからないけど、実験してみたのは役に立ったよ: https://github.com/skx/closure-based-brainfuck-vm

クロージャの配列と、交互の関数ポインタとデータの配列の違いにすごく興味があるんだ。後者はほとんどの言語ではあまり自然じゃないし、Cっぽい何かが必要になるよね。でも、直感的には静的関数とそのデータに同じ配列でアクセスできるのがキャッシュと相性が良い気がする。

pytypeは部分的にbyterunに基づいてるんだ https://github.com/google/pytype/blob/main/docs/developers/i... これに取り組むことでバイトコードインタープリタについてたくさん学んだし、最初にPythonの翻訳を触ったおかげでCPythonのソースコードもずっと理解しやすくなったよ。