模式匹配和C++的模板特殊化

既然买了，就看看呗！在序数一章讲到了自然数的定义，以及集合模型，作者说序数是公理集合论的精华。这点我不反对，毕竟，无论这种构造是不是数的本质，这种认识方法都是很有启发性的，关于自然数，它是这样说的：

- 一个自然数是一个集合，记为X；
- 如果集合X是一个自然数，那么它的后继集合X union {X}，记为X+，也是一个自然数；
- 空集{}，记为0，是一个自然数；
- 所有自然数都是这样产生的。

学过离散数学的人大概知道这种自然数的公理化定义。根据这几条，可以看到自然数是怎么一个样子的：

一个东西长的是什么样子就叫做这个东西的模式pattern，其实pattern就是长什么样子的意思。这里我们可以用粗样子和细样子来描述样子，看看我们对这个东西关心到什么程度了。

比如最粗的，一个自然数是一样东西 _ ：（这里我们用下划线表示一个东西，而不管它是什么，下划线被称为通佩符wildcard，代表什么东西都行）我们除了知道这个数是一个而不是两个或三个东西之外什么也没说；

稍微细一点，一个自然数是一个集合{ _ }：除了“一个”以外，我们还说明了一个自然数是一些不知道是什么玩艺的集合，如果我们只关心这个的话，比如有一个函数它需要随便一个集合作为参数的话，这就够了；

更细一点，一个自然数“3”是一个包含3个元素的集合{_, _, _}：我们又多说了一点。

这里，“_”，“{ _ }”和“{_, _, _}”都是pattern，它们也许表示了同一样东西，但是在不同的细节上。除了作为wildcard的下划线以外，其它的符号都表达了一个东西（自然数“3”）的样子的具体的某些构造，比如上面的“{}”和“, ,”。这些符号叫做构造子constructor，我们的数据（自然数或东西或对象）都是由这些构造子的组合完全表达的，构造子可能带有参数，上面的“{}”和“, ,”都是这样的构造子，也可能没有参数，比如如果用void表示什么也没有的话，void这个构造子就没有参数，

0就可以表达为{void}或“{}”(void)；
3就可以表达为“{}”(“, ,”(_, _, _))。

如果我们的东西是一个数据，那么表达数据的构造子就称为数据构造子，表达类型的构造子就称为类型构造子。不管怎么说，pattern就是一个东西的样子，具体来说就是用什么构造子来怎样的组合。当然不是任意的构造子的组合都可以是一个合法的东西，就像上面的自然数的公理化定义一样，我们用一些规则来定义构造子和它们可能的组合，这些规定如果赋予一个名称的话就是通常所说的数据类型，那么如果东西本身不是数据而是类型呢，那么定义类型的规则就叫做，嗯！叫什么呢？元类型meta-type，或者，你知道了，也可以叫做模板template，如果用在C++里面的话。

关于pattern就是长什么样子的话题，那天我和苦难买完书回到他家里的时候碰到了搜妈妈，也有了一番讨论。可能从很久以前开始，所谓的IT业界充斥了“设计模式”的讨论。我本人不敢称作IT人，IT这个词我很不喜欢，也许和我崇拜Knuth有关，他在一篇介绍计算机科学的短文中说道：欧洲人喜欢把这门科学叫做信息技术或信息学，这好像把重点放在了计算机处理的对象上了，而他认为重点还是在计算机怎样计算上，所以叫做计算机科学。我也很同意，除了崇拜以外，还因为我自己也是一个程序员，我也觉得写程序是为了表达怎样计算那些数据。回到设计模式，我也很讨厌通过给一个已有的东西起新名字的做法来故弄玄虚，据我的理解，设计模式不过就是一个设计长什么样子。当然这个样子包括了一些语义上的描述，比如一些东西通过一个代理把消息转换一下告诉其它的一些东西，这个设计（模式）就长这个样子：

{X, Y, Z, ...} <--- data ---> P <--- data' ---> {A, B, C, ...}

维持这个样子的说实在的也就是那两个双向箭头表示传递，一个撇表示改变，剩下的那些名字除了彼此之间的区别以外毫无意义。设计模式要说的只不过是某类常见问题的解决方案画成图的话应该是一些典型的样子，这些典型的样子是通过各种渠道证明是有效的，这难道是什么新鲜玩艺吗？我们在编程序的时候不是天天在用一些典型的写法吗？不是在用一些典型的数据结构吗？如此而已，在设计里叫模式pattern，在C++的某些书里叫惯用方法idiom（这个词我怎么看怎么觉得它蠢，也许我的英语不灵光，也许因为我的母语是象形文字），还不是一回事。

苦难、我和搜妈妈就什么是pattern确实讨论了个热火朝天，搞得苦难的夫人很是捏了一把汗，生怕我们打起来以后苦难会吃亏。最后问题好像是清楚了，至少也是各怀鬼胎的得到了只属于自己的观点。这种讨论我倒是很喜欢的，除了可以彼此了解增进友谊外，听听别人的想法总归是好的。

