OCaml、Haskell、Rust、Scala 这些语言里的 match 写起来理所当然，但它编译成什么？朴素做法是自上而下一行行试匹配，代价是大量重复测试。Jules Jacobs 的这篇笔记用五页纸讲清了高效模式匹配编译（Maranget 2008 的关键思想）：把 match 编译成一棵不做任何不必要测试的决策树。算法本身出人意料地简单，适合作为编译器入门读物。

原文链接：How to compile pattern matching（Jules Jacobs，2021 年 5 月 2 日）

以下为全文翻译。原文用颜色区分两类变量：绿色 a 表示已经有值的局部变量（被测试的对象），红色 x 表示将要由模式匹配赋予值的变量；译文中以 a 与 x 的字体区分，下标用 Unicode 字符表示。

引言

我们的目标是编译 ML 风格的模式匹配：

match a with
| Add(Zero, Zero)   ⟹ e₁
| Mul(Zero, x)      ⟹ e₂
| Add(Succ(x), y)   ⟹ e₃
| Mul(x, Zero)      ⟹ e₄
| Mul(Add(x, y), z) ⟹ e₅
| Add(x, Zero)      ⟹ e₆
| x                 ⟹ e₇

朴素的编译方式是自上而下一个一个模式地试：把 a 依次与每个模式匹配。这很低效——假设 a 的外层构造器是 Add，但第一个模式失败了，那么第二个模式还会去测试 a 是不是 Mul，尽管此时我们已经知道它是 Add 了；接着第三个模式又会再测一次 a 是不是 Add，完全是冗余的。我们希望把模式匹配编译成不做不必要测试的代码。

这确实意味着我们必须从第一个模式开始试：如果第一个模式成功了，那么为匹配其他模式所做的任何工作都是白费的。所以我们的策略是模拟那个「先试完第一个模式」的朴素策略，但一旦在匹配中途失败，我们就记住已经探明的事实，据此编译出一个特化版本的剩余模式匹配。

编译示例

把 match 表达式表示成「一组隐式测试外层变量 a 的模式」并不好用，更好用的形式是一组子句（clause），每个子句显式说明它测试的是什么：

match
| a is Add(Zero, Zero)   ⟹ e₁
| a is Mul(Zero, x)      ⟹ e₂
| a is Add(Succ(x), y)   ⟹ e₃
| a is Mul(x, Zero)      ⟹ e₄
| a is Mul(Add(x, y), z) ⟹ e₅
| a is Add(x, Zero)      ⟹ e₆
| a is x                 ⟹ e₇

一般来说，每个子句可以有多个测试，形如：

| a₁ is pattern₁, ..., aₖ is patternₖ ⟹ e

其中 a₁ ... aₖ 是已绑定的变量，pattern₁ ... patternₖ 是模式。这份额外的灵活性在编译过程中会派上用场。

我们的目标是这样一个算法：输入是这样一组子句，输出是一棵由简单原语模式匹配（match#）组成的树，每个 match# 只针对单个构造器做测试：

match# a with
| C(a₁, ..., aₙ) ⟹ [A]
| _              ⟹ [B]

来看看这个例子该怎么做。我们从第一个测试入手：用下面这个模式匹配测试 a 是否为 Add 构造器：

match# a with
| Add(a₁, a₂) ⟹ [A]
| _           ⟹ [B]

于是对分支 A，我们要解决如下子问题：

[A] =
  match
  | a₁ is Zero, a₂ is Zero ⟹ e₁
  | a₁ is Succ(x), a₂ is y ⟹ e₃
  | a₁ is x, a₂ is Zero    ⟹ e₆
  | a is x                 ⟹ e₇

注意现在每个子句里有多个测试了——它们对应生成的 match 里的 a₁ 和 a₂，这两个名字在子问题 A 中成为已绑定变量。（子句 a is x 不含对 a 的构造器测试，所以原样进入两个分支。）

我们可以把针对裸变量的测试（如 a₂ is y）下沉到右部，以此化简子问题。子问题 A 变成：

