View CPP Template

發表於   |   分類於

写在前面

写文一向是一件我不太拿手的事情，大多数时候单是起头就能让我大半天没法下笔：比如这次，大概十多分钟才写了这么两句。

决定写文的原因很简单：看到简历之后别人几乎都会问那么一句：“有没有上传到Github上去？”。经历了几次阵痛之后我终于觉得这应该是个比较重要的问题了：毕竟跟有Git加持的人相比，在话题主导方面我显然不占优势，况且我也不是个会聊天的人。于是乎，在注册了Git一年之后我终于下决心要在上面PO文章交代码了。

至于为什么用这样一篇分析报告这个作为第一篇博文，应该出于：选一个稍微高上一点的，自己多少能看懂的。另外，毕竟CPP用惯了，更亲近一些。

正文

本文的主线是一篇Matt教授的文章。Matt教授的这篇文章主要讲述了C++模板的图灵完备性（Turing-completeness），并以用模板构建了一个“高阶函数式编程语言”来证明之。之所以在Matt教授主页上面的C++文章中选择这样的一篇文章，一方面是因为我个人为这是搞懂C++模板，进而踏入C++泛型编程领域的关键所在；另一方面是也因为这篇文章涉及到的代码量只有200行左右，不至于使得读者过于专注代码细节而影响对整体思想的理解，并且这也是一篇代码分析报告所能承受的量。

当然本人水平有限，文中不免有错误之处，希望有心的读者来邮件（solaxu@outlook.com）批评指正。

模板特化

模板和模板特化赋予了C++模板图灵完备性，这使得C++模板能够像无类型的term-rewriting语言（例如ML、Lisp）一样工作。下面是一个模板和它特化的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// ListNode模板类
template <typename A>
struct ListNode
{
  A data;
  ListNode<A>* next;
};

// ListNode模板类的一个特殊化形式，注意该形式实现了对ListNode<uinsigned int>类型的屏蔽
template <>
struct ListNode<unsigned int>
{
  int data;
  ListNode<int>* next;
};

对于模板实例化这里就不再赘述，我们只看上面模板特化部分的代码：当我们的客户端程序在使用ListNode希望实现一个数据类型为uinsigned int类型的ListNode的时候，它将会被实际实例化为一个数据类型为int的ListNode，这样就实现了对ListNode类型的屏蔽。

一个求阶乘的例子

这个例子几乎出现在任意一本讲述C++模板编程的的书籍中：

1
2
3
4
5
6
7
8
9
10
11
template <int N>
struct Factorial
{
  enum {value = N * Factorial<N-1>::value};
};

template <>
struct Factorial<0>
{
  enum {value = 1};
};

假定我们需要求Factorial<3>，已知结果为123=6，那么上面代码的工作方式可以表示如下（编译期工作）：

1
2
3
4
5
6
7
Factorial<3>
{
  value = 3 * (Factorial<2>)
        = 3 * ( 2 * (Factorial<1>) )
        = 3 * ( 2 * ( 1 * (Factorial<0>) ) )
        = 3 * ( 2 * ( 1 * (1) ) )
}

在上面的代码中，每次对 Factorial<N> 的递归都先将N“压入” Factorial<N-1>的 “工作环境”之中，这个过程并没有计算（如果对Closure比较熟悉的话这应该不是一个难以理解的点）。也就是说，Factorial<N>每次计算都生成了一个“闭包”，该闭包接收一个参数N-1，直到N=0时，遇到特化模板Factorial<0>结束。最终Factorial<3>的展开式为3 * 2 * 1 * 1，这就可由编译器的常数优化来进行直接求结果了。

数据结构与类型匹配

这个小节的标题原文是“Encoding and pattern-matching data structures”，但是译作“编码与模式匹配数据结构”这个怎么感觉都不对味，所以做主张调整了标题。本小节建议诸位读者大人打开原文，与本文两厢对比来看。

在C++元编程中，“类型”（types）被作为数据结构的代指，而“特化”则用来“在某种程度上破坏”这种代指（参见第一小节对unsigned int的屏蔽）。请看下面代码：

1
2
3
4
5
6
7
8
9
10
struct Zero
{
  enum {value = 0};
};

template <typename N>
struct Succ
{
  enum {value = N::value + 1};
}