回到刚才所说的自然数pattern，这给我们一个感觉，既然最基本的类型自然数都可以用所谓的数据构造子pattern来描述，那么是不是所有数据的基本表达方法就是一个pattern呢？是的，这也是我要说的主题。与上面的集合pattern稍有不同，在计算机里面表达集合这种不区分元素顺序，只看它们之间区别的数据不太容易，反而以元组product形式表达多个东西的组合比较容易，这里元组中各元素的位置是有关的，下面的讨论要基于这一点，读者应该不难理解。

为了利用计算机的硬件，像自然数这样的数据就不会在拆成更为详细的pattern了，否则处理起来太慢，每个自然数都可以被语言的编译器看成是一个不带参数的数据构造子，比如“0”，“1”，“2”等等，它们仍旧是pattern，只不过这样一来预定义的构造子比较多一点而已。我们主要看看复杂一点的pattern，上面说过一个数据类型是一个定义了有关构造子和构造子怎样合法组合的规则，比如一个连接表的数据类型在sml（一种函数式设计语言）里面是这样定义的：

前面带有“'”的字母表达了一个类型的参数，'a LinkList说的是一个元素类型为'a的连接表。它是这样的，或者是Nil，这是一个连接表构造子，没有参数，构造了一个空连接表；或者是一个Cons，Cons是一个带有元组参数的构造子，这个元组的第一项是一个类型为'a的数据，后面一项是一个类型为'a LinkList的连接表，这是一个递归的类型定义。这样一来，连接表的数据就是下面样子的一些pattern：

但不能是

因为如果'a的类型是1的类型 = 整数的话，就不能再是字符串了。上面那些合法的pattern有一个普遍的样子，要么是Nil，要么是Cons(_, _)，不能再长成其它样子了。

我们知道，编程序的时候判断语句几乎是最基本的控制结构了，没有它似乎编不出什么太有用的东西。在大多数支持构造子的语言里，pattern matching是一种有效，整洁，表达力十分强劲的判断结构，它是通过比较数据的pattern也就是长的样子来进行分情处理，可以说它是这些语言的第一类控制结构。比如我们要计算上面定义的连接表的长度：

fun是一个关键字，它定义一个函数，这里叫做“Length”，Length接受一个连接表作为参数，它根据连接表长的两个样子分情处理，如果连接表长成Nil，那么它的长度是0，或者如果它长成Cons(_, tail)，就先计算后面那个连接表tail的长度然后加1。这里的tail由于不是上下文中的一个构造子，它就是一个自由变量，自由变量出现在哪里就被绑定bind到哪里（值得注意的是，一旦它被第一次绑定到一个东西上去以后，在它的作用范围内就一直代表那个东西，而不再是自由的了），现在它被绑定到Cons构造子的参数元组的第二个元素，也就是连接表的尾部（除去第一个元素剩下的部分）。tail会被继续分解成细一点pattern来和Nil或Cons进行比较，看看它长的像谁，这样连接表就被递归的分解到不能再分解的pattern为止，也就是当tail = Nil的时候，长度就在回程被一点点加出来了。

我的天（靠！），这样是不是笨了点，这么简单还要递归呀！我开始说了，递归是最简单的表达方法，也是最自然的，虽然笨了点，但是意思清楚以后，我们可以再优化它嘛！优化不是我要说的重点，这里只是顺便提一下，省得有人挑骨头。这个东西可以有一种典型的优化方法（design pattern或idiom随你喜欢），就是加一个累加器：

然后通过调用Length(list, 0)来计算长度。这还是递归呀！没错，但是这是一个尾递归，也就是递归调用的Length是最后一个函数调用（前面的写法调用完Length以后还要调用加法加1，所以不是尾递归），尾递归可以直接的goto实现，也就等价的我们通常的循环求长度的写法。几乎所有哪怕是弱智的函数式语言编译器都可以很简单的看到尾递归而将它优化成goto。

pattern matching是一种非常简洁的表达方式，许多时候我们会关心比较详细的数据的样子，这时就更为有用，比如我们要看看一个连接表有没有3个以上的元素，一般的做法我们要先看看连接表是不是空啊？哦，不是，那么后面有没有元素呀？啊，还有，那么再后面还有没有呀？…。有了pattern matching我们可以要关心到哪层就把pattern写到哪层：

