其实我在写这个系列的第三篇文章的时候就已经发现，距离机器越远，也就是抽象越高的概念，坑的数量是越少的。但是这并不是说，距离机器越近的概念就越强大或者说越接近本质。这是广大的程序员对计算理论的一种误解。大多数人理解编程的知识结构的时候，都是用还原论来理解的，这个方法其实并没有错。但问题在于，“还原”的方法并不是唯一的。很多人觉得，反正你多高级的语言编译完了无非都是机器码嘛。但是还有另一种解释，你无论多低级的语言编译完了无非也就是带CPS变换（continuation passing style）的λ-calculus程序嘛。他们是等价的，不仅能力上也是，“本质”上也是。

一个用CPS变换完整地处理过的λ-calculus程序长的就很像一串指令。而且类似于C++的inline操作，在这里是完全自然、安全、容易做的。那其实为什么我们的机器不发明成这样子呢？显然这完全跟我们想如何写一个程序是没关系的。正是这种冲突让我们有一种“概念距离机器越远运行速度就越慢”的错误的直觉。扯远了讲，就算你在用一门函数式语言，譬如说Haskell也好，F#也好，最终在运行的时候，还是在运行彻底编译出来的机器码。这些语言是完全不需要“模拟器”的，虽然由于各种历史原因人们首先开发了模拟器。当然一个精心设计过的C程序肯定还是要比haskell快的，但是我觉得能这么干的人不多，而且大多数时候这么干都是在浪费老板的钱而已，因为你们的程序原本就不需要快到那种份上。这种东西就跟那些做互联网对于测试的想法是一样的——有bug？发现了再说，先release抢市场。

如果对这方面有了解的话，CPS变换——也就是Lost In Stupid Parentheses-er们最喜欢的call-with-current-continuation，他的另一个名字叫call/cc——是一种跟goto一样强大而且基本的控制流的做法。goto和CPS可以互相转换不说了，所有其它控制流都可以转换成goto和CPS。它们两者在这方面是不相上下的。而且既然一个完全用CPS变换处理过的程序长得就像一串指令，那你说他们的区别是什么呢？区别就是，CPS可以是强类型的，而goto则永远都不可能。

作为废话的最后一段，我给个小例子来讲什么叫“一个用CPS变换完整地处理过的λ-calculus程序长的就很像一串指令”。就让我们用a(b( x ), c( x ))这样的一个表达式来讲：
处理前：

a (b x) (c x)

处理后：

b x λa0.
a a0 λa1.
c x λa2.
a1 a2

用我们熟悉到不能再熟悉的Haskell的Monad的手法来翻译一下其实就是：

a0 <- b(x)
a1 <- a(a0)
a2 <- c(x)
return (a1(a2))

好了，至于上面这种形式（看起来很像SSA）是怎么被做成机器码的，大家自己去看编译原理吧。上面这么多废话就是想表达一个结论：抽象并不意味着负担。当然，至于对程序员的智商上的要求，对某些人也是一种负担，这个我就没办法了，所以就不考虑他了。

===============废话结束================

模板也是这类抽象的一种。为什么我要把标题写成“坑”，只是想跟前面统一一下而已，其实到了模板这么高级的抽象的时候，基本上已经没什么坑了。当然C++的做法就另当别论了，而且我想那些坑你们大概一辈子也碰不到的了。那我们先从简单的讲起。

比模板更简单的东西自然就是泛型了。为什么叫他泛型？因为泛型实际上就是一种复制代码的方法，它本身是没有推导能力的，所以肯定谈不上什么模板了。但是在大多数情况下，泛型这么弱的抽象也已经基本够用了。跟泛型相关的手法大约有三个。

第一个就是定义一个返回一个类的函数（在这里参数是T）：

class Array<T>
{
    public Array(int count);
    public int Count{get;}
    public T this[int index]{get; set;}
}

第二个就是，调用这个函数，参数给他类型，帮我们new一个类的实例：

var xs = new Array<int>(10);

这其实有两步。第一步是对函数调用Array<int>求值得到一个T，然后对new T(10)进行求值获得一个对象。只是刚好Array<int>的返回值也叫Array<int>，所以比较混淆视听。

事情到这里还没完。上一篇文章中我们讲到，写一个类是要考虑很多contract的问题的。所以Array<T>是个什么东西呢？他至少是一个IEnumerable<T>：

interface IEnumerable<out T>
{
    // ...
}

class Array<T> : IEnumerable<T>
{
    public Array(int count);
    public int Count{get;}
    public T this[int index]{get; set;}
}

于是有一天我们构造了一个Array<Array<string>>的对象，然后要写一个函数来处理他。这个函数做的事情很简单，就是把这个二维的数组给平摊成一个一维的数组，里面所有的数组头尾相接起来。于是根据上一篇文章的内容，我们写一个接受class的函数，也是要想很多contract的问题的（面向对象就是麻烦啊）。这个函数需要的只是遍历的功能，那我们完全没有必要要求他必须是一个Array，于是我们的函数就这么写：

IEnumerable<T> Flatten<T>(IEnumerable<IEnumerable<T>> xss)
{
    foreach(var xs in xss)
        foreach(var x in xs)
            yield return x;
}

或者你也可以用高级一点的写法，反正是一样的：

IEnumerable<T> Flatten<T>(IEnumerable<IEnumerable<T>> xss)
{
    return xss.Aggregate(new T[], Enumerable.Concat);
}

有CPS变换就是好呀，没有CPS变换的语言都写不出yield return和async await的。但是你们这些搞前端的人，特别是做nodejs的也是，都是教条主义的，觉得eval是evil，硬是把老赵的windjs（曾用名：jscex）给拒了。亏js还是一个特别适合写callback的语言呢，结果没有$await，你们只能把一个好好的程序写成一支火箭了。

那现在问题来了。当我们想把Array<Array<string>>传给Flatten的时候，我们发现Flatten的参数需要的是IEnumerable<IEnumerable<string>>，究竟二维的数组能不能转成二维的迭代器呢？

C++嘛，因为它没有C#的协变和逆变的功能，所以是做不到的了。幸好我们这里用的是C# 4.0。那C#究竟是怎么做的呢？

其实从Array<Array<string>>到IEnumerable<IEnumerable<string>>需要两步。第一步因为Array继承自IEnumerable，所以类型变成了IEnumerable<Array<string>>。第二部就是最重要的步骤了，因为IEnumerable<out T>的T有一个out，这就说明，IEnumerable里面所有的T都是用在函数的返回值上的，他只生产T，不会消耗T。所以一个IEnumerable<子类型>就可以转变成IEnumerable<父类型>，因为子类型总是可以转变成父类型的。因此最后IEnumerable<Array<string>>就变成了IEnumerable<IEnumerable<string>>了。

所以现在我们回过头来看上面提到的泛型的三个手法
1、定义一个输入类型输出类型的函数（class Array<T>）
2、调用这个函数来得到你想要的类型（new Array<int>()）
3、协变和逆变（(IEnumerable<IEnumerable<string>>)new Array<Array<string>>()）

所以说白了泛型就是一个对类型进行操作的东西。当然它的内涵远远没有模板那么丰富，但是既然讨论到了对类型的操作，我觉得我要稍微普及一下一个类型系统的常识——父类型和子类型。

父类型和子类型说的是什么，如果我们有两个类型，一个T，一个U。如果一个U的值，总是可以被看成一个T的值的话，那么我们就说U是T的子类型。我们也可以说，U是T的子集。这里我要说一下为什么正方形是一个长方形但是我们却不能让正方形继承自长方形呢？因为这个“是一个”只在只读的时候成立。考虑了写，正方形就不是子类型了。

除了类的继承，协变逆变以外，还有另一种父类型和子类型的关系——那就是模板类型了。举个例子，我有一个函数是这么写的：T Do<T>(T t)。这是一个输入T输出T的模板函数。那我们有一天需要一个输入int输出int的函数怎么办呢？Do<int>就好了。反过来行不行呢？不行。所以delegate T F<T>(T t)就是delegate int F(int t)的子类型。

当然，上面这个例子千万不能和函数的协变逆变混起来了。只有模板才能这么做，delegate string(string)肯定变不了delegate object(object)的。只有delegate string(object)可以通过协变+逆变同时作用变成delegate object(string)。因为object和string是继承的关系，不是模板的关系。

泛型到这里基本上就说完了，轮到模板了。C#的泛型产生的类可以是静态类，其实C++就更可以了，而且C++还有偏特化这种必不可缺的东西。那偏特化有什么用呢？这跟上一篇文章将面向对象的时候一样，其中的一个很大的用处就是拿来做contract。

interface和template（其实是concept mapping）拿来做contract的区别，在于你选择一个具有contract的类型的实现的时候，是在运行时做的，还是在编译时做的。其实有很多时候我们并不想，有时候也不能入侵式地给一个类随便添加一个新功能。我们知道，功能就是contract，contract要么是interface，要么是template。interface并不是总是可以加上去的，譬如说对那些不能修改的类，就像string啊int什么的。而且我们也不会拿string和int做多态。这种时候我们就需要concept mapping了，然后靠类型推导去选择正确的实现。在C++里面，就是用template+偏特化来做了。

上面这段话说得好像很抽象（一点都不抽象！），我们还是用一个生动的例子来做吧。譬如说我们要做序列化和反序列化。首先我们可以让若干个类型支持序列化的功能。其次，只要T支持序列化，那么vector<T>啊、list<T>什么的也将自动支持序列化的功能。这是一个递归的描述，所以用template来做刚刚好。但是像vector和list这种不能修改的类，或者int这种原生的类型，我们要怎么支持序列化呢？不能修改类，那只能写在类的外面，变成一个函数了。那对于vector<T>来说，他怎么知道T的序列化函数是什么呢？相信熟悉模板的读者肯定知道正确的答案是什么了。

首先我们要做一个空类叫Serializable<T>，其次不断地偏特化他们，覆盖所有我们需要的类型：

template<typename T>
struct Serializable
{
};

template<>
struct Serializable<int>
{
    static int Read(istream& i);
    static void Write(ostream& o, int v);
};

template<>
struct Serializable<wstring>
{
    static wstring Read(istream& i);
    static void Write(ostream& o, const wstring& v);
};

template<typename T>
struct Serializable<vector<T>>
{
    static vector<T> Read(istream& i);  // 我们已经有右值引用构造函数了，不怕！
    static void Write(ostream& o, const vector<T>& v);
};

这里需要提到的一点是，当我们使用Serializable<vector<T>>的时候，我们首先要保证T也是Serializable的。可惜的是C++并不能让我们很好地表达这一点，本来C++0x是有个concept mapping的标准，不过后来被干掉了，我觉得永远都不会有这个东西了。但其实这并不是什么太大的事情，因为只要你写错了，那总是会有编译错误的。

不过go语言在这一点上就不一样了，go没有模板什么像样的代码都写不出就不说了，就算他有模板，然后同时具有Read和Write的类型都实现了go的一个叫做Serializable的interface的话，结果又如何呢？其实这相当于把Serializable<T>::Read(i)和Serializable<T>::Write(o, v)都改成Read(i, &v)和Write(o, v)。这样的问题老赵已经在他的博客讲过了，万一Read和Write不是你写的，功能跟你要的不一样，只是碰巧有了这两个函数怎么办，你还能救吗？你已经不能救了，因为名字都用过了，你想显式地实现一个interface的话go又没这个功能，于是程序就到此傻逼了，Read和Write改名吧，祝你不是项目快写完了才发现这个问题。

关于编译错误，我觉得有一个事情是很值得说的。为什么熟悉Haskell都觉得Haskell的程序只要经过了编译基本上运行就靠谱了？其实并不是Haskell的程序真的免去了调试的这一步，而是因为这门语言经过了精心的设计，把本来在运行时才检查的事情给转到了编译时。当然这有一个不好的地方，就是我们用C语言来写一个程序的时候，虽然因为C语言抽象能力太差被迫写的很糟糕，但是我们总可以运行一点改一点，最终让他可以执行。Haskell就不一样了，只有能编译和不能编译两种状态，你要不断的修改程序，让他可以编译。一旦可以编译，一般就好了。Haskell的这种特性需要淡定的程序员才能使用。

为什么呢，因为Haskell是没有语句的，所以只要你修改了函数让他做了不一样的事情，那么函数的类型就会发生变化。那么所有依赖到这个函数的函数的类型也会发生变化。如果你改错了，那类型检查就会过不去，然后你的程序就不能编译了。Erik Meijer菊苣说得好，函数的类型才是表达函数业务逻辑的地方。而之所以要函数体，那是因为编译器不够聪明，得让你告诉他满足这个类型的最简单的解是什么。

所以如果我们在C++也采用这种写法的话——其实也就是把逻辑都交给template+偏特化，或者继承+visitor来做，那么也会有一样的效果，虽然并没有Haskell那么严格。一旦你进行了本质上的逻辑的变动，那你的类型一定会受到影响，那不满足类型要求的地方编译器就会帮你找出来。所以，当你看到一个因为这种情况而产生的编译错误的时候，心理要想：“好棒，编译器又给我找出了一个错误，避免我在运行的时候才苦逼的调试它！”

当然，模板的这些手法，可以很轻易地用在continuation passing style变换啊、combinator（很像设计模式但其实不是的东西）啊、async啊actor等各种强类型的物体上面，不过这些东西我今天就不打算细说了。当我们在做类似的事情的时候，我们要把类型设计成能表达业务逻辑的那种形式，从而让编译器查更多的东西，把运行时错误尽量化简为编译错误。

当然，C++的template比concept mapping还要更牛逼一个等级的，就是可以做type traits。如果是concept mapping是在对值通过类型进行分类采用不同的计算方法的话，那么type traits就是用来直接对类型进行计算的。那什么是对类型进行计算呢？我来举个例子。

譬如说我们要对一个vector进行排序，但是这个时候我们不像std::sort一样直接给出一个比较函数，而是通过从T拿出一个U当key的方法来做。譬如说对Student类排序，我们可以用他的学号、成绩、姓名等等任何一个属性来排序，这还是一个相当有用的作法。当然，我们总是可以写一个lambda表达式来做出一个用某个属性来比较Student类的函数，然后让std::sort来解决。很可惜的是，现在team的编译器还不够新，不支持C++11，怎么办呢？于是我们决定撸一个自己的sort函数（虽然这种事情是不推荐的，但反正是个例子，就不纠结这个了）：

template<typename T, typename U>
void Sort(vector<T>& ts, U(*key)(T))
{
    for(int i=0;i<ts.size()-1;i++)
        for(int j=ts.size()-1;j>i;j--)
            if(key(ts[j-1]) > key(ts[j]))
                swap(ts[j-1], ts[j]);
}

这段冒泡排序看起来没什么问题对吧，无论用什么语言最后写出来都肯定是这个样子的。于是我们写了几个单元测试，譬如说用sin来对double排序啦，求个负数实现逆序啦等等，觉得都没问题。于是开始投入实战了！我们写了下面的代码：

int GetScore(const Student& st)
{
    return st.score;
}

vector<Student> students;
....
Sort(students, &GetScore); // error

为什么会错呢？因为GetScore函数接受的不是Student而是const Student&！这下可麻烦了。我们有些函数接受的是T，有些函数接受的是const T&，难道要写两个Sort嘛？当然这种代价肯定是不能接受的。于是我们想，如果可以从U(*key)(T)的T推导出vector里面装的是什么那该多好啊。反正无论函数接受的是string, string& const string, const string&，vector反正只能放string的。

这个时候就要祭出伟大的type traits了。怎么做呢？其实根上面的说法一样，我们把template看成是一个函数，输入是一个类型，输出再也不是值了，还是一个类型就好了：

template<typename T>
struct RemoveCR
{
    typedef T Result;
};

template<typename T>
struct RemoveCR<T&>
{
    typedef typename RemoveCR<T>::Result Result;
};

template<typename T>
struct RemoveCR<const T>
{
    typedef typename RemoveCR<T>::Result Result;
};

我们要怎么看这个过程呢？其实这是个pattern matching的过程，而pattern matching在一定程度上跟if-else其实是差不多的。所以我们看着一类的东西，心里不要总是想着他是个模板，而是要想，RemoveCR是个函数。所以当我们看见第一个RemoveCR的时候，我们心里浮现出来的景象大概是这个样子的：

Type RemoveCR(Type T)
{
    if(false);
    ....
    else
        return T;
}

好了，这个时候我们看见了第二个RemoveCR，那么这个RemoveCR函数又具体了一点：

