改变我对编程语言思考方式的文章 (PL)
[中文正文内容]
2025年5月13日
时不时地，我会遇到一些论文、博客文章，或者（偶尔）视频，它们完全改变了我对编程语言和编译器中某个主题的思考方式。对于其中一些文章，我甚至不记得在阅读它_之前_我是如何思考这个想法的——它就是这么有影响力。
以下是一些文章，排名不分先后：
-
a simple semi-space collector by Andy Wingo 将 Cheney/复制/压缩垃圾收集器的概念从理论带到了实践。文章中的垃圾收集器核心1非常小巧、可扩展，并且可以在一个下午内理解。
-
Implementing a Toy Optimizer by CF Bolz-Tereick 改变了我对优化器中指令重写的思考方式。不再是查找和替换，而是使用转发指针！我喜欢 union-find。整个 toy optimizer 系列非常棒：每篇文章都带来一些新的和有趣的东西。
-
A Knownbits Abstract Domain for the Toy Optimizer, Correctly by CF Bolz-Tereick 是一举两得。它既向我介绍了一种新的优化器抽象域，又改变了我对 Z3 的思考方式。以前，我模糊地知道 Z3 可以检查数值运算。然而，这篇文章将 Z3 用作证明引擎：如果 Z3 找不到反例，则代码是正确的2。此外，它通过在 Z3 对象和普通 Python 对象上使用相同的 Python 代码，将 Z3 用作 Python 代码 的验证器。
-
Cranelift, Part 3: Correctness in Register Allocation by Chris Fallin 也使证明更容易理解，但方式不同。与其证明你的寄存器分配器在 所有 输入上都是正确的，不如证明它在 一个 输入上是正确的：当前代码。这意味着在生产环境中，你要么获得正确的寄存器分配，要么获得有意义的崩溃。此外，它使用模糊测试作为状态空间探索工具，可以通过使验证器失败来识别错误。
-
Regular Expression Matching: the Virtual Machine Approach by Russ Cox 使正则表达式引擎对我来说变得有意义。这篇博文用不到 50 行可读代码实现了一个小的正则表达式引擎。作为副作用，它也使协程/纤程/调度器更容易理解，因为它对不确定性的实现使正则表达式在用户空间中变成了“线程”。
-
micrograd by Andrej Karpathy 是一个微型的神经网络实现，没有任何库（甚至没有 NumPy）。我就是通过它来理解机器学习，甚至写了一些关于它的博文。
-
How I implement SSA form by Fil Pizlo 改变了我对 union-find 的思考方式。与其在每个对象内部存储额外的指针或拥有一个边表，不如添加一个可以存储指针的
Identity标签。与另外两种方法不同，这是一种破坏性的重写，但它可以节省空间。它还引入了两件我仍在思考的新事物：Phi/Upsilon 形式和 TBAA 风格的堆效应。 -
Speculation in JavaScriptCore 也是 Fil Pizlo 的另一篇精彩文章。每次我重读这篇文章时，我都会学到新的东西，它描述了 JSC 的各种优化器是如何工作的（并且我想是 Fil 如何看待优化器的）。
-
Modernizing Compiler Design for Carbon Toolchain 是 Chandler Carruth 关于 Carbon 编译器设计的演讲。大约 29 分钟时，Chandler 设置了_非常激进的_编译时预算，并解释了如何构建编译器以适应该时间预算。大约 40 分钟时，他开始按层解释这是如何工作的，从词法分析器开始。
-
A Python Interpreter Written in Python by Allison Kaptur 使字节码解释器（特别是 CPython 内部的工作方式）对我来说更加清晰。
-
Parsing expressions by precedence climbing by Eli Bendersky 提出了一个可理解且更易于开发的替代方案，以替代传统的手写递归下降解析器。它既让我不再害怕解析器，同时也说明了优先级爬升与递归下降是相同的算法，但不是使用 10 个具有相似结构的函数，而是使用一个函数和一个表。
-
Ruby JIT Challenge by Takashi Kokubun 是代码生成的一个很好的开始，它比 JIT 更通用。在这篇文章中，他还展示了一种我以前从未见过的很酷的寄存器分配方法：在编译时折叠你的堆栈操作，以在物理寄存器的虚拟堆栈上操作。
-
An Incremental Approach to Compiler Construction (PDF) by Abdulaziz Ghuloum 将编译器和代码生成从一个神秘的多通道野兽变成了一个可理解的单通道形式。我喜欢它如何逐个地实现每个功能端到端。
-
Lessons from Writing a Compiler by Fernando Borretti 在第一节中用文字描述了这种条纹实现策略，这非常棒。
-
egg: Fast and extensible equality saturation by [multiple authors] 改变了我对优化器和pass排序的思考方式。为什么 不 直接生成表达式所有可能版本的压缩超图，然后选择“最佳”版本？我的意思是，这有很多原因，但它确实扩展了我的思维。
-
Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations by Chris Fallin 表明 e-graphs 在生产编译器中是可行的并且非常有效，即使你不做“完整的”事情。
-
Acyclic Egraphs and Smart Constructors by Phil Zucker 进一步探讨了小型的非循环 egraphs。这是一个缓慢的过程：我刚出来的时候就读了它，并没有真正理解它，几个月后它才变得更加清晰。我确信几个月后它会再次变得清晰。
-
This Reddit comment by Bob Nystrom and Flattening ASTs by Adrian Sampson 是一个双重打击，导致了两件事：1) AST 存储可以非常紧凑，几乎像字节码 2) 在 Mastodon 上关于大规模并行无锁抽象解释的非常有趣的讨论，如果 IRs 以这种方式存储。这（以及 Cliff Click 关于 bump-allocation 仅需花费“几个时钟周期”的随意评论）改变了我对分配和引用 IR 节点的思考方式。
希望你喜欢这些阅读材料！
- 这篇文章中只有一个小错误：
is_forwarded应该检查该位是否为 0，而不是 1。正确的版本是：
int is_forwarded(struct gc_obj *obj) {
return (obj->tag & NOT_FORWARDED_BIT) == 0;
}
“GC 和用户之间存在一个契约，用户同意始终在其对象的第一个字中设置 NOT_FORWARDED_BIT。” ↩