如果长成第一个样子就返回是，其它的返回否（pattern matching在sml里面是依次进行的）。这是多么简单明白，如果说程序是一种交流方式的话，简单明白不是很重要吗？我们可以想象一下在处理复杂的数据结构的时候pattern matching是多么有用，比如处理树的插入删除等等，我们可以直接说，如果树长成Nil，那么插入完x以后就长成Branch(x, Nil, Nil)，如果长成Branch(a, Branch(b, c, d), Nil)，插入完x以后就长成Branch(a, Branch(b, c, d), Branch(x, Nil, Nil))等等，用这种方法写平衡一个红黑树的算法只要大约5，6行，而且很清楚，只不过是把所有要处理的样子列出来而已。

习惯了pattern matching的概念以后再来看看C++的模板特殊化就很容易明白了，模板定义只不过是函数的原型，特殊化的模板定义就是根据不同的参数pattern来分情处理，每个作为模板参数的类型都是一个不带参数的构造子，模板本身可以用作代参数的构造子，C++编译器相当于函数的运行器，在编译的时候进行pattern matching，只不过C++不是根据特殊化模板的定义顺序来匹配模式，而是寻找最好的匹配。原来C++编译器可能不是为了进行很复杂的类型推导用的，但是最近的C++设计潮流和惯用方法倾向于利用这种简单的pattern matching来干很复杂的类型计算以便适应通用generic编程思想的需要。在类型计算时，语言并没有提供判断语句来比较类型是否一致，我们有的只是pattern matching。

在Modern C++ Design这本书里讲述了一种类型列表的模板结构，它允许我们把一些已知的类型组成一个表，可以在这个表里搜索一个类型并返回它在表里面的位置。这个很好用，我们利用这个位置可以显示一个类型的名字，安排一个我们希望的id给它，甚至是调用某个特殊的处理函数。用类型列表来说明pattern matching再好也不过了。

这几乎和刚才的连接表一模一样。我们的类型表可以类似的定义：

那么，如果想知道string在这个表里的什么位置（Index_of）应该怎么做呢？记住我们只有pattern matching可以用。首先定义一个原型：

接着阐述一些事实（和递归的结束的情形一样）：

也就是一个类型在空类型表里的位置是-1。接下来和计算表的长度一样进行迭代：

呵呵，非常简单。用起来就是这样：

我们来看看pattern matching是怎样进行的（由于下划线是C++里可以用作标识符，以下部分就用“?”来表示通配符）：

首先把<string, my_list>和<T, Nil>比较，当然由于string已经是一个类型（就是一个构造子，一个简单的pattern）所以没有更细的pattern可分，至于my_list则需要至少分解出一个构造子来和Nil进行比较，所以my_list = Cons<?, ?>，这就足以淘汰<T, Nil>了；

其次，和<T, Cons<T, Tail>>比较，这时T会首先绑定到string上，因为它是一个自由参数（注意看特例里面的参数表，不是特例上面的template<>参数表，template参数表只是声明一下特例的参数表里有几个是自由参数），然后Cons<?, ?>和Cons<string, Tail>对上号了，因为它们有同样的构造子，由于需要进一步的比较pattern，所以my_list会被进一步细化成Cons<int, ?>，和Cons<string, Tail>不一样，因为int和string是不同的构造子；

那只剩下最后一个pattern了，这个pattern多了一个Head自由参数，正好绑定到int上，所以<string, Cons<int, Cons<string,?>>>就被匹配到<T, Cons<Head, Tail>>上，因为所有的非自由构造子都相同，而自由参数就被绑定到相应的pattern上（T=string；Head=int；Tail=Cons<string, ?>）以备进一步的计算；

根据这个pattern的定义，编译器会进一步搜索Index_of<string, Tail>，也就是Index_of<string, Cons<string, ?>>，这个pattern显然匹配Index_of<T, Cons<T, Tail>>和Index_of<T, Cons<Head, Tail>>，但是它和前者匹配得更精确一些，C++会选择前者而定义相应的Pos值为0，这个Pos值在pattern matching的回程被累加，就得到了相应的位置。

pattern matching是很有力的表达工具，它比判断语句来得更为直观，在C++之前已经广泛的使用在形式方法和函数式设计语言中了。使用这种技术，C++很好的（虽然是很难看的）利用模板的部分特殊化partial specialization进行了有效的类型计算，使得构造通用的模板库更为容易了。对了，顺便说一下，有些老的C++编译器并不支持模板的部分特殊化，如果你想试验这些代码的话可以使用gcc，我相信以EDG作为前端的C++编译器是可以的，比如KAI，Intel等。

去年我看到一篇论述表达式模板expession template的文章，作为pattern matching的进一步应用，这又是一个好例子，有兴趣的不妨去看一看。表达式模板已经成为科学计算库Bliz++的一部分了。

我这次去北京和苦难花了不少时间打台球，这与我要跟他做的技术讨论没什么关系了，不过这两件事都是我们喜欢的，而且一起干比单干要有意思一些。关于设计模式和本文其实也没什么关系，但是也有一点是相同的，那就是我们在什么时候需要以什么细化程度来观察一个模式，这往往就是解决问题的关键所在了。