有了第二小节的铺垫，上面代码不难理解。在上述代码中，使用类型Zero来代指自然数0，类型Succ<N>来表示自然数N后面的一个数。这里需要注意的一点是：类模板其实是一个“类型运算函数”，它接收一个或者多个类型（也就是模板参数），最后得到一个新的类型。于是自然数1可以表示为Succ<Zero>，自然数2可以表示为Succ< Succ<Zero> >…依次类推就可以表示所有的自然数了。

1
2
3
4
5
6
7
8
9
10
11
template <typename N>
struct MatchOne
{
  enum{value = 0};
}

template <>
struct MatchOne<Succ<Zero> >
{
  enum{value = 1};
}

上面的代码可以这样工作：

1
2
3
cout << MatchOne<Zero>::value << endl; //prints 0
cout << MatchOne<Succ<Zero> >::value <<endl; // prints 1
cout << MatchOne<Succ<Succ<Zero> > >::value << endl; // prints 0

打印结果使用模板特化的知识很容易理解：只有特定类型才能产生特定的输出，这里是1；其他类型都产出0。

C++模板的图灵完备性

前面铺垫了许久，终于到了重头戏。
众所周知，λ演算是图灵完备的，那么C++的模板只需要能够支持完整的λ演算，就可以证明它的图灵完备性了，该小节将会通过200行左右的代码来展示模板的这种特性，Matt教授的代码可以在这里下载到。

接下来的代码中Environment可以认为是一个“运行环境”，这里的“运行环境” 不同于 经常提到的“程序的运行环境”。这里特指“一小段代码”（例如一个Closure），可以回顾一下前面提到的Factorial的“运行环境”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

struct EmptyEnv;

template <int Name, typename Value, typename Env>
struct Binding{};

// EnvLookup 的工作方式与前面的 Factorial类似
template <int Name, typename Env>
struct EnvLookup{};

template <int Name>
struct EnvLookup<Name,EmptyEnv>{};// Name Not found, 特化以终止递归

// 针对Binding类型特化
template <int Name, typename Value, typename Env>
struct EnvLookup <Name, Binding<Name,Value,Env> >
{
  Value typedef result;
};

template <int Name, int Name2, typename Value2, typename Env>
struct EnvLookup <Name, Binding<Name2,Value2,Env> >
{
  typename EnvLookup<Name,Env> :: result typedef result;
} ;

我们先来看看main函数里面对EnvLookup的使用：

1
2
3
4
5
6
7
8
// Testing [2 => 1, 3 => 0](3):
 int v = EnvLookup<3, Binding<2,
                              Succ<Zero>,
                              Binding<3, Zero,EmptyEnv>
                              >
                  > :: result :: value ;

 assert(v == 0) ;

首先从Binding入手。
Binding的作用是：在一个Environment中，把一个Value绑定到一个Name上。那么前面的代码首先把一个Zero绑定到名字为3的引用上，而这个引用位于环境EmptyEnv中，于是在进行了Binding操作之后，我们得到了一个新的Environment，假设我们对其命名为EmptyEnvWith3=0，接下来我们再把Succ<Zero>这个值再绑定到EmptyEnvWith3=0中的名字为2的引用上。这个过程可以表述如图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
EmptyEnv：
+--------------------+
| ref 1 = Null       |
| ref 2 = Null       |
| ref 3 = Null       |
|      ...           |
| ref 4 = 3 + 2      |
|      ...           |
+--------------------+
这里的EmptyEnv只是名字如此，并不意味着它就一定是一个“空”的，另外这些值为 Null 的引用代表着它们没有相对应的值，只“占位”而已。
而且这里的Environment虽然看起来似乎是一个结构体，但是实际上并不是，可以在某种程度上认为它是一段代码。
（可以查找一下Continuation的相关信息帮助理解，它与Closure是近亲）。

经过第一次 Binding 操作之后：
EmptyEnv：（在上面我们给他另外起名为 "EmptyEnvWith3=0" 实际上还是 EmptyEnv，临时变量，右值而已）
+--------------------+
| ref 1 = Null       |
| ref 2 = Null       |
| ref 3 = Zero       |
|      ...           |
| ref 4 = 3 + 2      |
|      ...           |
+--------------------+

经过第二次 Binding 操作之后：
EmptyEnv：
+--------------------+
| ref 1 = Null       |
| ref 2 = Succ<Zero> |
| ref 3 = Zero       |
|      ...           |
| ref 4 = 3 + 2      |
|      ...           |
+--------------------+