[A] =
  match
  | a₁ is Zero, a₂ is Zero ⟹ e₁
  | a₁ is Succ(x)          ⟹ let y = a₂ in e₃
  | a₂ is Zero             ⟹ let x = a₁ in e₆
  |                        ⟹ let x = a in e₇

（其实在上一步就可以对最后一条测试这么做了。）

现在我们继续匹配：尝试匹配 a₁ = Zero，生成模式匹配：

match# a₁ with
| Zero ⟹ [C]
| _    ⟹ [D]

然后对 [C] 和 [D] 递归地继续下去。

分支 [B] 的子问题，则是从原问题中删掉所有带 a is Add(..., ...) 的子句后得到的：

[B] =
  match
  | a is Mul(Zero, x)      ⟹ e₂
  | a is Mul(x, Zero)      ⟹ e₄
  | a is Mul(Add(x, y), z) ⟹ e₅
  | a is x                 ⟹ e₇

通用算法

把上面的过程一般化。给定一组要为之生成模式匹配树的子句，算法如下：

  1. 把针对裸变量的测试 a is y 用 let y = a 下沉到右部，使剩下的测试全部针对构造器。

  2. 用某种启发式，从第一个子句里挑出一个测试 a is C(P₁, ..., Pₙ)。

  3. 生成这个模式匹配：

    match# a with
| C(a₁, ..., aₙ) ⟹ [A]
| _              ⟹ [B]

  4. 遍历所有子句，按如下方式构造两个子问题 [A] 和 [B]。每个子句必居三种情况之一：

    • (a) 子句含有对 a 的测试 a is C(P₁, ..., Pₙ), ...REST...：把展开后的子句 a₁ is P₁, ..., aₙ is Pₙ, ...REST... 加入 A。注意新变量名 a₁ ... aₙ 要在 match a with C(a₁, ..., aₙ) 与各个测试 a₁ is P₁, ..., aₙ is Pₙ 中一致地使用。
    • (b) 子句含有对 a 的测试 a is D(P₁, ..., Pₙ), ...REST...，其中 D ≠ C：把该子句原样加入 B。
    • (c) 子句不含对 a 的测试：把该子句同时加入 A 和 B。
    • （注意每个子句对 a 至多只有一个测试。）

  5. 递归地为 [A] 和 [B] 生成代码。

递归有两个基准情形：

  • 子句列表为空：所有模式都失败了，生成错误：Error: Non-exhaustive pattern match.（模式匹配不穷尽）。
  • 第一个子句为空（零个测试）：第一个子句匹配成功，直接返回它的右部 eᵢ。

启发式

怎么决定从第一个子句里挑哪个测试来分支？挑任何测试都正确，但我们希望生成的模式匹配树尽量紧凑。只要某个其他子句落在情况 (c)，它就会被同时加进 A 和 B——这会导致代码爆炸。为了避免它，我们要挑引起最少代码复制的那份测试。因此我们选择在最多其他子句中也出现的那个测试（译注：即选择被最多子句共同约束的变量，让情况 (c) 尽量不发生）。

考虑这个例子：

match a with
| Add(Add(x, y), Zero) ⟹ e₁
| Add(Mul(x, y), Zero) ⟹ e₂
| Add(x, Mul(y, z))    ⟹ e₃
| Add(x, Add(y, z))    ⟹ e₄
| Add(x, Zero)         ⟹ e₅

外层构造器没得选，但内层构造器可以先测 Add(x, y) 也可以先测 Zero。如果先测 Add(x, y)，最后会把 e₃ 和 e₄ 两个子句各复制一份。我们的启发式选择先匹配 Zero，得到没有任何复制的最优代码：

match# a with
| Add(a₁, a₂) ⟹
    match# a₂ with
    | Zero ⟹
        match# a₁ with
        | Add(x, y) ⟹ e₁
        | Mul(x, y) ⟹ e₂
        | _         ⟹ e₅
    | Mul(y, z) ⟹ e₃
    | Add(y, z) ⟹ e₄
    | _         ⟹ ERR
| _ ⟹ ERR

（我把对同一个变量的连续测试合并成了单个 match——见下文。）

讨论

这个算法与文献中的算法略有不同，它基于以下观察与考量。

