各位道友好，最近一直没怎么弄 Emacs 
配置趋向稳定了，一直在学习别的东西，今天给大家分享一篇 Neel Krishnaswami 写的他对编译器教学的理解心得，某种意义上为编译器中的大部分技术点出了一个纲要，希望大家喜欢
全文
最近，我阅读了 Ben Karel 的一篇博文。他的博文总结了 John Regehr 提出的「关于如何教编译器」的请求所引起的反响。正如人们所预料的那样，网上一致认为这个问题的答案是「全都要」。基本上，每个人对「什么是最重要的事情」有着不同的看法，因此所有人的最重要事情加起来就是一切。其实，某种意义上我并不反对这一观点：编译器中的一切基本上都包含了绝对华丽的算法和证明：从解析到类型检查到中间表示到指令选择到数据表示到栈布局到垃圾收集器到 ABI 到调试器……编译器中精彩内容的密度之大简直超乎人们想象。
然而，John 说的是入门课程——唉，这样一来，「全都要」就成了一个错误的答案。John 需要的是一个教学为先的答案，这一答案应该能在少量的课时中就融会贯通。这就意味着，我们必须从「我们希望学生学到什么？」这一问题出发，然后围绕这个问题设立课程。
编译器教学的目标
那么，学生在上完编译器课后应该学到些什么？
显而易见（但错误）的答案是：「学到怎么写编译器。」课程结束后，学生们可能很快就会忘记大部分编译器实现技术，他们之中的大多数人不会再写更多的编译器，除非他们发现了编译器中的错误。因此，如果我们想让他们在编译器课程中获得一些持久的知识，就必须从更深层次的编程技术角度思考：这些技术首先要在写编译器时自然出现，但又必须适用于更多的环境，而不仅仅是编译器。
这种技术有两个明显的候选方案：
-
使用递归函数在归纳定义的数据结构上计算值
-
通过自底而上的迭代计算单调函数的最小不动点
这两者都是基本的算法技术。不过，考虑到其他课程可能比以前更多地教授现代函数式编程（即数据类型和模式匹配），「在归纳结构上递归」这一点更有可能在编译器课之外就教过了。
这样就剩下不动点计算了。
因此，我们把编译器入门课的目标设定为「在许多不同的情境中多次教授不动点计算」，并假定学生可以对许多具体的实例进行归纳，从而学到计算不动点的一般技术。而学生在「构建一个编译器」这一点的重要之处则在于：他们可以在一个激励性的情景中看到该技术的不同示例。
这一观点促使我们在设计课程时做出了一些选择。
首先，我们的目标在于展示「不动点计算」是如何在许多不同的情境中出现，而编译管线的各个阶段自然就提供了一系列外表迥异的情境。因此，我们应该以前后衔接的方式设计课程，从而涵盖编译管线的所有阶段。然而，这种课程风格一个真实的弱点，它可能会导致对每个主题的覆盖面都比较浅。而要克服这一点，就要在课程的其他部分上下功夫。
其次，我们设计的编译器结构应当非常有主观性——我们确实想要为学生提供各种选择（LR vs LL 解析、图着色 vs 线性扫描寄存器分配、CPS vs SSA 中间表示等等），然后介绍它们的优缺点，在工程和设计方面的考虑因素，以及这些因素使得你更倾向于选择哪一种。
但在本课程中，我们不会做上面谈到的事情。作为教师，我们只要钦定某个算法，尤其是那些最能受益于不动点计算的算法。在讲课时，我们应该指出我们选定的技术有备选方案，但当学生要求我们解释为什么不探讨那些备选方案时，我们应该告诉他们：「这是为了给你们的第一个编译器提供一个好的选择，与 GCC 和 LLVM 相比，我们更倾向于实现简单。」（如果有高级编译器课，或者学生有期末项目能让他们写一个更花哨的编译器，这样就更容易说服学生。）
此外，我们还需咬紧牙关，不再强调与不动点计算关系不大的编译工作。因此，我们就不会详细介绍语言的运行时系统和数据内存布局。这些东西很大程度上会影响编译语言的设计——特别注意的是，不应选择具有闭包或者对象的语言。我们只需告诉学生使用什么样的栈布局，以及通过 Boehm GC 实现垃圾回收。
课程/编译器结构
在本文的其余部分，我将把用来编译的语言叫做 Introl，因为我很喜欢 Algol 的命名方式。Introl 是一种一阶函数式语言，把嵌套函数、λ-表达式、引用和异常从 Ocaml 中移除之后基本就是我们的这一语言，本文末尾附带了这一语言的草案。
这语言有两个「硬菜」特性——多态与数据类型。多态使得「把类型推导描述为不动点计算问题」更加有趣，而添加数据类型则在于：一、对数据结构进行模式匹配带来了有趣的控制流；二、它们真正展示了稀疏条件常量传播的功能。
因此，课程将采用自上而下的方式，从词法分析讲到代码生成。虽然这种课程安排受到不少人的诟病，但实际上（对我们的目标而言）是完全合适的。
词法分析与解析
在词法分析教学中，我会以正则表达式和非确定性有限自动机［Non-deterministic Finite Automata, NFA］ 为起点。但和这些东西的一般教学会不同的是：首先，我会告诉他们正则的状态集大小可能会爆炸，然后向他们介绍 Brüggemen-Klein 和 Derick Wood 的确定性正则表达式［deterministic regular expression］，将其作为防止状态爆炸的一种方法。
这样做的原因在于，这些限制本质上就是在检查「该正则表达式是否可以通过无需回溯的递归下降法进行解析」——或者说，你需要计算正则表达式的 NULLABLE 集、FIRST 集以及 FOLLOW 集（的一种变体）。这样就可以在没有递归或不动点的上下文中向学生解释这些集合的含义，从而轻松过渡到 LL(1) 文法。从根本上来说，LL(1) 文法就是在确定性正则表达式语言上加上递归。
因此，将这些集合作为某些不动点方程的解来计算就非常容易，确定性正则语言在这里扮演了「将这些集合的解释和不动点计算解耦」的角色。
当然，这意味着 Introl 的文法必须满足 LL(1)。
类型检查
对这类语言进行类型检查是很平常的事，但在我们的情况下，应当遵循 Cousot 的 Types as Abstract Interpretation 风格，将其描述为一种抽象解释。
有趣的点在于：多态性［polymorphism］可以通过 Cousot 所谓的 Herbrand 抽象［Herbrand Abstraction］来表达。我们的想法是：设抽象元素为带有统合变量［unification variable］的单类型［monotype］，若存在替换 σ 使 t_{2}=σ(t_{1})，那么它们就满足偏序关系 t_{2}≥t_{1}。统合算法本身则是一种通过计算这一替换，从而证明两个抽象元素有并［join］的尝试——之所以是尝试，是因为统合算法可能会失败。所以统合是一种部分并运算，如果算不出两个元素的并，那么一定是出现了类型错误！
在所介绍的 Introl 语言中，所有顶层函数都有类型注解，因此最终不需要进行严格的不动点计算就能推断出类型。事实上，即便省略掉这些类型注解，「统合算法会计算出最泛用的解」这一点也意味着：对递归函数进行不动点迭代也只需要迭代一次就可停机（这并不奇怪，因为 Damas-Milner 类型推导算法就只需要遍历一次程序语法）。
这一点值得我们关注，因为静态分析中的大量工作都是在想方设法地减少迭代次数。事实上，这也是转向 SSA 的动机所在——这将是编译器的下一阶段。
转换为 SSA/CPS
在编译器课程中，如何选择中间表示［Intermediate Representation, IR］总是充满争议。而在本课程中，我将使用静态单赋值形式［Static Single-Assignment form, SSA］。SSA 是一个不错的选择，一方面它简化了各种数据流分析［data-flow analysis］；而另一方面，要生成它也需要进行数据流分析。此外，它也是各种严肃编译器的首选 IR。这意味着我们可以围绕 SSA 进行大量的不动点计算，而且不会让年轻人们觉得矫揉造作。
不过，我不会直接使用 SSA，因为我觉得 ϕ-函数很难直接解释。我觉得应该向 Richard Kelsey 偷师一招：利用延续传递形式［Continuation Passing Style, CPS］与静态单赋值形式之间的对应关系。
CPS 常常伴随着各种玄之又玄的东西和高阶函数，但在我们的情况下，它的原理十分简单。我们对程序进行 let-规范化，然后将表面语言转化成带参数的基本块［basic block］（或者你喜欢的话，也可以转换成一堆互相尾调用的函数）。这就是 MLton 编译器使用的 SSA 版本，而且（如果我没记错的话）Swift SIL 中间表示也使用了这一版本。
粗略的说，程序中的每个基本块最终都会带有零个或更多的形式参数，要跳转到该基本块，就必须填写这些参数。这么一来，要解释这些概念就超级简单了：把程序转换为 let-范式后，所有尾调用都会编译成带参数的跳转，非尾调用则使用 call IR 指令。
现在，如果我们将这一做法简单地推到极限（我们绝对想这么做），就会得到一种「悲观 SSA」——每个基本块都将其作用域中所有变量作为参数。这样做的原因是为了把「让 SSA 最小化」的需求变得显而易见：我们收缩每个基本块的参数列表，让它不要把没有变化或没有使用到的变量作为基本块参数。而这样做之后我们将到达精简 SSA 形式［pruned SSA-form］，虽然对于第一个编译器而言这样有些杀鸡用牛刀，但我们希望通过它来引出支配树［dominator tree］的概念。鉴于这种收缩的二元对立性质，我们可以通过两种分析来实现——活跃性分析［live analysis］和 常量性分析［constancy analysis］。
这两种分析都是数据流分析，我们可以借此展示：如何利用支配树来安排迭代中的工作顺序，以便更快地计算出不动点。从而证明我们在计算支配树时用到的不动点计算是合理的。这虽然有点冗余，但正是有意为之——我认为在计算支配关系前就进行两次不动点计算很有必要，因为如果用一次不动点计算来加速另一次不动点计算，可能会让人感觉有点刻意；但如果计算一次能加快两次，那么好处就不言自明，更何况在这里我们可以把不动点计算表述为支配树与转移函数的一种结合。
从教学角度而言，计算过程接近于问题定义的算法能更好地向学生解释。因此，我会避免使用某种能快速计算支配关系的算法。而另一个好处在于，选定一个好的抽象域有助于加快类型检查，而选择一个好的迭代顺序则有助于加快流分析。
一旦学生有了一定的操作这些中间表示的经验，我可能就会改用传统 SSA 形式。这样主要是为了提高学生阅读现有文献的能力。
高层次优化
值得说明的一点是，这种语言的中间表示是高层次 SSA（就像 MLton 的 SSA 一样）—— switch 分支、数据构造函数、以及字段选择函数之类的东西都是 SSA IR 的一部分。这样我们可以在语言层面，而非机器层面进行优化。此外，既然学生们已经有了像样的 SSA 表示，我们当然应该用它来进行所有「简单」的 SSA 优化：比如复写传播［copy propagation］和循环不变代码移动［loop-invariant code motion］。在 SSA 下，这些优化都是无条件代码重写，很容易实现，并且能让学生适应操作 SSA 表示。下一步则是死代码消除［dead code elimination］，这本身是一个很好的优化，也让他们需要重新运行存活性分析。这样他们就会明白：编译器的某些过程［pass］可能需要反复进行。
当学生完成这些后，他们就可以为课程中的「英雄级优化」热身了——稀疏条件常量传播［Sparse Conditional Constant Propagation］。由于我们使用的是高层次 IR，这一优化应该会产生一些比平时更令人印象深刻的结果：大量的元组［tuple］创建/模式匹配，以及数据构造函数上的模式匹配都会以一种令人满意的方式消失：以使用 option monad 的安全除法 safediv : int -> int -> option int 为例，若「测试除数非 0」的 IR 节点支配了调用这一除法的 IR 节点，那么优化就会自动删除掉 None 分支。
降维与寄存器分配
正如我之前所说，大的优化是在高层次 SSA 形式上进行的。在这一表示中，switch 语句，数据构造函数以及字段选择函数仍然存在，在生成机器码之前，我们必须将这些操作转化为低层次操作。因此我们可以定义一种「低层次」SSA，在这一表示中，字段选择等操作将变成内存存取操作。然后将高层次 IR 翻译成低层次 IR。
这一翻译应当非常直观朴素，将每个高层次操作以非常直接的方式转换为对应的低层次指令序列。鉴于我们课程设计目的在于进行尽可能多的数据流优化，从而帮助学生提炼出这些优化的精髓。那么，一个关于编译器开发过程是否平滑的测试标准就是：我们的数据流分析算法是否足够参数化，以至于在更改 IR 和格［lattice］的时，仍能获得很好的代码复用性。然后，我们就可以利用这些分析来清理低层次指令序列。
如果说更抽象的代码太难理解，那我就会跳过大部分低层次优化。在低层表示中唯一必须做的分析是重新进行存活性分析，这样我们就可以使用 Hack 的 SSA 形式上的寄存器分配算法。这一算法在避免使用图着色的同时也能获得良好的效果，还让寄存器合并［register coalescing］（通常是一个高级课题）变得出奇的简单。而且它也显然是基于各种数据流分析的结果进行的。
这样一来，代码生成就非常简单了。一旦完成寄存器分配，我们就可以把这些低层次 IR 操作以显而易见的方式映射为汇编上的加载、存入和跳转指令；函数调用和返回将显而易见地重写成对栈的操作；分配对象则变成对 Boehm GC 的函数调用——这一点并不是最优的方法，但据我所知，这方面的大多数技术都不怎么使用不动点计算，因此相对于课程目标而言有点走偏了。
个人观点
令人惊讶的一点是（反正对我来说是这样）：我们通过专注于不动点计算，加上只使用 SSA ，为构造出一个令人惊讶的可靠编译器铺平了道路。在写这篇笔记之前，我曾认为：「对于一个编译器而言，这种级别的编译器过于托大了。」但现在，我认为它可能只是有点托大。
显然，使用一阶函数式语言给我们带来了许多好处。在许多方面，它都只是一种换皮 SSA 语言。不过，它看起来与 SSA 截然不同，而且看起来像一种高级语言，这意味着学生会感觉自己有所成就。
不过，在我愿意采用这种方式教学前，我想先用这种方式编写一两个编译器。这样要么能证明这种这种方案可行，要么就证明编译器太大，不适用于教学。如果编译器太大，我可能会把表面语言简化到只支持整数和布尔类型。由于这两种类型都可以直接放入一个计算机字［word］，这样就可以完全放弃编译中的降维［lowering］过程了。
我喜欢这种方案的另外一点是：我们不但可以用普通的数据流分析实现代码解析；还可以通过一些巧妙的方法表达已知类型信息，从而使用数据流分析进行类型检查；甚至通过一些巧妙的迭代方案，从而利用数据流分析实现优化/代码生成。
不过，如果这一做法太过可爱，以至于造成了学生的混乱。那么另一个选择就是转向简单的有类型语言，放弃类型推导；再放弃 SSA，转用 Kildall/Allen 式的数据流方法。你仍可以教学生如何计算「定义-使用链」，并将这一数据用于加速存活性之类的分析。这也将揭示解析与数据流分析之间的相似之处。
对比与某个想象中的高级编译器课程，我们的课程还缺乏内联［inline］、部分冗余消除［partial redundancy elimination］，以及一些花哨的循环优化等高层次优化，以及指令调度［instruction scheduling］等低层次优化。此外，我们还缺乏一个角度来切入控制流分析［control-flow analysis］，这一分析能处理具有对象或闭包特征的高阶语言。
但是我们直接教授了 SSA，学生想自学这些也将会有个不错的起点。
Introl 语言草案
类型结构
语言有如下类型
-
整数类型.
int -
单位类型.
unit -
元组类型.
T_1 * ... * T_n -
通过 datatype 声明的和类型.
datatype list a = Nil | Cons of a * list a
程序结构
顶层定义
所有函数声明都是顶层生命，不允许嵌套函数和匿名 $$λ$$-表达式。函数声明需带有类型，类型可以是多态的：
val foo : forall a_1, ..., a_n. (T_1, ..., T_n) -> T
def foo(x_1, ...,x_n) = e
表达式
表达式就是那些常见的东西
-
变量.
x -
常量.
3 -
算术.
e_1 + e_2 -
单位.
() -
元组.
(e_1, ...,e_n) -
数据构造函数.
Foo(e) -
变量绑定.
let p = e_1; e_2 -
直接函数调用.
f(e_1, ...,e_n) -
模式匹配语句.
match e { p_1 -> e_1 | ... p_n -> e_n }
请注意，我们没有像 while 或 for 这样的控制结构，而是通过尾递归实现这一点。还要注意的是：调用多态函数时不需要显式提供类型参数。
模式匹配
支持模式匹配，但不支持嵌套的模式匹配，这样可以避免提起模式匹配编译。具体见下
-
变量模式.
xx -
构造函数模式.
Foo(x_1, ..., x_n) -
元组模式.
(x_1, ..., x_n)
示例
下面是一个翻转链表的函数
val reverse_acc : forall a. (list a, list a) -> list a
def reverse_acc(xs, acc) =
match xs {
| Nil -> acc
| Cons(x, xs) -> reverse_acc(xs, Cons(x, acc))
}
val reverse : forall a. list a -> list a
def reverse(xs) = reverse_acc(xs, Nil)
下面是一个压缩两个链表的函数
val zip : forall a, b. (list a, list b) -> list (a * b)
def zip(as, bs) =
match as {
| Nil -> Nil
| Cons(a, as') ->
match bs {
| Nil -> Nil
| Cons(b, bs') -> Cons((a,b), zip(as',bs'))
}
}
注意与 ML 语言相比，我们没有嵌套的模式匹配。