Type RemoveCR(Type T)
{
    if(false);
    else if(T is T0&)
        return RemoveCR(T0);
    ....
    else
        return T;
}

后来我们看到了第三个RemoveCR，发现定义到此结束了，于是RemoveCR函数的实际的样子就出来了：

Type RemoveCR(Type T)
{
    if(false);
    else if(T is T0&)
        return RemoveCR(T0);
    else if(T is const T0)
        return RemoveCR(T0);
    else
        return T;
}

于是我们就可以做很多验证了，譬如说RemoveCR<int>::Result的结果是int，RemoveCR<const int&>::Result的结果还是int。现在好了，我们可以修改我们的Sort函数了：

template<typename T, typename U>
void Sort(vector<typename RemoveCR<T>::Result>& ts, U(*key)(T))
{
    ....
}

无论你的排序函数接受的是Student还是const Student&，现在Sort函数都知道，你需要对vector<Student>进行排序。于是任务就完成了！

别的语言里面没有这种问题，是因为只有C++才会把const、volatile和&这样的东西用来修饰一个类型而不是一个变量。这一点我第二篇文章已经讲过了，就不继续啰嗦了。所以说C++的设计虽然考虑得很周到，Bjarne Stroustrup菊苣也说过他不喜欢像别的语言的作者一样把自己的观点强加给用户。从这个出发点上来看，C++这一点相当好。只要你肯学习，又不会太蠢的话，总是可以学会C++的正确使用方法，正常使用C++来写代码的。但是，人真的蠢怎么办呢？Bjarne Stroustrup你这样歧视愚蠢的程序员是不对的，难道蠢就不能做程序员吗，难道学了go陷进去不能自拔的人就再也没有机会学习C++了吗！

关于type traits，haskell的type class（这东西就跟concept mapping一样）其实也有一部分这样的能力，可以帮你从type class的一部分类型参数推导出另一部分的类型参数。譬如说你这么写：

class MyClass a b c : a b => c
  where ....

那么只要你实现了MyClass Int String Char，就不能实现MyClass Int String String了，因为a b => c这条规则已经限制了，(Int String)只能出现一次，c要完全被a和b决定。所以拥有这个=>的haskell的type class也就可以有一部分type traits的功能了，虽然用法跟C++是截然不同的。

那C++的template除了泛型、concept和type traits之外，还有没有别的功能呢？当然有，我们不仅可以把类型放进模板的参数列表里面去，也可以把一个整数放进去。这个时候我们就可以用Int<100>来表达100，用Pair<Int<100>, Pair<Int<200>, Pair<Int<300>, PairEnd>>>来代表数组[100, 200, 300]，然后各种奇技淫巧就可以用来把模板写成一个不带类型的函数式语言了，在编译期什么东西都可以算。这个事情展开讲就太复杂了，而且也没什么用，你们感兴趣的话去看《C++ Template Metaprogramming》就行了。

在所有的文字之前，我需要强调一下，我本人对structure typing持反对态度，所以就算文中的内容“看起来很像”go的interface，读者们也最好不要觉得我是在赞扬go的interface。我比较喜欢的是haskell和rust的那种手法。可惜rust跟go一样恨不得把所有的单词都缩成最短，结果代码写出来连可读性都没有了，单词都变成了符号。如果rust把那乱七八糟的指针设计和go的那种屎缩写一起干掉的话，我一定会很喜欢rust的。同理，COM这个东西设计得真是太他妈正确了，简直就是学习面向对象手法的最佳范例，可惜COM在C++下面操作起来有点傻逼，于是很多人看见这个东西就呵呵呵了。

上一篇文章说这次要写类成员函数和lambda的东西，不过我想了想，还是先把OO放前面，这样顺序才对。

我记得我在读中学的时候经常听到的宣传，是面向对象的做法非常符合人类的思维习惯，所以人人喜欢，大行其道，有助于写出鲁棒性强的程序。如今已经过了十几年了，我发现网上再也没有这样的言论了，但是也没有跟反C++的浪潮一样拼命说面向对象这里不好那里不好要废除——明显人们还是觉得带面向对象的语言用起来还是比较爽的，不然也就没有那么多人去研究，一个特别合用来写functional programming的语言——javascript——是如何可以“模拟”面向对象语言里面的常用操作——new、继承和虚函数覆盖了。

所以像面向对象这种定义特别简单的东西，语法上应该做不出什么坑的了。那今天的坑是什么呢？答案：是人。

动态类型语言里面的面向对象说实话我也不知道究竟好在哪里，对于这种语言那来讲，只要做好functional programming的那部分，剩下的OO究竟要不要，纯粹是一个语法糖的问题。在动态类型语言里面，一个类和一个lambda expression的差别其实不大。

那么静态类型语言里面的面向对象要怎么看待呢？首先我们要想到的一个是，凡是面向对象的语言都支持interface。C++虽然没有直接支持，但是他有多重继承，我们只需要写出一个纯虚类出来，就可以当interface用了。

在这里我不得不说一下C++的纯虚类和interface的这个东西。假设一下我们有下面的C#代码：

interface IButton{}
interface ISelectableButton : IButton{}
interface IDropdownButton : IButton{}
class CheckBox : ISelectableButton{}

class MyPowerfulButton : CheckBox, IDropdownButton
{
    // 在这里我们只需要实现IDropdownButton里面比IButton多出来的那部分函数就够了。
}

我们先不管GUI是不是真的能这么写，我们就看看这个继承关系就好了。这是一个简单到不能再简单的例子。意思就是我有两种button的接口，我从一个实现里面扩展出一个支持另一种button接口的东西。但是大家都知道，我那个完美的GacUI用的是C++，那么在C++下面会遇到什么问题呢：

#region 抱怨

一般来说在C++里面用纯虚类来代替interface的时候，我们继承一个interface用的都是virtual继承。为什么呢？看上面那个例子，ISelectableButton继承自IButton，IDropdownButton继承自IButton。那么当你写一个MyPowerfulButton的时候，你希望那两个接口里面各自的IButton是不一样的东西吗？这当然不是。那如何让两个接口的IButton指向的是同一个东西呢？当然就是用virtual继承了。

好了，现在我们有CheckBox这个实现了ISelectableButton（带IButton）的类了，然后我们开始写MyPowerfulButton。会发生什么事情呢？

猜错了！答案是，其实我们可以写，但是Visual C++（gcc什么的你们自己玩玩就好了）会给我们一个warning，大意就是你IDropdownButton里面的IButton被CheckBox给覆盖了，再说抽象一点就是一个父类覆盖了另一个父类的虚函数。这跟virtual继承是没关系的，你怎么继承都会出这个问题。

但这其实也怪不了编译器，本来在其他情况下，虚函数这么覆盖自然是不好的，谁让C++没有interface这个概念呢。但是GUI经常会碰到这种东西，所以我只好无可奈何地在这些地方用#pragma来supress掉这个warning，反正我知道我自己在干什么。

C++没有interface的抱怨到这里就完了，但是virtual继承的事情到这里还没完。我再举一个例子：

class A
{
private:
    int i;
public:
    A(int _i)i:(_i){}
};

class B : public virtual A
{
public:
    B(int _i):A(_i){}
};

class C : public virtual A
{
public:
    C(int _i):A(_i){}
};

class D : public B, public C
{
public:
    D():B(1), C(2){}
};

大家都是知道什么是virtual继承的，就是像上面这个例子，D里面只有一个A对象，B和C在D里面共享了A。那么，我们给B和C用了不同的参数来构造，难道一个A对象可以用不同的参数构造两次吗，还是说编译器帮我们随便挑了一个？

呵呵呵呵呵呵呵呵，我觉得C++的virtual继承就是这里非常反直觉——但是它的解决方法是合理的。反正C++编译器也不知道究竟要让B还是C来初始化A，所以你为了让Visual C++编译通过，你需要做的事情是：

D()
    : A(0)  // 参数当然是胡扯的，我只是想说，你在D里面需要显式地给A构造函数的参数
    , B(1)
    , C(2)
{
}

#endregion

大家估计就又开始吵了，C++干嘛要支持多重继承和virtual继承这两个傻逼东西呢？我在想，对于一个没有内建interface机制的语言，你要是没有多重继承和virtual继承，那用起来就跟傻逼一样，根本发挥不了静态类型语言的优势——让interface当contract。当然，我基本上用多重继承和virtual继承也是用来代替interface的，不会用来做羞耻play的。

当我们在程序里面拿到一个interface也好，拿到一个class也好，究竟这代表了一种什么样的精神呢？interface和class的功能其实是很相似的

interface IA：只要你拿到了一个IA，你就可以对她做很多很多的事情了，当然仅限大括号里面的！
class C : IA, IB：只要你拿到了一个C——哦不，你只能拿到interface不能拿到class的——反正意思就是，你可以对她做对IA和IB都可以做的事情了！

所以contract这个概念是很容易理解的，就是只要你跟她达成了contract，你就可以对她做这样那样的事情了。所以当一个函数返回给你一个interface的时候，他告诉你的是，函数运行完了你就可以做这样那样的事情。当一个函数需要一个interface的时候，他告诉你的是，你得想办法让我（函数）干这样那样的事情，我才会干活。

那class呢？class使用来实现interface的，不是给你直接用的。当然这是一个很理想的情况，可惜现在的语言糖不够甜，坚持这么做的话实在是太麻烦了，所以只好把某些class也直接拿来用了，GUI的控件也只好叫Control而不是IControl了。

其实说到底class和interface有什么区别呢？我们知道面向对象的一大特征就是封装，封装的意思就是封装状态。什么是状态呢？反正云风一直在说的“类里面的数据”就不是状态。我们先来看什么是数据：

struct Point
{
    int x;
    int y;
};

这就是典型的数据，你往x和y里面随便写什么东西都是没问题的，反正那只是一个点。那什么是状态呢：

struct String
{
    wchar_t* buffer;
    int length;
};

String和Point有什么不一样呢？区别只有一个：String的成员变量之间是满足一个不变量的：wcslen(buffer) == length;

如果我们真的决定要给String加上这么个不变量的话，那这里面包含了两点：
1：buffer永远不是nullptr，所以他总是可以被wcslen(buffer)
2：length的值和buffer有直接的关系

如果你要表达一个空字符串，你总是可以写buffer=L””，不过这就要你给String再加上一些数据来指明这个buffer需要如何被释放了，不过这是题外话了。我们可以假设buffer永远是new[]出来的——反正这里不关心它怎么释放。

这个不变量代表什么呢？意思就是说，无论你怎么折腾String，无论你怎么创建释放String，这个等式是一定要满足的。也就是说，作为String外部的“操作人员”，你应当没机会“观测”到这个String处于一个不满足不变量的状态。

所以这两个成员变量都不应该是public的。因为哪怕你public了他们其中的一个，你也会因为外部可以随意修改它而使他进入一个不满足不变量的状态。

这代表了，为了操作这些成员变量，我们需要public一些函数来给大家用。其实这也是contract，String的成员函数告诉我们，你可以对我（String）做很多很多的事情哦！

这同时也代表了，我们需要一个构造函数。因为如果我们在创建一个String之后，实例没有被正确初始化，那么他就处于了一个不满足不变量的状态，这就不满足上面说的东西了。有些人喜欢带一个Init函数和一个基本不干什么事情的构造函数，我想说的是，反正你构造完了不Init都不能用，你为什么非要我每次创建它的时候都立刻调用Init这么多次一举呢？而且你这样会使得我无法对于一个这样的函数f(shared_ptr<ClassThatNeedsInit> x)直接写f(make_shared(new ClassThatNeedInit))因为你的构造函数是残废的！

有些人会说，init没有返回值，我不知道他犯了错误啊——你可以用Exception！

还有些人会说，exception safe的构造函数好难写啊——学啊我艸！

但是这样仍然有些人会负隅顽抗，都这么麻烦了反正我可以用对Init和返回值就好了——你连exception safe的构造函数都不知道怎么写你怎么知道你可以“用对”它们？

#region 题外话展开

但是有些人就喜欢返回error，怎么办呢？其实我们都很讨厌Java那个checked exception的对吧，要抛什么exception都得在函数签名里面写，多麻烦啊。其实这跟error是一样的。一个exception是可以带有很多丰富的信息的——譬如说他的callstack什么的，还可以根据需要有很多其他的信息，总之不是一个int可以表达的。这就是为什么exception【通常】都是一个类。那如果我们不能用exception，但是也要返回一样多的信息怎么办？你只好把函数的返回值写得相当的复杂，譬如说：

struct ErrorInfoForThisFunction
{
    xxxxxxxx
};

template<typename R, typename E>
struct ReturnValue // C++没有好用的tuple就是卧槽
{
    bool hasError;
    R returnValue;
    E errorInfo;
};

ReturnValue<ReturnType, ErrorInfoForThisFunction> ThisFunction( ... ); //我知道因为信息实在太多你们又要纠结返回struct还是它的指针还是ReturnValue里面的东西用指针还是用引用参数等等各种乱七八糟的事情了哈哈哈哈哈哈

于是现在出问题了，我有一个ThatFunction调用ThisFunction，当错误是一种原因的时候我可以处理，当错误是另一种原因的时候我无法处理，所以在这种情况下我有两个选择：
1：把错误信息原封不断的返回
2：把ThisFunction的错误信息包装成ThatFunction的错误信息
不过我们知道其实这两种方法都一样，所以我们采用第一种：

struct ErrorInfoForThatFunction
{
    yyyyyyyy
};

ReturnValue<ReturnType2, tuple<ErrorInfoForThisFunction, ErrorForThatFunctio, bool /*用来代表哪个是有效的*/> ThatFunction( ...  ); //数据越来越多我知道你们会对返回值纠结的越厉害

你可能会说，为什么不把tuple包装成另一个struct？其实都一样，懒得写了。

我们知道，通常一个常见的几百人一起写的小软件都会有几百上千万行甚至几十G代码的，函数的调用层次只有几十层都已经很不错了。就算调用链里面只有10%的函数添加了自己的错误信息，那累积到最后肯定会很壮观的。而且只要底层的一个函数修改了错误信息，所有直接间接调用它的函数都会受到影响。

这简直就跟Java的checked exception一样嘛！

有些人会说，我们有error code就够了！我知道你们根本没有好好想“怎么做error recovery”这件事情。

有些人还会说（就在我微博上看见的），用error code就是代表可以不处理，我干嘛要费那么多心思搞你这些返回值的东西？我对这种人只能呵呵呵了，转行吧……

这个时候我就会想，C++多好啊，我只要把ReturnValue<ReturnType, ErrorInfoForThisFunction>给改成ReturnType，然后在函数里面发生了错误还是构造一个ErrorInfoForThisFunction，然后直接给throw出来就好了。throw一个值我们还不用关心怎么释放它，多省事。对于ErrorInfoForThatFunction，我还可以让这两个struct都继承自同一个基struct（就是你们经常在别的语言里面看见的Exception类了），这样我在外面还可以直接catch(const 基struct& ex)。

有些人会说，为什么不强制所有继承都继承自Exception？我知道你们就只是想catch了之后不理罢了，反正C++也有catch(…)你们偷着乐就行了。

用Exception有性能问题？反正在不发生错误的情况下，写了几句try也就只是操作了写在FS : [ 0 ]里面的一个链表而已，复制几个指针根本就不算什么影响。

C++的catch不能抓到Access Violation（也就是segmant fault？）？现在连最新的.net你来写catch(Exception ex)也抓不到AccessViolationException了。都AV了你的内存都搞得一团糟了，如果你这个时候还不备份数据dump自己然后退出重启（如果需要的话），那你接着执行代码，天知道会发生什么事情啊！连C#都觉得这么做危险了，C++只能更危险——所以用SEH抓下来dump自己然后进程自杀吧。Java还区分Error和Exception，虽然我不知道他具体代表什么，反正一般来说Exception有两种
1：可以预见的错误，譬如说Socket断开了所以Write就是败了给个Exception之类的
2：必须修改代码的错误，譬如说数组下标越界——这除了你写错以外根本没有别的原因，就应该挂掉，这时候你debug的时候才能立刻知道，然后改代码。

所以有三个基类然后最严重的那种不能catch我觉得也是一种好的选择。你可能会问，那C#在AV之后你又抓不到那怎么知道呢？答案：Application类有一个事件就是在发生这类事情的时候被调用的，在里面dump就好了。如果你非要抓AV，那也可以抓得到，就是有点麻烦……

#endregion