有些文献花大力气避免指数级代码爆炸，宁可生成冗余测试 [Aug85]。但指数级爆炸在实践中并不会发生 [SR00]。因此在我看来，正确的做法是永远不生成冗余测试，并用启发式（如 [Mar08] 那样）尽量避免代码复制。

事实上，文献表明对真实世界的代码，不同模式匹配算法生成的代码几乎一模一样 [SR00, Mar08]。我们这里的做法是：(1) 永远先匹配第一个子句，以避免不必要的测试；(2) 用启发式贪心地最小化复制。这与文献中的做法不完全相同，但与 [Mar08] 的启发式相近。

生成二分测试（而不是同时对多个候选构造器分支的 n 路测试）可能是避免复制所必需的：

match (a, b) with
| (A, _) ⟹ e₁
| (_, A) ⟹ e₂
| (_, B) ⟹ e₃
| (_, C) ⟹ e₄
| (_, D) ⟹ e₅
| (B, E) ⟹ e₆
| (C, F) ⟹ e₇

如果对 a = A, B, C 做三路分支，那么中间那些子句在 B 和 C 两个分支里都得复制一份。相反，如果只是测试 a = A 是否成立，然后再测试 b = A, B, C, D, E, F，就没有任何复制。

n 路分支用跳转表（jump table）执行可能比一串二路分支更高效。检测出一串针对同一个变量的二路分支、再把它们转回 n 路分支，并不困难。

有些文献使用决策 DAG 而不是决策树。生成决策 DAG 最简单的办法，就是先生成决策树，再用 hash-consing 把它压缩成 DAG [Mar08]。一个更简单（虽然不那么优）的办法是只对右部做这件事、而不对决策树的内部节点做：为每个不同的右部生成一个独立的基本块，把各处右部替换成跳转到对应基本块的跳转。

要利用类型信息，可以跟踪每个变量剩余可能的构造器。这样，当没有剩余可能的构造器时，就可以避免生成错误分支。于是，检查模式匹配是否穷尽，只要看有没有生成错误分支即可；检查冗余模式，只要看某个原始右部 eᵢ 是否没有出现在决策树里。

代码

实现该算法的 Scala 代码见 pmatch.sc。

Yorick Peterse 用 Rust 实现了一个先进得多的版本，支持构造器、整数字面量与区间、或模式（or-pattern）、守卫（guard），以及穷尽性与冗余检查。仓库里还有一份很好的 README，讲解这个算法以及如何实现那些高级特性。「a is pattern」这个语法就是 Yorick 发明的——我最初用的是「a = pattern」，但我认为 Yorick 的写法更清楚。

参考文献

  • [Aug85] Lennart Augustsson. Compiling pattern matching. FPCA 1985.
  • [Mar92] Luc Maranget. Compiling lazy pattern matching. LFP 1992.
  • [Mar08] Luc Maranget. Compiling pattern matching to good decision trees. ML Workshop 2008.
  • [Pet92] Mikael Pettersson. A Term Pattern-Match Compiler Inspired by Finite Automata Theory. CC 1992.
  • [Ses96] Peter Sestoft. ML pattern match compilation and partial evaluation. Partial Evaluation, 1996.
  • [SR00] Kevin Scott, Norman Ramsey. When Do Match-compilation Heuristics Matter? 2000.

译后小结

这篇笔记的精髓可以浓缩成三句话：

  1. 把 match 改写成显式子句列表，每个子句是一组「变量 is 模式」的测试，裸变量测试用 let 下沉到右部；
  2. 递归分治：挑一个测试生成二分 match#，按「匹配 / 构造器不同 / 不涉及该变量」三种情况把子句分进两个子问题，直到子句为空（报错）或首个子句为空（成功）；
  3. 启发式防复制：优先选被最多子句共同测试的变量，避免子句被复制进两个分支导致代码膨胀。

它还澄清了一个常见误解：与其像早期文献那样为防止指数爆炸而容忍冗余测试，不如坚持「零冗余测试」，因为实践中爆炸几乎不发生——真实代码里各算法生成的代码本来就没多大差别。如果你在实现自己的语言，从 Scala 那份百行实现或 Yorick 的 Rust 版本入手，比直接啃论文要平滑得多。