在编程语言中，模式匹配是一种强大的特性，它允许开发者以声明式的方式处理数据结构。然而，模式匹配的效率很大程度上依赖于编译器的优化能力。本文将探讨编译器如何处理模式匹配，以及程序员的编码风格如何影响编译器的优化决策。
模式匹配可以被编译成高效的自动机。存在两种风格的自动机：“决策树”和“法国风格”。每种风格都有其优势：决策树检查最少数量的值以做出决策，但一个简单的实现可能在最坏情况下需要指数级的代码空间。法国风格提供了不同的时间-空间权衡，对两者都有不错但不最优的保证。
源代码可以在查看。
在F#中，定义了一个模式匹配函数test1：
let test1 x =
match x with
| [|1; 2; 3|] -> A
| [|1; 2; _ |] -> A
| [|1; _; _ |] -> A
反编译后的C#代码如下：
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
return Program.MyType.A;
}
break;
default:
return Program.MyType.A;
}
break;
}
}
throw new MatchFailureException(...);
结论：模式匹配并不基于"->"之后的值进行优化。模式匹配能够在数组分解下找到优化的方法。不完整的模式匹配总是抛出异常，因此添加一个通配符来捕获缺失的模式并显式抛出异常是没有害处的。
在F#中，定义了两个测试函数test1a和test1b：
let test1a x =
match x with
| [|1; 2; 3|] | [|1; 2; _ |] | [|1; _; _ |] -> A
let test1b x =
match x with
| [|4; 5; 6|] & [|4; 5; _ |] & [|4; _; _ |] -> A
反编译后的C#代码如下：
public static Program.MyType test1a(int[] x)
{
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
}
break;
}
return Program.MyType.A;
}
}
throw new MatchFailureException(...);
}
public static Program.MyType test1b(int[] x)
{
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 4:
switch (x[1])
{
case 5:
switch (x[2])
{
case 6:
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 4:
switch (x[1])
{
case 5:
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 4:
return Program.MyType.A;
}
break;
}
break;
}
}
break;
default:
break;
}
break;
}
break;
}
}
throw new MatchFailureException(...);
}
结论：编译器无法在And/Or模式中检查完整性/重复性，因此无法找到最优方法。
在F#中，定义了一个模式匹配函数test2：
let test2 x =
match x with
| [|1; 2; 3|] -> A
| [|_; 2; 3|] -> B
| [|_; _; 3|] -> C
反编译后的C#代码如下：
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
goto IL_49;
}
break;
default:
switch (x[2])
{
case 3:
break;
default:
goto IL_49;
}
break;
}
break;
default:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.B;
default:
goto IL_49;
}
break;
default:
switch (x[2])
{
case 3:
goto IL_58;
}
goto IL_49;
}
break;
}
IL_58:
return Program.MyType.C;
}
IL_49:
throw new MatchFailureException(...);
结论：模式匹配从数组的开始检查值直到结束。因此它无法找到最优方法。代码大小是最优方法的2倍。
在F#中，定义了一个模式匹配函数test3：
let test3 x =
match x with
| [|1; 2; 3|] -> A
| [|1; 2; a |] when a <> 3 -> B
| [|1; 2; _ |] -> C
反编译后的C#代码如下：
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
if (x[2] != 3)
{
int a = x[2];
return Program.MyType.B;
}
break;
}
break;
}
break;
}
}
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
return Program.MyType.C;
}
break;
}
}
throw new MatchFailureException(...);
结论：编译器不够智能，无法看穿Guard来检查完整性/重复性。Guard使模式匹配产生奇怪的未优化代码。
在F#中，定义了一个模式匹配函数test4：
let (|Is3|IsNot3|) x =
if x = 3 then Is3 else IsNot3
let test4 x =
match x with
| [|1; 2; 3|] -> A
| [|1; 2; Is3 |] -> B
| [|1; 2; IsNot3 |] -> C
| [|1; 2; _ |] -> D // This rule will never be matched.
反编译后的C#代码如下：
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
{
FSharpChoice fSharpChoice = Program.|Is3|IsNot3|(x[2]);
if (fSharpChoice is FSharpChoice.Choice2Of2)
{
return Program.MyType.C;
}
return Program.MyType.B;
}
break;
}
break;
}
break;
}
}
throw new MatchFailureException(...);
结论：多个案例的活跃模式编译成FSharpChoice。编译器能够检查活跃模式的完整性/重复性，但它不能与普通模式进行比较。不可达的模式不会被编译。
在F#中，定义了一个模式匹配函数test5：
let (|Equal3|) x =
if x = 3 then Equal3 1 else Equal3 0
let test5 x =
match x with
| [|1; 2; 3|] -> A
| [|1; 2; Equal3 0|] -> B
| [|1; 2; Equal3 1|] -> C
| [|1; 2; _ |] -> D
反编译后的C#代码如下：
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
{
int num = x[2];
switch ((num != 3) ? 0 : 1)
{
case 0:
return Program.MyType.B;
case 1:
return Program.MyType.C;
default:
return Program.MyType.D;
}
break;
}
break;
}
break;
}
}
throw new MatchFailureException(...);
结论：单案例活跃模式编译成返回类型。编译器有时会自动内联函数。（惊喜！）
在F#中，定义了一个模式匹配函数test6：
let (|Partial3|_|) x =
if x = 3 then Some (Partial3 true) else None
let test6 x =
match x with
| [|1; 2; 3|] -> A
| [|1; 2; Partial3 true|] -> B
| [|1; 2; Partial3 true|] -> C
反编译后的C#代码如下：
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
switch (x[2])
{
case 3:
return Program.MyType.A;
default:
{
FSharpOption fSharpOption = Program.|Partial3|_|(x[2]);
if (fSharpOption != null && fSharpOption.Value)
{
return Program.MyType.B;
}
break;
}
break;
}
break;
}
break;
}
}
if (x != null && x.Length == 3)
{
switch (x[0])
{
case 1:
switch (x[1])
{
case 2:
{
FSharpOption fSharpOption = Program.|Partial3|_|(x[2]);
if (fSharpOption != null && fSharpOption.Value)
{
return Program.MyType.C;
}
break;
}
break;
}
break;
}
}
throw new MatchFailureException(...);
结论：部分活跃模式编译成FSharpOption。编译器无法检查部分活跃模式的完整性/重复性。
在F#中，定义了两个类型MyOne和MyAnother，以及一个模式匹配函数test7a和test7b：
type MyOne =
| AA
| BB of int
| CC
type MyAnother =
| AAA
| BBB of int
| CCC
| DDD
let test7a x =
match x with
| AA -> 2
let test7b x =
match x with
| AAA -> 2
反编译后的C#代码如下：
public static int test7a(Program.MyOne x)
{
if (x is Program.MyOne._AA)
{
return 2;
}
throw new MatchFailureException(...);
}
public static int test7b(Program.MyAnother x)
{
if (x.Tag == 0)
{
return 2;
}
throw new MatchFailureException(...);
}