说了这么多，无非就是因为一个类的构造函数——其实他真的是一个函数，只是函数名和类名一样了，这种事情在js里面反正经常出现——强制了你只能返回正确的时候的结果，于是有些人没办法加入error code了，又不知道怎么正确使用exception，只好搞出个C语言的封建社会残留思想Init函数来。其实我们知道，一旦有了Exception，函数签名里面的返回值就是他正确执行的时候返回的东西，这根构造函数一样。

C++的exception在构造函数里面不好，其实是因为一旦构造函数发生了异常，那代表这个类没构造完，所以析构函数是不会执行的。这在一定程度上给你写一个正确的构造函数（这也是“如何写一个正确的类”的其中一个方面）带来了麻烦，所以很多人到这里就呵呵呵了。

这就跟很多人学习SQL语言结果到group by这里就怎样也跨不过去了一样——人和人之间说没有差距这个不符合客观现实啊……

不过我不否认，想写一个正确的C++程序是一件非常困难的事情，以至于连我在【只有我自己用的那部分library】里面都不是总是遵守各种各样的规则，反正我写的代码，我知道怎么用。不过公司的代码都是一大堆人一起写的，就像sqlserver一个组有一千多人一样（oracle是我们的十几倍，我们还能活下来真是太不容易了）——你能每个人都沟通到吗？撑死了就几十个吧，才不到10%。天知道别人会在代码里面干什么。所以写代码是不能太随便的。同理，招人也不能太随便，特别是你们这些连code review都不做的公司，你平时都不能阻止他checkin垃圾代码，你还敢招不合格的人吗？

现在我们回到面向对象的东西。Exception其实也应该算在contract里面，所以其实interface里面的函数会抛什么异常是需要明确的表达出来的。但是checked exception这个东西实在是太蠢了，因为这个规则是不能组合的，会导致上面说的error返回值一样的“接口信息大爆炸”。

所有不能组合的东西都是很难用的，譬如checked exception，譬如锁，譬如第一篇文章说的C语言那个碉堡了的函数指针数组作为参数的一个成员函数指针类型的声明什么的。

如果你不直接写出这个函数会抛exception，那要怎么办呢？方法有两个：
1：你给我把文档写好了，而且你，还有你，用这个library之前，给我RTFM！
2：就跟VisualStudio一样支持xml注释，这样VS就可以在你调用这个函数的时候用tooltip的形式提示你，你需要注意这些那些事情……

什么？你不用IDE？给我RTFM！你连文档都不看？滚！明天不要来上班了！

突然发现本来要写面向对象的，结果Exception也写了相当长的一段。这件故事告诉我们，就算你不知道interface as contract是什么意思，你还能凑合写点能维护的代码。但是你Exception用得不好，程序就写成了渣，这个问题比较严重，所以写的也就比较多了。所以下面我们真正来谈contract的事情。需要注意的是，C++对这种东西是用你们很讨厌的东西来支持的——模板和偏特化。

contract的概念是很广泛的。对于面向对象语言来说，int这种东西其实也可以是一个类。你们不要老是想着编译后生成什么代码的事情，语法这种东西只是障眼法而已，编译出来的东西跟你们看到的可以是完全不同的。一个典型的例子就是尾递归优化了。还有C#的int虽然继承自object但是你直接用他的话生成出来的代码跟C++是没什么区别的——因为编译器什么后门都可以开！

那我们就拿int来说吧。int有一个很重要的特征，就是可以用来比较。C++怎么表达这个事情的呢？

struct int
{
    ......
    bool operator<(int i);
    ......
};

如果你想写一个排序函数，内部想用<来排序的话，你不需要在接口上写任何东西，你只需要假设那个typename T的T可以被<就好了。所有带有<的类型都可以被这个函数使用。这特别的structure typing，而且C++没有concept mapping，导致了你无法在接口上表达“这个类必须带<”的这件事情，所以一旦你用错了，这错误信息只能跟烟雾一般缭绕了……

concept mapping其实也是一个面向对象的特别好用特征不过这太高级了估计很多人都没用过——你们又不喜欢haskell和rust——那对于我们熟悉的面向对象的特性来讲，这样的事情要怎么表达呢？

于是我们伟大的先知Anders Hejlsberg菊苣就做了这么个决定（不是他干的也是他手下干的！）

interface IComparable // .net 1.0没有模板，只好搞了这么个傻逼东西出来
{
    int CompareTo(object o); //具体的忘了，这是我根据记忆随便写的
}

interface IComparable<T>
{
    int CompareTo(T o);
}

struct Int32 : IComparable, IComarable<T> ...
{
    ......
}

所以你的排序函数只需要写成：

void Sort<T>(T[] data)
    where T : IComparable<T>
{ ...... }

看看IComparable<int>这个傻逼。我为什么要创建一个对象（IComparable<int>），他的职责就是跟另一个int作比较？这实在是太蠢了，无论怎么想都不能想出这种对象到底有什么存在的意义。不过因为C#没有concept mapping，于是看在interface as contract的份上，让interface来干这种事情其实也是很合理的。

所以contract这个东西又赋予了一个更加清晰的意义了。我们其实想要表达的事情是“我们可以对这个参数做什么事情”，而不是“这个参数是什么类型”。所以在这个Sort函数里面，这个T其实不代表任何事情，真正起到声明的作用的是where T : IComparable<T>这一句，指明了data数组里面的所有东西都是可以被排序的。那你可能会问，为什么不把IComparable<T>改成IComparable然后干脆把参数改成IComparable[] data呢？虽然说这样做的确更加“面向对象”，但是实在是太不现实了……

本来面向对象这种概念就不是特别的可以表达客观现实，所以出现一些这种状况，也是正常的。

#region 题外话

看看这两个函数：

void Sort<T>(T[] data) where T:IComparable<T>;
void Sort(IComparable[] data);

他们互相之间存在了一个特别优美的（数学意义上的）变换，发现没有，发现没有！所以对于动态类型语言（interface可以从代码里面得到）做一些“静态化”的优化的时候，就可以利用类似的技巧——咳咳，说太远了，赶紧打住。谁说懂点代数对编程没用的？哼！

#endregion

在这里我们终于看到了contract在带泛型的纯洁的面向对象语言里面的两种表达方法。你可能会想，我想在java里面干这种事情怎么办？还是换C#吧。那我们拿到一个class的时候，这代表什么呢？其实我们应该看成，其实我们拿到的是一个interface，只是他恰好只有一个实现。所以在这种时候，你最好不要依赖于“这个interface恰好只有一种实现而且我知道他是什么”的这个事情，否则程序写大了，你会发现你越来越不满足“面向interface编程”的这个原则，代码越来越难处理了。

我们可能会想到另一件事情，先知们跟我们说，当你设计函数参数的类型的时候，这个类型越基，哦不，越是在继承链里面距离object靠得越近越好，这是为什么呢？这其实也是一个interface as contract的问题。举个例子，我们需要对一个数组求和：

T Sum<T>(T[] data, Func<T, T, T> 加法函数); // C#真的可以用中文变量的哦！

费尽心思终于写好了，然后我们第二天发现，我们对List<T>也要做一样的事情。那怎么办呢？

在这里，Sum究竟对data有什么需求呢？其实研究一下就会发现，我们需要的只是想遍历data里面的所有内容而已。那data是不是一个数组，还是列表，还是一颗二叉树，还是你垃圾ipad里面的一些莫名其妙的数据也好，其实都一样。那C#里面什么interface代表“遍历”这个contract呢？当然是IEnumerable<T>了：

T Sum<T>(IEnumerable<T> data, Func<T, T, T> 加法函数); // C#真的可以用中文变量的哦！

这样你的容器只要能够被foreach，也就是继承自IEnumearble<T>，就可以用这个函数了。这也是为什么”linq to 容器”基本上都是在IEnumerable上做的，因为他们只需要遍历。

哦，我们还说到了foreach。foreach是一个语句，用来遍历一个容器。那你如何表达一个容器可以被foreach拿来遍历的这个contract呢？还是IEnumerable<T>。interface拿来做contract的确是最佳匹配呀。

其实说了这么多，我只想表达一个东西。不要太在意“这个变量的类型是什么”，你要关心的是“我可以对这个变量做这样那样的事情”。这就是为什么我们会推荐“面向接口编程”，因为人总是懒散的，需要一些约束。interface不能用来new，不包含成员变量，刚好是contract的一种很好地表达方法。C++表达contract其实还可以用模板，不过这个就下次再说了。如果你们非得现在就知道到底怎么用的话，我就告诉你们，只要把C#的(i as IComparable<int>).CompareTo(j)换成Comparable<int>::Compare(i, j)就好了。

所以在可能的情况下，我们设计函数的参数和返回值的类型，也尽量用更基的那些类型。因为如果你跟上面的Sum一样，只关心遍历，那么你根本不应该要求你的参数可以被随机访问（数组就是这个意思）。

希望大家看完这篇文章之后可以明白很多我们在面向对象编程的时候，先知们建议的那些条款。当然这里还不涉及设计模式的东西。其实设计模式说白了是语法的补丁。设计模式这种东西用的最多，C#略少，你们会发现像listener模式这种东西C#就不常用，因为它有更好的东西——event。

我从来没有在别的语言的粉里面看见过这么容易展示人性丑陋一面的粉，就算是从十几年前开始的C++和C对喷，GC和非GC对喷，静态类型动态类型对喷的时候，甚至是云风出来喷C++黑得那么惊天动地的时候，都没有发生过这么脑残的事情。这种事情只发生在go语言的脑残粉的身上，这究竟代表什么呢？想学go语言的人最好小心一点了，学怎么用go没关系，go学成了因为受不了跳到别的语言去也没关系，就算是抖M很喜欢被折腾所以坚持用go也没关系，但是把自己学成了脑残粉，自己的心智发生不可逆转的变换，那就不好了。

当然，上一篇文章最后那个例子应该是我还没说清楚，所以有些人有这种“加上一个虚析构函数就可以了”的错觉也是情有可原的。Base* base = new Derived;之后你去delete没问题，是因为析构函数你还可以声明成虚的。但是Base* base = new Derived[10];之后你去delete[]发生了问题，是因为Derived和Base的长度不一样，所以当你开始试图计算&base[1]的时候，你实际上是拿到了第一个Derived对象的中间的一个位置，根本不是第二个Derived。这个时候你在上面做各种操作（譬如调用析构函数），你连正确的this指针都拿不到，你再怎么虚也是没用的。不过VC++单纯做delete[]的话，在这种情况下是不会有问题的，我猜它内部不仅记录了数组的长度，还记录了每一个元素的尺寸。当然，你直接用bases[1]->DoSomething()的时候，出事是必须的。

所以今天粉丝群在讨论昨天的这个例子的时候，我们的其中一位菊苣就说了一句话：

当你使用C++的时候C的一部分子集最好少碰

我也很赞同。反正C++已经有各种内置类型了，譬如typeid出来的按个东西（我给忘了）啊，initialization_list啊，range什么的。为什么就不给new T[x]创建一个类型呢？不过反正都已经成为现实了，没事就多用用vector和shared_ptr吧，不要想着什么自己new自己delete了。

今天我们来讲一个稍微“高级”一点点的坑。这是我在工作之后遇到的一个现实的例子。当然，语言的坑都摆在那里，人往坑里面跳都肯定是因为自己知道的东西还不够多造成的。但是坑有三种，第一种是很明显的，只要遵守一些看起来很愚蠢但是却很有效的原则（譬如说if(1 == a)…）就可以去除的。第二种坑是因为你不知道一些高级的知识（譬如说lambda和变量揉在一起的生命周期的事情）从而跳坑的。第三种纯粹就是由于远见不够了——譬如说下面的例子。

在春光明媚的一个早上，我接到了一个新任务，要跟另一个不是我们组的人一起写一个图像处理的pipeline的东西。这种pipeline的节点无非就是什么直方图啊，卷积啊，灰度还有取边缘什么的。于是第一天开会的时候，我拿到了一份spec，上面写好了他们设计好但是还没开始写的C++的interface（没错，就是那种就算只有一个实现也要用interface的那种流派），让我回去看一看，过几天跟他们一起把这个东西实现出来。当然，这些interface里面肯定会有矩阵：

template<typename T>
class IMatrix
{
public:
    virtual ~IMatrix(){}

    virtual T* GetData()=0;
    virtual int GetRows()=0;
    virtual int GetColumns()=0;
    virtual int GetStride()=0;
    virtual T Get(int r, int c)=0;
    virtual void Set(int r, int c, T t)=0;
};

其实说实话，IMatrix这么写的确没什么大问题。于是我们就很愉快的工作了几天，然后把这些纯粹跟数学有关的算法都完成了，然后就开始做卷积的事情了。卷积所需要的那一堆数字其实说白了他不是矩阵，但因为为这种东西专门做一个类也没意义，所以我们就用行列一样多的矩阵来当filter。一开始的接口定义成这个样子，因为IBitmap可能有不同的储存方法，所以如何做卷积其实只有IBitmap的实现自己才知道：

template<typename TChannel>
class IBitmap
{
......
    virtual void Apply(IMatrix<float>& filter)=0;
......
};

于是我们又愉快的度过了几天，直到有一天有个人跳出来说：“Apply里面又不能修改filter，为什么不给他做成const的？”于是他给我们展示了他修改后的接口：

template<typename TChannel>
class IBitmap
{
......
    virtual void Apply(IMatrix<const float>& filter)=0;
......
};

我依稀还记得我当时的表情就是这样子的→囧。

语言的类型系统是一件特别复杂的事情，特别是像C++这种，const T<a, b, c>和T<const a, const b, cont c>是两个不一样的类型的。一们语言，凡是跟优美的理论每一个不一致的地方都是一个坑，区别只是有些坑严重有些坑不严重。当然上面这个不是什么大问题，因为真的按照这个接口写下去，最后会因为发现创建不了IMatrix<const float>的实现而作罢。

而原因很简单，因为一般来说IMatrix<T>的实现内部都有一个T*代表的数组。这个时候给你换成了const float，你会发现，你的Set函数在也没办法把const float写进const float*了，然后就挂了。所以正确的方法当然是：

virtual void Apply(const IMatrix<float>& filter)=0;

不过在展开这个问题之前，我们先来看一个更加浅显易懂的“坑”，是关于C#的值类型的。譬如说我们有一天需要做一个超高性能的包含四大力学的粒子运动模拟程序——咳咳——总之从一个Point类型开始。一开始是这么写的（C# 5.0）：

struct Point
{
    public int x;
    public int y;
}

var ps = new Point[] { new Point { x = 1, y = 2 } };
ps[0].x = 3;

已开始运作的很好，什么事情都没有发生，ps[0]里面的Point也被很好的更改了。但是有一天，情况变了，粒子之间会开始产生和消灭新的粒子了，于是我把数组改成了List：

var ps = new List<Point> { new Point { x = 1, y = 2 } };
ps[0].x = 3;

结果编译器告诉我最后一行出了一个错误：

Cannot modify the return value of 'System.Collections.Generic.List<ArrayTest2.Program.Point>.this[int]' because it is not a variable

C#这语言就是牛逼啊，我用了这么久，就只找出这个“不起眼的问题”的同时，还是一个编译错误，所以用C#的时候根本没有办法用错啊。不过想想，VB以前这么多人用，除了on error resume next以外也没用出什么坑，可见Microsoft设计语言的功力比某狗公司那是要强多了。

于是我当时就觉得很困惑，随手写了另一个类来验证这个问题：

class PointBox
{
    public int Number { get; set; }
    public Point Point { get; set; }
}

var box = new PointBox() { Number = 1, Point = new Point { x = 1, y = 2 } };
box.Number += 3;
box.Point.x = 5;

结果倒数第二行过了，倒数第一行还是编译错误了。为什么同样是属性，int就可以+=3，Point就不能改一个field非得创建一个新的然后再复制进去呢？后来只能得到一个结论，数组可以List不可以，属性可以+=不能改field（你给Point定义一个operator+，那你对box.Point做+=也是可以的），只能认为是语言故意这么设计的了。

写到这里，我想起以前在MSDN上看过的一句话，说一个结构，如果超过了16个字节，就建议最好不要做成struct。而且以前老赵写了一个小sample也证明大部分情况下用struct其实还不如用class快。当然至于是为什么我这里就不详细展开了，我们来讲语法上的问题。