于是最后轮到EnvLookup出手了：它使用与前面求Factorial一样的过程来求出两次Binding操作之后EmptyEnv对应名字的result，然后通过这个result来获取到具体的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// Core syntax
template <int FormalName, typename Body>
struct Lambda{};

template <typename Fun, typename Arg>
struct App{};

template <int Name>
struct Ref{};

// Sugar:
template <typename Cond, typename Then, typename Else>
struct If{};

template <typename T>
struct Lit{};

// Values
template <typename Lam, typename Env>
struct Closure {} ;

struct True {} ;
struct False {} ;

// Eval procs
template <typename Exp, typename Env>
struct Eval {} ;

template <typename Proc, typename Value>
struct Apply {} ;

template <typename T, typename Env>
struct Eval <Lit<T>, Env>
{
  T typedef result ;
} ;

template <int Name, typename Env>
struct Eval <Ref<Name>, Env>
{
  typename EnvLookup<Name, Env> :: result typedef result ;
} ;

template <int Name, typename Body, typename Env>
struct Eval <Lambda<Name,Body>, Env>
{
  Closure<Lambda<Name, Body>, Env> typedef result ;
} ;

template <typename Fun, typename Arg, typename Env>
struct Eval<App<Fun, Arg> , Env> {
  typename Apply<typename Eval<Fun,Env> :: result ,
                 typename Eval<Arg,Env> :: result > :: result
           typedef result ;
} ;

template <typename Then, typename Else, typename Env>
struct Eval<If<True,Then,Else>,Env> {
  typename Eval<Then,Env> :: result typedef result ;
} ;

template <typename Cond, typename Then, typename Else, typename Env>
struct Eval<If<Cond,Then,Else>,Env> {
  typename Eval<If<typename Eval<Cond,Env> :: result,
                   Then,
                   Else>,
                Env> :: result
           typedef result ;
} ;

template <int Name, typename Body, typename Env, typename Value>
struct Apply<Closure<Lambda<Name,Body>, Env>, Value> {
  typename Eval<Body, Binding<Name,Value,Env> > :: result
           typedef result ;
} ;

好长一段代码……
还是先看看main中是怎么使用的吧：

1
2
3
4
5
6
7
8
9
10
11
12
// Testing ((lambda (x) x) 2):
enum { X } ;
int x = Eval  <
                  App <
                        Lambda<X,Ref<X> >,
                        Lit <
                              Succ < Succ<Zero> >  // ===> 2
                            >
                      >,
                  EmptyEnv
              > :: result :: value ;
assert(x == 2) ;

首先把代码中的Succ <Succ <Zero> >简化为2。
然后是Lambda<Name,Body>，相当于一个这样的表达：

1
2
lambda x :
  return x

于是这里的App<Lambda,Lit>实际上就是上面第49行代码中的App<Fun, Arg>，其作用是：将参数Arg应用到一个方法Fun中，最后得到依旧是一个方法（这一点需要特别注意，这个方法并没有直接得到结果，而是形成了一个闭包被返回了）。
那么Eval<App,EmptyEnv>就成了：将上面得到的闭包放置在EmptyEnv这个“环境”之中进行求值从而得到结果。至于为什么会得到2，请自行按照模板展开的方式一层一层剥离下去就可以了，注意模板特化带来的影响，这里不再赘述。

再来看main中的另外一段代码：

1
2
3
4
5
6
7
8
9
10
// Testing (if #f 0 1):
int y = Eval  <
                  If  <
                        Lit<False>,
                        Lit<Zero>,
                        Lit<Succ<Zero> >
                      >,
                      EmptyEnv
              > :: result :: value ;
assert(y == 1) ;

通过前面的分析，我们可以很容易的就知道这段代码的目的了：把If放置在EmptyEnv中执行一次，结果是Succ<Zero>，也就是1。

结语

Matt教授的文章跟代码分析完了，通过分析我们可以看到C++模板是图灵完备的，这使得C++模板元编程成为了可能。
在文章的结束部分，Matt教授给出了一个Exercise，这个Exercise需要我们自己在给出的框架上填写一段代码来实现自然数的加法，其实就是把两个代表不同数的Succ合并起来成为一个Succ，然后传递给Eval：

1
2
3
4
5
6
7
8
9
10
// 模板特化Add，感觉有点不太对劲……虽然Pass了
template <>
struct Add
<
  Succ<Succ<Zero> >,
  Succ<Succ<Succ<Zero> > >
>
{
  Succ<Succ<Succ<Succ<Succ<Zero> > > > > typedef result;
};