在C#里面，struct和class的区别，就是值和引用的区别。C#专门做了值类型和引用类型，值类型不能转成引用（除非box成object或nullable或lazy等），引用类型不能转值类型。值不可以继承，引用可以继承。我们都知道，你一个类继承自另一个类，目的说到底都是为了覆盖几个虚函数。如果你不是为了覆盖虚函数然后你还要继承，八成是你的想法有问题。如果继承了，你就可以从子类的引用隐式转换成父类的引用，然后满足里氏代换原则。

但是C#的struct是值类型，也就是说他不是个引用（指针），所以根本不存在什么拿到父类引用的这个事情。既然你每一次见到的类型都是他真正的类型（而不像class，你拿到IEnumerable<T>，他可能是个List<T>），那也没有什么必要有虚函数了。如果你在struct里面不能写虚函数，那还要继承干什么呢？所以struct就不能继承。

然后我们来看一看C#的属性。其实C#的operator[]不是一个操作符，跟C++不一样，他是当成属性来看待的。属性其实是一个语法糖，其中的getter和setter是两个函数。所以如果一个属性的类型是struct，那么getter的返回值也是struct。一个函数返回struct是什么意思呢？当然是把结果【复制】一遍然后返回出去了。所以当我们写box.Point.x=5的时候，其实等价于box.get_Point().x=5。你拿到的Point是复制过的，你对一个复制过的struct来修改里面的x，自然不能影响box里面存放着的那个Point。所以这是一个无效语句，C#干脆就给你定了个编译错误了。不过你可能会问，List和Array大家都是operator[]也是一个属性，那为什么Array就可以呢？答案很简单，Array是有特殊照顾的……

不过话说回来，为什么很少人遇到这个问题？想必是能写成struct的这些东西，作为整体来讲本身是一个状态。譬如说上面的Point，x和y虽然是分离的，但是他们并不独立代表状态，代表状态的是Point这个整体。Tuple（这是个class，不过其实很像struct）也一样，还有很多其他的.net framework里面定义的struct也一样。因此就算我们经常构造List<Point>这种东西，我们也很少要去单独修改其中一个element的一部分。

那为什么struct不干脆把每一个field都做成不可修改的呢？原因是这样做完全没有带来什么好处，反正你误操作了，总是会有编译错误的。还有些人可能会问，为什么在struct里面的方法里，对this的操作就会产生影响呢？这个问题问得太好了，因为this是一个本质上是“指针”的东西。

这就跟上一篇文章所讲的东西不一样了。这篇文章的两个“坑”其实不能算坑，因为他们最终都会引发编译错误来迫使你必须修改代码。所以说，如果C++的new T[x]返回的东西是一个货真价实的数组，那该多好啊。数组质检科从来没有什么转换的。就像Delphi的array of T也好，C#的T[]也好，C++的array<T>或者vector<T>也好，你从来都不能把一个T的数组转成U的数组，所以也就没有这个问题了。所以在用C++的时候，STL有的东西，你就不要自己撸了，只伤身体没好处的……

那么回到一开始说的const的问题。我们在C++里面用const，一般都是有两个目的。第一个是用const引用来组织C++复制太多东西，第二个是用const指针来代表某些值是不打算让你碰的。但是一个类里面的函数会做什么我们并不知道，所以C++给函数也加上了const。这样对于一个const T的类型，你只能调用T里面所有标记了const的函数了。而且对于标记了const的成员函数，他的this指针也是const T* const类型的，而不是以前的T* const类型。

那类似的问题在C#里面是怎么解决的呢？首先第一个问题是不存在的，因为C#复制东西都是按bit复制的，你的struct无论怎么写都一样。其次，C#没有const类型，所以如果你想表达一个类不想让别人修改，那你就得把那些“const”的部分抽出来放在父类或父接口里面了。所以现在C#里面除了IList<T>类型以外，还有IReadOnlyList<T>。其实我个人觉得IReadOnlyList这个名字不好，因为这个对象说不定底下是个List，你用着用着，因为别人改了这个List导致你IReadOnlyList读出来的东西变了，迷惑性就产生了。所以在这种情况下，我宁可叫他IReadableList。他是Readable的，只是把write的接口藏起来的你碰不到而已。

所以，const究竟是在修饰什么的呢？如果是修饰类型的话，跟下面一样让函数的参数的类型都变成const，似乎完全是没有意义的：

int Add(const int a, const int b);

或者更甚，把返回值也改成const：

const int Add(const int a, const int b);

那他跟

int Add(int a, int b);

究竟有什么区别呢？或许在函数内部你不能把参数a和b当变量用了。但是在函数的外部，其实这三个函数调用起来都没有任何区别。而且根据我们的使用习惯来讲，const修饰的应该不是一个类型，而是一个变量才对。我们不希望IBitmap::Apply函数里面会修改filter，所以函数签名就改成了：

virtual void Apply(const IMatrix<float>& filter)=0;

我们不希望用宏来定义常数，所以我们会在头文件里面这么写：

const int ADD = 1;
const int SUB = 2;
const int MUL = 3;
const int DIV = 4;
const int PUSH = 5;
const int POP = 6;

或者干脆用enum：

enum class Instructions
{
    ADD = 1,
    SUB,
    MUL,
    DIV,
    PUSH,
    POP
};

对于C++来讲，const还会对链接造成影响。整数数值类型的static const成员变量也好，const全局变量也好，都可以只写在头文件给一个符号，而不需要在cpp里面定义它的实体。但是对于非static const的成员变量来说，他又占用了class的一些位置（C#的const成员变量跟static是不相容的，它只是一个符号，跟C++完全不是一回事）。

而且根据大部分人对const的认识，我们用const&也好，const*也好，都是为了修饰一个变量或者参数。譬如说一个临时的字符串：

const wchar_t* name = L"@GeniusVczh";

或者一个用来计算16进制编码的数组：

const wchar_t code[] = L"0123456789ABCDEF";

其实说到底，我们心目中的const都是为了修饰变量或者参数而产生的，说白了就是为了控制一个内存中的值是否可以被更改（这一点跟volatile一样，而C#的volatile还带fence语义，这一点做得比C++那个只用来控制是否可以被cache进寄存器的要强多了）。所以C++用const来修饰类型又是一个违反直觉的设计了。当然，如果去看《C++设计与演化》的话，的确可以从中找到一些讲为什么const会用来描述类型的原因。不过从我的使用经验上来看，const至少给我们带来了一些不方便的地方。

第一个就是让我们写一个正确的C++ class变得更难。就像C#里面说的，一个只读的列表，其实跟一个可读写的列表的概念是不一样的。在C++里面，一个只读的列表，是一个可以让你看见写函数却不让你用的一个进入了特殊状态的可读写的列表。一般来说，一个软件都要几千个人一起做。我今天写了一个类，你明天写了一个带const T&参数的模板函数，后天他发现这两个东西凑在一起刚好能用，但是一编译发现那个类的所有成员函数都不带const结果没办法搞了。怎么办？重写吗，那我们得自己维护多出来的一份代码，还可能跟原类的作者犯下一样的错误。修改它的代码吗，鬼知道给一个函数加上const会不会给这个超大的软件的其他部分带来问题，说不定就像字符串类一样，有一些语义上是const的函数实际上需要修改一些成员变量结果你又不得不给那些东西加上mutable关键字了。你修改了之后，代码谁来维护，又成为一个跟技术无关的政治问题了。而且就算你弄明白了什么函数要加const，结果你声明一个const变量的时候const放错了位置，也会有一些莫名其妙的问题出现了。

如果从一开始就用C#的做法，把它分离成两个接口，这样做又跟C++有点格格不入，为什么呢？为什么STL那么喜欢泛型+值类型而不是泛型+引用类型？为什么C#就喜欢泛型+引用类型而不是泛型+值类型？其实这两种设计并没有谁好谁不好的地方，至于C++和C#有不同的偏爱，我想原因应该是出在GC上。语言有GC，你new的时候就不需要担心什么时候去delete，反正内存可以循环回收总是用不完的。C++却不行，内存一旦leak就永远的leak了，这么下去迟早都会挂掉的。所以当我们在C++和C#里面输入new这个关键字的时候，心情其实是差别相当大的。所以大家在C++里面就不喜欢用指针，而在C#里面就new的很开心。既然C++不喜欢指针，类似IReadOnlyList<T>的东西不拿指针直接拿来做值类型的话又是没有什么意义的，所以干脆就加上了const来“禁止你访问类里面的一部分东西”。于是每当你写一个类的时候，你就需要思考上一段所描述的那些问题。但是并不是所有C++的程序员都知道所有的这些细节的，所以后面加起来，总会有傻逼的时候——当然这并不怪C++，怪的是你面试提出的太容易，让一些不合格的程序员溜进来了。C++不是谁都可以用的。

第二个问题就是，虽然我们喜欢在参数上用const T&来避免无谓的复制，但是到底在函数的返回值上这么做对不对呢？const在返回值的这个问题上这是一把双刃剑。我自己写过一个linq for C++，山寨了一把IEnumerable和IEnumerator类，在Current函数里面我返回的就是一个const T&。本来容器自己的IEnumerator写的挺好，因为本来返回的东西就在容器里面，是有地址的。但是开始写Select和Where的时候就傻逼了。我为了正确返回一个const T&，我就得返回一个带内存地址的东西，当然最终我选择了在MoveNext的时候把结果cache在了这个SelectEnumerator的成员变量里面。当然这样做是有好处的，因为他强迫我把所有计算都放在MoveNext里面，而不会偷懒写在Current里。但是总的来说，要不是我写代码的时候蛋定，说不定什么时候就掉坑里了。

总的来说，引入const让我们写出一个正确的C++程序的难度变大了。const并不是一无是处，如果你是在想不明白什么时候要const什么时候不要，那你大不了不要在自己的程序里面用const就好了。当然我在这里并不是说C语言什么都没有就比C++好。一个语言是不可能通过删掉什么来让他变得更好的。C语言的抽象能力实在是太低了，以至于让我根本没办法安心做好逻辑部分的工作，而总要关心这些概念究竟要用什么样的扭曲的方法才能在C语言里面比较顺眼的表达出来（我知道你们最后都选择了宏！是吧！是吧！），从而让我变“烦”，bug就变多，程序到最后也懒得写好了，最后变成了一坨屎。

嘛，当然如果你们说我没有linus牛逼，那我自然也没办法说什么。但是C语言大概就是那种只有linus才能用的顺手的语言了。C++至少如果你心态好的话，没事多用STL，掉坑的概率就要比直接上C语言小多了。

语言的坑这种事情实在是罄竹难书啊，本来以为两篇文章就可以写完的，结果发现远远不够。看在文章长度的份上，今天就到此为止了，下一篇文章还有大家喜闻乐见的函数指针和lambda的大坑等着你们……

待续

这个系列的起因是这样的，王垠写了一篇喷go的博客http://www.yinwang.org/blog-cn/2013/04/24/go-language/，里面说go已经烂到无可救药了，已经懒得说了，所以让大家去看http://www.mindomo.com/view.htm?m=8cc4f95228f942f8886106d876d1b041，里面有详细的解释。然后这篇东西被发上了微博，很多博友立刻展示了人性丑陋的一面：
1、那些go的拥护者们，因为go被喷了，就觉得自己的人格受到了侮辱一样，根本来不及看到最后一段的链接，就开始张牙舞爪。
2、王垠这个人的确是跟人合不来，所以很多人就这样断定他的东西“毫无参考价值”。

不过说实话，文章里面是喷得有点不礼貌，这也在一定程度上阻止了那些不学无术的人们继续阅读后面的精华部分。如果所有的文章都这样那该多好啊，那么烂人永远都是烂人，不纠正自己的心态永远获得不了任何有用的知识，永远过那种月入一蛆的日子，用垃圾的语言痛苦的写一辈子没价值的程序。

废话就说到这里了，下面我来说说我自己对于语言的观点。为什么要设计一门新语言？原因无非就两个，要么旧的语言实在是让人受不了，要么是针对领域设计的专用语言。后一种我就不讲了，因为如果没有具体的领域知识的话，这种东西永远都做不好（譬如SQL永远不可能出自一个数据库很烂的人手里），基本上这不是什么语言设计的问题。所以这个系列只会针对前一种情况——也就是设计一门通用的语言。通用的语言其实也有自己的“领域”，只是太多了，所以被淡化了。纵观历史，你让一个只做过少量的领域的人去设计一门语言，如果他没有受过程序设计语言理论的系统教育，那只能做出屎。譬如说go就是其中一个——虽然他爹很牛逼，但反正不包含“设计语言”这个事情。

因此，在21世纪你还要做一门语言，无非就是对所有的通用语言都不满意，所以你想自己做一个。不满意体现在什么方面？譬如说C#的原因可能就是他爹不够帅啦，譬如说C++的原因可能就是自己智商太低hold不住啦，譬如说Haskell的原因可能就是用的人太少招不到人啦，譬如说C的原因可能就是实在是无法完成人和抽象所以没有linus的水平的人都会把C语言写成屎但是你又招不到linus啦，总之有各种各样的原因。不过排除使用者的智商因素来讲，其实有几个语言我还是很欣赏的——C++、C#、Haskell、Rust和Ruby。如果要我给全世界的语言排名，前五名反正是这五个，虽然他们之间可能很难决出胜负。不过就算如此，其实这些语言也有一些让我不爽的地方，让我一直很想做一个新的语言（来给自己用（？）），证据就是——“看我的博客”。

那么。一个好的语言的好，体现在什么方面呢？一直以来，人们都觉得，只有库好用，语言才会好用。其实这完全是颠倒了因果关系，如果没有好用的语法，怎么能写出好用的库呢？要找例子也很简单，只要比较一下Java和C#就够了。C#的库之所以好用，跟他语言的表达能力强是分不开的，譬如说linq（，to xml，to sql，to parser，etc），譬如说WCF（仅考虑易用性部分），譬如说WPF。Java能写得出来这些库吗？硬要写还是可以写的，但是你会发现你无论如何都没办法把他们做到用起来很顺手的样子，其实这都是因为Java的语法垃圾造成的。这个时候可以抬头看一看我上面列出来的五种语言，他们的特点都是——因为语法的原因，库用起来特别爽。

当然，这并不要求所有的人都应该把语言学习到可以去写库。程序员的分布也是跟金字塔的结构一样的，库让少数人去写就好了，大多数人尽管用，也不用学那么多，除非你们想成为写库的那些。不过最近有一个很不好的风气，就是有些人觉得一个语言难到自己无法【轻松】成为写库的人，就开始说他这里不好那里不好了，具体都是谁我就不点名了，大家都知道，呵呵呵。

好的语言，除了库写起来又容易又好用以外，还有两个重要的特点：容易学，容易分析。关于容易学这一点，其实不是说，你随便看一看就能学会，而是说，只要你掌握了门道，很多未知的特性你都可以猜中。这就有一个语法的一致性问题在里面了。语法的一致性问题，是一个很容易让人忽略的问题，因为所有因为语法的一致性不好而引发的错误，原因都特别的隐晦，很难一眼看出来。这里我为了让大家可以建立起这个概念，我来举几个例子。

第一个例子是我们喜闻乐见的C语言的指针变量定义啦：

int a, *b, **c;

相信很多人都被这种东西坑过，所以很多教科书都告诉我们，当定义一个变量的时候，类型最后的那些星号都要写在变量前面，避免让人误解。所以很多人都会想，为什么要设计成这样呢，这明显就是挖个坑让人往下跳嘛。但是在实际上，这是一个语法的一致性好的例子，至于为什么他是个坑，问题在别的地方。

我们都知道，当一个变量b是一个指向int的指针的时候，*b的结果就是一个int。定义一个变量int a;也等于在说“定义a是一个int”。那我们来看上面那个变量声明：int *b;。这究竟是在说什么呢？其实真正的意思是“定义*b是一个int”。这种“定义和使用相一致”的方法其实正是我们要推崇的。C语言的函数定义参数用逗号分隔，调用的时候也用逗号分隔，这是好的。Pascal语言的函数定义参数用分号分隔，调用的时候用逗号分隔，这个一致性就少了一点。

看到这里你可能会说，你怎么知道C语言他爹就是这么想的呢？我自己觉得如果他不是这么想的估计也不会差到哪里去，因为还有下面一个例子：

int F(int a, int b);
int (*f)(int a, int b);

这也是一个“定义和使用相一致”的例子。就第一行代码来说，我们要如何看待“int F(int a, int b);”这个写法呢？其实跟上面一样，他说的是“定义F(a, b)的结果为int”。至于a和b是什么，他也告诉你：定义a为int，b也为int。所以等价的，下面这一行也是“定义(*f)(a, b)的结果为int”。函数类型其实也是可以不写参数名的，不过我们还是鼓励把参数名写进去，这样Visual Studio的intellisense会让你在敲“(”的时候把参数名给你列出来，你看到了提示，有时候就不需要回去翻源代码了。

关于C语言的“定义和使用相一致”还有最后一个例子，这个例子也是很美妙的：

int a;
typedef int a;

int (*f)(int a, int b);
typedef int (*f)(int a, int b);

typedef是这样的一个关键字：他把一个符号从变量给修改成了类型。所以每当你需要给一个类型名一个名字的时候，就先想一想，怎么定义一个这个类型的变量，写出来之后往前面加个typedef，事情就完成了。

不过说实话，就一致性来讲，C语言也就到此为止了。至于说为什么，因为上面这几条看起来很美好的“定义和使用相一致”的规则是不能组合的，譬如说看下面这一行代码：

typedef int(__stdcall*f[10])(int(*a)(int, int));

这个时候我们再回头看一看上面那一段长长的函数指针数组变量的声明，会发现其实在这种时候，C语言还是希望你把它看成“int* b;”的这种形式的：f是一个数组，数组返回了一个函数指针，函数返回int，函数的参数是int(*a)(int, int)所以他还是一个函数指针。

我们为什么会觉得C语言在这一个知识点上特别的难学，就是因为他同时混用了两种原则来设计语法。那你说好的设计是什么呢？让我们来看看一些其它的语言的作法：

C++:
function<int __stdcall(function<int(int, int)>)> f[10];

C#:
Func<Func<int, int, int>, int>[] f;

Haskell:
f :: [(int->int->int)->int]

Pascal:
var f : array[0..9] of function(a : function(x : integer; y : integer):integer):integer;

这些语言的做法，虽然并没有遵守“定义和使用相一致”的原则，但是他们比C语言好的地方在于，他们只采用一种原则——这就比好的和坏的混在一起要强多了（这一点go也是，做得比C语言更糟糕）。

当然，上面这个说法对Haskell来说其实并不公平。Haskell是一种带有完全类型推导的语言，他不认为类型声明是声明的一部分，他把类型声明当成是“提示”的一部分。所以实际上当你真的需要一个这种复杂结构的函数的时候，实际上你并不会真的去把它的类型写出来，而是通过写一个正确的函数体，然后让Haskell编译器帮你推导出正确的类型。我来举个例子：

superApply fs x = (foldr id (.) fs) x

关于foldr有一个很好的理解方法，譬如说foldr 0 (+) [1,2,3,4]说的就是1 + (2 + (3 + (4 + 0)))。而(.)其实是一个把两个函数合并成一个的函数：f (.) g = \x->f(g( x ))。所以上述代码的意思就是，如果我有下面的三个函数：

add1 x = x + 1
mul2 x = x * 2
sqr x = x * x

那么当我写下下面的代码的时候：

superApply [sqr, mul2, add1] 1

superApply [(\x->x*x), (*2), (+1)] 1

Haskell代码的简洁程度真是丧心病狂啊，因为如果我们要用C++来写出对应的东西的话（C语言的参数无法是一个带长度的数组类型所以其实是写不出等价的东西的），会变成下面这个样子：

template<typename T>
T SuperApply(const vector<function<T(T)>>& fs, const T& x)
{
    T result = x;
    for(int i=fs.size()-1; i>=0; i--)
    {
        result = fs[i](result);
    }
    return result;
}

C++不仅要把每一个步骤写得很清楚，而且还要把类型描述出来，整个代码就变得特别的混乱。除此之外，C++还没办法跟Haskell一样吧三个函数直接搞成一个vector然后送进这个SuperApply里面直接调用。当然有人会说，这还不是因为Haskell里面有foldr嘛。那让我们来看看同样有foldr（reverse + aggregate = foldr）的C#会怎么写：

T SuperApply<T>(Func<T, T>[] fs, T x)
{
    return (fs
        .Reverse()
        .Aggregate(x=>x, (a, b)=>y=>b(a(y)))
        )(x);
}

C#基本上已经达到跟Haskell一样的描述过程了，而且也可以写出下面的代码了，就是无论声明和使用的语法的噪音稍微有点大……

SuperApply(new Func<T, T>[]{
    x=>x*x,
    x=>x*2,
    x=>x+1
    }, 1);

为什么要在讨论语法的一致性的时候说这些问题呢，在这里我想向大家展示Haskell的另一种“定义和使用相一致”的做法。Haskell整个语言都要用pattern matching去理解，所以上面的这段代码

superApply fs x = (foldr id (.) fs) x

superApply [(\x->x*x), (*2), (+1)] 1

(foldr id (.) [(\x->x*x), (*2), (+1)]) 1

(Point x y) + (Point z w) = Point (x+z) (y+w)
(+) (Point x y) (Point z w) = Point (x+z) (y+w)

(Point x y) `Add` (Point z w) = Point (x+z) (y+w)
Add (Point x y) (Point z w) = Point (x+z) (y+w)

斐波那契数列的简单形式甚至还可以这么写：

f 1 = 1
f 2 = 1
f (n+2) = f(n+1) + f(n)

甚至连递归都可以写成：

GetListLength [] = 0
GetListLength (x:xs) = 1 + GetListLength xs

Haskell到处都贯彻了“函数和操作符的替换关系”和“pattern matching”两个原则来做“定义和实现相一致”的基础，从而实现了一个比C语言那个做了一半的混乱的原则要好得多的原则。

有些人可能会说，Haskell写递归这么容易，那会不会因为鼓励人们写递归，而整个程序充满了递归，很容易stack overflow或者降低运行效率呢？在这里你可以往上翻，在这篇文章的前面有一句话“好的语言，除了库写起来又容易又好用以外，还有两个重要的特点：容易学，容易分析。”，这在Haskell里面体现得淋漓尽致。

我们知道循环就是尾递归，所以如果我们把代码写成尾递归，那Haskell的编译器就会识别出来，从而在生成x86代码的时候把它处理成循环。一个尾递归递归函数的退出点，要么是一个不包含自身函数调用的表达式，要么就是用自身函数来和其它参数来调用。听起来比较拗口，不过说白了其实就是：

GetListLength_ [] c = c
GetListLength_ (x:xs) c = GetListLength_ xs (c+1)
GetListLength xs = GetListLength_ xs 0

当你写出这样的代码的时候，Haskell把你的代码编译了之后，就会真的输出一个循环，从而上面的担心都一扫而空。

实际上，有很多性能测试都表明，在大多数平台上，Haskell的速度也不会被C/C++慢超过一倍的同时，要远比go的性能高出许多。在Windows上，函数式语言最快的是F#。Linux上则是Scala。Haskell一直都是第二名，但是只比第一名慢一点点。

为了不让文章太长，好分成若干次发布，每次间隔都较短，所以今天的坑我只想多讲一个——C++的指针的坑。剩下的坑留到下一篇文章里面。下面要讲的这个坑，如果不是在粉丝群里面被问了，我还不知道有人会这么做：

class Base
{
  ...
};

class Derived : public Base
{
  ...
};

Base* bs = new Derived[10];
delete[] bs;

我想说，这完全是C++兼容C语言，然后让C语言给坑了。其实这个问题在C语言里面是不会出现的，因为C语言的指针其实说白了只有一种：char*。很多C语言的函数都接受char*，void*还是后来才有的。C语言操作指针用的malloc和free，其实也是把他当char*在看。所以当你malloc了一个东西，然后cast成你需要的类型，最后free掉，这一步cast存在不存在对于free能否正确执行来说是没有区别的。

但是事情到了C++就不一样了。C++有继承，有了继承就有指针的隐式类型转换。于是看上面的代码，我们new[]了一个指针是Derived*类型的，然后隐式转换到了Base*。最后我们拿他delete[]，因为delete[]需要调用析构函数，但是Base*类型的指针式不能正确计算出Derived数组的10个析构函数需要的this指针的位置的，所以在这个时候，代码就完蛋了（如果没完蛋，那只是巧合）。

为了兼容C语言，“new[]的指针需要delete[]”和“子类指针可以转父类指针”的两条规则成功的冲突到了一起。实际上，如果需要解决这种问题，那类型应该怎么改呢？其实我们可以跟C#一样引入Derived[]的这种指针类型。这还是new[]出来的东西，C++里面也可以要求delete[]，但是区别是他再也不能转成Base[]了。只可惜，T[]这种类型被C语言占用了，在函数参数类型里面当T*用。C语言浪费语法罪该万死呀……

待续

上一篇文章对大部分文法都构造出了一个使用的状态机了，这次主要来讲右递归的情况。右递归不像左递归那么麻烦，因为大部分右递归写成循环也不会过分的让语法树变得难以操作，不过仍然有少数情况是我们仍然希望保留递归的语法树形状，譬如C++的连等操作，因此这里就来讲一下这个问题。

右递归是怎么形成的呢？在这里我们先不想这个问题，我们来看一个普通的文法。在上一篇文章我们已经说过了，如果一条文法有一个非终结符引用了另一条文法，那么就要做一条shift和reduce来从这个状态机穿插到那个状态机上：

在这里需要讲一下，绿色的箭头是shift，紫色的箭头是reduce，他们都是ε边。更进一步说，如果A刚好以B作为结尾，那么A的最后一个输入就不是终结符输入，不过因为她不是右递归，所以现在看起来还没什么问题：

我们已经接近右递归的形状了。右递归的一个根本特征当然是递归（废话）。为了制作一个右递归，我们可以想一下，如果A和B不是两个rule而是同一个rule会怎么样？当然咋这么一看，好像就是A可以访问自己了：

实际上这已经构成了一个ε边的循环。左递归是shift的循环，右递归是reduce的循环，其实他们都一样。那你可能会想，既然左递归和右递归只是相反的情况，为什么左递归处理起来就那么容易，右递归好像就没什么方法呢？其实如果你只是想要检查一个字符串是不是一个文法的其中一个元素而不建立语法树的话，你完全可以把这条循环的ε reduce边给压缩成一条。为什么呢？在之前讲到，我们可以判断一个reduce是不是由左递归造成的，我们也可以判断一个shift是不是由右递归造成的。这种shift只要不压状态进栈，那么右递归的reduce循环不管循环多少次，其实都是pop一个状态出来，于是问题就没有了。等价地，不处理语法树的话，其实左递归也可以用相同的方法处理。

但是一旦当你涉及到创建语法树的问题，你就等于给每一条边都加上了一些semantic actions。这个时候shift和reduce就不是简单地可以互相抵消的关系了，于是你就不能把一个循环的ε reduce边压缩成一条，那怎么办呢？

方法其实很简单，只要我们在状态机走着走着发现无路可走的时候，看看有没有一条右递归reduce可以给我们“试一试”就好了。为什么可以这样做呢？我们还记得，当我们把整个状态及压缩到没有ε边的时候，每一个输入都需要对堆栈的情况进行一次匹配。令人欣慰的事，没有什么边可以跟右递归的reduce边一样产生同样的匹配结构（但是我不想在这里证明），所以这样做是安全的。

到了这里，我们已经把构造不带lookahead状态机的所有情况都说清楚了。一个文法如果需要构造lookahead的话，其实就等于在边的匹配规则里面加上一条对未来的一些token的要求，并没有本质上改变语法分析的结构。但是我们知道，还有两种上下文无关文法是不在这里面的，C语言全占了。我在这里举两个简单的例子：

变量声明：对于一个已经typedef过的结构我们完全可以写出这样的代码：A*B;。这个时候A如果是类型，那这就需要走VariableDeclarationStatement的rule。如果A是一个表达式，那这就需要走ExpressionStatement的rule。但是对于语法分析来说，A就是一个简单的token（除了typedef过的类型以外，所有C语言的类型都是以关键字开头的，所以如果你们想做简单的C语言的parser，就去掉typedef吧，啊哈哈哈哈），在语法分析的时候是无法做出预测的。

这种时候有两种方法，第一种是准备更加丰富的semantic actions，让符号表可以在parse的时候构造出来。那到了这里，我们根据A究竟是不是一个类型，就可以赚到不同的分支上了。另一种就是，我们保留一个AmbiguousStatement的语法树节点，把语法树的一颗子树遇到的不能处理的歧义的情况都写进去。我们可能回想，为什么我们不干脆一个parser返回多个分析结果呢？因为如果不这么做的话，一个函数里面有10个这样子的变量声明，那你就有1024个结果了。如果我们把歧义收缩到一颗子树上，那其实还是1个结果，只是多了10颗子树，效果完全不同。

强制类型转换：写C语言的时候是不可能没有强制类型转换的，但是当parser看到类似这样的代码的时候：(A*****)B，因为类型的结构和表达式的结构是不一样的，但是你这个时候并不能在看到“(”的时候就做lookahead——因为这个lookahead是无限长的，括号里面的表达式或者类型都可以无限长。不过就算你想把他局限成有限长，就算你给100个token，那也会长出成千上万种lookahead的模式，所以在这里我们就不要用lookahead了。

那怎么做呢？我们只需要把这个状态机当成NDA（因为到了这里他已经是NDA了），从deterministic push-down automaton变成了non-deterministic push-down automaton，我们也唯有让我们的parser也变成non-deterministic了。关于这个内容，就等到下一篇——也就是这个系列的最后一篇文章——来详细讲解了。

一、

这篇文章是应之前在微博上爆过的下个周末某出版社的线下活动而写的。回顾我和C++在这个世纪的第二个春天开始发生过的种种事情，我发现我并不是用一个正常的方法来学会如何正常使用C++的。我的C++学习伴随着很多其他流行或者不流行的语言。现在手中掌握的很多淫荡的技巧正是因为学习了很多编程语言的缘故，不过这并不妨碍我正常地使用C++来在合理的时间内完成我的目标。

学习C++是一个艰难的过程。如果从我第一次看C++的书算起，现在已经过了11年了。一开始的动机也是很不靠谱的。刚开始我很喜欢用VB6来开发游戏，但是我能找到的资料都是用C++来做例子的，文字部分又不丰富，于是我遇到了很多困难。因此我去三联书店买了本C++的书，想着我如果学会了C++，就可以把这些例子翻译成VB6的代码，然后继续用VB6来写游戏。阴差阳错，我买到的是一本语法手册。不过那个时候我还小，不知道什么是MSDN，也不知道MSDN是可以打印出来卖的：

不过因为C++在当时并不是我学习的重点，于是我就没事的时候翻一翻。我们都知道语言参考手册（MSDN里面叫Language Reference）的顺序都是按照类别而不是教学顺序来排列的。于是当我花了很长时间看完了第一遍的时候，就觉得这本书写的云里雾里。刚开始讲什么是表达式的时候，例子就出现了大量的函数和类这种更加复杂的东西。于是我选择重新看一遍，基本的概念就都知道了。当然这个时候完全不能算“学会C++”，编程这种事情就跟下象棋一样，规则都很容易，但是你想要下得好，一定要通过长期的练习才能做到。

当然，在这段时间里面，我依然是一边看C++一边用VB6来学习编程。初二的时候学校发了QBasic的课本，当时看了一个星期就完全学会了，我觉得写代码很好玩，于是从此就养成了我没事逛书店的习惯（就连长大了之后泡MM也有时候会去书店，哈哈哈哈哈）。值得一提的是，我第二次去书店的时候，遇到了下面的这本书《Visual Basic高级图形程序设计教程》：

在这之前我买到的两本VB6的书都是在教你怎么用简单的语法，拖拖界面。然后就做出一个程序来。那个时候我心目中编程的概念就是写写记事本啊、写字板啊、计算器等等这些东西，直到我发现了这本书。我还记得当时的心情。我在书架上随手翻了翻，发现VB竟然也可以写出那么漂亮的图形程序。

这本书包含的知识非常丰富，从如何调用VB内置的绘图命令、如何调用Windows API函数来快速访问图片，讲到了如何做各种图像的特效滤镜、如何做几何图形的变换，一直到如何对各种3D物体做真实感渲染，甚至是操作4维图形，都讲得清清楚楚。这本书比其他大多数编程读物好的地方在于，读者可以仅靠里面的文字，基本不用看他的代码，就可以学会作者想让你学会的所有东西。因此当我发现我怎么着也找不到这本书的光盘（事实上书店就没有给我）的时候，我并没有感到我失去了什么。这本书的文字部分不仅写得很详细，而且作者还很负责任。作者知道像图形这种对数学基础有一定要求的东西，程序员不一定懂——尤其是我那个时候才上初中，就更不可能懂了——所以在书里面看到一些复杂的数学公式的时候，作者都会很耐心的告诉你这些公式的来源，它们的“物理意义”，有些时候甚至还会推导给你看。因此可以想象，这本书包含的内容也特别的丰富。这导致我在读的时候不断地找资料补充自己的数学知识，从而可以亲自把那些程序写（而不是抄）出来。这个过程一直持续到了我终于不用VB转Delphi，到最后上大学改用C++的那个时候，我终于理解了整本书里面讲的所有内容，给我后面的很多事情打下了坚实的基础。

因为数学知识缺乏的关系，学习这些基础知识又不可能那么快，所以我把一部分时间投入在了游戏开发里面，尝试自己弄点什么出来。毕竟当时对编程有兴趣，就是因为“说不定游戏也可以用代码写出来”的想法，于是我得到了下面的这本书：

这本书是我觉得21天惊天阴谋系列里面唯一一本良心的书。它并没有只是简单的罗列知识，而是教你利用VB6内置的功能搭建从简单到复杂的游戏程序。我第一次看到关于链表的知识就是在这里。可惜在我还没学会如何使用VB6的类模块功能之前，我就已经投向了Delphi，因此并没有机会实践这个知识。不过在此之后，我用VB6写的小游戏，已经尝试把游戏本身的模块（这是VB6的一个功能，就跟namespace差不多）分离，积累一些基础代码。

在这段时间里面，我学习语法都学得很慢。循环甚至是在我用人肉展开循环的方法一行一行复制黏贴出了一个井字棋的AI之后才学会的。后来很晚才学会了写函数，全局变量则更晚了。于是在那个时候我写了很多看起来很愚蠢的代码。曾经我以为一个函数的全局变量在退出函数之后是会保留的，然后对着自己写出来的不能运行的代码感到十分的莫名其妙。还有一次做一个记事本，因为不知道“当前文件路径”要存在什么地方，于是在界面上放了一个Label来放文件名。后来有了雄心壮志，想用VB搞定一个长得像Basic的超简陋的脚本。这当然最后是失败了，但是我依稀记得，我当时取得的成就就是把脚本语言的字符串分割成了一个一个的token之后，保存在了一个表格控件里面，以便之后（后来这个“之后”没写出来）读的时候方便一点。之后还尝试写一个读四则运算字符串计算结果的程序，都是先找最里层的括号，把那条不带括号的简单式子计算完之后，把结果也处理成字符串replace回去。直到整个字符串收敛成一个值为止。一直等到我后来买到了一本系统介绍VB6语法和用法的书之后，我的代码才稍微变得不像猴子打出来的。

在刚开始学编程的时候，基本上都没有什么固定的方向，都是在书店里面碰到什么酒写什么。于是有一次我在书店里看到了《Visual Basic 网络高级编程》

这本书是我在学习VB的过程中最后一本我觉得不错的书了。虽然VB本身也提供了很多访问网络资源的控件，但是这本书并没有让你仅仅会用被人的轮子来写代码，而是一步一步的告诉你这些网络协议的内容，然后让你用Socket来跟这些服务器直接交互。我记得我最后成功的做出了一个邮件收发程序，跟联想1+1系列自带程序的功能已经可以媲美了。

二、

当我发现C++实在是太难，根本没办法真的把网上那些C++的程序改成VB之后，我上了高一，接触了NOI。NOI让我得到的一个收获就是，让我在上了大学之后很坚定的不把时间浪费在ACM上，从而有了很多时间可以搞图形、编译器和女同学。参加高中的NOI培训让我知道了什么是数据结构，还有什么是指针。老师在讲Pascal的时候说，要灵活使用指针才可以写出高性能的程序。这让我大开眼界，不仅因为VB没有指针，而且当时用VB写图形的程序感觉怎么样也快不上去（当然这有大半原因是因为我代码写得烂，不能全怪VB）的同时，还让我认识了Delphi。Delphi跟VB一样可以拖控件，而且控件长得还很像。于是我就抱着试一试的心理，开始学习如何用Delphi来写代码。

因为有《Visual Basic 高级图形程序设计教程》的知识作为背景，我很快就掌握了如何用Delphi来开发跟图形相关的程序。那个时候我觉得该做的准备已经准备好了，于是用Delphi写了一遍我在VB的时候总是写不快的一个RPG游戏。这个游戏虽然不大，但是结构很完整。在开发这个游戏的过程中，我第一次体验到了模块化开发的好处，以及积累基础代码对开发的便利性。同时也让我尝到了一个难以维护的程序时多么的可怕。这个游戏前后开发了八个月，有一半的事件都是在写代码。对于当时的我来说，程序的结构已经过于复杂，代码也多到差不多失控的地步了。后来我统计了一下，一共有一万两千行代码。由于那个时候我的调试能力有限，而且也不知道如何把程序写成易于调试的形式。结果我等到了我的核心部分都写完了之后，才能按下F9做第一次的运行（！！！）。当然运行结果是一塌糊涂。我花了很大的努力才把搞到能跑。

由于程序本身过长，我在开发的过程中觉得已经很难控制了。再加上我发现我的同一个模块里的函数基本上都是下面的形式：
PrefixFunction(var data:DataStructure, other parameters ...)
总觉得跟调用Delphi的类库的时候很像。所以我就想，既然代码都变成了这样，那是不是学习面向对象开发会好一点？在这个过程中我有幸遇到了这本《Delphi6 彻底研究》：

虽然说这本书并没有包含那些深刻的面向对象的知识，但是他详细的介绍了Delphi的语法、基础的类库的用法还有Delphi那套强大的控件库和数据开发的能力。这本书第一次让我知道，Delphi是可以内嵌汇编代码的。这给我对计算机的深入理解打开了一扇门。

学习汇编是一个漫长的过程。这倒不是因为汇编的概念很复杂，而是因为里面的细节实在是太多了。这些知识靠网络上零星的文章实在是无法掌握，于是在常年逛书店的习惯之下，我又遇到了《Windows 汇编语言程序设计教程》。

这本书内容其实并不是很多，但是他给了我一个很好的入门的方法，也讲了一些简单的汇编的技巧，譬如说怎么写循环啊，怎么用REPZ这样的前缀等等，让我可以用汇编写出有意义的程序。汇编和Delphi的结合也促使我开始去思考他们之间的关系，譬如说一段Delphi的代码就经是如何映射到汇编上面的。下面发生的一个小故事让我印象深刻。

那还是一个，我还很喜欢各种不知所谓的奇技淫巧的日子。有一天我在论坛里看到有人说，交换两个integer变量可以用一种奇葩的写法：
a:=a xor b;
b:=b xor a;
a:=a xor b;
于是我就理所当然得想，如果我把它改成汇编，那是不是可以更快，并且超过那种需要中间变量的写法？后来我试了一次，发现慢了许多。这个事件打破了我对会变的迷信，当然什么C语言是最快的语言之类的，我从此也就以辩证的眼光去看带了。在接下来的高中生涯里，我只用了汇编一次，那还是在一个对图像做alpha blending的程序里面。我要同时计算RGB，但是寄存器每一个都那么大，我觉得很浪费，于是尝试用R<<16+G放到一个寄存器里面，跟另一个R<<16+G相加。中间隔了一个字节用来做进位的缓冲，从而达到了同时计算两个byte加法的效果。后来测试了一下，的确比直接用Delphi的代码来写要快一些。

纯粹的教程类书籍看多了之后，除了类库用得熟、代码写得多以外，好处并不大。所以当我有一天在书店里发现《凌波微步》的时候，刚翻开好几页，我就被它的内容吸引住了，断然入手。

这本书让我第一次觉得，一个程序写得好和写得烂竟然有如此之大的差别。作者下笔幽默，行文诙谐，把十几个例子用故事一般的形式讲出来。这本书不告诉你什么是好的，而告诉你什么是不好的。每一个案例的开头都给出了写得不好的代码的例子，然后会跟你解释的很清楚，说这么做有什么不好，改要怎么改的同时，为什么好的方法是长那个样子的。这本书也开始让我相信方法论的意义。在这个时候之前，我在编程这个东西上的理论基础基本上就只有链表和排序的知识，其它的东西基本都不懂，但是想做出自己想要做的事情却又不觉得有什么太大的麻烦。甚至我到高三的时候写了一个带指令集和虚拟机的Pascal脚本语言（不含指针）的时候，我连《编译原理》这本书都没有听过。因此以前觉得，反正要写程序，只要往死里写，总是可以写出来的。但是实际上，有理论基础和没有理论基础的程序员之间的区别，不在于一个程序能不能写出来，而在于写出来之后性能是不是好，代码是不是容易看懂的同时还很好改，而且还容易测试。这本书对于我的意义就是给我带来了这么一个观点，从而让我开始想去涉猎类似的内容。

当然，那段时间只是这么想，但是却不知道要看什么。所以在一次偶然之下，我发现了《OpenGL 超级宝典》。当然第一次看的时候还是第二版，后来我又买了第三版。

鉴于以前因为《Visual Basic 高级图形程序设计教程》的缘故，我在看这本书之前已经用Delphi写过一个简单的支持简单光照和贴图的软件渲染程序，于是看起来特别的快。其实OpenGL相比起DirectX，入门级的那部分API（指glBegin(GL_TRIANGLE_STRIP)这些）是做得比DirectX漂亮的，可惜性能太低，没人会真的在大型游戏里使用。剩下的那部分比DirectX就要烂多了。所以当我开始接触高级的API的时候，OpenGL的低速部分让我恋恋不舍。OpenGL的程序我一路写到了差不多要高考的时候。在那之前学习了一些简单的技巧。上了大学之后，学习了一些骨骼动画啊、LOD模型啊、场景管理这些在OpenGL和DirectX上都通用的知识，但是却并没有在最后把一个游戏给做出来。

我最后一次用OpenGL，是为了做一个自绘的C++GUI库。这个库的结构比起现在的GacUI当然是没法。当时用OpenGL来做GUI的时候，让我感觉到要操作和渲染字符串在OpenGL上是困难重重，已经难到了几乎没办法处理一些高级文字效果（譬如RichText的渲染）的地步了。最后只能每次都用GDI画完之后把图片作为一个贴图保存起来。OpenGL贴图数量有限，为了做这个事情还得搞一个贴图管理器，把不同的文字都贴到同一张图上。做得筋疲力尽之余，效果还不好。当我后来开发GacUI的时候，我用GDI和DirectX作为两个渲染器后端，都成功的把RichText渲染实现出来了，我就觉得我以后应该再也不会使用OpenGL了。GDI和DirectX才是那种完整的绘图API，OpenGL只能用来画图，写不了字。

有些人可能会觉得，为什么我会一直在同时做图形图像、编译器和GUI的事情。大家还记得上文我曾经说过我曾经用了好久做了一个伊苏那种模式的RPG出来。其实我一直都很想走游戏开发的路线，可惜由于各种现实原因，最后我没有把这件事情当成工作。做出那个RPG的时候我也很开心，丝毫不亚于我毕业后用C#写出了一个带智能提示的代码编辑器的那一次。当然在上大学之后我已经觉得没有一个美工是做不出什么好游戏的，但是想花时间跟你一起干的美工同学又很难找，因此干脆就来研究游戏里面的各种技术，于是就变成了今天这个样子。当然，现在开发游戏的心思还在，我想等过些时日能够空闲了下来，我就来忽悠个美工妹纸慢慢搞这个事情。

虽然说《Visual Basic高级图形程序设计教程》是一本好书，但这只是一本好的入门书，想要深入了解这方面的内容还是免不了花时间看其他材料的。后来我跟何咏一起做图形的时候，知识大部分来源于论文。不过图像方面，还是下面这本冈萨雷斯写的《数字图像处理》给了我相当多的知识。

这本书的特点是，里面没有代码，我很喜欢，不会觉得浪费钱。不过可惜的是在看完这本书之后，我已经没有真的去写什么图像处理的东西了。后面做软件渲染的时候，我也没有把它当成我的主业来做，权当是消磨时间。每当我找不到程序可以写觉得很伤心的时候，就来看看论文，改改我那个软件渲染器，增加点功能之后，我就会发现一个新的课题，然后把时间都花在那上面。

三、

整个高三的成绩都不错，所以把时间花在编程上的时候没人理我，直到我二模一落千丈，因此在高考前一个月只好“封笔”，好好学习。最后因为失误看错了题目，在高考的时候丢了十几分的原始分，估计换算成标准分应该有几十分之多吧，于是去了华南理工大学。所幸这本来就是我的第一志愿，所以当时我也不觉得有什么不开心的。去了华南理工大学之后，一个令我感到十分振奋的事情就是，学校里面有图书馆，图书馆的书还都不错。虽然大部分都很烂，但是因为基数大，所以总能够很轻松的找到一些值得看的东西。

我还记得我们那一年比较特殊，一进去就要军训。军训的时候电脑还没来得及带去学校，学校也不给开网络，所以那一个月的晚上都很无聊，跟同学也还不熟悉，不知道要干什么。所以那段时间每到军训吃晚饭，我就会跑到学校的图书馆里面泡到闭馆为止。于是有一天让我发现了李维写的这本《Inside VCL》。

虽然到了这个时候我用Delphi已经用得很熟悉了，同时也能写一些比较复杂的程序了，但是对于Delphi本身的运作过程我是一点都不知道。所以当我发现这本书的时候，如鱼得水。这本书不仅内容深刻，更重要的是写的一点都不晦涩难懂，所以我看的速度非常快。基本上每个晚上都可以看100页，连续七八天下来这本书就被我翻完了。这带来了一个副作用就是，图书馆的姐姐也认识我了——当然这并没有什么用。

过后我又在书店得到了一本《Delphi 源代码分析》。

这本书跟《Inside VCL》的区别是，《Inside VCL》讲的是VCL的设计是如何精妙，《Delphi 源代码分析》讲的则是Delphi本身的基础设施的内部实现的细节。以前我从来不了解也没主动想过，Delphi的AnsiString和UnicodeString是指向一个带长度记录的字符串指针，学习了指针我也没把这两者联系起来（当然这跟我当时还没开始试图写C++程序有关）。于是看了这本书，我就有一种醍醐灌顶的感觉。虽然这一切看起来都是那么的自然，让我觉得“就是应该这么实现的才对”，但是在接触之前，就是没有去想过这个事情。

令人遗憾的是，在我得到这本书的同时，Borland也把Delphi独立出来做了一个叫做Codegear的公司，后来转手卖掉了。我在用Delphi的时候还想着，以后干脆去Borland算了，东西做得那么好，在那里工作肯定很开心。我在高中的时候还曾经把Borland那个漂亮的总部的图片给我妈看过，不过她一直以为是微软的。于是我在伤心了两个晚上之后，看了一眼为了做参考我带到学校来的《Visual C++ 5.0语言参考手册》，找了一个盗版的Visual C++ 2005，开始决定把时间投入在C++上面了。于是Delphi之旅到此结束，从此之后，就是C++的时光了。

四、

学习图形学的内容让我学会了如何写一个高性能的计算密集型程序，也让我不会跟很多程序员一样排斥数学的内容。学习Delphi让我开阔了眼界的同时，还有机会让我了解Delphi内部工作原理和细节。这一切都为我之后做那些靠谱的编译器打下了基础。

因为在高三的时候我在不懂得《编译原理》和大部分数据结构的知识的情况下，用Delphi写出了一个Pascal脚本引擎，所以当我听说我大学的班主任是教编译原理的时候，我就很开心，去跟她交流这方面的内容，把我当时的设想也拿给她看。当然我的设想，没有理论基础的知识，都是很糟糕的，于是班主任就给了我一本《编译原理》。当然，这并不是《龙书》，而是一本质量普通的书。不过当我了解了这方面的内容之后，《龙书》的大名也就进入我的耳朵里了：

由于之前用很愚蠢的方法写了个Pascal脚本的缘故，看《龙书》之后很容易就理解了里面各种精妙的算法在工程上的好处。我之前的作法是先用扫描的方法切下一个一个的token，然后做一个递归来递归去复杂到自己都没法看的一遍扫描生成简单指令的方法来做。程序写出来之后我当场就已经看不懂了。自从看了《龙书》之后，我才知道这些过程可以用token和语法树来对算法之间进行解耦。不过《龙书》的性质也是跟《Visual Basic 高级图形程序设计教程》一样，是入门类的书籍。用来理解一下编译器的运作过程是没问题的，但是一旦需要用到高级的知识。

这个时候我已经初步理解了编译器前端的一些知识，但是后端——譬如代码生成和垃圾收集——却还是一知半解。不过这并不妨碍我用好的前端知识和烂的后端知识来做出一个东西来。当时我简单看了一下Java语言的语法，把我不喜欢的那些东西砍掉，然后给他加上了泛型。Java那个时候的泛型实现好像也是刚刚出现的，但是我不知道，我也从来没想过泛型要怎么实现。所以当时我想来想去做了一个决定，泛型只让编译器去检查就好了，编译的时候那些T都当成object来处理，然后就把东西做出来了。我本来以为我这种偷工减料拆东墙补西墙忽悠傻逼用户的方法是业界所不容的，不过后来发现Java竟然也是那么做的，让我觉得我一定要黑他一辈子。后来我用我做的这个破语言写了一个俄罗斯方块的游戏，拿给了我的班主任看，向她证明她拿给我的书我没有白看。

不过由于受到了Delphi的影响，我并没有在我的C++代码里面使用泛型。当时由于不了解STL，也懒得去看，于是自己就尝试折腾这么几个容器类自己用。现在代码还留着，可以给大家贴一段：

这段代码已经可以作为反面教材使用了。除了基类有一个virtual的析构函数和代码对齐的比较漂亮以外，基本所有的地方都是设计错误的典型表现。为了这段代码的贴图我特地在硬盘里面翻出来了我那个山寨Java脚本的代码，一打开就有一股傻逼的气息扑面而来，截图放进word之后，屏幕犹如溢屎，内容不堪入目。

之所以把代码写成这样，跟Delphi的class不是值类型的这个功能是分不开的。写了几年的Delphi之后，再加上第一次开始写有点小规模的C++程序，我从来没考虑过一个用来new的class是可以创建成值类型的。所以那个时候我一直处于用C++的语法来写Delphi的状态上。当然这样是不对的，但是因为那一段时间运气比较背，好的C++书都没给我碰上，直到我看到了《C++语言的设计和演化》

C++他爹写的这本《C++语言的设计和演化》是一本好书，我认为每一个学习C++的人都应该看。本来《C++Primer》也是一本不错的书，不过因为我阴差阳错用了《Visual C++ 5.0 语言参考手册》入门，所以这本书就被我跳过了。一开始C++用得很烂，觉得浑身不舒服，但是有知道为什么。看了这本书之后很多疑问就解决了。

《C++语言的设计和演化》讲的是当年C++他爹发明C++的时候如何对语言的各种功能做取舍的故事。在这个长篇小说里面，C++他爹不厌其烦地说，虽然C++看起来很鸟，但是如果不这样做，那就会更鸟。看完了这本书之后，基本上就剩下不会模板元编程了，剩下的语言的功能都知道在什么时候应该用，什么时候不该用。C++他爹还描述了一些重要的类——譬如说智能指针和STL的迭代器——在语义上的意思。其实这就跟我们在看待C++11的shared_ptr、unique_ptr和weak_ptr的时候，不要去想这是一个delete对象的策略，而是要想这是一个描述对象所有权关系的这么个“关键字”一样。有些时候细节看得太明白，而忽略了更高层次上的抽象，此乃见树木不见森林。

C++知道每一个特性如何正常使用还不够，如果不知道他们是如何实现的，那有可能在非常极端的情况下，写出来的程序会发挥的不好。正如同如果你知道C++编译器、操作系统和CPU内部是如何处理这些东西的细节，如果你顺着他们去写你的程序的话，那性能的提高会特别明显。譬如说在做渲染器的时候，为什么光线追踪要按照希尔伯特顺序来发射光线，为什么KD树可以把每一个节点压缩成8个字节的同时还会建议你按层来排列他们，都是因为这些背后的细节所致。这些细节做得好，渲染器的效率提高一倍是完全没问题的。这些知识固然很多，但是C++的那部分，却包含在了一本《深度探索C++对象模型》里面：

读《深度探索C++对象模型》，不仅仅是为了知道C++在涉及虚拟多重继承基类的成员函数指针结构是怎样的，而且你还可以从中学到很多技巧——当然是指数据结构的技巧。这本书的内容大概分为两个部分。第一个部分就跟需求一样，会跟你介绍C++的对象模型的语义，主要就是告诉你，如果你这样写，那你就可以获得XXX，失去YYY。第二部分就跟实现一样。按照需求来得到一个好的实现总是一个程序员想做的事情，那么这就是个很好的例子。正常使用C++需要的无限智慧，大部分就包含在上面这两本书里面。一旦把这两本书的内容都理解好，以后写起C++的代码都会得心应手，不会被各种坑所困扰，正确审视自己的代码。

文章之前的部分有提到过，让我正视理论和方法论的意义的是《凌波微步》，所以当工具都掌握的差不多的时候，总需要花时间补一补这方面的内容。首当其冲当然就是大家喜闻乐见的《算法导论》了。我记得当时是唐良同学推荐给我的这本书，还重点强调了一定要看原文，因为中文的翻译不行。所以我就在一个春光明媚的早上，来到了广州天河书城，把这本书搞到手。

这本书的封面颜色暗示着你，想读这本书， 应该去一个山清水秀绿荫环绕的地方。事实证明这是对的。在差不多考英语四级的前后，我有一段时间每天都去华南理工大学那个著名的分手亭看这本书。亭子后面是一个湖，前面有很多树和杂草，旁边还有一个艺术学院，充满了人文的气息。在这种地方看《算法导论》，不仅吸收得快，而且过了一年，我真的分手了。

说实话这本书我没有看完，而且那些证明的部分我都跳过了，实在是对这些东西没有兴趣。不过关于数据结构和大部分算法我看得很仔细。于是我在这方面的能力就大幅度提高——当然跟那些搞ACM的人相比反应还是不够快，不过我的志向并不在这里。除此之外，我通过《算法导论》也学到了如何准确的计算一个函数的时间复杂度和空间复杂度。事实证明这个技能十分重要，不仅可以用来找bug，还可以用来面试。

五、

对于一个读计算机的大学生来说，算法懂了，工具会了，接下来就是开眼界了。不过这些东西我觉得是没法强求的，就像下面这本《程序设计语言——实践之路》一样，都是靠运气才到手的——这是一个小师妹送我的生日礼物：

原本学习的汇编也好，VB、Delphi和C++也好，都是同一类的编程语言。这导致我在相当长的时间里面都无疑为编程就差不多是这个样子。直到我看到了《程序设计语言——实践之路》。这本书告诉我，这个世界上除了命令是语言，还有各种不同的编程的范式和方法。于是借着这本书的机会，我了解到世界上还有Prolog、Erlang和Haskell这么美妙的语言。

这对我的触动很大。一直以来我都是用一种编程方法来解决所有我遇到的问题的。然后突然有一天，我发现有很多问题用别的方法来解决更好，于是我就开始去研究这方面的内容。一开始我的认识还是比较浅，应用这些方法的时候还处于只能了解表面的状态，譬如说曾经流行过几天的Fluent Interface，还有声明式编程啊，AOP等等。直到我遇到了这本全面改变我对C++模板看法的书——《Real World Haskell》：

是的，你没看错，是《Real World Haskell》！Haskell颠覆了我的世界观，让我第一次知道，原来代码也是可以推导的。说实话我用Haskell用的并不熟，而且我也没写过多少个Haskell的大程序，但是Haskell的很多方面我都去花了很长时间去了解，譬如那个著名的Monad。多亏了当时搞明白了Monad，我借助这方面的知识，理解了《Monadic Parser Combinator》这篇论文，还看懂ajoo那篇著名的面向组合子编程系列。

当我终于明白了Haskell的类型推导之后，我终于体会到了Haskell和C++之间的巨大差异——Haskell的程序的逻辑，都是完全表达在函数签名上的类型里面，而不是代码里的。当你写一个Haskell函数的时候，你首先要知道你的函数是什么类型的，接下来你就把代码当成是方程的解一样，找到一个满足类型要求的实现。Haskell的表达式一环扣一环，几乎每两个部分的类型都互相制约，要求特别严格。导致Haskell的程序只要编译通过，基本上不用运行都有95%的概率是靠谱的，这一点其他语言远远达不到。而且Haskell的类库（Hackage）之多覆盖GUI、GPU程序、分布式、并发支持、图像处理，甚至是网页（Haskell Server Page）都有，用来写实用的程序完全没问题。之所以Haskell不流行，我觉得仅有的原因就是对初学者来说太难了，但是人们一旦熟悉了C的那一套，看Haskell的难度就更大了，比什么都不会的时候更大。

于是回过头来，模板元编程也就变成一个很自然的东西了。你把模板元编程看成是一门语言，把“类型”本身看成是一个巨大的带参数enum的一部分（scala叫case type），于是类型的名字就变成了值，那么模板元编程的技巧，其实就是对类型进行变换、操作和计算的过程。接下来只要会用模板的形式来表达if、while、函数调用和类型匹配，那掌握模板元编程是顺利成章的事情。撇去type traits这些只是模板元编程的具体应用不说，只要熟悉了Haskell，熟悉C++的模板语法，学会模板元编程，只需要一个下午——就是学会用蹩脚的方法来写那些你早就熟悉了的控制流语句罢了。

当模板元编程变成了跟写i++一样自然的东西之后，我看语言的感觉也变了。现在看到一个程序语言，再也不是学习与发这么简单了，而是可以看到作者设计这门语言的时候想灌输给你的价值观。譬如说，为什么C语言的typedef长那个样子的？因为他想告诉你，你int a;定义的是一个变量，那么typedef int a;就把这个变量的名字改成了类型的名字。为什么C语言定义函数的时候，参数是用逗号隔开？因为你调用函数的时候，也是用逗号来隔开参数的。这就是语法里面的一致性问题。一个一致性好的语言，一个有编程经验初学者只要学习到了其中的一部分，就可以推测他所想要的未知特性究竟是如何用于发表达出来的。一个一致性差的语言，你每一次学到一个新的功能或者语法，都是一个全新的形式，到处杂乱无章，让人无可适从（所以我很讨厌go，还不把go的library移植成C++直接用C++写算了）。

从此之后，我就从一个解决问题的程序员，变成一个研究编程本身的程序员了。当然我并不去搞什么学术研究，我也不打算走在理论的前沿——这并不适合我，我还是觉得做一个程序员是更快乐一点的。这些知识在我后续学习开发编译器和设计语言的时候，起了决定性的作用。而且当你知道如何设计一个优美的语法，那么你用现有的语法来设计一个优美的library，也就不会那么难了。当然，设计优美的library是需要深入的了解正在使用的语言本身的，这样的话有可能维护这个library的门槛就会提高。不过这没有关系，这个世界上本来就有很多东西是2000块钱的程序员所无法完成的，譬如维护STL，维护linux内核，甚至是维护Microsoft Office。

六、

上面所列出来的书，每一本都是对我有深刻的影响的。当然光有深刻的影响是不够的，具体的领域的知识，还是需要更多的资料来深入研究，譬如说下面的一个单子，就是我在学习开发编译器和虚拟机的时候所看过的。内容都很深刻，很适合消磨时间。在这里我要感谢g9yuayon同学，他在我需要开阔眼界的时候，给我提供了大量的资料，让我得以快速成长，功不可没。

虚拟机——系统与进程的通用平台

Garbage Collection——Algorithms for Automatic Dynamic Memory Management

高级编译器设计与实现（鲸书）

程序设计语言理论基础

类型与程序设计语言

Parsing Techniques——A Practical Guide

The Implementation of Functional Programming Languages

今天我写了一个给Visual C++用的配置，用来让VC++在显示自己写的字符串和容器等设施变得跟显示STL一样漂亮。VC++的可配置型还是很高的，我们只要写一个xml，就可以改变调试器对自己的数据结构的显示了.

在这里我简单地介绍一下用法。假设大家觉得vlpp（Vczh Library++，也就是GacUI用的那个库）的WString啊List这些东西在调试器里面显示出来的东西太丑，就可以用以下三步来修改它。

1：去http://gac.codeplex.com/SourceControl/changeset/view/99419#2395529下载我写的那个natvis文件。这个文件在整个zip包里面的位置是Common\vlpp.natvis
2：把这个文件复制到C:\Program Files (x86)\Microsoft Visual Studio 11.0\Common7\Packages\Debugger\Visualizers（如果使用默认安装路径的话）
3：重启你最喜爱的Visual Studio 2012，就可以看到下面的东西了：

空的智能指针

有东西的智能指针

有内容的“惰性计算”类

有内容但是还没计算的“惰性计算”类

没内容的“惰性计算”类

新鲜热辣的容器

新鲜热辣的映射

就连一对多的映射也是如此的新鲜热辣

List<Nullable<vint>>的互相嵌套也是如此的完美

如果大家想写自己的Customized Visualizer的话，可以去参考微软良心提供的文档http://msdn.microsoft.com/en-us/library/vstudio/jj620914.aspx，然后按照上面的步骤写自己的natvis文件。在这里我把我的natvis贴上来，以供参考：

<?xml version="1.0" encoding="utf-8"?>
<AutoVisualizer xmlns="http://schemas.microsoft.com/vstudio/debugger/natvis/2010">

  <Type Name="vl::ObjectString&lt;wchar_t&gt;">
    <DisplayString>{{ size={length}, buffer={buffer+start,su} }}</DisplayString>
    <StringView>buffer+start,su</StringView>
    <Expand>
      <Item Name="[size]">length</Item>
      <ArrayItems>
        <Size>length</Size>
        <ValuePointer>buffer+start</ValuePointer>
      </ArrayItems>
    </Expand>
  </Type>

  <Type Name="vl::ObjectString&lt;char&gt;">
    <DisplayString>{{ size={length}, buffer={buffer+start,s} }}</DisplayString>
    <StringView>buffer+start,s</StringView>
    <Expand>
      <Item Name="[size]">length</Item>
      <ArrayItems>
        <Size>length</Size>
        <ValuePointer>buffer+start</ValuePointer>
      </ArrayItems>
    </Expand>
  </Type>

  <Type Name="vl::collections::List&lt;*,*&gt;">
    <AlternativeType Name="vl::collections::SortedList&lt;*,*&gt;"/>
    <AlternativeType Name="vl::collections::Array&lt;*,*&gt;"/>
    <DisplayString>{{ size={count} }}</DisplayString>
    <Expand>
      <Item Name="[size]">count</Item>
      <ArrayItems>
        <Size>count</Size>
        <ValuePointer>buffer</ValuePointer>
      </ArrayItems>
    </Expand>
  </Type>

  <Type Name="vl::collections::Dictionary&lt;*,*,*,*&gt;">
    <AlternativeType Name="vl::collections::Group&lt;*,*,*,*&gt;"/>
    <DisplayString>{{ size={keys.count} }}</DisplayString>
    <Expand>
      <Item Name="[size]">keys.count</Item>
      <Item Name="Keys">keys</Item>
      <Item Name="Values">values</Item>
    </Expand>
  </Type>

  <Type Name="vl::Ptr&lt;*&gt;">
    <AlternativeType Name="vl::ComPtr&lt;*&gt;"/>
    <DisplayString Condition="reference == 0">[empty]</DisplayString>
    <DisplayString Condition="reference != 0">{*reference}</DisplayString>
    <Expand>
      <Item Condition="reference != 0" Name="[ptr]">reference</Item>
    </Expand>
  </Type>

  <Type Name="vl::Lazy&lt;*&gt;">
    <DisplayString Condition="internalValue.reference == 0">[empty]</DisplayString>
    <DisplayString Condition="internalValue.reference != 0 &amp;&amp; internalValue.reference->evaluated == false">[not evaluated]</DisplayString>
    <DisplayString Condition="internalValue.reference != 0 &amp;&amp; internalValue.reference->evaluated == true">{internalValue.reference->value}</DisplayString>
    <Expand>
      <Item Condition="internalValue.reference != 0 &amp;&amp; internalValue.reference->evaluated == true" Name="[value]">internalValue.reference->value</Item>
    </Expand>
  </Type>

  <Type Name="vl::ObjectBox&lt;*&gt;">
    <DisplayString>{object}</DisplayString>
    <Expand>
      <ExpandedItem>object</ExpandedItem>
    </Expand>
  </Type>

  <Type Name="vl::Nullable&lt;*&gt;">
    <DisplayString Condition="object == 0">[empty]</DisplayString>
    <DisplayString Condition="object != 0">{*object}</DisplayString>
    <Expand>
      <ExpandedItem Condition="object != 0">*object</ExpandedItem>
    </Expand>
  </Type>

</AutoVisualizer>

本来每年都要写一篇年经帖来提高一下知名度的，但是最近因为做GacUI太兴奋，竟然把这件事情给忘了，实在是罪过。

如果要说我2012年做过的什么事情最重要，那当然要属开发了GacUI（Home Page, Codeplex, Github）和创建了粉丝群（啊哈哈）了吧。博客到现在还有三个坑没填完，分别是那个已经坑了好久、大家都要看、但是我却不知道要写什么的《C++使用技巧》，还有两个大家不怎么想看的《可配置语法分析器开发纪事》和《GacUI与设计模式》。

关于GacUI，我已经在微博上做了许多广告，也有一些人开始尝试使用它了。目前GacUI还处于一个凑合着能用的beta状态，我在接下来的很长一段时间内应该会继续update它。我的本意是要把WPF那么精妙的设计给山寨到C++上面来，从而结束非得用MFC才能正常开发GUI的日子。而且因为之前我用C#的WinForm开发IDE太蛋疼了，parser需要写两遍（编译器一遍，IDE一遍，语言还不一样），所以我在设计GacUI的时候，质量要求就是朝着Visual Studio看齐的。所以大家会看到我在做GacUI的时候，文本框就内置了高速的着色系统，还做了一个新的parser来产生严格的parser或者松散的parser，分别给编译器和IDE使用。然后我用这个parser写了一个xml和json的库，最后在昨天还update了一下Linq to C++，把我看得不顺眼的东西都干掉，于是我也拥有了一个Linq to Xml for C++的库了。

但是GacUI还是有很多东西要做。我脑子里一直有一个清晰的路线图，而且这个路线图是直接朝着目标前进的：做一个C++的GUI库，顺便给一个类似Expression Blend那样子的东西，然后那个框架还可以为我以后开发语言，或者给现有的语言做IDE。所以为了达到这个目标，我至少要给GacUI的控件和对象模型做反射。为了让大家可以使用，我还得准备一个看起来跟MSDN很像的文档。因此路线图就是（粗体的部分已经完成了）

1. 开发控件库
2. 拥有一套生成Release的工具链，包括parser生成器、文档生成器、各种代码生成器等
3. 有一个小巧玲珑简单好用的XML库
4. 可以读PDB把GacUI的对象声明都拿到手
5. 利用PDB和GacUI的源代码里面的XML注释生成文档
6. 用一个类似C#那样子的语法来给GacUI“声明”一个对象模型，让他可以被反射，也可以用来生成各种语言用的接口，特别是动态语言例如javascript和python的
7. 把PDB的内容和对象模型结合起来，生成C++用的反射代码
8. 利用反射代码，设计一个GUI的XML（或者别的什么东西）表示，从而实现动态加载窗口
9. 制作一个长得和操作模式都跟Visual Studio差不多的多文档编辑框架
10. 用上面的框架开发一个GUI编辑器，用来拖控件生成xml+资源，就可以嵌入C++的exe，或者提供给脚本语言使用了
11. 提供一个脚本语言，作为可选的插件，来简化复杂GUI的开发
12. 给这个语言提供一个IDE

大家可以看到，这就是为什么我最近要花时间做着色、parser生成器、用parser生成器来生成xml和json的库的parsing部分、做一个linq to C++并且让xml库直接支持就像C#的linq to xml一样。虽然看起来这些东西跟GacUI本身毫无关系，但是实际上为了实现那个复杂又得自动生成不然写到孩子出来还人肉不完的反射代码生成，一定要有配套的基础设施才行。

关于粉丝群，因为我加入的大部分编程区最后都瘪了，所以本来我并没有创建一个群用来交流技术的想法。不过因为某群友说找不到人研究我以前的代码的一篇回复，我还是创建了这个群。本来群只有100人的，但是有两个人赞助了一下，瞬间变成了500人群。所以以后不断的有人进来的时候我就再也不需要踢掉不说话的人了。很快群里就开始热烈的讨论起问题，经常讨论的那么十几二十个人也这么固定下来了。这个群和别的群不一样的地方在于，所有问傻逼问题和求大作业的全部被我和鹳狸猿们一个不留的干掉了，啊哈哈哈哈。

由于我在cppblog广告的关系，加入这个群的人大部分还是做C++的，和S1那群做web的平时跟技术有关的话题完全不同，对待某些人生底线问题（譬如说大括号要不要换行等）的态度也是完全不同。当然偶尔有人经不住每天几千个消息的冲击退群了，但是群的热烈程度还是一点也没有消减。

关于C++实用技巧，由于我自诩是一个做C++基础类库的人，对待C++各种奇技淫巧的态度自然也是不一样的。尽管大家都说C++学起来很难，坑很多，模板根本看不懂，析构函数没写程序函数经常要烂掉之类的，不过我的观点还是很明确的——其实C++有很多难以理解的功能，都是给写基础类库准备的。只要程序员们不要本着“我一定要看懂类库怎么写才用”的这种无聊观点的话，其实压力并不会那么大。大多数人觉得C++难，但其实难的部分他做项目大概也是用不上的，本质原因还是不够淡定导致。

说到这里我就想起了以前跟人家讨论的，为什么C#用起来就那么舒服呢？很重要的一点其实是，因为选择少，所以连烦恼都没有了。反正事情都能完成，但是方法只有一种的话，你永远都不需要去比较或者纠结说，究竟要用什么样的方法来实现。而且一个自带垃圾收集器+泛型+函数式编程+continuation的语言，语法懂得少也可以用，语法懂得多用起来还特别省事，这一点的确比C++要好得多。回想起2002在CSDN那个著名的对垃圾收集器的大讨论，ajoo有一点说得很好，有没有GC，设计出来的架构都大不一样。想想原因其实也很简单，语言一旦带有GC的话，通常都会对内存做出严格的控制，因此你想干掉一个对象就只有一种方法——等他去死了（C#的IDisposable跟这个其实没什么关系）。因此那些C++里面很执着的谁创建谁删除啊，COM的什么引用计数啊，这些乱七八糟的东西统统就没有了。你可以不顾一起的创建各种细粒度对象，不断地创建各种接口，而根本不用担心这些对象在死的时候你要干些什么，不仅做出来的设计干净，用起来也省心。

关于可配置语法分析器开发纪事，按照计划还剩下两篇，不过因为这两篇的内容已经不怎么重要，所以最近的时间都用在开发GacUI上面了。等杂事搞完了之后我就补上这部分内容。

关于GacUI与设计模式，这个系列自从写了两篇文章之后，尽管GacUI都是我一手写出来的，但是我发现要整理出那个架构清楚的表达出来，需要花很多的时间。为了保证文章的质量，我干脆就暂时停下来了，一边推进GacUI的开发进度，一边 重新整理。虽然我从来都只用VC++来编译我的代码，不过GacUI从一开始设计架构上就有考虑跨平台的问题，而且我也把对Windows.h的依赖也局限在少数的几个cpp文件里，头文件则完全是没有污染的。尽管代码里面肯定有VC++对标准作出的一点点人性化修改而垃圾GCC故意不支持从而造成代码不能再GCC上面编译，不过在计划上我大概会在今年的下半年开始把代码修改成让垃圾GCC也可以编译GacUI了。

关于2013年，出去开发GacUI和心目中的那个脚本引擎，我在2013年最想点的技能树就是编译器的后端知识了。尽管我在09年的时候做过一个傻逼C语言编译器，尽管也是编译成机器码，但是都是用最简单粗暴的方法来做的。为了以后的脚本引擎，把这件事情做好，掌握编译器的后端也就变成必要的事情了。不过我在这里还是想说，编译器的前端知识也是很重要的。经过设计语言的语法的训练，和对设计类型系统的训练，不仅可以提高数学知识、提高智商，还可以让你学习新的语言和类库变得更快。编程都是举一反三的，并不是直接的针对他学习才是长远看来最好的方法。

上一篇博客写到了如何给一个非终结符的文法规则构造出一个压缩过的下推状态机，那么今天说的就是如何把所有的文法都连接起来。其实主要的idea在（三）和他的勘误（三点五）里面已经说得差不多了。但是今天我们要处理的是带信息的transition，所以还有一些地方要注意一下。

所以在这里我们先把几条文法的最后的状态机都列出来（大图）：

接下来的这一步，就是要对所有靠非终结符（Exp啊Term这些）进行跳转的transition都执行上一篇文章所说的传说中的交叉链接。在产生链接的时候，我们给shift和reduce的边分别加上shift和reduce。而shift和reduce是有参数的——就是被shift走的状态的id。这样可以在parse的时候匹配和处理状态堆栈。在这里我门对e3->e1这一步做一下操作做为例子。红色的边是被删掉的，而粗壮的绿色边是被新加进去的：

红色的边变成了两条绿色的边，红色的边附带的信息则被复制到了绿色的reduce边上。当我们使用这个状态机的时候，shift(s3)就表示往堆栈里面压入s3，reduce(s3)就表示从堆栈里面弹出(s3)。当然弹出不一定会成功，所以如果不成功的话，这条边就不能在当时使用。因此这也就是为什么在e3跳转到t0之后，t1知道往回跳的是e1而不是别的什么地方——就如同为什么C++的函数执行完之后总是知道如何跳转回调用它的地方一样——因为把信息推入了堆栈。

那现在我们就来看一下，当所有的非终结符跳转都处理掉之后，会变成什么样子吧（这个图真是复杂和乱到我不想画啊），为了让图变得不那么糟糕，我把shift都变成紫色，reduce都变成绿色：

在添加shift和reduce边之前，每一条边都是有输入token的。但是我们刚刚添加上去的shift和reduce边却是不输入token的，所以他们是epsilon边，下一步就是要消除他们。上面这个图消除了epsilon边之后，会变成一个状态很少，但是每一条边附带的信息都会非常多，而且像n1这种经常到达的状态（因为四则运算里面有很多数字）将恢复射出无数条边。到了这里这个状态机已经再也画不出来了。所以我下面就只拿两个例子来画。下面要展示的是用Exp来parse单独的一个数字会走的边，当然就是Exp –> Term –> Factor –> Number了：

就会被处理成：

注意边上面的信息是要按顺序重新叠加在一起的。当所有的epsilon边都去掉了之后，我们就得到了最终的一个状态机。最重要的一件事情出现了。我们知道，发明LR和LALR这种东西就基本上是为了处理左递归的，所以这种图就可以在去除epsilon边的过程中自动发现左递归。这是怎么做到的呢？只要在去除epsilon边的时候，发现了一条完全由shift这种epsilon边组成的环，那么左递归就发现了。为了方便，我们可以只处理直接左递归——就是这种环的长度是1的。不包含间接左递归的问法是很容易写出来的。当然这种环并不一定是首尾相接的，譬如说我们在处理e0的时候就会发现e0->t0->t0这种环（当然严格来说环只有最后一截的这个部分）。我们的程序要很好地应对这种情况。因为我们只接受直接左递归，所以类似这种结构的epsilon路径可以直接的抛弃他，因为t0->t0会被t0状态单独处理掉。因此这样做并不会漏掉什么。

细心的朋友可能会发现，这个结构的图是不能直接处理右递归的（总之左递归和右递归总要有一个会让你的状态机傻逼就是了！）。关于如何处理有递归（其实内容也不复杂）地方法会在“下篇”描述出来。那处理左递归有什么用呢？举个例子，我们的e0->e2就是一个左递归，而他会在之前的步骤被处理成shift(e0->e0)和reduce(e1->e2)。我们要记下shift和reduce的对应关系，那么当我们找到一个左递归的shift之后，我们就可以把对应的reduce给标记成“left-recursive-reduce”。这是一个在构造语法树的时候，非常关键的一种构造指令。

处理完这些之后，我们可以把左递归的shift边全部删掉，最后把token和state都统统处理成连续的数字，做成一张[state, token] –> [transitions]的二维表，每一个表的元素是transition的列表。为什么是这样呢？因为我们对一个state输入一个token之后，由于保存着state的堆栈（你还记得吗？shift==push，reduce==pop）的栈顶若干个元素的不同，可能会走不通的路线。于是最后我们就得到了这么一张图。

下面这张图可以通过运行gac.codeplex.com上面的Common\UnitTest\UnitTest.sln（VS2012限定）之后，在Common\UnitTest\TestFiles\Parsing.Calculator.Table.txt里面找到。这一组文件都是我在测试状态机的时候log下来的。

如果大家有VS2012的话，通过运行我准备的几个输入，譬如说“1*2+3*4”，就可以在Parsing.Calculator.[2].txt里面找到所有状态跳转的轨迹。因为我们总是需要parse一个Exp，所以我们从22: Exp.RootStart开始。我们假设token stream的第一个和最后一个分别是$TokenBegin和$TokenFinish。上图的$TryReduce是为了应对右递归而设计出来的一种特殊输入。由于四则运算里面并没有右递归，所以这一列就是空的：

StartState: 22[Exp.RootStart]
$TokenBegin => 23[Exp.Start]
    State Stack:
NUMBER[1] => 2[Number.1]
    State Stack: 23[Exp.Start], 21[Term.Start], 19[Factor.Start]
    Shift 23[Exp]
    Shift 21[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
MUL[*] => 5[Term.3]
    State Stack: 23[Exp.Start]
    Reduce 19[Factor]
    Using
    Reduce 21[Term]
    Using
    LR-Reduce 21[Term]
    Assign firstOperand
    Setter binaryOperator = Mul
    Create BinaryExpression
NUMBER[2] => 2[Number.1]
    State Stack: 23[Exp.Start], 5[Term.3], 19[Factor.Start]
    Shift 5[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
ADD[+] => 10[Exp.3]
    State Stack:
    Reduce 19[Factor]
    Using
    Reduce 5[Term]
    Assign secondOperand
    Reduce 23[Exp]
    Using
    LR-Reduce 23[Exp]
    Assign firstOperand
    Setter binaryOperator = Add
    Create BinaryExpression
NUMBER[3] => 2[Number.1]
    State Stack: 10[Exp.3], 21[Term.Start], 19[Factor.Start]
    Shift 10[Exp]
    Shift 21[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
MUL[*] => 5[Term.3]
    State Stack: 10[Exp.3]
    Reduce 19[Factor]
    Using
    Reduce 21[Term]
    Using
    LR-Reduce 21[Term]
    Assign firstOperand
    Setter binaryOperator = Mul
    Create BinaryExpression
NUMBER[4] => 2[Number.1]
    State Stack: 10[Exp.3], 5[Term.3], 19[Factor.Start]
    Shift 5[Term]
    Shift 19[Factor]
    Assign value
    Create NumberExpression
$TokenFinish => 11[Exp.RootEnd]
    State Stack:
    Reduce 19[Factor]
    Using
    Reduce 5[Term]
    Assign secondOperand
    Reduce 10[Exp]
    Assign secondOperand

我们把所有跳转过的transition的信息都记录下来，就可以构造语法苏了。我们想象一下，在执行这些指令的时候，遇到NUMBER[4]就等于获得了一个内容为4的token，shift的话就是往堆栈里面push进一个状态的名字，而reduce则是弹出。

相对应的，因为每一个文法都会创建一个对象，所以我们在初始化的时候，要先放一个空对象在堆栈上。shift一次就再创建一个空的对象push进去，reduce的时候就把栈顶的对象弹出来作为“待处理对象”，using了就把待处理对象和栈顶对象合并，left-reduce就是把栈顶对象弹出来作为待处理对象的同时，push一个空对象进去。assign fieldName就是把“待处理对象”保存到栈顶对象的叫做fieldName的成员变量里面去。如果栈顶对象为空，那么被保存的对象就是刚刚输入的那个token了。因此我们从头到尾执行一遍之后，就可以得到下面的一颗语法树：

BinaryExpression {
    binaryOperator = [Add]
    firstOperand = BinaryExpression {
        binaryOperator = [Mul]
        firstOperand = NumberExpression {
            value = [1]
        }
        secondOperand = NumberExpression {
            value = [2]
        }
    }
    secondOperand = BinaryExpression {
        binaryOperator = [Mul]
        firstOperand = NumberExpression {
            value = [3]
        }
        secondOperand = NumberExpression {
            value = [4]
        }
    }
}

基本上parsing的过程就结束了。在“下篇”——也就是（六）——里面，我会讲述如何处理右递归，然后这个系列基本上就要完结了。