其實(shí)我在寫這個(gè)系列的第三篇文章的時(shí)候就已經(jīng)發(fā)現(xiàn)，距離機(jī)器越遠(yuǎn)，也就是抽象越高的概念，坑的數(shù)量是越少的。但是這并不是說，距離機(jī)器越近的概念就越強(qiáng)大或者說越接近本質(zhì)。這是廣大的程序員對(duì)計(jì)算理論的一種誤解。大多數(shù)人理解編程的知識(shí)結(jié)構(gòu)的時(shí)候，都是用還原論來理解的，這個(gè)方法其實(shí)并沒有錯(cuò)。但問題在于，“還原”的方法并不是唯一的。很多人覺得，反正你多高級(jí)的語言編譯完了無非都是機(jī)器碼嘛。但是還有另一種解釋，你無論多低級(jí)的語言編譯完了無非也就是帶CPS變換（continuation passing style）的λ-calculus程序嘛。他們是等價(jià)的，不僅能力上也是，“本質(zhì)”上也是。

一個(gè)用CPS變換完整地處理過的λ-calculus程序長的就很像一串指令。而且類似于C++的inline操作，在這里是完全自然、安全、容易做的。那其實(shí)為什么我們的機(jī)器不發(fā)明成這樣子呢？顯然這完全跟我們想如何寫一個(gè)程序是沒關(guān)系的。正是這種沖突讓我們有一種“概念距離機(jī)器越遠(yuǎn)運(yùn)行速度就越慢”的錯(cuò)誤的直覺。扯遠(yuǎn)了講，就算你在用一門函數(shù)式語言，譬如說Haskell也好，F(xiàn)#也好，最終在運(yùn)行的時(shí)候，還是在運(yùn)行徹底編譯出來的機(jī)器碼。這些語言是完全不需要“模擬器”的，雖然由于各種歷史原因人們首先開發(fā)了模擬器。當(dāng)然一個(gè)精心設(shè)計(jì)過的C程序肯定還是要比haskell快的，但是我覺得能這么干的人不多，而且大多數(shù)時(shí)候這么干都是在浪費(fèi)老板的錢而已，因?yàn)槟銈兊某绦蛟揪筒恍枰斓侥欠N份上。這種東西就跟那些做互聯(lián)網(wǎng)對(duì)于測試的想法是一樣的——有bug？發(fā)現(xiàn)了再說，先release搶市場。

如果對(duì)這方面有了解的話，CPS變換——也就是Lost In Stupid Parentheses-er們最喜歡的call-with-current-continuation，他的另一個(gè)名字叫call/cc——是一種跟goto一樣強(qiáng)大而且基本的控制流的做法。goto和CPS可以互相轉(zhuǎn)換不說了，所有其它控制流都可以轉(zhuǎn)換成goto和CPS。它們兩者在這方面是不相上下的。而且既然一個(gè)完全用CPS變換處理過的程序長得就像一串指令，那你說他們的區(qū)別是什么呢？區(qū)別就是，CPS可以是強(qiáng)類型的，而goto則永遠(yuǎn)都不可能。

作為廢話的最后一段，我給個(gè)小例子來講什么叫“一個(gè)用CPS變換完整地處理過的λ-calculus程序長的就很像一串指令”。就讓我們用a(b( x ), c( x ))這樣的一個(gè)表達(dá)式來講：
處理前：

a (b x) (c x)

處理后：

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

用我們熟悉到不能再熟悉的Haskell的Monad的手法來翻譯一下其實(shí)就是：

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

好了，至于上面這種形式（看起來很像SSA）是怎么被做成機(jī)器碼的，大家自己去看編譯原理吧。上面這么多廢話就是想表達(dá)一個(gè)結(jié)論：抽象并不意味著負(fù)擔(dān)。當(dāng)然，至于對(duì)程序員的智商上的要求，對(duì)某些人也是一種負(fù)擔(dān)，這個(gè)我就沒辦法了，所以就不考慮他了。

===============廢話結(jié)束================

模板也是這類抽象的一種。為什么我要把標(biāo)題寫成“坑”，只是想跟前面統(tǒng)一一下而已，其實(shí)到了模板這么高級(jí)的抽象的時(shí)候，基本上已經(jīng)沒什么坑了。當(dāng)然C++的做法就另當(dāng)別論了，而且我想那些坑你們大概一輩子也碰不到的了。那我們先從簡單的講起。

比模板更簡單的東西自然就是泛型了。為什么叫他泛型？因?yàn)榉盒蛯?shí)際上就是一種復(fù)制代碼的方法，它本身是沒有推導(dǎo)能力的，所以肯定談不上什么模板了。但是在大多數(shù)情況下，泛型這么弱的抽象也已經(jīng)基本夠用了。跟泛型相關(guān)的手法大約有三個(gè)。

第一個(gè)就是定義一個(gè)返回一個(gè)類的函數(shù)（在這里參數(shù)是T）：

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

第二個(gè)就是，調(diào)用這個(gè)函數(shù)，參數(shù)給他類型，幫我們new一個(gè)類的實(shí)例：

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

這其實(shí)有兩步。第一步是對(duì)函數(shù)調(diào)用Array<int>求值得到一個(gè)T，然后對(duì)new T(10)進(jìn)行求值獲得一個(gè)對(duì)象。只是剛好Array<int>的返回值也叫Array<int>，所以比較混淆視聽。

事情到這里還沒完。上一篇文章中我們講到，寫一個(gè)類是要考慮很多contract的問題的。所以Array<T>是個(gè)什么東西呢？他至少是一個(gè)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;}
}

于是有一天我們構(gòu)造了一個(gè)Array<Array<string>>的對(duì)象，然后要寫一個(gè)函數(shù)來處理他。這個(gè)函數(shù)做的事情很簡單，就是把這個(gè)二維的數(shù)組給平攤成一個(gè)一維的數(shù)組，里面所有的數(shù)組頭尾相接起來。于是根據(jù)上一篇文章的內(nèi)容，我們寫一個(gè)接受class的函數(shù)，也是要想很多contract的問題的（面向?qū)ο缶褪锹闊┌。＿@個(gè)函數(shù)需要的只是遍歷的功能，那我們完全沒有必要要求他必須是一個(gè)Array，于是我們的函數(shù)就這么寫：

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

或者你也可以用高級(jí)一點(diǎn)的寫法，反正是一樣的：

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還是一個(gè)特別適合寫callback的語言呢，結(jié)果沒有$await，你們只能把一個(gè)好好的程序?qū)懗梢恢Щ鸺恕?/p>

那現(xiàn)在問題來了。當(dāng)我們想把Array<Array<string>>傳給Flatten的時(shí)候，我們發(fā)現(xiàn)Flatten的參數(shù)需要的是IEnumerable<IEnumerable<string>>，究竟二維的數(shù)組能不能轉(zhuǎn)成二維的迭代器呢？

C++嘛，因?yàn)樗鼪]有C#的協(xié)變和逆變的功能，所以是做不到的了。幸好我們這里用的是C# 4.0。那C#究竟是怎么做的呢？

其實(shí)從Array<Array<string>>到IEnumerable<IEnumerable<string>>需要兩步。第一步因?yàn)锳rray繼承自IEnumerable，所以類型變成了IEnumerable<Array<string>>。第二部就是最重要的步驟了，因?yàn)镮Enumerable<out T>的T有一個(gè)out，這就說明，IEnumerable里面所有的T都是用在函數(shù)的返回值上的，他只生產(chǎn)T，不會(huì)消耗T。所以一個(gè)IEnumerable<子類型>就可以轉(zhuǎn)變成IEnumerable<父類型>，因?yàn)樽宇愋涂偸强梢赞D(zhuǎn)變成父類型的。因此最后IEnumerable<Array<string>>就變成了IEnumerable<IEnumerable<string>>了。

所以現(xiàn)在我們回過頭來看上面提到的泛型的三個(gè)手法
1、定義一個(gè)輸入類型輸出類型的函數(shù)（class Array<T>）
2、調(diào)用這個(gè)函數(shù)來得到你想要的類型（new Array<int>()）
3、協(xié)變和逆變（(IEnumerable<IEnumerable<string>>)new Array<Array<string>>()）

所以說白了泛型就是一個(gè)對(duì)類型進(jìn)行操作的東西。當(dāng)然它的內(nèi)涵遠(yuǎn)遠(yuǎn)沒有模板那么豐富，但是既然討論到了對(duì)類型的操作，我覺得我要稍微普及一下一個(gè)類型系統(tǒng)的常識(shí)——父類型和子類型。

父類型和子類型說的是什么，如果我們有兩個(gè)類型，一個(gè)T，一個(gè)U。如果一個(gè)U的值，總是可以被看成一個(gè)T的值的話，那么我們就說U是T的子類型。我們也可以說，U是T的子集。這里我要說一下為什么正方形是一個(gè)長方形但是我們卻不能讓正方形繼承自長方形呢？因?yàn)檫@個(gè)“是一個(gè)”只在只讀的時(shí)候成立?？紤]了寫，正方形就不是子類型了。

除了類的繼承，協(xié)變逆變以外，還有另一種父類型和子類型的關(guān)系——那就是模板類型了。舉個(gè)例子，我有一個(gè)函數(shù)是這么寫的：T Do<T>(T t)。這是一個(gè)輸入T輸出T的模板函數(shù)。那我們有一天需要一個(gè)輸入int輸出int的函數(shù)怎么辦呢？Do<int>就好了。反過來行不行呢？不行。所以delegate T F<T>(T t)就是delegate int F(int t)的子類型。

當(dāng)然，上面這個(gè)例子千萬不能和函數(shù)的協(xié)變逆變混起來了。只有模板才能這么做，delegate string(string)肯定變不了delegate object(object)的。只有delegate string(object)可以通過協(xié)變+逆變同時(shí)作用變成delegate object(string)。因?yàn)閛bject和string是繼承的關(guān)系，不是模板的關(guān)系。

泛型到這里基本上就說完了，輪到模板了。C#的泛型產(chǎn)生的類可以是靜態(tài)類，其實(shí)C++就更可以了，而且C++還有偏特化這種必不可缺的東西。那偏特化有什么用呢？這跟上一篇文章將面向?qū)ο蟮臅r(shí)候一樣，其中的一個(gè)很大的用處就是拿來做contract。

interface和template（其實(shí)是concept mapping）拿來做contract的區(qū)別，在于你選擇一個(gè)具有contract的類型的實(shí)現(xiàn)的時(shí)候，是在運(yùn)行時(shí)做的，還是在編譯時(shí)做的。其實(shí)有很多時(shí)候我們并不想，有時(shí)候也不能入侵式地給一個(gè)類隨便添加一個(gè)新功能。我們知道，功能就是contract，contract要么是interface，要么是template。interface并不是總是可以加上去的，譬如說對(duì)那些不能修改的類，就像string啊int什么的。而且我們也不會(huì)拿string和int做多態(tài)。這種時(shí)候我們就需要concept mapping了，然后靠類型推導(dǎo)去選擇正確的實(shí)現(xiàn)。在C++里面，就是用template+偏特化來做了。

上面這段話說得好像很抽象（一點(diǎn)都不抽象?。?，我們還是用一個(gè)生動(dòng)的例子來做吧。譬如說我們要做序列化和反序列化。首先我們可以讓若干個(gè)類型支持序列化的功能。其次，只要T支持序列化，那么vector<T>啊、list<T>什么的也將自動(dòng)支持序列化的功能。這是一個(gè)遞歸的描述，所以用template來做剛剛好。但是像vector和list這種不能修改的類，或者int這種原生的類型，我們要怎么支持序列化呢？不能修改類，那只能寫在類的外面，變成一個(gè)函數(shù)了。那對(duì)于vector<T>來說，他怎么知道T的序列化函數(shù)是什么呢？相信熟悉模板的讀者肯定知道正確的答案是什么了。

首先我們要做一個(gè)空類叫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);  // 我們已經(jīng)有右值引用構(gòu)造函數(shù)了，不怕！
    static void Write(ostream& o, const vector<T>& v);
};

這里需要提到的一點(diǎn)是，當(dāng)我們使用Serializable<vector<T>>的時(shí)候，我們首先要保證T也是Serializable的?？上У氖荂++并不能讓我們很好地表達(dá)這一點(diǎn)，本來C++0x是有個(gè)concept mapping的標(biāo)準(zhǔn)，不過后來被干掉了，我覺得永遠(yuǎn)都不會(huì)有這個(gè)東西了。但其實(shí)這并不是什么太大的事情，因?yàn)橹灰銓戝e(cuò)了，那總是會(huì)有編譯錯(cuò)誤的。

不過go語言在這一點(diǎn)上就不一樣了，go沒有模板什么像樣的代碼都寫不出就不說了，就算他有模板，然后同時(shí)具有Read和Write的類型都實(shí)現(xiàn)了go的一個(gè)叫做Serializable的interface的話，結(jié)果又如何呢？其實(shí)這相當(dāng)于把Serializable<T>::Read(i)和Serializable<T>::Write(o, v)都改成Read(i, &v)和Write(o, v)。這樣的問題老趙已經(jīng)在他的博客講過了，萬一Read和Write不是你寫的，功能跟你要的不一樣，只是碰巧有了這兩個(gè)函數(shù)怎么辦，你還能救嗎？你已經(jīng)不能救了，因?yàn)槊侄加眠^了，你想顯式地實(shí)現(xiàn)一個(gè)interface的話go又沒這個(gè)功能，于是程序就到此傻逼了，Read和Write改名吧，祝你不是項(xiàng)目快寫完了才發(fā)現(xiàn)這個(gè)問題。

關(guān)于編譯錯(cuò)誤，我覺得有一個(gè)事情是很值得說的。為什么熟悉Haskell都覺得Haskell的程序只要經(jīng)過了編譯基本上運(yùn)行就靠譜了？其實(shí)并不是Haskell的程序真的免去了調(diào)試的這一步，而是因?yàn)檫@門語言經(jīng)過了精心的設(shè)計(jì)，把本來在運(yùn)行時(shí)才檢查的事情給轉(zhuǎn)到了編譯時(shí)。當(dāng)然這有一個(gè)不好的地方，就是我們用C語言來寫一個(gè)程序的時(shí)候，雖然因?yàn)镃語言抽象能力太差被迫寫的很糟糕，但是我們總可以運(yùn)行一點(diǎn)改一點(diǎn)，最終讓他可以執(zhí)行。Haskell就不一樣了，只有能編譯和不能編譯兩種狀態(tài)，你要不斷的修改程序，讓他可以編譯。一旦可以編譯，一般就好了。Haskell的這種特性需要淡定的程序員才能使用。

為什么呢，因?yàn)镠askell是沒有語句的，所以只要你修改了函數(shù)讓他做了不一樣的事情，那么函數(shù)的類型就會(huì)發(fā)生變化。那么所有依賴到這個(gè)函數(shù)的函數(shù)的類型也會(huì)發(fā)生變化。如果你改錯(cuò)了，那類型檢查就會(huì)過不去，然后你的程序就不能編譯了。Erik Meijer菊苣說得好，函數(shù)的類型才是表達(dá)函數(shù)業(yè)務(wù)邏輯的地方。而之所以要函數(shù)體，那是因?yàn)榫幾g器不夠聰明，得讓你告訴他滿足這個(gè)類型的最簡單的解是什么。

所以如果我們?cè)贑++也采用這種寫法的話——其實(shí)也就是把邏輯都交給template+偏特化，或者繼承+visitor來做，那么也會(huì)有一樣的效果，雖然并沒有Haskell那么嚴(yán)格。一旦你進(jìn)行了本質(zhì)上的邏輯的變動(dòng)，那你的類型一定會(huì)受到影響，那不滿足類型要求的地方編譯器就會(huì)幫你找出來。所以，當(dāng)你看到一個(gè)因?yàn)檫@種情況而產(chǎn)生的編譯錯(cuò)誤的時(shí)候，心理要想：“好棒，編譯器又給我找出了一個(gè)錯(cuò)誤，避免我在運(yùn)行的時(shí)候才苦逼的調(diào)試它！”

當(dāng)然，模板的這些手法，可以很輕易地用在continuation passing style變換啊、combinator（很像設(shè)計(jì)模式但其實(shí)不是的東西）啊、async啊actor等各種強(qiáng)類型的物體上面，不過這些東西我今天就不打算細(xì)說了。當(dāng)我們?cè)谧鲱愃频氖虑榈臅r(shí)候，我們要把類型設(shè)計(jì)成能表達(dá)業(yè)務(wù)邏輯的那種形式，從而讓編譯器查更多的東西，把運(yùn)行時(shí)錯(cuò)誤盡量化簡為編譯錯(cuò)誤。

當(dāng)然，C++的template比concept mapping還要更牛逼一個(gè)等級(jí)的，就是可以做type traits。如果是concept mapping是在對(duì)值通過類型進(jìn)行分類采用不同的計(jì)算方法的話，那么type traits就是用來直接對(duì)類型進(jìn)行計(jì)算的。那什么是對(duì)類型進(jìn)行計(jì)算呢？我來舉個(gè)例子。

譬如說我們要對(duì)一個(gè)vector進(jìn)行排序，但是這個(gè)時(shí)候我們不像std::sort一樣直接給出一個(gè)比較函數(shù)，而是通過從T拿出一個(gè)U當(dāng)key的方法來做。譬如說對(duì)Student類排序，我們可以用他的學(xué)號(hào)、成績、姓名等等任何一個(gè)屬性來排序，這還是一個(gè)相當(dāng)有用的作法。當(dāng)然，我們總是可以寫一個(gè)lambda表達(dá)式來做出一個(gè)用某個(gè)屬性來比較Student類的函數(shù)，然后讓std::sort來解決。很可惜的是，現(xiàn)在team的編譯器還不夠新，不支持C++11，怎么辦呢？于是我們決定擼一個(gè)自己的sort函數(shù)（雖然這種事情是不推薦的，但反正是個(gè)例子，就不糾結(jié)這個(gè)了）：

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]);
}

這段冒泡排序看起來沒什么問題對(duì)吧，無論用什么語言最后寫出來都肯定是這個(gè)樣子的。于是我們寫了幾個(gè)單元測試，譬如說用sin來對(duì)double排序啦，求個(gè)負(fù)數(shù)實(shí)現(xiàn)逆序啦等等，覺得都沒問題。于是開始投入實(shí)戰(zhàn)了！我們寫了下面的代碼：

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

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

為什么會(huì)錯(cuò)呢？因?yàn)镚etScore函數(shù)接受的不是Student而是const Student&！這下可麻煩了。我們有些函數(shù)接受的是T，有些函數(shù)接受的是const T&，難道要寫兩個(gè)Sort嘛？當(dāng)然這種代價(jià)肯定是不能接受的。于是我們想，如果可以從U(*key)(T)的T推導(dǎo)出vector里面裝的是什么那該多好啊。反正無論函數(shù)接受的是string, string& const string, const string&，vector反正只能放string的。

這個(gè)時(shí)候就要祭出偉大的type traits了。怎么做呢？其實(shí)根上面的說法一樣，我們把template看成是一個(gè)函數(shù)，輸入是一個(gè)類型，輸出再也不是值了，還是一個(gè)類型就好了：

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;
};

我們要怎么看這個(gè)過程呢？其實(shí)這是個(gè)pattern matching的過程，而pattern matching在一定程度上跟if-else其實(shí)是差不多的。所以我們看著一類的東西，心里不要總是想著他是個(gè)模板，而是要想，RemoveCR是個(gè)函數(shù)。所以當(dāng)我們看見第一個(gè)RemoveCR的時(shí)候，我們心里浮現(xiàn)出來的景象大概是這個(gè)樣子的：

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

好了，這個(gè)時(shí)候我們看見了第二個(gè)RemoveCR，那么這個(gè)RemoveCR函數(shù)又具體了一點(diǎn)：

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

后來我們看到了第三個(gè)RemoveCR，發(fā)現(xiàn)定義到此結(jié)束了，于是RemoveCR函數(shù)的實(shí)際的樣子就出來了：

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;
}

于是我們就可以做很多驗(yàn)證了，譬如說RemoveCR<int>::Result的結(jié)果是int，RemoveCR<const int&>::Result的結(jié)果還是int?，F(xiàn)在好了，我們可以修改我們的Sort函數(shù)了：

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

無論你的排序函數(shù)接受的是Student還是const Student&，現(xiàn)在Sort函數(shù)都知道，你需要對(duì)vector<Student>進(jìn)行排序。于是任務(wù)就完成了！

別的語言里面沒有這種問題，是因?yàn)橹挥蠧++才會(huì)把const、volatile和&這樣的東西用來修飾一個(gè)類型而不是一個(gè)變量。這一點(diǎn)我第二篇文章已經(jīng)講過了，就不繼續(xù)啰嗦了。所以說C++的設(shè)計(jì)雖然考慮得很周到，Bjarne Stroustrup菊苣也說過他不喜歡像別的語言的作者一樣把自己的觀點(diǎn)強(qiáng)加給用戶。從這個(gè)出發(fā)點(diǎn)上來看，C++這一點(diǎn)相當(dāng)好。只要你肯學(xué)習(xí)，又不會(huì)太蠢的話，總是可以學(xué)會(huì)C++的正確使用方法，正常使用C++來寫代碼的。但是，人真的蠢怎么辦呢？Bjarne Stroustrup你這樣歧視愚蠢的程序員是不對(duì)的，難道蠢就不能做程序員嗎，難道學(xué)了go陷進(jìn)去不能自拔的人就再也沒有機(jī)會(huì)學(xué)習(xí)C++了嗎！

關(guān)于type traits，haskell的type class（這東西就跟concept mapping一樣）其實(shí)也有一部分這樣的能力，可以幫你從type class的一部分類型參數(shù)推導(dǎo)出另一部分的類型參數(shù)。譬如說你這么寫：

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

那么只要你實(shí)現(xiàn)了MyClass Int String Char，就不能實(shí)現(xiàn)MyClass Int String String了，因?yàn)閍 b => c這條規(guī)則已經(jīng)限制了，(Int String)只能出現(xiàn)一次，c要完全被a和b決定。所以擁有這個(gè)=>的haskell的type class也就可以有一部分type traits的功能了，雖然用法跟C++是截然不同的。

那C++的template除了泛型、concept和type traits之外，還有沒有別的功能呢？當(dāng)然有，我們不僅可以把類型放進(jìn)模板的參數(shù)列表里面去，也可以把一個(gè)整數(shù)放進(jìn)去。這個(gè)時(shí)候我們就可以用Int<100>來表達(dá)100，用Pair<Int<100>, Pair<Int<200>, Pair<Int<300>, PairEnd>>>來代表數(shù)組[100, 200, 300]，然后各種奇技淫巧就可以用來把模板寫成一個(gè)不帶類型的函數(shù)式語言了，在編譯期什么東西都可以算。這個(gè)事情展開講就太復(fù)雜了，而且也沒什么用，你們感興趣的話去看《C++ Template Metaprogramming》就行了。

在所有的文字之前，我需要強(qiáng)調(diào)一下，我本人對(duì)structure typing持反對(duì)態(tài)度，所以就算文中的內(nèi)容“看起來很像”go的interface，讀者們也最好不要覺得我是在贊揚(yáng)go的interface。我比較喜歡的是haskell和rust的那種手法。可惜rust跟go一樣恨不得把所有的單詞都縮成最短，結(jié)果代碼寫出來連可讀性都沒有了，單詞都變成了符號(hào)。如果rust把那亂七八糟的指針設(shè)計(jì)和go的那種屎縮寫一起干掉的話，我一定會(huì)很喜歡rust的。同理，COM這個(gè)東西設(shè)計(jì)得真是太他媽正確了，簡直就是學(xué)習(xí)面向?qū)ο笫址ǖ淖罴逊独?，可惜COM在C++下面操作起來有點(diǎn)傻逼，于是很多人看見這個(gè)東西就呵呵呵了。

上一篇文章說這次要寫類成員函數(shù)和lambda的東西，不過我想了想，還是先把OO放前面，這樣順序才對(duì)。

我記得我在讀中學(xué)的時(shí)候經(jīng)常聽到的宣傳，是面向?qū)ο蟮淖龇ǚ浅７先祟惖乃季S習(xí)慣，所以人人喜歡，大行其道，有助于寫出魯棒性強(qiáng)的程序。如今已經(jīng)過了十幾年了，我發(fā)現(xiàn)網(wǎng)上再也沒有這樣的言論了，但是也沒有跟反C++的浪潮一樣拼命說面向?qū)ο筮@里不好那里不好要廢除——明顯人們還是覺得帶面向?qū)ο蟮恼Z言用起來還是比較爽的，不然也就沒有那么多人去研究，一個(gè)特別合用來寫functional programming的語言——javascript——是如何可以“模擬”面向?qū)ο笳Z言里面的常用操作——new、繼承和虛函數(shù)覆蓋了。

所以像面向?qū)ο筮@種定義特別簡單的東西，語法上應(yīng)該做不出什么坑的了。那今天的坑是什么呢？答案：是人。

動(dòng)態(tài)類型語言里面的面向?qū)ο笳f實(shí)話我也不知道究竟好在哪里，對(duì)于這種語言那來講，只要做好functional programming的那部分，剩下的OO究竟要不要，純粹是一個(gè)語法糖的問題。在動(dòng)態(tài)類型語言里面，一個(gè)類和一個(gè)lambda expression的差別其實(shí)不大。

那么靜態(tài)類型語言里面的面向?qū)ο笠趺纯创?？首先我們要想到的一個(gè)是，凡是面向?qū)ο蟮恼Z言都支持interface。C++雖然沒有直接支持，但是他有多重繼承，我們只需要寫出一個(gè)純虛類出來，就可以當(dāng)interface用了。

在這里我不得不說一下C++的純虛類和interface的這個(gè)東西。假設(shè)一下我們有下面的C#代碼：

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

class MyPowerfulButton : CheckBox, IDropdownButton
{
    // 在這里我們只需要實(shí)現(xiàn)IDropdownButton里面比IButton多出來的那部分函數(shù)就夠了。
}

我們先不管GUI是不是真的能這么寫，我們就看看這個(gè)繼承關(guān)系就好了。這是一個(gè)簡單到不能再簡單的例子。意思就是我有兩種button的接口，我從一個(gè)實(shí)現(xiàn)里面擴(kuò)展出一個(gè)支持另一種button接口的東西。但是大家都知道，我那個(gè)完美的GacUI用的是C++，那么在C++下面會(huì)遇到什么問題呢：

#region 抱怨

一般來說在C++里面用純虛類來代替interface的時(shí)候，我們繼承一個(gè)interface用的都是virtual繼承。為什么呢？看上面那個(gè)例子，ISelectableButton繼承自IButton，IDropdownButton繼承自IButton。那么當(dāng)你寫一個(gè)MyPowerfulButton的時(shí)候，你希望那兩個(gè)接口里面各自的IButton是不一樣的東西嗎？這當(dāng)然不是。那如何讓兩個(gè)接口的IButton指向的是同一個(gè)東西呢？當(dāng)然就是用virtual繼承了。

好了，現(xiàn)在我們有CheckBox這個(gè)實(shí)現(xiàn)了ISelectableButton（帶IButton）的類了，然后我們開始寫MyPowerfulButton。會(huì)發(fā)生什么事情呢？

猜錯(cuò)了！答案是，其實(shí)我們可以寫，但是Visual C++（gcc什么的你們自己玩玩就好了）會(huì)給我們一個(gè)warning，大意就是你IDropdownButton里面的IButton被CheckBox給覆蓋了，再說抽象一點(diǎn)就是一個(gè)父類覆蓋了另一個(gè)父類的虛函數(shù)。這跟virtual繼承是沒關(guān)系的，你怎么繼承都會(huì)出這個(gè)問題。

但這其實(shí)也怪不了編譯器，本來在其他情況下，虛函數(shù)這么覆蓋自然是不好的，誰讓C++沒有interface這個(gè)概念呢。但是GUI經(jīng)常會(huì)碰到這種東西，所以我只好無可奈何地在這些地方用#pragma來supress掉這個(gè)warning，反正我知道我自己在干什么。

C++沒有interface的抱怨到這里就完了，但是virtual繼承的事情到這里還沒完。我再舉一個(gè)例子：

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繼承的，就是像上面這個(gè)例子，D里面只有一個(gè)A對(duì)象，B和C在D里面共享了A。那么，我們給B和C用了不同的參數(shù)來構(gòu)造，難道一個(gè)A對(duì)象可以用不同的參數(shù)構(gòu)造兩次嗎，還是說編譯器幫我們隨便挑了一個(gè)？

呵呵呵呵呵呵呵呵，我覺得C++的virtual繼承就是這里非常反直覺——但是它的解決方法是合理的。反正C++編譯器也不知道究竟要讓B還是C來初始化A，所以你為了讓Visual C++編譯通過，你需要做的事情是：

D()
    : A(0)  // 參數(shù)當(dāng)然是胡扯的，我只是想說，你在D里面需要顯式地給A構(gòu)造函數(shù)的參數(shù)
    , B(1)
    , C(2)
{
}

#endregion

大家估計(jì)就又開始吵了，C++干嘛要支持多重繼承和virtual繼承這兩個(gè)傻逼東西呢？我在想，對(duì)于一個(gè)沒有內(nèi)建interface機(jī)制的語言，你要是沒有多重繼承和virtual繼承，那用起來就跟傻逼一樣，根本發(fā)揮不了靜態(tài)類型語言的優(yōu)勢——讓interface當(dāng)contract。當(dāng)然，我基本上用多重繼承和virtual繼承也是用來代替interface的，不會(huì)用來做羞恥play的。

當(dāng)我們?cè)诔绦蚶锩婺玫揭粋€(gè)interface也好，拿到一個(gè)class也好，究竟這代表了一種什么樣的精神呢？interface和class的功能其實(shí)是很相似的

interface IA：只要你拿到了一個(gè)IA，你就可以對(duì)她做很多很多的事情了，當(dāng)然僅限大括號(hào)里面的！
class C : IA, IB：只要你拿到了一個(gè)C——哦不，你只能拿到interface不能拿到class的——反正意思就是，你可以對(duì)她做對(duì)IA和IB都可以做的事情了！

所以contract這個(gè)概念是很容易理解的，就是只要你跟她達(dá)成了contract，你就可以對(duì)她做這樣那樣的事情了。所以當(dāng)一個(gè)函數(shù)返回給你一個(gè)interface的時(shí)候，他告訴你的是，函數(shù)運(yùn)行完了你就可以做這樣那樣的事情。當(dāng)一個(gè)函數(shù)需要一個(gè)interface的時(shí)候，他告訴你的是，你得想辦法讓我（函數(shù)）干這樣那樣的事情，我才會(huì)干活。

那class呢？class使用來實(shí)現(xiàn)interface的，不是給你直接用的。當(dāng)然這是一個(gè)很理想的情況，可惜現(xiàn)在的語言糖不夠甜，堅(jiān)持這么做的話實(shí)在是太麻煩了，所以只好把某些class也直接拿來用了，GUI的控件也只好叫Control而不是IControl了。

其實(shí)說到底class和interface有什么區(qū)別呢？我們知道面向?qū)ο蟮囊淮筇卣骶褪欠庋b，封裝的意思就是封裝狀態(tài)。什么是狀態(tài)呢？反正云風(fēng)一直在說的“類里面的數(shù)據(jù)”就不是狀態(tài)。我們先來看什么是數(shù)據(jù)：

struct Point
{
    int x;
    int y;
};

這就是典型的數(shù)據(jù)，你往x和y里面隨便寫什么東西都是沒問題的，反正那只是一個(gè)點(diǎn)。那什么是狀態(tài)呢：

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

String和Point有什么不一樣呢？區(qū)別只有一個(gè)：String的成員變量之間是滿足一個(gè)不變量的：wcslen(buffer) == length;

如果我們真的決定要給String加上這么個(gè)不變量的話，那這里面包含了兩點(diǎn)：
1：buffer永遠(yuǎn)不是nullptr，所以他總是可以被wcslen(buffer)
2：length的值和buffer有直接的關(guān)系

如果你要表達(dá)一個(gè)空字符串，你總是可以寫buffer=L””，不過這就要你給String再加上一些數(shù)據(jù)來指明這個(gè)buffer需要如何被釋放了，不過這是題外話了。我們可以假設(shè)buffer永遠(yuǎn)是new[]出來的——反正這里不關(guān)心它怎么釋放。

這個(gè)不變量代表什么呢？意思就是說，無論你怎么折騰String，無論你怎么創(chuàng)建釋放String，這個(gè)等式是一定要滿足的。也就是說，作為String外部的“操作人員”，你應(yīng)當(dāng)沒機(jī)會(huì)“觀測”到這個(gè)String處于一個(gè)不滿足不變量的狀態(tài)。

所以這兩個(gè)成員變量都不應(yīng)該是public的。因?yàn)槟呐履鉷ublic了他們其中的一個(gè)，你也會(huì)因?yàn)橥獠靠梢噪S意修改它而使他進(jìn)入一個(gè)不滿足不變量的狀態(tài)。

這代表了，為了操作這些成員變量，我們需要public一些函數(shù)來給大家用。其實(shí)這也是contract，String的成員函數(shù)告訴我們，你可以對(duì)我（String）做很多很多的事情哦！

這同時(shí)也代表了，我們需要一個(gè)構(gòu)造函數(shù)。因?yàn)槿绻覀冊(cè)趧?chuàng)建一個(gè)String之后，實(shí)例沒有被正確初始化，那么他就處于了一個(gè)不滿足不變量的狀態(tài)，這就不滿足上面說的東西了。有些人喜歡帶一個(gè)Init函數(shù)和一個(gè)基本不干什么事情的構(gòu)造函數(shù)，我想說的是，反正你構(gòu)造完了不Init都不能用，你為什么非要我每次創(chuàng)建它的時(shí)候都立刻調(diào)用Init這么多次一舉呢？而且你這樣會(huì)使得我無法對(duì)于一個(gè)這樣的函數(shù)f(shared_ptr<ClassThatNeedsInit> x)直接寫f(make_shared(new ClassThatNeedInit))因?yàn)槟愕臉?gòu)造函數(shù)是殘廢的！

有些人會(huì)說，init沒有返回值，我不知道他犯了錯(cuò)誤啊——你可以用Exception！

還有些人會(huì)說，exception safe的構(gòu)造函數(shù)好難寫啊——學(xué)啊我艸！

但是這樣仍然有些人會(huì)負(fù)隅頑抗，都這么麻煩了反正我可以用對(duì)Init和返回值就好了——你連exception safe的構(gòu)造函數(shù)都不知道怎么寫你怎么知道你可以“用對(duì)”它們？

#region 題外話展開

但是有些人就喜歡返回error，怎么辦呢？其實(shí)我們都很討厭Java那個(gè)checked exception的對(duì)吧，要拋什么exception都得在函數(shù)簽名里面寫，多麻煩啊。其實(shí)這跟error是一樣的。一個(gè)exception是可以帶有很多豐富的信息的——譬如說他的callstack什么的，還可以根據(jù)需要有很多其他的信息，總之不是一個(gè)int可以表達(dá)的。這就是為什么exception【通常】都是一個(gè)類。那如果我們不能用exception，但是也要返回一樣多的信息怎么辦？你只好把函數(shù)的返回值寫得相當(dāng)?shù)膹?fù)雜，譬如說：

struct ErrorInfoForThisFunction
{
    xxxxxxxx
};

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

ReturnValue<ReturnType, ErrorInfoForThisFunction> ThisFunction( ... ); //我知道因?yàn)樾畔?shí)在太多你們又要糾結(jié)返回struct還是它的指針還是ReturnValue里面的東西用指針還是用引用參數(shù)等等各種亂七八糟的事情了哈哈哈哈哈哈

于是現(xiàn)在出問題了，我有一個(gè)ThatFunction調(diào)用ThisFunction，當(dāng)錯(cuò)誤是一種原因的時(shí)候我可以處理，當(dāng)錯(cuò)誤是另一種原因的時(shí)候我無法處理，所以在這種情況下我有兩個(gè)選擇：
1：把錯(cuò)誤信息原封不斷的返回
2：把ThisFunction的錯(cuò)誤信息包裝成ThatFunction的錯(cuò)誤信息
不過我們知道其實(shí)這兩種方法都一樣，所以我們采用第一種：

struct ErrorInfoForThatFunction
{
    yyyyyyyy
};

ReturnValue<ReturnType2, tuple<ErrorInfoForThisFunction, ErrorForThatFunctio, bool /*用來代表哪個(gè)是有效的*/> ThatFunction( ...  ); //數(shù)據(jù)越來越多我知道你們會(huì)對(duì)返回值糾結(jié)的越厲害

你可能會(huì)說，為什么不把tuple包裝成另一個(gè)struct？其實(shí)都一樣，懶得寫了。

我們知道，通常一個(gè)常見的幾百人一起寫的小軟件都會(huì)有幾百上千萬行甚至幾十G代碼的，函數(shù)的調(diào)用層次只有幾十層都已經(jīng)很不錯(cuò)了。就算調(diào)用鏈里面只有10%的函數(shù)添加了自己的錯(cuò)誤信息，那累積到最后肯定會(huì)很壯觀的。而且只要底層的一個(gè)函數(shù)修改了錯(cuò)誤信息，所有直接間接調(diào)用它的函數(shù)都會(huì)受到影響。

這簡直就跟Java的checked exception一樣嘛！

有些人會(huì)說，我們有error code就夠了！我知道你們根本沒有好好想“怎么做error recovery”這件事情。

有些人還會(huì)說（就在我微博上看見的），用error code就是代表可以不處理，我干嘛要費(fèi)那么多心思搞你這些返回值的東西？我對(duì)這種人只能呵呵呵了，轉(zhuǎn)行吧……

這個(gè)時(shí)候我就會(huì)想，C++多好啊，我只要把ReturnValue<ReturnType, ErrorInfoForThisFunction>給改成ReturnType，然后在函數(shù)里面發(fā)生了錯(cuò)誤還是構(gòu)造一個(gè)ErrorInfoForThisFunction，然后直接給throw出來就好了。throw一個(gè)值我們還不用關(guān)心怎么釋放它，多省事。對(duì)于ErrorInfoForThatFunction，我還可以讓這兩個(gè)struct都繼承自同一個(gè)基struct（就是你們經(jīng)常在別的語言里面看見的Exception類了），這樣我在外面還可以直接catch(const 基struct& ex)。

有些人會(huì)說，為什么不強(qiáng)制所有繼承都繼承自Exception？我知道你們就只是想catch了之后不理罷了，反正C++也有catch(…)你們偷著樂就行了。

用Exception有性能問題？反正在不發(fā)生錯(cuò)誤的情況下，寫了幾句try也就只是操作了寫在FS : [ 0 ]里面的一個(gè)鏈表而已，復(fù)制幾個(gè)指針根本就不算什么影響。

C++的catch不能抓到Access Violation（也就是segmant fault？）？現(xiàn)在連最新的.net你來寫catch(Exception ex)也抓不到AccessViolationException了。都AV了你的內(nèi)存都搞得一團(tuán)糟了，如果你這個(gè)時(shí)候還不備份數(shù)據(jù)dump自己然后退出重啟（如果需要的話），那你接著執(zhí)行代碼，天知道會(huì)發(fā)生什么事情啊！連C#都覺得這么做危險(xiǎn)了，C++只能更危險(xiǎn)——所以用SEH抓下來dump自己然后進(jìn)程自殺吧。Java還區(qū)分Error和Exception，雖然我不知道他具體代表什么，反正一般來說Exception有兩種
1：可以預(yù)見的錯(cuò)誤，譬如說Socket斷開了所以Write就是敗了給個(gè)Exception之類的
2：必須修改代碼的錯(cuò)誤，譬如說數(shù)組下標(biāo)越界——這除了你寫錯(cuò)以外根本沒有別的原因，就應(yīng)該掛掉，這時(shí)候你debug的時(shí)候才能立刻知道，然后改代碼。

所以有三個(gè)基類然后最嚴(yán)重的那種不能catch我覺得也是一種好的選擇。你可能會(huì)問，那C#在AV之后你又抓不到那怎么知道呢？答案：Application類有一個(gè)事件就是在發(fā)生這類事情的時(shí)候被調(diào)用的，在里面dump就好了。如果你非要抓AV，那也可以抓得到，就是有點(diǎn)麻煩……

#endregion

說了這么多，無非就是因?yàn)橐粋€(gè)類的構(gòu)造函數(shù)——其實(shí)他真的是一個(gè)函數(shù)，只是函數(shù)名和類名一樣了，這種事情在js里面反正經(jīng)常出現(xiàn)——強(qiáng)制了你只能返回正確的時(shí)候的結(jié)果，于是有些人沒辦法加入error code了，又不知道怎么正確使用exception，只好搞出個(gè)C語言的封建社會(huì)殘留思想Init函數(shù)來。其實(shí)我們知道，一旦有了Exception，函數(shù)簽名里面的返回值就是他正確執(zhí)行的時(shí)候返回的東西，這根構(gòu)造函數(shù)一樣。

C++的exception在構(gòu)造函數(shù)里面不好，其實(shí)是因?yàn)橐坏?gòu)造函數(shù)發(fā)生了異常，那代表這個(gè)類沒構(gòu)造完，所以析構(gòu)函數(shù)是不會(huì)執(zhí)行的。這在一定程度上給你寫一個(gè)正確的構(gòu)造函數(shù)（這也是“如何寫一個(gè)正確的類”的其中一個(gè)方面）帶來了麻煩，所以很多人到這里就呵呵呵了。

這就跟很多人學(xué)習(xí)SQL語言結(jié)果到group by這里就怎樣也跨不過去了一樣——人和人之間說沒有差距這個(gè)不符合客觀現(xiàn)實(shí)啊……

不過我不否認(rèn)，想寫一個(gè)正確的C++程序是一件非常困難的事情，以至于連我在【只有我自己用的那部分library】里面都不是總是遵守各種各樣的規(guī)則，反正我寫的代碼，我知道怎么用。不過公司的代碼都是一大堆人一起寫的，就像sqlserver一個(gè)組有一千多人一樣（oracle是我們的十幾倍，我們還能活下來真是太不容易了）——你能每個(gè)人都溝通到嗎？撐死了就幾十個(gè)吧，才不到10%。天知道別人會(huì)在代碼里面干什么。所以寫代碼是不能太隨便的。同理，招人也不能太隨便，特別是你們這些連code review都不做的公司，你平時(shí)都不能阻止他checkin垃圾代碼，你還敢招不合格的人嗎？

現(xiàn)在我們回到面向?qū)ο蟮臇|西。Exception其實(shí)也應(yīng)該算在contract里面，所以其實(shí)interface里面的函數(shù)會(huì)拋什么異常是需要明確的表達(dá)出來的。但是checked exception這個(gè)東西實(shí)在是太蠢了，因?yàn)檫@個(gè)規(guī)則是不能組合的，會(huì)導(dǎo)致上面說的error返回值一樣的“接口信息大爆炸”。

所有不能組合的東西都是很難用的，譬如checked exception，譬如鎖，譬如第一篇文章說的C語言那個(gè)碉堡了的函數(shù)指針數(shù)組作為參數(shù)的一個(gè)成員函數(shù)指針類型的聲明什么的。

如果你不直接寫出這個(gè)函數(shù)會(huì)拋exception，那要怎么辦呢？方法有兩個(gè)：
1：你給我把文檔寫好了，而且你，還有你，用這個(gè)library之前，給我RTFM！
2：就跟VisualStudio一樣支持xml注釋，這樣VS就可以在你調(diào)用這個(gè)函數(shù)的時(shí)候用tooltip的形式提示你，你需要注意這些那些事情……

什么？你不用IDE？給我RTFM！你連文檔都不看？滾！明天不要來上班了！

突然發(fā)現(xiàn)本來要寫面向?qū)ο蟮模Y(jié)果Exception也寫了相當(dāng)長的一段。這件故事告訴我們，就算你不知道interface as contract是什么意思，你還能湊合寫點(diǎn)能維護(hù)的代碼。但是你Exception用得不好，程序就寫成了渣，這個(gè)問題比較嚴(yán)重，所以寫的也就比較多了。所以下面我們真正來談contract的事情。需要注意的是，C++對(duì)這種東西是用你們很討厭的東西來支持的——模板和偏特化。

contract的概念是很廣泛的。對(duì)于面向?qū)ο笳Z言來說，int這種東西其實(shí)也可以是一個(gè)類。你們不要老是想著編譯后生成什么代碼的事情，語法這種東西只是障眼法而已，編譯出來的東西跟你們看到的可以是完全不同的。一個(gè)典型的例子就是尾遞歸優(yōu)化了。還有C#的int雖然繼承自object但是你直接用他的話生成出來的代碼跟C++是沒什么區(qū)別的——因?yàn)榫幾g器什么后門都可以開！

那我們就拿int來說吧。int有一個(gè)很重要的特征，就是可以用來比較。C++怎么表達(dá)這個(gè)事情的呢？

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

如果你想寫一個(gè)排序函數(shù)，內(nèi)部想用<來排序的話，你不需要在接口上寫任何東西，你只需要假設(shè)那個(gè)typename T的T可以被<就好了。所有帶有<的類型都可以被這個(gè)函數(shù)使用。這特別的structure typing，而且C++沒有concept mapping，導(dǎo)致了你無法在接口上表達(dá)“這個(gè)類必須帶<”的這件事情，所以一旦你用錯(cuò)了，這錯(cuò)誤信息只能跟煙霧一般繚繞了……

concept mapping其實(shí)也是一個(gè)面向?qū)ο蟮奶貏e好用特征不過這太高級(jí)了估計(jì)很多人都沒用過——你們又不喜歡haskell和rust——那對(duì)于我們熟悉的面向?qū)ο蟮奶匦詠碇v，這樣的事情要怎么表達(dá)呢？

于是我們偉大的先知Anders Hejlsberg菊苣就做了這么個(gè)決定（不是他干的也是他手下干的?。?

interface IComparable // .net 1.0沒有模板，只好搞了這么個(gè)傻逼東西出來
{
    int CompareTo(object o); //具體的忘了，這是我根據(jù)記憶隨便寫的
}

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

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

所以你的排序函數(shù)只需要寫成：

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

看看IComparable<int>這個(gè)傻逼。我為什么要?jiǎng)?chuàng)建一個(gè)對(duì)象（IComparable<int>），他的職責(zé)就是跟另一個(gè)int作比較？這實(shí)在是太蠢了，無論怎么想都不能想出這種對(duì)象到底有什么存在的意義。不過因?yàn)镃#沒有concept mapping，于是看在interface as contract的份上，讓interface來干這種事情其實(shí)也是很合理的。

所以contract這個(gè)東西又賦予了一個(gè)更加清晰的意義了。我們其實(shí)想要表達(dá)的事情是“我們可以對(duì)這個(gè)參數(shù)做什么事情”，而不是“這個(gè)參數(shù)是什么類型”。所以在這個(gè)Sort函數(shù)里面，這個(gè)T其實(shí)不代表任何事情，真正起到聲明的作用的是where T : IComparable<T>這一句，指明了data數(shù)組里面的所有東西都是可以被排序的。那你可能會(huì)問，為什么不把IComparable<T>改成IComparable然后干脆把參數(shù)改成IComparable[] data呢？雖然說這樣做的確更加“面向?qū)ο?#8221;，但是實(shí)在是太不現(xiàn)實(shí)了……

本來面向?qū)ο筮@種概念就不是特別的可以表達(dá)客觀現(xiàn)實(shí)，所以出現(xiàn)一些這種狀況，也是正常的。

#region 題外話

看看這兩個(gè)函數(shù)：

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

他們互相之間存在了一個(gè)特別優(yōu)美的（數(shù)學(xué)意義上的）變換，發(fā)現(xiàn)沒有，發(fā)現(xiàn)沒有！所以對(duì)于動(dòng)態(tài)類型語言（interface可以從代碼里面得到）做一些“靜態(tài)化”的優(yōu)化的時(shí)候，就可以利用類似的技巧——咳咳，說太遠(yuǎn)了，趕緊打住。誰說懂點(diǎn)代數(shù)對(duì)編程沒用的？哼！

#endregion

在這里我們終于看到了contract在帶泛型的純潔的面向?qū)ο笳Z言里面的兩種表達(dá)方法。你可能會(huì)想，我想在java里面干這種事情怎么辦？還是換C#吧。那我們拿到一個(gè)class的時(shí)候，這代表什么呢？其實(shí)我們應(yīng)該看成，其實(shí)我們拿到的是一個(gè)interface，只是他恰好只有一個(gè)實(shí)現(xiàn)。所以在這種時(shí)候，你最好不要依賴于“這個(gè)interface恰好只有一種實(shí)現(xiàn)而且我知道他是什么”的這個(gè)事情，否則程序?qū)懘罅?，你?huì)發(fā)現(xiàn)你越來越不滿足“面向interface編程”的這個(gè)原則，代碼越來越難處理了。

我們可能會(huì)想到另一件事情，先知們跟我們說，當(dāng)你設(shè)計(jì)函數(shù)參數(shù)的類型的時(shí)候，這個(gè)類型越基，哦不，越是在繼承鏈里面距離object靠得越近越好，這是為什么呢？這其實(shí)也是一個(gè)interface as contract的問題。舉個(gè)例子，我們需要對(duì)一個(gè)數(shù)組求和：

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

費(fèi)盡心思終于寫好了，然后我們第二天發(fā)現(xiàn)，我們對(duì)List<T>也要做一樣的事情。那怎么辦呢？

在這里，Sum究竟對(duì)data有什么需求呢？其實(shí)研究一下就會(huì)發(fā)現(xiàn)，我們需要的只是想遍歷data里面的所有內(nèi)容而已。那data是不是一個(gè)數(shù)組，還是列表，還是一顆二叉樹，還是你垃圾ipad里面的一些莫名其妙的數(shù)據(jù)也好，其實(shí)都一樣。那C#里面什么interface代表“遍歷”這個(gè)contract呢？當(dāng)然是IEnumerable<T>了：

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

這樣你的容器只要能夠被foreach，也就是繼承自IEnumearble<T>，就可以用這個(gè)函數(shù)了。這也是為什么”linq to 容器”基本上都是在IEnumerable上做的，因?yàn)樗麄冎恍枰闅v。

哦，我們還說到了foreach。foreach是一個(gè)語句，用來遍歷一個(gè)容器。那你如何表達(dá)一個(gè)容器可以被foreach拿來遍歷的這個(gè)contract呢？還是IEnumerable<T>。interface拿來做contract的確是最佳匹配呀。

其實(shí)說了這么多，我只想表達(dá)一個(gè)東西。不要太在意“這個(gè)變量的類型是什么”，你要關(guān)心的是“我可以對(duì)這個(gè)變量做這樣那樣的事情”。這就是為什么我們會(huì)推薦“面向接口編程”，因?yàn)槿丝偸菓猩⒌?，需要一些約束。interface不能用來new，不包含成員變量，剛好是contract的一種很好地表達(dá)方法。C++表達(dá)contract其實(shí)還可以用模板，不過這個(gè)就下次再說了。如果你們非得現(xiàn)在就知道到底怎么用的話，我就告訴你們，只要把C#的(i as IComparable<int>).CompareTo(j)換成Comparable<int>::Compare(i, j)就好了。

所以在可能的情況下，我們?cè)O(shè)計(jì)函數(shù)的參數(shù)和返回值的類型，也盡量用更基的那些類型。因?yàn)槿绻愀厦娴腟um一樣，只關(guān)心遍歷，那么你根本不應(yīng)該要求你的參數(shù)可以被隨機(jī)訪問（數(shù)組就是這個(gè)意思）。

希望大家看完這篇文章之后可以明白很多我們?cè)诿嫦驅(qū)ο缶幊痰臅r(shí)候，先知們建議的那些條款。當(dāng)然這里還不涉及設(shè)計(jì)模式的東西。其實(shí)設(shè)計(jì)模式說白了是語法的補(bǔ)丁。設(shè)計(jì)模式這種東西用的最多，C#略少，你們會(huì)發(fā)現(xiàn)像listener模式這種東西C#就不常用，因?yàn)樗懈玫臇|西——event。

我從來沒有在別的語言的粉里面看見過這么容易展示人性丑陋一面的粉，就算是從十幾年前開始的C++和C對(duì)噴，GC和非GC對(duì)噴，靜態(tài)類型動(dòng)態(tài)類型對(duì)噴的時(shí)候，甚至是云風(fēng)出來噴C++黑得那么驚天動(dòng)地的時(shí)候，都沒有發(fā)生過這么腦殘的事情。這種事情只發(fā)生在go語言的腦殘粉的身上，這究竟代表什么呢？想學(xué)go語言的人最好小心一點(diǎn)了，學(xué)怎么用go沒關(guān)系，go學(xué)成了因?yàn)槭懿涣颂絼e的語言去也沒關(guān)系，就算是抖M很喜歡被折騰所以堅(jiān)持用go也沒關(guān)系，但是把自己學(xué)成了腦殘粉，自己的心智發(fā)生不可逆轉(zhuǎn)的變換，那就不好了。

當(dāng)然，上一篇文章最后那個(gè)例子應(yīng)該是我還沒說清楚，所以有些人有這種“加上一個(gè)虛析構(gòu)函數(shù)就可以了”的錯(cuò)覺也是情有可原的。Base* base = new Derived;之后你去delete沒問題，是因?yàn)槲鰳?gòu)函數(shù)你還可以聲明成虛的。但是Base* base = new Derived[10];之后你去delete[]發(fā)生了問題，是因?yàn)镈erived和Base的長度不一樣，所以當(dāng)你開始試圖計(jì)算&base[1]的時(shí)候，你實(shí)際上是拿到了第一個(gè)Derived對(duì)象的中間的一個(gè)位置，根本不是第二個(gè)Derived。這個(gè)時(shí)候你在上面做各種操作（譬如調(diào)用析構(gòu)函數(shù)），你連正確的this指針都拿不到，你再怎么虛也是沒用的。不過VC++單純做delete[]的話，在這種情況下是不會(huì)有問題的，我猜它內(nèi)部不僅記錄了數(shù)組的長度，還記錄了每一個(gè)元素的尺寸。當(dāng)然，你直接用bases[1]->DoSomething()的時(shí)候，出事是必須的。

所以今天粉絲群在討論昨天的這個(gè)例子的時(shí)候，我們的其中一位菊苣就說了一句話：

當(dāng)你使用C++的時(shí)候C的一部分子集最好少碰

我也很贊同。反正C++已經(jīng)有各種內(nèi)置類型了，譬如typeid出來的按個(gè)東西（我給忘了）啊，initialization_list啊，range什么的。為什么就不給new T[x]創(chuàng)建一個(gè)類型呢？不過反正都已經(jīng)成為現(xiàn)實(shí)了，沒事就多用用vector和shared_ptr吧，不要想著什么自己new自己delete了。

今天我們來講一個(gè)稍微“高級(jí)”一點(diǎn)點(diǎn)的坑。這是我在工作之后遇到的一個(gè)現(xiàn)實(shí)的例子。當(dāng)然，語言的坑都擺在那里，人往坑里面跳都肯定是因?yàn)樽约褐赖臇|西還不夠多造成的。但是坑有三種，第一種是很明顯的，只要遵守一些看起來很愚蠢但是卻很有效的原則（譬如說if(1 == a)…）就可以去除的。第二種坑是因?yàn)槟悴恢酪恍└呒?jí)的知識(shí)（譬如說lambda和變量揉在一起的生命周期的事情）從而跳坑的。第三種純粹就是由于遠(yuǎn)見不夠了——譬如說下面的例子。

在春光明媚的一個(gè)早上，我接到了一個(gè)新任務(wù)，要跟另一個(gè)不是我們組的人一起寫一個(gè)圖像處理的pipeline的東西。這種pipeline的節(jié)點(diǎn)無非就是什么直方圖啊，卷積啊，灰度還有取邊緣什么的。于是第一天開會(huì)的時(shí)候，我拿到了一份spec，上面寫好了他們?cè)O(shè)計(jì)好但是還沒開始寫的C++的interface（沒錯(cuò)，就是那種就算只有一個(gè)實(shí)現(xiàn)也要用interface的那種流派），讓我回去看一看，過幾天跟他們一起把這個(gè)東西實(shí)現(xiàn)出來。當(dāng)然，這些interface里面肯定會(huì)有矩陣：

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;
};

其實(shí)說實(shí)話，IMatrix這么寫的確沒什么大問題。于是我們就很愉快的工作了幾天，然后把這些純粹跟數(shù)學(xué)有關(guān)的算法都完成了，然后就開始做卷積的事情了。卷積所需要的那一堆數(shù)字其實(shí)說白了他不是矩陣，但因?yàn)闉檫@種東西專門做一個(gè)類也沒意義，所以我們就用行列一樣多的矩陣來當(dāng)filter。一開始的接口定義成這個(gè)樣子，因?yàn)镮Bitmap可能有不同的儲(chǔ)存方法，所以如何做卷積其實(shí)只有IBitmap的實(shí)現(xiàn)自己才知道：

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

于是我們又愉快的度過了幾天，直到有一天有個(gè)人跳出來說：“Apply里面又不能修改filter，為什么不給他做成const的？”于是他給我們展示了他修改后的接口：

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

我依稀還記得我當(dāng)時(shí)的表情就是這樣子的→囧。

語言的類型系統(tǒng)是一件特別復(fù)雜的事情，特別是像C++這種，const T<a, b, c>和T<const a, const b, cont c>是兩個(gè)不一樣的類型的。一們語言，凡是跟優(yōu)美的理論每一個(gè)不一致的地方都是一個(gè)坑，區(qū)別只是有些坑嚴(yán)重有些坑不嚴(yán)重。當(dāng)然上面這個(gè)不是什么大問題，因?yàn)檎娴陌凑者@個(gè)接口寫下去，最后會(huì)因?yàn)榘l(fā)現(xiàn)創(chuàng)建不了IMatrix<const float>的實(shí)現(xiàn)而作罷。

而原因很簡單，因?yàn)橐话銇碚fIMatrix<T>的實(shí)現(xiàn)內(nèi)部都有一個(gè)T*代表的數(shù)組。這個(gè)時(shí)候給你換成了const float，你會(huì)發(fā)現(xiàn)，你的Set函數(shù)在也沒辦法把const float寫進(jìn)const float*了，然后就掛了。所以正確的方法當(dāng)然是：

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

不過在展開這個(gè)問題之前，我們先來看一個(gè)更加淺顯易懂的“坑”，是關(guān)于C#的值類型的。譬如說我們有一天需要做一個(gè)超高性能的包含四大力學(xué)的粒子運(yùn)動(dòng)模擬程序——咳咳——總之從一個(gè)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;

已開始運(yùn)作的很好，什么事情都沒有發(fā)生，ps[0]里面的Point也被很好的更改了。但是有一天，情況變了，粒子之間會(huì)開始產(chǎn)生和消滅新的粒子了，于是我把數(shù)組改成了List：

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

結(jié)果編譯器告訴我最后一行出了一個(gè)錯(cuò)誤：

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

C#這語言就是牛逼啊，我用了這么久，就只找出這個(gè)“不起眼的問題”的同時(shí)，還是一個(gè)編譯錯(cuò)誤，所以用C#的時(shí)候根本沒有辦法用錯(cuò)啊。不過想想，VB以前這么多人用，除了on error resume next以外也沒用出什么坑，可見Microsoft設(shè)計(jì)語言的功力比某狗公司那是要強(qiáng)多了。

于是我當(dāng)時(shí)就覺得很困惑，隨手寫了另一個(gè)類來驗(yàn)證這個(gè)問題：

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;

結(jié)果倒數(shù)第二行過了，倒數(shù)第一行還是編譯錯(cuò)誤了。為什么同樣是屬性，int就可以+=3，Point就不能改一個(gè)field非得創(chuàng)建一個(gè)新的然后再復(fù)制進(jìn)去呢？后來只能得到一個(gè)結(jié)論，數(shù)組可以List不可以，屬性可以+=不能改field（你給Point定義一個(gè)operator+，那你對(duì)box.Point做+=也是可以的），只能認(rèn)為是語言故意這么設(shè)計(jì)的了。

寫到這里，我想起以前在MSDN上看過的一句話，說一個(gè)結(jié)構(gòu)，如果超過了16個(gè)字節(jié)，就建議最好不要做成struct。而且以前老趙寫了一個(gè)小sample也證明大部分情況下用struct其實(shí)還不如用class快。當(dāng)然至于是為什么我這里就不詳細(xì)展開了，我們來講語法上的問題。

在C#里面，struct和class的區(qū)別，就是值和引用的區(qū)別。C#專門做了值類型和引用類型，值類型不能轉(zhuǎn)成引用（除非box成object或nullable或lazy等），引用類型不能轉(zhuǎn)值類型。值不可以繼承，引用可以繼承。我們都知道，你一個(gè)類繼承自另一個(gè)類，目的說到底都是為了覆蓋幾個(gè)虛函數(shù)。如果你不是為了覆蓋虛函數(shù)然后你還要繼承，八成是你的想法有問題。如果繼承了，你就可以從子類的引用隱式轉(zhuǎn)換成父類的引用，然后滿足里氏代換原則。

但是C#的struct是值類型，也就是說他不是個(gè)引用（指針），所以根本不存在什么拿到父類引用的這個(gè)事情。既然你每一次見到的類型都是他真正的類型（而不像class，你拿到IEnumerable<T>，他可能是個(gè)List<T>），那也沒有什么必要有虛函數(shù)了。如果你在struct里面不能寫虛函數(shù)，那還要繼承干什么呢？所以struct就不能繼承。

然后我們來看一看C#的屬性。其實(shí)C#的operator[]不是一個(gè)操作符，跟C++不一樣，他是當(dāng)成屬性來看待的。屬性其實(shí)是一個(gè)語法糖，其中的getter和setter是兩個(gè)函數(shù)。所以如果一個(gè)屬性的類型是struct，那么getter的返回值也是struct。一個(gè)函數(shù)返回struct是什么意思呢？當(dāng)然是把結(jié)果【復(fù)制】一遍然后返回出去了。所以當(dāng)我們寫box.Point.x=5的時(shí)候，其實(shí)等價(jià)于box.get_Point().x=5。你拿到的Point是復(fù)制過的，你對(duì)一個(gè)復(fù)制過的struct來修改里面的x，自然不能影響box里面存放著的那個(gè)Point。所以這是一個(gè)無效語句，C#干脆就給你定了個(gè)編譯錯(cuò)誤了。不過你可能會(huì)問，List和Array大家都是operator[]也是一個(gè)屬性，那為什么Array就可以呢？答案很簡單，Array是有特殊照顧的……

不過話說回來，為什么很少人遇到這個(gè)問題？想必是能寫成struct的這些東西，作為整體來講本身是一個(gè)狀態(tài)。譬如說上面的Point，x和y雖然是分離的，但是他們并不獨(dú)立代表狀態(tài)，代表狀態(tài)的是Point這個(gè)整體。Tuple（這是個(gè)class，不過其實(shí)很像struct）也一樣，還有很多其他的.net framework里面定義的struct也一樣。因此就算我們經(jīng)常構(gòu)造List<Point>這種東西，我們也很少要去單獨(dú)修改其中一個(gè)element的一部分。

那為什么struct不干脆把每一個(gè)field都做成不可修改的呢？原因是這樣做完全沒有帶來什么好處，反正你誤操作了，總是會(huì)有編譯錯(cuò)誤的。還有些人可能會(huì)問，為什么在struct里面的方法里，對(duì)this的操作就會(huì)產(chǎn)生影響呢？這個(gè)問題問得太好了，因?yàn)閠his是一個(gè)本質(zhì)上是“指針”的東西。

這就跟上一篇文章所講的東西不一樣了。這篇文章的兩個(gè)“坑”其實(shí)不能算坑，因?yàn)樗麄冏罱K都會(huì)引發(fā)編譯錯(cuò)誤來迫使你必須修改代碼。所以說，如果C++的new T[x]返回的東西是一個(gè)貨真價(jià)實(shí)的數(shù)組，那該多好啊。數(shù)組質(zhì)檢科從來沒有什么轉(zhuǎn)換的。就像Delphi的array of T也好，C#的T[]也好，C++的array<T>或者vector<T>也好，你從來都不能把一個(gè)T的數(shù)組轉(zhuǎn)成U的數(shù)組，所以也就沒有這個(gè)問題了。所以在用C++的時(shí)候，STL有的東西，你就不要自己擼了，只傷身體沒好處的……

那么回到一開始說的const的問題。我們?cè)贑++里面用const，一般都是有兩個(gè)目的。第一個(gè)是用const引用來組織C++復(fù)制太多東西，第二個(gè)是用const指針來代表某些值是不打算讓你碰的。但是一個(gè)類里面的函數(shù)會(huì)做什么我們并不知道，所以C++給函數(shù)也加上了const。這樣對(duì)于一個(gè)const T的類型，你只能調(diào)用T里面所有標(biāo)記了const的函數(shù)了。而且對(duì)于標(biāo)記了const的成員函數(shù)，他的this指針也是const T* const類型的，而不是以前的T* const類型。

那類似的問題在C#里面是怎么解決的呢？首先第一個(gè)問題是不存在的，因?yàn)镃#復(fù)制東西都是按bit復(fù)制的，你的struct無論怎么寫都一樣。其次，C#沒有const類型，所以如果你想表達(dá)一個(gè)類不想讓別人修改，那你就得把那些“const”的部分抽出來放在父類或父接口里面了。所以現(xiàn)在C#里面除了IList<T>類型以外，還有IReadOnlyList<T>。其實(shí)我個(gè)人覺得IReadOnlyList這個(gè)名字不好，因?yàn)檫@個(gè)對(duì)象說不定底下是個(gè)List，你用著用著，因?yàn)閯e人改了這個(gè)List導(dǎo)致你IReadOnlyList讀出來的東西變了，迷惑性就產(chǎn)生了。所以在這種情況下，我寧可叫他IReadableList。他是Readable的，只是把write的接口藏起來的你碰不到而已。

所以，const究竟是在修飾什么的呢？如果是修飾類型的話，跟下面一樣讓函數(shù)的參數(shù)的類型都變成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);

究竟有什么區(qū)別呢？或許在函數(shù)內(nèi)部你不能把參數(shù)a和b當(dāng)變量用了。但是在函數(shù)的外部，其實(shí)這三個(gè)函數(shù)調(diào)用起來都沒有任何區(qū)別。而且根據(jù)我們的使用習(xí)慣來講，const修飾的應(yīng)該不是一個(gè)類型，而是一個(gè)變量才對(duì)。我們不希望IBitmap::Apply函數(shù)里面會(huì)修改filter，所以函數(shù)簽名就改成了：

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

我們不希望用宏來定義常數(shù)，所以我們會(huì)在頭文件里面這么寫：

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
};

對(duì)于C++來講，const還會(huì)對(duì)鏈接造成影響。整數(shù)數(shù)值類型的static const成員變量也好，const全局變量也好，都可以只寫在頭文件給一個(gè)符號(hào)，而不需要在cpp里面定義它的實(shí)體。但是對(duì)于非static const的成員變量來說，他又占用了class的一些位置（C#的const成員變量跟static是不相容的，它只是一個(gè)符號(hào)，跟C++完全不是一回事）。

而且根據(jù)大部分人對(duì)const的認(rèn)識(shí)，我們用const&也好，const*也好，都是為了修飾一個(gè)變量或者參數(shù)。譬如說一個(gè)臨時(shí)的字符串：

const wchar_t* name = L"@GeniusVczh";

或者一個(gè)用來計(jì)算16進(jìn)制編碼的數(shù)組：

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

其實(shí)說到底，我們心目中的const都是為了修飾變量或者參數(shù)而產(chǎn)生的，說白了就是為了控制一個(gè)內(nèi)存中的值是否可以被更改（這一點(diǎn)跟volatile一樣，而C#的volatile還帶fence語義，這一點(diǎn)做得比C++那個(gè)只用來控制是否可以被cache進(jìn)寄存器的要強(qiáng)多了）。所以C++用const來修飾類型又是一個(gè)違反直覺的設(shè)計(jì)了。當(dāng)然，如果去看《C++設(shè)計(jì)與演化》的話，的確可以從中找到一些講為什么const會(huì)用來描述類型的原因。不過從我的使用經(jīng)驗(yàn)上來看，const至少給我們帶來了一些不方便的地方。

第一個(gè)就是讓我們寫一個(gè)正確的C++ class變得更難。就像C#里面說的，一個(gè)只讀的列表，其實(shí)跟一個(gè)可讀寫的列表的概念是不一樣的。在C++里面，一個(gè)只讀的列表，是一個(gè)可以讓你看見寫函數(shù)卻不讓你用的一個(gè)進(jìn)入了特殊狀態(tài)的可讀寫的列表。一般來說，一個(gè)軟件都要幾千個(gè)人一起做。我今天寫了一個(gè)類，你明天寫了一個(gè)帶const T&參數(shù)的模板函數(shù)，后天他發(fā)現(xiàn)這兩個(gè)東西湊在一起剛好能用，但是一編譯發(fā)現(xiàn)那個(gè)類的所有成員函數(shù)都不帶const結(jié)果沒辦法搞了。怎么辦？重寫嗎，那我們得自己維護(hù)多出來的一份代碼，還可能跟原類的作者犯下一樣的錯(cuò)誤。修改它的代碼嗎，鬼知道給一個(gè)函數(shù)加上const會(huì)不會(huì)給這個(gè)超大的軟件的其他部分帶來問題，說不定就像字符串類一樣，有一些語義上是const的函數(shù)實(shí)際上需要修改一些成員變量結(jié)果你又不得不給那些東西加上mutable關(guān)鍵字了。你修改了之后，代碼誰來維護(hù)，又成為一個(gè)跟技術(shù)無關(guān)的政治問題了。而且就算你弄明白了什么函數(shù)要加const，結(jié)果你聲明一個(gè)const變量的時(shí)候const放錯(cuò)了位置，也會(huì)有一些莫名其妙的問題出現(xiàn)了。

如果從一開始就用C#的做法，把它分離成兩個(gè)接口，這樣做又跟C++有點(diǎn)格格不入，為什么呢？為什么STL那么喜歡泛型+值類型而不是泛型+引用類型？為什么C#就喜歡泛型+引用類型而不是泛型+值類型？其實(shí)這兩種設(shè)計(jì)并沒有誰好誰不好的地方，至于C++和C#有不同的偏愛，我想原因應(yīng)該是出在GC上。語言有GC，你new的時(shí)候就不需要擔(dān)心什么時(shí)候去delete，反正內(nèi)存可以循環(huán)回收總是用不完的。C++卻不行，內(nèi)存一旦leak就永遠(yuǎn)的leak了，這么下去遲早都會(huì)掛掉的。所以當(dāng)我們?cè)贑++和C#里面輸入new這個(gè)關(guān)鍵字的時(shí)候，心情其實(shí)是差別相當(dāng)大的。所以大家在C++里面就不喜歡用指針，而在C#里面就new的很開心。既然C++不喜歡指針，類似IReadOnlyList<T>的東西不拿指針直接拿來做值類型的話又是沒有什么意義的，所以干脆就加上了const來“禁止你訪問類里面的一部分東西”。于是每當(dāng)你寫一個(gè)類的時(shí)候，你就需要思考上一段所描述的那些問題。但是并不是所有C++的程序員都知道所有的這些細(xì)節(jié)的，所以后面加起來，總會(huì)有傻逼的時(shí)候——當(dāng)然這并不怪C++，怪的是你面試提出的太容易，讓一些不合格的程序員溜進(jìn)來了。C++不是誰都可以用的。

第二個(gè)問題就是，雖然我們喜歡在參數(shù)上用const T&來避免無謂的復(fù)制，但是到底在函數(shù)的返回值上這么做對(duì)不對(duì)呢？const在返回值的這個(gè)問題上這是一把雙刃劍。我自己寫過一個(gè)linq for C++，山寨了一把IEnumerable和IEnumerator類，在Current函數(shù)里面我返回的就是一個(gè)const T&。本來容器自己的IEnumerator寫的挺好，因?yàn)楸緛矸祷氐臇|西就在容器里面，是有地址的。但是開始寫Select和Where的時(shí)候就傻逼了。我為了正確返回一個(gè)const T&，我就得返回一個(gè)帶內(nèi)存地址的東西，當(dāng)然最終我選擇了在MoveNext的時(shí)候把結(jié)果cache在了這個(gè)SelectEnumerator的成員變量里面。當(dāng)然這樣做是有好處的，因?yàn)樗麖?qiáng)迫我把所有計(jì)算都放在MoveNext里面，而不會(huì)偷懶寫在Current里。但是總的來說，要不是我寫代碼的時(shí)候蛋定，說不定什么時(shí)候就掉坑里了。

總的來說，引入const讓我們寫出一個(gè)正確的C++程序的難度變大了。const并不是一無是處，如果你是在想不明白什么時(shí)候要const什么時(shí)候不要，那你大不了不要在自己的程序里面用const就好了。當(dāng)然我在這里并不是說C語言什么都沒有就比C++好。一個(gè)語言是不可能通過刪掉什么來讓他變得更好的。C語言的抽象能力實(shí)在是太低了，以至于讓我根本沒辦法安心做好邏輯部分的工作，而總要關(guān)心這些概念究竟要用什么樣的扭曲的方法才能在C語言里面比較順眼的表達(dá)出來（我知道你們最后都選擇了宏！是吧！是吧?。?，從而讓我變“煩”，bug就變多，程序到最后也懶得寫好了，最后變成了一坨屎。

嘛，當(dāng)然如果你們說我沒有l(wèi)inus牛逼，那我自然也沒辦法說什么。但是C語言大概就是那種只有l(wèi)inus才能用的順手的語言了。C++至少如果你心態(tài)好的話，沒事多用STL，掉坑的概率就要比直接上C語言小多了。

語言的坑這種事情實(shí)在是罄竹難書啊，本來以為兩篇文章就可以寫完的，結(jié)果發(fā)現(xiàn)遠(yuǎn)遠(yuǎn)不夠?？丛谖恼麻L度的份上，今天就到此為止了，下一篇文章還有大家喜聞樂見的函數(shù)指針和lambda的大坑等著你們……

待續(xù)

這個(gè)系列的起因是這樣的，王垠寫了一篇噴go的博客http://www.yinwang.org/blog-cn/2013/04/24/go-language/，里面說go已經(jīng)爛到無可救藥了，已經(jīng)懶得說了，所以讓大家去看http://www.mindomo.com/view.htm?m=8cc4f95228f942f8886106d876d1b041，里面有詳細(xì)的解釋。然后這篇東西被發(fā)上了微博，很多博友立刻展示了人性丑陋的一面：
1、那些go的擁護(hù)者們，因?yàn)間o被噴了，就覺得自己的人格受到了侮辱一樣，根本來不及看到最后一段的鏈接，就開始張牙舞爪。
2、王垠這個(gè)人的確是跟人合不來，所以很多人就這樣斷定他的東西“毫無參考價(jià)值”。

不過說實(shí)話，文章里面是噴得有點(diǎn)不禮貌，這也在一定程度上阻止了那些不學(xué)無術(shù)的人們繼續(xù)閱讀后面的精華部分。如果所有的文章都這樣那該多好啊，那么爛人永遠(yuǎn)都是爛人，不糾正自己的心態(tài)永遠(yuǎn)獲得不了任何有用的知識(shí)，永遠(yuǎn)過那種月入一蛆的日子，用垃圾的語言痛苦的寫一輩子沒價(jià)值的程序。

廢話就說到這里了，下面我來說說我自己對(duì)于語言的觀點(diǎn)。為什么要設(shè)計(jì)一門新語言？原因無非就兩個(gè)，要么舊的語言實(shí)在是讓人受不了，要么是針對(duì)領(lǐng)域設(shè)計(jì)的專用語言。后一種我就不講了，因?yàn)槿绻麤]有具體的領(lǐng)域知識(shí)的話，這種東西永遠(yuǎn)都做不好（譬如SQL永遠(yuǎn)不可能出自一個(gè)數(shù)據(jù)庫很爛的人手里），基本上這不是什么語言設(shè)計(jì)的問題。所以這個(gè)系列只會(huì)針對(duì)前一種情況——也就是設(shè)計(jì)一門通用的語言。通用的語言其實(shí)也有自己的“領(lǐng)域”，只是太多了，所以被淡化了。縱觀歷史，你讓一個(gè)只做過少量的領(lǐng)域的人去設(shè)計(jì)一門語言，如果他沒有受過程序設(shè)計(jì)語言理論的系統(tǒng)教育，那只能做出屎。譬如說go就是其中一個(gè)——雖然他爹很牛逼，但反正不包含“設(shè)計(jì)語言”這個(gè)事情。

因此，在21世紀(jì)你還要做一門語言，無非就是對(duì)所有的通用語言都不滿意，所以你想自己做一個(gè)。不滿意體現(xiàn)在什么方面？譬如說C#的原因可能就是他爹不夠帥啦，譬如說C++的原因可能就是自己智商太低hold不住啦，譬如說Haskell的原因可能就是用的人太少招不到人啦，譬如說C的原因可能就是實(shí)在是無法完成人和抽象所以沒有l(wèi)inus的水平的人都會(huì)把C語言寫成屎但是你又招不到linus啦，總之有各種各樣的原因。不過排除使用者的智商因素來講，其實(shí)有幾個(gè)語言我還是很欣賞的——C++、C#、Haskell、Rust和Ruby。如果要我給全世界的語言排名，前五名反正是這五個(gè)，雖然他們之間可能很難決出勝負(fù)。不過就算如此，其實(shí)這些語言也有一些讓我不爽的地方，讓我一直很想做一個(gè)新的語言（來給自己用（？）），證據(jù)就是——“看我的博客”。

那么。一個(gè)好的語言的好，體現(xiàn)在什么方面呢？一直以來，人們都覺得，只有庫好用，語言才會(huì)好用。其實(shí)這完全是顛倒了因果關(guān)系，如果沒有好用的語法，怎么能寫出好用的庫呢？要找例子也很簡單，只要比較一下Java和C#就夠了。C#的庫之所以好用，跟他語言的表達(dá)能力強(qiáng)是分不開的，譬如說linq（，to xml，to sql，to parser，etc），譬如說WCF（僅考慮易用性部分），譬如說WPF。Java能寫得出來這些庫嗎？硬要寫還是可以寫的，但是你會(huì)發(fā)現(xiàn)你無論如何都沒辦法把他們做到用起來很順手的樣子，其實(shí)這都是因?yàn)镴ava的語法垃圾造成的。這個(gè)時(shí)候可以抬頭看一看我上面列出來的五種語言，他們的特點(diǎn)都是——因?yàn)檎Z法的原因，庫用起來特別爽。

當(dāng)然，這并不要求所有的人都應(yīng)該把語言學(xué)習(xí)到可以去寫庫。程序員的分布也是跟金字塔的結(jié)構(gòu)一樣的，庫讓少數(shù)人去寫就好了，大多數(shù)人盡管用，也不用學(xué)那么多，除非你們想成為寫庫的那些。不過最近有一個(gè)很不好的風(fēng)氣，就是有些人覺得一個(gè)語言難到自己無法【輕松】成為寫庫的人，就開始說他這里不好那里不好了，具體都是誰我就不點(diǎn)名了，大家都知道，呵呵呵。

好的語言，除了庫寫起來又容易又好用以外，還有兩個(gè)重要的特點(diǎn)：容易學(xué)，容易分析。關(guān)于容易學(xué)這一點(diǎn)，其實(shí)不是說，你隨便看一看就能學(xué)會(huì)，而是說，只要你掌握了門道，很多未知的特性你都可以猜中。這就有一個(gè)語法的一致性問題在里面了。語法的一致性問題，是一個(gè)很容易讓人忽略的問題，因?yàn)樗幸驗(yàn)檎Z法的一致性不好而引發(fā)的錯(cuò)誤，原因都特別的隱晦，很難一眼看出來。這里我為了讓大家可以建立起這個(gè)概念，我來舉幾個(gè)例子。

第一個(gè)例子是我們喜聞樂見的C語言的指針變量定義啦：

int a, *b, **c;

相信很多人都被這種東西坑過，所以很多教科書都告訴我們，當(dāng)定義一個(gè)變量的時(shí)候，類型最后的那些星號(hào)都要寫在變量前面，避免讓人誤解。所以很多人都會(huì)想，為什么要設(shè)計(jì)成這樣呢，這明顯就是挖個(gè)坑讓人往下跳嘛。但是在實(shí)際上，這是一個(gè)語法的一致性好的例子，至于為什么他是個(gè)坑，問題在別的地方。

我們都知道，當(dāng)一個(gè)變量b是一個(gè)指向int的指針的時(shí)候，*b的結(jié)果就是一個(gè)int。定義一個(gè)變量int a;也等于在說“定義a是一個(gè)int”。那我們來看上面那個(gè)變量聲明：int *b;。這究竟是在說什么呢？其實(shí)真正的意思是“定義*b是一個(gè)int”。這種“定義和使用相一致”的方法其實(shí)正是我們要推崇的。C語言的函數(shù)定義參數(shù)用逗號(hào)分隔，調(diào)用的時(shí)候也用逗號(hào)分隔，這是好的。Pascal語言的函數(shù)定義參數(shù)用分號(hào)分隔，調(diào)用的時(shí)候用逗號(hào)分隔，這個(gè)一致性就少了一點(diǎn)。

看到這里你可能會(huì)說，你怎么知道C語言他爹就是這么想的呢？我自己覺得如果他不是這么想的估計(jì)也不會(huì)差到哪里去，因?yàn)檫€有下面一個(gè)例子：

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

這也是一個(gè)“定義和使用相一致”的例子。就第一行代碼來說，我們要如何看待“int F(int a, int b);”這個(gè)寫法呢？其實(shí)跟上面一樣，他說的是“定義F(a, b)的結(jié)果為int”。至于a和b是什么，他也告訴你：定義a為int，b也為int。所以等價(jià)的，下面這一行也是“定義(*f)(a, b)的結(jié)果為int”。函數(shù)類型其實(shí)也是可以不寫參數(shù)名的，不過我們還是鼓勵(lì)把參數(shù)名寫進(jìn)去，這樣Visual Studio的intellisense會(huì)讓你在敲“(”的時(shí)候把參數(shù)名給你列出來，你看到了提示，有時(shí)候就不需要回去翻源代碼了。

關(guān)于C語言的“定義和使用相一致”還有最后一個(gè)例子，這個(gè)例子也是很美妙的：

int a;
typedef int a;

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

typedef是這樣的一個(gè)關(guān)鍵字：他把一個(gè)符號(hào)從變量給修改成了類型。所以每當(dāng)你需要給一個(gè)類型名一個(gè)名字的時(shí)候，就先想一想，怎么定義一個(gè)這個(gè)類型的變量，寫出來之后往前面加個(gè)typedef，事情就完成了。

不過說實(shí)話，就一致性來講，C語言也就到此為止了。至于說為什么，因?yàn)樯厦孢@幾條看起來很美好的“定義和使用相一致”的規(guī)則是不能組合的，譬如說看下面這一行代碼：

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

這個(gè)時(shí)候我們?cè)倩仡^看一看上面那一段長長的函數(shù)指針數(shù)組變量的聲明，會(huì)發(fā)現(xiàn)其實(shí)在這種時(shí)候，C語言還是希望你把它看成“int* b;”的這種形式的：f是一個(gè)數(shù)組，數(shù)組返回了一個(gè)函數(shù)指針，函數(shù)返回int，函數(shù)的參數(shù)是int(*a)(int, int)所以他還是一個(gè)函數(shù)指針。

我們?yōu)槭裁磿?huì)覺得C語言在這一個(gè)知識(shí)點(diǎn)上特別的難學(xué)，就是因?yàn)樗瑫r(shí)混用了兩種原則來設(shè)計(jì)語法。那你說好的設(shè)計(jì)是什么呢？讓我們來看看一些其它的語言的作法：

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語言好的地方在于，他們只采用一種原則——這就比好的和壞的混在一起要強(qiáng)多了（這一點(diǎn)go也是，做得比C語言更糟糕）。

當(dāng)然，上面這個(gè)說法對(duì)Haskell來說其實(shí)并不公平。Haskell是一種帶有完全類型推導(dǎo)的語言，他不認(rèn)為類型聲明是聲明的一部分，他把類型聲明當(dāng)成是“提示”的一部分。所以實(shí)際上當(dāng)你真的需要一個(gè)這種復(fù)雜結(jié)構(gòu)的函數(shù)的時(shí)候，實(shí)際上你并不會(huì)真的去把它的類型寫出來，而是通過寫一個(gè)正確的函數(shù)體，然后讓Haskell編譯器幫你推導(dǎo)出正確的類型。我來舉個(gè)例子：

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

關(guān)于foldr有一個(gè)很好的理解方法，譬如說foldr 0 (+) [1,2,3,4]說的就是1 + (2 + (3 + (4 + 0)))。而(.)其實(shí)是一個(gè)把兩個(gè)函數(shù)合并成一個(gè)的函數(shù)：f (.) g = \x->f(g( x ))。所以上述代碼的意思就是，如果我有下面的三個(gè)函數(shù)：

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

那么當(dāng)我寫下下面的代碼的時(shí)候：

superApply [sqr, mul2, add1] 1

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

Haskell代碼的簡潔程度真是喪心病狂啊，因?yàn)槿绻覀円肅++來寫出對(duì)應(yīng)的東西的話（C語言的參數(shù)無法是一個(gè)帶長度的數(shù)組類型所以其實(shí)是寫不出等價(jià)的東西的），會(huì)變成下面這個(gè)樣子：

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++不僅要把每一個(gè)步驟寫得很清楚，而且還要把類型描述出來，整個(gè)代碼就變得特別的混亂。除此之外，C++還沒辦法跟Haskell一樣吧三個(gè)函數(shù)直接搞成一個(gè)vector然后送進(jìn)這個(gè)SuperApply里面直接調(diào)用。當(dāng)然有人會(huì)說，這還不是因?yàn)镠askell里面有foldr嘛。那讓我們來看看同樣有foldr（reverse + aggregate = foldr）的C#會(huì)怎么寫：

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

C#基本上已經(jīng)達(dá)到跟Haskell一樣的描述過程了，而且也可以寫出下面的代碼了，就是無論聲明和使用的語法的噪音稍微有點(diǎn)大……

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

為什么要在討論語法的一致性的時(shí)候說這些問題呢，在這里我想向大家展示Haskell的另一種“定義和使用相一致”的做法。Haskell整個(gè)語言都要用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)

斐波那契數(shù)列的簡單形式甚至還可以這么寫：

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

甚至連遞歸都可以寫成：

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

Haskell到處都貫徹了“函數(shù)和操作符的替換關(guān)系”和“pattern matching”兩個(gè)原則來做“定義和實(shí)現(xiàn)相一致”的基礎(chǔ)，從而實(shí)現(xiàn)了一個(gè)比C語言那個(gè)做了一半的混亂的原則要好得多的原則。

有些人可能會(huì)說，Haskell寫遞歸這么容易，那會(huì)不會(huì)因?yàn)楣膭?lì)人們寫遞歸，而整個(gè)程序充滿了遞歸，很容易stack overflow或者降低運(yùn)行效率呢？在這里你可以往上翻，在這篇文章的前面有一句話“好的語言，除了庫寫起來又容易又好用以外，還有兩個(gè)重要的特點(diǎn)：容易學(xué)，容易分析。”，這在Haskell里面體現(xiàn)得淋漓盡致。

我們知道循環(huán)就是尾遞歸，所以如果我們把代碼寫成尾遞歸，那Haskell的編譯器就會(huì)識(shí)別出來，從而在生成x86代碼的時(shí)候把它處理成循環(huán)。一個(gè)尾遞歸遞歸函數(shù)的退出點(diǎn)，要么是一個(gè)不包含自身函數(shù)調(diào)用的表達(dá)式，要么就是用自身函數(shù)來和其它參數(shù)來調(diào)用。聽起來比較拗口，不過說白了其實(shí)就是：

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

當(dāng)你寫出這樣的代碼的時(shí)候，Haskell把你的代碼編譯了之后，就會(huì)真的輸出一個(gè)循環(huán)，從而上面的擔(dān)心都一掃而空。

實(shí)際上，有很多性能測試都表明，在大多數(shù)平臺(tái)上，Haskell的速度也不會(huì)被C/C++慢超過一倍的同時(shí)，要遠(yuǎn)比go的性能高出許多。在Windows上，函數(shù)式語言最快的是F#。Linux上則是Scala。Haskell一直都是第二名，但是只比第一名慢一點(diǎn)點(diǎn)。

為了不讓文章太長，好分成若干次發(fā)布，每次間隔都較短，所以今天的坑我只想多講一個(gè)——C++的指針的坑。剩下的坑留到下一篇文章里面。下面要講的這個(gè)坑，如果不是在粉絲群里面被問了，我還不知道有人會(huì)這么做：

class Base
{
  ...
};

class Derived : public Base
{
  ...
};

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

我想說，這完全是C++兼容C語言，然后讓C語言給坑了。其實(shí)這個(gè)問題在C語言里面是不會(huì)出現(xiàn)的，因?yàn)镃語言的指針其實(shí)說白了只有一種：char*。很多C語言的函數(shù)都接受char*，void*還是后來才有的。C語言操作指針用的malloc和free，其實(shí)也是把他當(dāng)char*在看。所以當(dāng)你malloc了一個(gè)東西，然后cast成你需要的類型，最后free掉，這一步cast存在不存在對(duì)于free能否正確執(zhí)行來說是沒有區(qū)別的。

但是事情到了C++就不一樣了。C++有繼承，有了繼承就有指針的隱式類型轉(zhuǎn)換。于是看上面的代碼，我們new[]了一個(gè)指針是Derived*類型的，然后隱式轉(zhuǎn)換到了Base*。最后我們拿他delete[]，因?yàn)閐elete[]需要調(diào)用析構(gòu)函數(shù)，但是Base*類型的指針式不能正確計(jì)算出Derived數(shù)組的10個(gè)析構(gòu)函數(shù)需要的this指針的位置的，所以在這個(gè)時(shí)候，代碼就完蛋了（如果沒完蛋，那只是巧合）。

為了兼容C語言，“new[]的指針需要delete[]”和“子類指針可以轉(zhuǎn)父類指針”的兩條規(guī)則成功的沖突到了一起。實(shí)際上，如果需要解決這種問題，那類型應(yīng)該怎么改呢？其實(shí)我們可以跟C#一樣引入Derived[]的這種指針類型。這還是new[]出來的東西，C++里面也可以要求delete[]，但是區(qū)別是他再也不能轉(zhuǎn)成Base[]了。只可惜，T[]這種類型被C語言占用了，在函數(shù)參數(shù)類型里面當(dāng)T*用。C語言浪費(fèi)語法罪該萬死呀……

待續(xù)

上一篇文章對(duì)大部分文法都構(gòu)造出了一個(gè)使用的狀態(tài)機(jī)了，這次主要來講右遞歸的情況。右遞歸不像左遞歸那么麻煩，因?yàn)榇蟛糠钟疫f歸寫成循環(huán)也不會(huì)過分的讓語法樹變得難以操作，不過仍然有少數(shù)情況是我們?nèi)匀幌ＭＡ暨f歸的語法樹形狀，譬如C++的連等操作，因此這里就來講一下這個(gè)問題。

右遞歸是怎么形成的呢？在這里我們先不想這個(gè)問題，我們來看一個(gè)普通的文法。在上一篇文章我們已經(jīng)說過了，如果一條文法有一個(gè)非終結(jié)符引用了另一條文法，那么就要做一條shift和reduce來從這個(gè)狀態(tài)機(jī)穿插到那個(gè)狀態(tài)機(jī)上：

在這里需要講一下，綠色的箭頭是shift，紫色的箭頭是reduce，他們都是ε邊。更進(jìn)一步說，如果A剛好以B作為結(jié)尾，那么A的最后一個(gè)輸入就不是終結(jié)符輸入，不過因?yàn)樗皇怯疫f歸，所以現(xiàn)在看起來還沒什么問題：

我們已經(jīng)接近右遞歸的形狀了。右遞歸的一個(gè)根本特征當(dāng)然是遞歸（廢話）。為了制作一個(gè)右遞歸，我們可以想一下，如果A和B不是兩個(gè)rule而是同一個(gè)rule會(huì)怎么樣？當(dāng)然咋這么一看，好像就是A可以訪問自己了：

實(shí)際上這已經(jīng)構(gòu)成了一個(gè)ε邊的循環(huán)。左遞歸是shift的循環(huán)，右遞歸是reduce的循環(huán)，其實(shí)他們都一樣。那你可能會(huì)想，既然左遞歸和右遞歸只是相反的情況，為什么左遞歸處理起來就那么容易，右遞歸好像就沒什么方法呢？其實(shí)如果你只是想要檢查一個(gè)字符串是不是一個(gè)文法的其中一個(gè)元素而不建立語法樹的話，你完全可以把這條循環(huán)的ε reduce邊給壓縮成一條。為什么呢？在之前講到，我們可以判斷一個(gè)reduce是不是由左遞歸造成的，我們也可以判斷一個(gè)shift是不是由右遞歸造成的。這種shift只要不壓狀態(tài)進(jìn)棧，那么右遞歸的reduce循環(huán)不管循環(huán)多少次，其實(shí)都是pop一個(gè)狀態(tài)出來，于是問題就沒有了。等價(jià)地，不處理語法樹的話，其實(shí)左遞歸也可以用相同的方法處理。

但是一旦當(dāng)你涉及到創(chuàng)建語法樹的問題，你就等于給每一條邊都加上了一些semantic actions。這個(gè)時(shí)候shift和reduce就不是簡單地可以互相抵消的關(guān)系了，于是你就不能把一個(gè)循環(huán)的ε reduce邊壓縮成一條，那怎么辦呢？

方法其實(shí)很簡單，只要我們?cè)跔顟B(tài)機(jī)走著走著發(fā)現(xiàn)無路可走的時(shí)候，看看有沒有一條右遞歸reduce可以給我們“試一試”就好了。為什么可以這樣做呢？我們還記得，當(dāng)我們把整個(gè)狀態(tài)及壓縮到?jīng)]有ε邊的時(shí)候，每一個(gè)輸入都需要對(duì)堆棧的情況進(jìn)行一次匹配。令人欣慰的事，沒有什么邊可以跟右遞歸的reduce邊一樣產(chǎn)生同樣的匹配結(jié)構(gòu)（但是我不想在這里證明），所以這樣做是安全的。

到了這里，我們已經(jīng)把構(gòu)造不帶lookahead狀態(tài)機(jī)的所有情況都說清楚了。一個(gè)文法如果需要構(gòu)造lookahead的話，其實(shí)就等于在邊的匹配規(guī)則里面加上一條對(duì)未來的一些token的要求，并沒有本質(zhì)上改變語法分析的結(jié)構(gòu)。但是我們知道，還有兩種上下文無關(guān)文法是不在這里面的，C語言全占了。我在這里舉兩個(gè)簡單的例子：

變量聲明：對(duì)于一個(gè)已經(jīng)typedef過的結(jié)構(gòu)我們完全可以寫出這樣的代碼：A*B;。這個(gè)時(shí)候A如果是類型，那這就需要走VariableDeclarationStatement的rule。如果A是一個(gè)表達(dá)式，那這就需要走ExpressionStatement的rule。但是對(duì)于語法分析來說，A就是一個(gè)簡單的token（除了typedef過的類型以外，所有C語言的類型都是以關(guān)鍵字開頭的，所以如果你們想做簡單的C語言的parser，就去掉typedef吧，啊哈哈哈哈），在語法分析的時(shí)候是無法做出預(yù)測的。

這種時(shí)候有兩種方法，第一種是準(zhǔn)備更加豐富的semantic actions，讓符號(hào)表可以在parse的時(shí)候構(gòu)造出來。那到了這里，我們根據(jù)A究竟是不是一個(gè)類型，就可以賺到不同的分支上了。另一種就是，我們保留一個(gè)AmbiguousStatement的語法樹節(jié)點(diǎn)，把語法樹的一顆子樹遇到的不能處理的歧義的情況都寫進(jìn)去。我們可能回想，為什么我們不干脆一個(gè)parser返回多個(gè)分析結(jié)果呢？因?yàn)槿绻贿@么做的話，一個(gè)函數(shù)里面有10個(gè)這樣子的變量聲明，那你就有1024個(gè)結(jié)果了。如果我們把歧義收縮到一顆子樹上，那其實(shí)還是1個(gè)結(jié)果，只是多了10顆子樹，效果完全不同。

強(qiáng)制類型轉(zhuǎn)換：寫C語言的時(shí)候是不可能沒有強(qiáng)制類型轉(zhuǎn)換的，但是當(dāng)parser看到類似這樣的代碼的時(shí)候：(A*****)B，因?yàn)轭愋偷慕Y(jié)構(gòu)和表達(dá)式的結(jié)構(gòu)是不一樣的，但是你這個(gè)時(shí)候并不能在看到“(”的時(shí)候就做lookahead——因?yàn)檫@個(gè)lookahead是無限長的，括號(hào)里面的表達(dá)式或者類型都可以無限長。不過就算你想把他局限成有限長，就算你給100個(gè)token，那也會(huì)長出成千上萬種lookahead的模式，所以在這里我們就不要用lookahead了。

那怎么做呢？我們只需要把這個(gè)狀態(tài)機(jī)當(dāng)成NDA（因?yàn)榈搅诉@里他已經(jīng)是NDA了），從deterministic push-down automaton變成了non-deterministic push-down automaton，我們也唯有讓我們的parser也變成non-deterministic了。關(guān)于這個(gè)內(nèi)容，就等到下一篇——也就是這個(gè)系列的最后一篇文章——來詳細(xì)講解了。

一、

這篇文章是應(yīng)之前在微博上爆過的下個(gè)周末某出版社的線下活動(dòng)而寫的?；仡櫸液虲++在這個(gè)世紀(jì)的第二個(gè)春天開始發(fā)生過的種種事情，我發(fā)現(xiàn)我并不是用一個(gè)正常的方法來學(xué)會(huì)如何正常使用C++的。我的C++學(xué)習(xí)伴隨著很多其他流行或者不流行的語言?，F(xiàn)在手中掌握的很多淫蕩的技巧正是因?yàn)閷W(xué)習(xí)了很多編程語言的緣故，不過這并不妨礙我正常地使用C++來在合理的時(shí)間內(nèi)完成我的目標(biāo)。

學(xué)習(xí)C++是一個(gè)艱難的過程。如果從我第一次看C++的書算起，現(xiàn)在已經(jīng)過了11年了。一開始的動(dòng)機(jī)也是很不靠譜的。剛開始我很喜歡用VB6來開發(fā)游戲，但是我能找到的資料都是用C++來做例子的，文字部分又不豐富，于是我遇到了很多困難。因此我去三聯(lián)書店買了本C++的書，想著我如果學(xué)會(huì)了C++，就可以把這些例子翻譯成VB6的代碼，然后繼續(xù)用VB6來寫游戲。陰差陽錯(cuò)，我買到的是一本語法手冊(cè)。不過那個(gè)時(shí)候我還小，不知道什么是MSDN，也不知道MSDN是可以打印出來賣的：

不過因?yàn)镃++在當(dāng)時(shí)并不是我學(xué)習(xí)的重點(diǎn)，于是我就沒事的時(shí)候翻一翻。我們都知道語言參考手冊(cè)（MSDN里面叫Language Reference）的順序都是按照類別而不是教學(xué)順序來排列的。于是當(dāng)我花了很長時(shí)間看完了第一遍的時(shí)候，就覺得這本書寫的云里霧里。剛開始講什么是表達(dá)式的時(shí)候，例子就出現(xiàn)了大量的函數(shù)和類這種更加復(fù)雜的東西。于是我選擇重新看一遍，基本的概念就都知道了。當(dāng)然這個(gè)時(shí)候完全不能算“學(xué)會(huì)C++”，編程這種事情就跟下象棋一樣，規(guī)則都很容易，但是你想要下得好，一定要通過長期的練習(xí)才能做到。

當(dāng)然，在這段時(shí)間里面，我依然是一邊看C++一邊用VB6來學(xué)習(xí)編程。初二的時(shí)候?qū)W校發(fā)了QBasic的課本，當(dāng)時(shí)看了一個(gè)星期就完全學(xué)會(huì)了，我覺得寫代碼很好玩，于是從此就養(yǎng)成了我沒事逛書店的習(xí)慣（就連長大了之后泡MM也有時(shí)候會(huì)去書店，哈哈哈哈哈）。值得一提的是，我第二次去書店的時(shí)候，遇到了下面的這本書《Visual Basic高級(jí)圖形程序設(shè)計(jì)教程》：

在這之前我買到的兩本VB6的書都是在教你怎么用簡單的語法，拖拖界面。然后就做出一個(gè)程序來。那個(gè)時(shí)候我心目中編程的概念就是寫寫記事本啊、寫字板啊、計(jì)算器等等這些東西，直到我發(fā)現(xiàn)了這本書。我還記得當(dāng)時(shí)的心情。我在書架上隨手翻了翻，發(fā)現(xiàn)VB竟然也可以寫出那么漂亮的圖形程序。

這本書包含的知識(shí)非常豐富，從如何調(diào)用VB內(nèi)置的繪圖命令、如何調(diào)用Windows API函數(shù)來快速訪問圖片，講到了如何做各種圖像的特效濾鏡、如何做幾何圖形的變換，一直到如何對(duì)各種3D物體做真實(shí)感渲染，甚至是操作4維圖形，都講得清清楚楚。這本書比其他大多數(shù)編程讀物好的地方在于，讀者可以僅靠里面的文字，基本不用看他的代碼，就可以學(xué)會(huì)作者想讓你學(xué)會(huì)的所有東西。因此當(dāng)我發(fā)現(xiàn)我怎么著也找不到這本書的光盤（事實(shí)上書店就沒有給我）的時(shí)候，我并沒有感到我失去了什么。這本書的文字部分不僅寫得很詳細(xì)，而且作者還很負(fù)責(zé)任。作者知道像圖形這種對(duì)數(shù)學(xué)基礎(chǔ)有一定要求的東西，程序員不一定懂——尤其是我那個(gè)時(shí)候才上初中，就更不可能懂了——所以在書里面看到一些復(fù)雜的數(shù)學(xué)公式的時(shí)候，作者都會(huì)很耐心的告訴你這些公式的來源，它們的“物理意義”，有些時(shí)候甚至還會(huì)推導(dǎo)給你看。因此可以想象，這本書包含的內(nèi)容也特別的豐富。這導(dǎo)致我在讀的時(shí)候不斷地找資料補(bǔ)充自己的數(shù)學(xué)知識(shí)，從而可以親自把那些程序?qū)懀ǘ皇浅┏鰜?。這個(gè)過程一直持續(xù)到了我終于不用VB轉(zhuǎn)Delphi，到最后上大學(xué)改用C++的那個(gè)時(shí)候，我終于理解了整本書里面講的所有內(nèi)容，給我后面的很多事情打下了堅(jiān)實(shí)的基礎(chǔ)。

因?yàn)閿?shù)學(xué)知識(shí)缺乏的關(guān)系，學(xué)習(xí)這些基礎(chǔ)知識(shí)又不可能那么快，所以我把一部分時(shí)間投入在了游戲開發(fā)里面，嘗試自己弄點(diǎn)什么出來。畢竟當(dāng)時(shí)對(duì)編程有興趣，就是因?yàn)?#8220;說不定游戲也可以用代碼寫出來”的想法，于是我得到了下面的這本書：

這本書是我覺得21天驚天陰謀系列里面唯一一本良心的書。它并沒有只是簡單的羅列知識(shí)，而是教你利用VB6內(nèi)置的功能搭建從簡單到復(fù)雜的游戲程序。我第一次看到關(guān)于鏈表的知識(shí)就是在這里。可惜在我還沒學(xué)會(huì)如何使用VB6的類模塊功能之前，我就已經(jīng)投向了Delphi，因此并沒有機(jī)會(huì)實(shí)踐這個(gè)知識(shí)。不過在此之后，我用VB6寫的小游戲，已經(jīng)嘗試把游戲本身的模塊（這是VB6的一個(gè)功能，就跟namespace差不多）分離，積累一些基礎(chǔ)代碼。

在這段時(shí)間里面，我學(xué)習(xí)語法都學(xué)得很慢。循環(huán)甚至是在我用人肉展開循環(huán)的方法一行一行復(fù)制黏貼出了一個(gè)井字棋的AI之后才學(xué)會(huì)的。后來很晚才學(xué)會(huì)了寫函數(shù)，全局變量則更晚了。于是在那個(gè)時(shí)候我寫了很多看起來很愚蠢的代碼。曾經(jīng)我以為一個(gè)函數(shù)的全局變量在退出函數(shù)之后是會(huì)保留的，然后對(duì)著自己寫出來的不能運(yùn)行的代碼感到十分的莫名其妙。還有一次做一個(gè)記事本，因?yàn)椴恢?#8220;當(dāng)前文件路徑”要存在什么地方，于是在界面上放了一個(gè)Label來放文件名。后來有了雄心壯志，想用VB搞定一個(gè)長得像Basic的超簡陋的腳本。這當(dāng)然最后是失敗了，但是我依稀記得，我當(dāng)時(shí)取得的成就就是把腳本語言的字符串分割成了一個(gè)一個(gè)的token之后，保存在了一個(gè)表格控件里面，以便之后（后來這個(gè)“之后”沒寫出來）讀的時(shí)候方便一點(diǎn)。之后還嘗試寫一個(gè)讀四則運(yùn)算字符串計(jì)算結(jié)果的程序，都是先找最里層的括號(hào)，把那條不帶括號(hào)的簡單式子計(jì)算完之后，把結(jié)果也處理成字符串replace回去。直到整個(gè)字符串收斂成一個(gè)值為止。一直等到我后來買到了一本系統(tǒng)介紹VB6語法和用法的書之后，我的代碼才稍微變得不像猴子打出來的。

在剛開始學(xué)編程的時(shí)候，基本上都沒有什么固定的方向，都是在書店里面碰到什么酒寫什么。于是有一次我在書店里看到了《Visual Basic 網(wǎng)絡(luò)高級(jí)編程》

這本書是我在學(xué)習(xí)VB的過程中最后一本我覺得不錯(cuò)的書了。雖然VB本身也提供了很多訪問網(wǎng)絡(luò)資源的控件，但是這本書并沒有讓你僅僅會(huì)用被人的輪子來寫代碼，而是一步一步的告訴你這些網(wǎng)絡(luò)協(xié)議的內(nèi)容，然后讓你用Socket來跟這些服務(wù)器直接交互。我記得我最后成功的做出了一個(gè)郵件收發(fā)程序，跟聯(lián)想1+1系列自帶程序的功能已經(jīng)可以媲美了。

二、

當(dāng)我發(fā)現(xiàn)C++實(shí)在是太難，根本沒辦法真的把網(wǎng)上那些C++的程序改成VB之后，我上了高一，接觸了NOI。NOI讓我得到的一個(gè)收獲就是，讓我在上了大學(xué)之后很堅(jiān)定的不把時(shí)間浪費(fèi)在ACM上，從而有了很多時(shí)間可以搞圖形、編譯器和女同學(xué)。參加高中的NOI培訓(xùn)讓我知道了什么是數(shù)據(jù)結(jié)構(gòu)，還有什么是指針。老師在講Pascal的時(shí)候說，要靈活使用指針才可以寫出高性能的程序。這讓我大開眼界，不僅因?yàn)閂B沒有指針，而且當(dāng)時(shí)用VB寫圖形的程序感覺怎么樣也快不上去（當(dāng)然這有大半原因是因?yàn)槲掖a寫得爛，不能全怪VB）的同時(shí)，還讓我認(rèn)識(shí)了Delphi。Delphi跟VB一樣可以拖控件，而且控件長得還很像。于是我就抱著試一試的心理，開始學(xué)習(xí)如何用Delphi來寫代碼。

因?yàn)橛小禫isual Basic 高級(jí)圖形程序設(shè)計(jì)教程》的知識(shí)作為背景，我很快就掌握了如何用Delphi來開發(fā)跟圖形相關(guān)的程序。那個(gè)時(shí)候我覺得該做的準(zhǔn)備已經(jīng)準(zhǔn)備好了，于是用Delphi寫了一遍我在VB的時(shí)候總是寫不快的一個(gè)RPG游戲。這個(gè)游戲雖然不大，但是結(jié)構(gòu)很完整。在開發(fā)這個(gè)游戲的過程中，我第一次體驗(yàn)到了模塊化開發(fā)的好處，以及積累基礎(chǔ)代碼對(duì)開發(fā)的便利性。同時(shí)也讓我嘗到了一個(gè)難以維護(hù)的程序時(shí)多么的可怕。這個(gè)游戲前后開發(fā)了八個(gè)月，有一半的事件都是在寫代碼。對(duì)于當(dāng)時(shí)的我來說，程序的結(jié)構(gòu)已經(jīng)過于復(fù)雜，代碼也多到差不多失控的地步了。后來我統(tǒng)計(jì)了一下，一共有一萬兩千行代碼。由于那個(gè)時(shí)候我的調(diào)試能力有限，而且也不知道如何把程序?qū)懗梢子谡{(diào)試的形式。結(jié)果我等到了我的核心部分都寫完了之后，才能按下F9做第一次的運(yùn)行（?。。。?。當(dāng)然運(yùn)行結(jié)果是一塌糊涂。我花了很大的努力才把搞到能跑。

由于程序本身過長，我在開發(fā)的過程中覺得已經(jīng)很難控制了。再加上我發(fā)現(xiàn)我的同一個(gè)模塊里的函數(shù)基本上都是下面的形式：
PrefixFunction(var data:DataStructure, other parameters ...)
總覺得跟調(diào)用Delphi的類庫的時(shí)候很像。所以我就想，既然代碼都變成了這樣，那是不是學(xué)習(xí)面向?qū)ο箝_發(fā)會(huì)好一點(diǎn)？在這個(gè)過程中我有幸遇到了這本《Delphi6 徹底研究》：

雖然說這本書并沒有包含那些深刻的面向?qū)ο蟮闹R(shí)，但是他詳細(xì)的介紹了Delphi的語法、基礎(chǔ)的類庫的用法還有Delphi那套強(qiáng)大的控件庫和數(shù)據(jù)開發(fā)的能力。這本書第一次讓我知道，Delphi是可以內(nèi)嵌匯編代碼的。這給我對(duì)計(jì)算機(jī)的深入理解打開了一扇門。

學(xué)習(xí)匯編是一個(gè)漫長的過程。這倒不是因?yàn)閰R編的概念很復(fù)雜，而是因?yàn)槔锩娴募?xì)節(jié)實(shí)在是太多了。這些知識(shí)靠網(wǎng)絡(luò)上零星的文章實(shí)在是無法掌握，于是在常年逛書店的習(xí)慣之下，我又遇到了《Windows 匯編語言程序設(shè)計(jì)教程》。

這本書內(nèi)容其實(shí)并不是很多，但是他給了我一個(gè)很好的入門的方法，也講了一些簡單的匯編的技巧，譬如說怎么寫循環(huán)啊，怎么用REPZ這樣的前綴等等，讓我可以用匯編寫出有意義的程序。匯編和Delphi的結(jié)合也促使我開始去思考他們之間的關(guān)系，譬如說一段Delphi的代碼就經(jīng)是如何映射到匯編上面的。下面發(fā)生的一個(gè)小故事讓我印象深刻。

那還是一個(gè)，我還很喜歡各種不知所謂的奇技淫巧的日子。有一天我在論壇里看到有人說，交換兩個(gè)integer變量可以用一種奇葩的寫法：
a:=a xor b;
b:=b xor a;
a:=a xor b;
于是我就理所當(dāng)然得想，如果我把它改成匯編，那是不是可以更快，并且超過那種需要中間變量的寫法？后來我試了一次，發(fā)現(xiàn)慢了許多。這個(gè)事件打破了我對(duì)會(huì)變的迷信，當(dāng)然什么C語言是最快的語言之類的，我從此也就以辯證的眼光去看帶了。在接下來的高中生涯里，我只用了匯編一次，那還是在一個(gè)對(duì)圖像做alpha blending的程序里面。我要同時(shí)計(jì)算RGB，但是寄存器每一個(gè)都那么大，我覺得很浪費(fèi)，于是嘗試用R<<16+G放到一個(gè)寄存器里面，跟另一個(gè)R<<16+G相加。中間隔了一個(gè)字節(jié)用來做進(jìn)位的緩沖，從而達(dá)到了同時(shí)計(jì)算兩個(gè)byte加法的效果。后來測試了一下，的確比直接用Delphi的代碼來寫要快一些。

純粹的教程類書籍看多了之后，除了類庫用得熟、代碼寫得多以外，好處并不大。所以當(dāng)我有一天在書店里發(fā)現(xiàn)《凌波微步》的時(shí)候，剛翻開好幾頁，我就被它的內(nèi)容吸引住了，斷然入手。

這本書讓我第一次覺得，一個(gè)程序?qū)懙煤煤蛯懙脿€竟然有如此之大的差別。作者下筆幽默，行文詼諧，把十幾個(gè)例子用故事一般的形式講出來。這本書不告訴你什么是好的，而告訴你什么是不好的。每一個(gè)案例的開頭都給出了寫得不好的代碼的例子，然后會(huì)跟你解釋的很清楚，說這么做有什么不好，改要怎么改的同時(shí)，為什么好的方法是長那個(gè)樣子的。這本書也開始讓我相信方法論的意義。在這個(gè)時(shí)候之前，我在編程這個(gè)東西上的理論基礎(chǔ)基本上就只有鏈表和排序的知識(shí)，其它的東西基本都不懂，但是想做出自己想要做的事情卻又不覺得有什么太大的麻煩。甚至我到高三的時(shí)候?qū)懥艘粋€(gè)帶指令集和虛擬機(jī)的Pascal腳本語言（不含指針）的時(shí)候，我連《編譯原理》這本書都沒有聽過。因此以前覺得，反正要寫程序，只要往死里寫，總是可以寫出來的。但是實(shí)際上，有理論基礎(chǔ)和沒有理論基礎(chǔ)的程序員之間的區(qū)別，不在于一個(gè)程序能不能寫出來，而在于寫出來之后性能是不是好，代碼是不是容易看懂的同時(shí)還很好改，而且還容易測試。這本書對(duì)于我的意義就是給我?guī)砹诉@么一個(gè)觀點(diǎn)，從而讓我開始想去涉獵類似的內(nèi)容。

當(dāng)然，那段時(shí)間只是這么想，但是卻不知道要看什么。所以在一次偶然之下，我發(fā)現(xiàn)了《OpenGL 超級(jí)寶典》。當(dāng)然第一次看的時(shí)候還是第二版，后來我又買了第三版。

鑒于以前因?yàn)椤禫isual Basic 高級(jí)圖形程序設(shè)計(jì)教程》的緣故，我在看這本書之前已經(jīng)用Delphi寫過一個(gè)簡單的支持簡單光照和貼圖的軟件渲染程序，于是看起來特別的快。其實(shí)OpenGL相比起DirectX，入門級(jí)的那部分API（指glBegin(GL_TRIANGLE_STRIP)這些）是做得比DirectX漂亮的，可惜性能太低，沒人會(huì)真的在大型游戲里使用。剩下的那部分比DirectX就要爛多了。所以當(dāng)我開始接觸高級(jí)的API的時(shí)候，OpenGL的低速部分讓我戀戀不舍。OpenGL的程序我一路寫到了差不多要高考的時(shí)候。在那之前學(xué)習(xí)了一些簡單的技巧。上了大學(xué)之后，學(xué)習(xí)了一些骨骼動(dòng)畫啊、LOD模型啊、場景管理這些在OpenGL和DirectX上都通用的知識(shí)，但是卻并沒有在最后把一個(gè)游戲給做出來。

我最后一次用OpenGL，是為了做一個(gè)自繪的C++GUI庫。這個(gè)庫的結(jié)構(gòu)比起現(xiàn)在的GacUI當(dāng)然是沒法。當(dāng)時(shí)用OpenGL來做GUI的時(shí)候，讓我感覺到要操作和渲染字符串在OpenGL上是困難重重，已經(jīng)難到了幾乎沒辦法處理一些高級(jí)文字效果（譬如RichText的渲染）的地步了。最后只能每次都用GDI畫完之后把圖片作為一個(gè)貼圖保存起來。OpenGL貼圖數(shù)量有限，為了做這個(gè)事情還得搞一個(gè)貼圖管理器，把不同的文字都貼到同一張圖上。做得筋疲力盡之余，效果還不好。當(dāng)我后來開發(fā)GacUI的時(shí)候，我用GDI和DirectX作為兩個(gè)渲染器后端，都成功的把RichText渲染實(shí)現(xiàn)出來了，我就覺得我以后應(yīng)該再也不會(huì)使用OpenGL了。GDI和DirectX才是那種完整的繪圖API，OpenGL只能用來畫圖，寫不了字。

有些人可能會(huì)覺得，為什么我會(huì)一直在同時(shí)做圖形圖像、編譯器和GUI的事情。大家還記得上文我曾經(jīng)說過我曾經(jīng)用了好久做了一個(gè)伊蘇那種模式的RPG出來。其實(shí)我一直都很想走游戲開發(fā)的路線，可惜由于各種現(xiàn)實(shí)原因，最后我沒有把這件事情當(dāng)成工作。做出那個(gè)RPG的時(shí)候我也很開心，絲毫不亞于我畢業(yè)后用C#寫出了一個(gè)帶智能提示的代碼編輯器的那一次。當(dāng)然在上大學(xué)之后我已經(jīng)覺得沒有一個(gè)美工是做不出什么好游戲的，但是想花時(shí)間跟你一起干的美工同學(xué)又很難找，因此干脆就來研究游戲里面的各種技術(shù)，于是就變成了今天這個(gè)樣子。當(dāng)然，現(xiàn)在開發(fā)游戲的心思還在，我想等過些時(shí)日能夠空閑了下來，我就來忽悠個(gè)美工妹紙慢慢搞這個(gè)事情。

雖然說《Visual Basic高級(jí)圖形程序設(shè)計(jì)教程》是一本好書，但這只是一本好的入門書，想要深入了解這方面的內(nèi)容還是免不了花時(shí)間看其他材料的。后來我跟何詠一起做圖形的時(shí)候，知識(shí)大部分來源于論文。不過圖像方面，還是下面這本岡薩雷斯寫的《數(shù)字圖像處理》給了我相當(dāng)多的知識(shí)。

這本書的特點(diǎn)是，里面沒有代碼，我很喜歡，不會(huì)覺得浪費(fèi)錢。不過可惜的是在看完這本書之后，我已經(jīng)沒有真的去寫什么圖像處理的東西了。后面做軟件渲染的時(shí)候，我也沒有把它當(dāng)成我的主業(yè)來做，權(quán)當(dāng)是消磨時(shí)間。每當(dāng)我找不到程序可以寫覺得很傷心的時(shí)候，就來看看論文，改改我那個(gè)軟件渲染器，增加點(diǎn)功能之后，我就會(huì)發(fā)現(xiàn)一個(gè)新的課題，然后把時(shí)間都花在那上面。

三、

整個(gè)高三的成績都不錯(cuò)，所以把時(shí)間花在編程上的時(shí)候沒人理我，直到我二模一落千丈，因此在高考前一個(gè)月只好“封筆”，好好學(xué)習(xí)。最后因?yàn)槭д`看錯(cuò)了題目，在高考的時(shí)候丟了十幾分的原始分，估計(jì)換算成標(biāo)準(zhǔn)分應(yīng)該有幾十分之多吧，于是去了華南理工大學(xué)。所幸這本來就是我的第一志愿，所以當(dāng)時(shí)我也不覺得有什么不開心的。去了華南理工大學(xué)之后，一個(gè)令我感到十分振奮的事情就是，學(xué)校里面有圖書館，圖書館的書還都不錯(cuò)。雖然大部分都很爛，但是因?yàn)榛鶖?shù)大，所以總能夠很輕松的找到一些值得看的東西。

我還記得我們那一年比較特殊，一進(jìn)去就要軍訓(xùn)。軍訓(xùn)的時(shí)候電腦還沒來得及帶去學(xué)校，學(xué)校也不給開網(wǎng)絡(luò)，所以那一個(gè)月的晚上都很無聊，跟同學(xué)也還不熟悉，不知道要干什么。所以那段時(shí)間每到軍訓(xùn)吃晚飯，我就會(huì)跑到學(xué)校的圖書館里面泡到閉館為止。于是有一天讓我發(fā)現(xiàn)了李維寫的這本《Inside VCL》。

雖然到了這個(gè)時(shí)候我用Delphi已經(jīng)用得很熟悉了，同時(shí)也能寫一些比較復(fù)雜的程序了，但是對(duì)于Delphi本身的運(yùn)作過程我是一點(diǎn)都不知道。所以當(dāng)我發(fā)現(xiàn)這本書的時(shí)候，如魚得水。這本書不僅內(nèi)容深刻，更重要的是寫的一點(diǎn)都不晦澀難懂，所以我看的速度非?？??；旧厦總€(gè)晚上都可以看100頁，連續(xù)七八天下來這本書就被我翻完了。這帶來了一個(gè)副作用就是，圖書館的姐姐也認(rèn)識(shí)我了——當(dāng)然這并沒有什么用。

過后我又在書店得到了一本《Delphi 源代碼分析》。

這本書跟《Inside VCL》的區(qū)別是，《Inside VCL》講的是VCL的設(shè)計(jì)是如何精妙，《Delphi 源代碼分析》講的則是Delphi本身的基礎(chǔ)設(shè)施的內(nèi)部實(shí)現(xiàn)的細(xì)節(jié)。以前我從來不了解也沒主動(dòng)想過，Delphi的AnsiString和UnicodeString是指向一個(gè)帶長度記錄的字符串指針，學(xué)習(xí)了指針我也沒把這兩者聯(lián)系起來（當(dāng)然這跟我當(dāng)時(shí)還沒開始試圖寫C++程序有關(guān)）。于是看了這本書，我就有一種醍醐灌頂?shù)母杏X。雖然這一切看起來都是那么的自然，讓我覺得“就是應(yīng)該這么實(shí)現(xiàn)的才對(duì)”，但是在接觸之前，就是沒有去想過這個(gè)事情。

令人遺憾的是，在我得到這本書的同時(shí)，Borland也把Delphi獨(dú)立出來做了一個(gè)叫做Codegear的公司，后來轉(zhuǎn)手賣掉了。我在用Delphi的時(shí)候還想著，以后干脆去Borland算了，東西做得那么好，在那里工作肯定很開心。我在高中的時(shí)候還曾經(jīng)把Borland那個(gè)漂亮的總部的圖片給我媽看過，不過她一直以為是微軟的。于是我在傷心了兩個(gè)晚上之后，看了一眼為了做參考我?guī)У綄W(xué)校來的《Visual C++ 5.0語言參考手冊(cè)》，找了一個(gè)盜版的Visual C++ 2005，開始決定把時(shí)間投入在C++上面了。于是Delphi之旅到此結(jié)束，從此之后，就是C++的時(shí)光了。

四、

學(xué)習(xí)圖形學(xué)的內(nèi)容讓我學(xué)會(huì)了如何寫一個(gè)高性能的計(jì)算密集型程序，也讓我不會(huì)跟很多程序員一樣排斥數(shù)學(xué)的內(nèi)容。學(xué)習(xí)Delphi讓我開闊了眼界的同時(shí)，還有機(jī)會(huì)讓我了解Delphi內(nèi)部工作原理和細(xì)節(jié)。這一切都為我之后做那些靠譜的編譯器打下了基礎(chǔ)。

因?yàn)樵诟呷臅r(shí)候我在不懂得《編譯原理》和大部分?jǐn)?shù)據(jù)結(jié)構(gòu)的知識(shí)的情況下，用Delphi寫出了一個(gè)Pascal腳本引擎，所以當(dāng)我聽說我大學(xué)的班主任是教編譯原理的時(shí)候，我就很開心，去跟她交流這方面的內(nèi)容，把我當(dāng)時(shí)的設(shè)想也拿給她看。當(dāng)然我的設(shè)想，沒有理論基礎(chǔ)的知識(shí)，都是很糟糕的，于是班主任就給了我一本《編譯原理》。當(dāng)然，這并不是《龍書》，而是一本質(zhì)量普通的書。不過當(dāng)我了解了這方面的內(nèi)容之后，《龍書》的大名也就進(jìn)入我的耳朵里了：

由于之前用很愚蠢的方法寫了個(gè)Pascal腳本的緣故，看《龍書》之后很容易就理解了里面各種精妙的算法在工程上的好處。我之前的作法是先用掃描的方法切下一個(gè)一個(gè)的token，然后做一個(gè)遞歸來遞歸去復(fù)雜到自己都沒法看的一遍掃描生成簡單指令的方法來做。程序?qū)懗鰜碇笪耶?dāng)場就已經(jīng)看不懂了。自從看了《龍書》之后，我才知道這些過程可以用token和語法樹來對(duì)算法之間進(jìn)行解耦。不過《龍書》的性質(zhì)也是跟《Visual Basic 高級(jí)圖形程序設(shè)計(jì)教程》一樣，是入門類的書籍。用來理解一下編譯器的運(yùn)作過程是沒問題的，但是一旦需要用到高級(jí)的知識(shí)。

這個(gè)時(shí)候我已經(jīng)初步理解了編譯器前端的一些知識(shí)，但是后端——譬如代碼生成和垃圾收集——卻還是一知半解。不過這并不妨礙我用好的前端知識(shí)和爛的后端知識(shí)來做出一個(gè)東西來。當(dāng)時(shí)我簡單看了一下Java語言的語法，把我不喜歡的那些東西砍掉，然后給他加上了泛型。Java那個(gè)時(shí)候的泛型實(shí)現(xiàn)好像也是剛剛出現(xiàn)的，但是我不知道，我也從來沒想過泛型要怎么實(shí)現(xiàn)。所以當(dāng)時(shí)我想來想去做了一個(gè)決定，泛型只讓編譯器去檢查就好了，編譯的時(shí)候那些T都當(dāng)成object來處理，然后就把東西做出來了。我本來以為我這種偷工減料拆東墻補(bǔ)西墻忽悠傻逼用戶的方法是業(yè)界所不容的，不過后來發(fā)現(xiàn)Java竟然也是那么做的，讓我覺得我一定要黑他一輩子。后來我用我做的這個(gè)破語言寫了一個(gè)俄羅斯方塊的游戲，拿給了我的班主任看，向她證明她拿給我的書我沒有白看。

不過由于受到了Delphi的影響，我并沒有在我的C++代碼里面使用泛型。當(dāng)時(shí)由于不了解STL，也懶得去看，于是自己就嘗試折騰這么幾個(gè)容器類自己用?，F(xiàn)在代碼還留著，可以給大家貼一段：

這段代碼已經(jīng)可以作為反面教材使用了。除了基類有一個(gè)virtual的析構(gòu)函數(shù)和代碼對(duì)齊的比較漂亮以外，基本所有的地方都是設(shè)計(jì)錯(cuò)誤的典型表現(xiàn)。為了這段代碼的貼圖我特地在硬盤里面翻出來了我那個(gè)山寨Java腳本的代碼，一打開就有一股傻逼的氣息撲面而來，截圖放進(jìn)word之后，屏幕猶如溢屎，內(nèi)容不堪入目。

之所以把代碼寫成這樣，跟Delphi的class不是值類型的這個(gè)功能是分不開的。寫了幾年的Delphi之后，再加上第一次開始寫有點(diǎn)小規(guī)模的C++程序，我從來沒考慮過一個(gè)用來new的class是可以創(chuàng)建成值類型的。所以那個(gè)時(shí)候我一直處于用C++的語法來寫Delphi的狀態(tài)上。當(dāng)然這樣是不對(duì)的，但是因?yàn)槟且欢螘r(shí)間運(yùn)氣比較背，好的C++書都沒給我碰上，直到我看到了《C++語言的設(shè)計(jì)和演化》

C++他爹寫的這本《C++語言的設(shè)計(jì)和演化》是一本好書，我認(rèn)為每一個(gè)學(xué)習(xí)C++的人都應(yīng)該看。本來《C++Primer》也是一本不錯(cuò)的書，不過因?yàn)槲谊幉铌栧e(cuò)用了《Visual C++ 5.0 語言參考手冊(cè)》入門，所以這本書就被我跳過了。一開始C++用得很爛，覺得渾身不舒服，但是有知道為什么?？戳诉@本書之后很多疑問就解決了。

《C++語言的設(shè)計(jì)和演化》講的是當(dāng)年C++他爹發(fā)明C++的時(shí)候如何對(duì)語言的各種功能做取舍的故事。在這個(gè)長篇小說里面，C++他爹不厭其煩地說，雖然C++看起來很鳥，但是如果不這樣做，那就會(huì)更鳥?？赐炅诉@本書之后，基本上就剩下不會(huì)模板元編程了，剩下的語言的功能都知道在什么時(shí)候應(yīng)該用，什么時(shí)候不該用。C++他爹還描述了一些重要的類——譬如說智能指針和STL的迭代器——在語義上的意思。其實(shí)這就跟我們?cè)诳创鼵++11的shared_ptr、unique_ptr和weak_ptr的時(shí)候，不要去想這是一個(gè)delete對(duì)象的策略，而是要想這是一個(gè)描述對(duì)象所有權(quán)關(guān)系的這么個(gè)“關(guān)鍵字”一樣。有些時(shí)候細(xì)節(jié)看得太明白，而忽略了更高層次上的抽象，此乃見樹木不見森林。

C++知道每一個(gè)特性如何正常使用還不夠，如果不知道他們是如何實(shí)現(xiàn)的，那有可能在非常極端的情況下，寫出來的程序會(huì)發(fā)揮的不好。正如同如果你知道C++編譯器、操作系統(tǒng)和CPU內(nèi)部是如何處理這些東西的細(xì)節(jié)，如果你順著他們?nèi)懩愕某绦虻脑?，那性能的提高?huì)特別明顯。譬如說在做渲染器的時(shí)候，為什么光線追蹤要按照希爾伯特順序來發(fā)射光線，為什么KD樹可以把每一個(gè)節(jié)點(diǎn)壓縮成8個(gè)字節(jié)的同時(shí)還會(huì)建議你按層來排列他們，都是因?yàn)檫@些背后的細(xì)節(jié)所致。這些細(xì)節(jié)做得好，渲染器的效率提高一倍是完全沒問題的。這些知識(shí)固然很多，但是C++的那部分，卻包含在了一本《深度探索C++對(duì)象模型》里面：

讀《深度探索C++對(duì)象模型》，不僅僅是為了知道C++在涉及虛擬多重繼承基類的成員函數(shù)指針結(jié)構(gòu)是怎樣的，而且你還可以從中學(xué)到很多技巧——當(dāng)然是指數(shù)據(jù)結(jié)構(gòu)的技巧。這本書的內(nèi)容大概分為兩個(gè)部分。第一個(gè)部分就跟需求一樣，會(huì)跟你介紹C++的對(duì)象模型的語義，主要就是告訴你，如果你這樣寫，那你就可以獲得XXX，失去YYY。第二部分就跟實(shí)現(xiàn)一樣。按照需求來得到一個(gè)好的實(shí)現(xiàn)總是一個(gè)程序員想做的事情，那么這就是個(gè)很好的例子。正常使用C++需要的無限智慧，大部分就包含在上面這兩本書里面。一旦把這兩本書的內(nèi)容都理解好，以后寫起C++的代碼都會(huì)得心應(yīng)手，不會(huì)被各種坑所困擾，正確審視自己的代碼。

文章之前的部分有提到過，讓我正視理論和方法論的意義的是《凌波微步》，所以當(dāng)工具都掌握的差不多的時(shí)候，總需要花時(shí)間補(bǔ)一補(bǔ)這方面的內(nèi)容。首當(dāng)其沖當(dāng)然就是大家喜聞樂見的《算法導(dǎo)論》了。我記得當(dāng)時(shí)是唐良同學(xué)推薦給我的這本書，還重點(diǎn)強(qiáng)調(diào)了一定要看原文，因?yàn)橹形牡姆g不行。所以我就在一個(gè)春光明媚的早上，來到了廣州天河書城，把這本書搞到手。

這本書的封面顏色暗示著你，想讀這本書， 應(yīng)該去一個(gè)山清水秀綠蔭環(huán)繞的地方。事實(shí)證明這是對(duì)的。在差不多考英語四級(jí)的前后，我有一段時(shí)間每天都去華南理工大學(xué)那個(gè)著名的分手亭看這本書。亭子后面是一個(gè)湖，前面有很多樹和雜草，旁邊還有一個(gè)藝術(shù)學(xué)院，充滿了人文的氣息。在這種地方看《算法導(dǎo)論》，不僅吸收得快，而且過了一年，我真的分手了。

說實(shí)話這本書我沒有看完，而且那些證明的部分我都跳過了，實(shí)在是對(duì)這些東西沒有興趣。不過關(guān)于數(shù)據(jù)結(jié)構(gòu)和大部分算法我看得很仔細(xì)。于是我在這方面的能力就大幅度提高——當(dāng)然跟那些搞ACM的人相比反應(yīng)還是不夠快，不過我的志向并不在這里。除此之外，我通過《算法導(dǎo)論》也學(xué)到了如何準(zhǔn)確的計(jì)算一個(gè)函數(shù)的時(shí)間復(fù)雜度和空間復(fù)雜度。事實(shí)證明這個(gè)技能十分重要，不僅可以用來找bug，還可以用來面試。

五、

對(duì)于一個(gè)讀計(jì)算機(jī)的大學(xué)生來說，算法懂了，工具會(huì)了，接下來就是開眼界了。不過這些東西我覺得是沒法強(qiáng)求的，就像下面這本《程序設(shè)計(jì)語言——實(shí)踐之路》一樣，都是靠運(yùn)氣才到手的——這是一個(gè)小師妹送我的生日禮物：

原本學(xué)習(xí)的匯編也好，VB、Delphi和C++也好，都是同一類的編程語言。這導(dǎo)致我在相當(dāng)長的時(shí)間里面都無疑為編程就差不多是這個(gè)樣子。直到我看到了《程序設(shè)計(jì)語言——實(shí)踐之路》。這本書告訴我，這個(gè)世界上除了命令是語言，還有各種不同的編程的范式和方法。于是借著這本書的機(jī)會(huì)，我了解到世界上還有Prolog、Erlang和Haskell這么美妙的語言。

這對(duì)我的觸動(dòng)很大。一直以來我都是用一種編程方法來解決所有我遇到的問題的。然后突然有一天，我發(fā)現(xiàn)有很多問題用別的方法來解決更好，于是我就開始去研究這方面的內(nèi)容。一開始我的認(rèn)識(shí)還是比較淺，應(yīng)用這些方法的時(shí)候還處于只能了解表面的狀態(tài)，譬如說曾經(jīng)流行過幾天的Fluent Interface，還有聲明式編程啊，AOP等等。直到我遇到了這本全面改變我對(duì)C++模板看法的書——《Real World Haskell》：

是的，你沒看錯(cuò)，是《Real World Haskell》！Haskell顛覆了我的世界觀，讓我第一次知道，原來代碼也是可以推導(dǎo)的。說實(shí)話我用Haskell用的并不熟，而且我也沒寫過多少個(gè)Haskell的大程序，但是Haskell的很多方面我都去花了很長時(shí)間去了解，譬如那個(gè)著名的Monad。多虧了當(dāng)時(shí)搞明白了Monad，我借助這方面的知識(shí)，理解了《Monadic Parser Combinator》這篇論文，還看懂a(chǎn)joo那篇著名的面向組合子編程系列。

當(dāng)我終于明白了Haskell的類型推導(dǎo)之后，我終于體會(huì)到了Haskell和C++之間的巨大差異——Haskell的程序的邏輯，都是完全表達(dá)在函數(shù)簽名上的類型里面，而不是代碼里的。當(dāng)你寫一個(gè)Haskell函數(shù)的時(shí)候，你首先要知道你的函數(shù)是什么類型的，接下來你就把代碼當(dāng)成是方程的解一樣，找到一個(gè)滿足類型要求的實(shí)現(xiàn)。Haskell的表達(dá)式一環(huán)扣一環(huán)，幾乎每兩個(gè)部分的類型都互相制約，要求特別嚴(yán)格。導(dǎo)致Haskell的程序只要編譯通過，基本上不用運(yùn)行都有95%的概率是靠譜的，這一點(diǎn)其他語言遠(yuǎn)遠(yuǎn)達(dá)不到。而且Haskell的類庫（Hackage）之多覆蓋GUI、GPU程序、分布式、并發(fā)支持、圖像處理，甚至是網(wǎng)頁（Haskell Server Page）都有，用來寫實(shí)用的程序完全沒問題。之所以Haskell不流行，我覺得僅有的原因就是對(duì)初學(xué)者來說太難了，但是人們一旦熟悉了C的那一套，看Haskell的難度就更大了，比什么都不會(huì)的時(shí)候更大。

于是回過頭來，模板元編程也就變成一個(gè)很自然的東西了。你把模板元編程看成是一門語言，把“類型”本身看成是一個(gè)巨大的帶參數(shù)enum的一部分（scala叫case type），于是類型的名字就變成了值，那么模板元編程的技巧，其實(shí)就是對(duì)類型進(jìn)行變換、操作和計(jì)算的過程。接下來只要會(huì)用模板的形式來表達(dá)if、while、函數(shù)調(diào)用和類型匹配，那掌握模板元編程是順利成章的事情。撇去type traits這些只是模板元編程的具體應(yīng)用不說，只要熟悉了Haskell，熟悉C++的模板語法，學(xué)會(huì)模板元編程，只需要一個(gè)下午——就是學(xué)會(huì)用蹩腳的方法來寫那些你早就熟悉了的控制流語句罷了。

當(dāng)模板元編程變成了跟寫i++一樣自然的東西之后，我看語言的感覺也變了。現(xiàn)在看到一個(gè)程序語言，再也不是學(xué)習(xí)與發(fā)這么簡單了，而是可以看到作者設(shè)計(jì)這門語言的時(shí)候想灌輸給你的價(jià)值觀。譬如說，為什么C語言的typedef長那個(gè)樣子的？因?yàn)樗敫嬖V你，你int a;定義的是一個(gè)變量，那么typedef int a;就把這個(gè)變量的名字改成了類型的名字。為什么C語言定義函數(shù)的時(shí)候，參數(shù)是用逗號(hào)隔開？因?yàn)槟阏{(diào)用函數(shù)的時(shí)候，也是用逗號(hào)來隔開參數(shù)的。這就是語法里面的一致性問題。一個(gè)一致性好的語言，一個(gè)有編程經(jīng)驗(yàn)初學(xué)者只要學(xué)習(xí)到了其中的一部分，就可以推測他所想要的未知特性究竟是如何用于發(fā)表達(dá)出來的。一個(gè)一致性差的語言，你每一次學(xué)到一個(gè)新的功能或者語法，都是一個(gè)全新的形式，到處雜亂無章，讓人無可適從（所以我很討厭go，還不把go的library移植成C++直接用C++寫算了）。

從此之后，我就從一個(gè)解決問題的程序員，變成一個(gè)研究編程本身的程序員了。當(dāng)然我并不去搞什么學(xué)術(shù)研究，我也不打算走在理論的前沿——這并不適合我，我還是覺得做一個(gè)程序員是更快樂一點(diǎn)的。這些知識(shí)在我后續(xù)學(xué)習(xí)開發(fā)編譯器和設(shè)計(jì)語言的時(shí)候，起了決定性的作用。而且當(dāng)你知道如何設(shè)計(jì)一個(gè)優(yōu)美的語法，那么你用現(xiàn)有的語法來設(shè)計(jì)一個(gè)優(yōu)美的library，也就不會(huì)那么難了。當(dāng)然，設(shè)計(jì)優(yōu)美的library是需要深入的了解正在使用的語言本身的，這樣的話有可能維護(hù)這個(gè)library的門檻就會(huì)提高。不過這沒有關(guān)系，這個(gè)世界上本來就有很多東西是2000塊錢的程序員所無法完成的，譬如維護(hù)STL，維護(hù)linux內(nèi)核，甚至是維護(hù)Microsoft Office。

六、

上面所列出來的書，每一本都是對(duì)我有深刻的影響的。當(dāng)然光有深刻的影響是不夠的，具體的領(lǐng)域的知識(shí)，還是需要更多的資料來深入研究，譬如說下面的一個(gè)單子，就是我在學(xué)習(xí)開發(fā)編譯器和虛擬機(jī)的時(shí)候所看過的。內(nèi)容都很深刻，很適合消磨時(shí)間。在這里我要感謝g9yuayon同學(xué)，他在我需要開闊眼界的時(shí)候，給我提供了大量的資料，讓我得以快速成長，功不可沒。

虛擬機(jī)——系統(tǒng)與進(jìn)程的通用平臺(tái)

Garbage Collection——Algorithms for Automatic Dynamic Memory Management

高級(jí)編譯器設(shè)計(jì)與實(shí)現(xiàn)（鯨書）

程序設(shè)計(jì)語言理論基礎(chǔ)

類型與程序設(shè)計(jì)語言

Parsing Techniques——A Practical Guide

The Implementation of Functional Programming Languages

今天我寫了一個(gè)給Visual C++用的配置，用來讓VC++在顯示自己寫的字符串和容器等設(shè)施變得跟顯示STL一樣漂亮。VC++的可配置型還是很高的，我們只要寫一個(gè)xml，就可以改變調(diào)試器對(duì)自己的數(shù)據(jù)結(jié)構(gòu)的顯示了.

在這里我簡單地介紹一下用法。假設(shè)大家覺得vlpp（Vczh Library++，也就是GacUI用的那個(gè)庫）的WString啊List這些東西在調(diào)試器里面顯示出來的東西太丑，就可以用以下三步來修改它。

1：去http://gac.codeplex.com/SourceControl/changeset/view/99419#2395529下載我寫的那個(gè)natvis文件。這個(gè)文件在整個(gè)zip包里面的位置是Common\vlpp.natvis
2：把這個(gè)文件復(fù)制到C:\Program Files (x86)\Microsoft Visual Studio 11.0\Common7\Packages\Debugger\Visualizers（如果使用默認(rèn)安裝路徑的話）
3：重啟你最喜愛的Visual Studio 2012，就可以看到下面的東西了：

空的智能指針

有東西的智能指針

有內(nèi)容的“惰性計(jì)算”類

有內(nèi)容但是還沒計(jì)算的“惰性計(jì)算”類

沒內(nèi)容的“惰性計(jì)算”類

新鮮熱辣的容器

新鮮熱辣的映射

就連一對(duì)多的映射也是如此的新鮮熱辣

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>

本來每年都要寫一篇年經(jīng)帖來提高一下知名度的，但是最近因?yàn)樽鯣acUI太興奮，竟然把這件事情給忘了，實(shí)在是罪過。

如果要說我2012年做過的什么事情最重要，那當(dāng)然要屬開發(fā)了GacUI（Home Page, Codeplex, Github）和創(chuàng)建了粉絲群（啊哈哈）了吧。博客到現(xiàn)在還有三個(gè)坑沒填完，分別是那個(gè)已經(jīng)坑了好久、大家都要看、但是我卻不知道要寫什么的《C++使用技巧》，還有兩個(gè)大家不怎么想看的《可配置語法分析器開發(fā)紀(jì)事》和《GacUI與設(shè)計(jì)模式》。

關(guān)于GacUI，我已經(jīng)在微博上做了許多廣告，也有一些人開始嘗試使用它了。目前GacUI還處于一個(gè)湊合著能用的beta狀態(tài)，我在接下來的很長一段時(shí)間內(nèi)應(yīng)該會(huì)繼續(xù)update它。我的本意是要把WPF那么精妙的設(shè)計(jì)給山寨到C++上面來，從而結(jié)束非得用MFC才能正常開發(fā)GUI的日子。而且因?yàn)橹拔矣肅#的WinForm開發(fā)IDE太蛋疼了，parser需要寫兩遍（編譯器一遍，IDE一遍，語言還不一樣），所以我在設(shè)計(jì)GacUI的時(shí)候，質(zhì)量要求就是朝著Visual Studio看齊的。所以大家會(huì)看到我在做GacUI的時(shí)候，文本框就內(nèi)置了高速的著色系統(tǒng)，還做了一個(gè)新的parser來產(chǎn)生嚴(yán)格的parser或者松散的parser，分別給編譯器和IDE使用。然后我用這個(gè)parser寫了一個(gè)xml和json的庫，最后在昨天還update了一下Linq to C++，把我看得不順眼的東西都干掉，于是我也擁有了一個(gè)Linq to Xml for C++的庫了。

但是GacUI還是有很多東西要做。我腦子里一直有一個(gè)清晰的路線圖，而且這個(gè)路線圖是直接朝著目標(biāo)前進(jìn)的：做一個(gè)C++的GUI庫，順便給一個(gè)類似Expression Blend那樣子的東西，然后那個(gè)框架還可以為我以后開發(fā)語言，或者給現(xiàn)有的語言做IDE。所以為了達(dá)到這個(gè)目標(biāo)，我至少要給GacUI的控件和對(duì)象模型做反射。為了讓大家可以使用，我還得準(zhǔn)備一個(gè)看起來跟MSDN很像的文檔。因此路線圖就是（粗體的部分已經(jīng)完成了）

1. 開發(fā)控件庫
2. 擁有一套生成Release的工具鏈，包括parser生成器、文檔生成器、各種代碼生成器等
3. 有一個(gè)小巧玲瓏簡單好用的XML庫
4. 可以讀PDB把GacUI的對(duì)象聲明都拿到手
5. 利用PDB和GacUI的源代碼里面的XML注釋生成文檔
6. 用一個(gè)類似C#那樣子的語法來給GacUI“聲明”一個(gè)對(duì)象模型，讓他可以被反射，也可以用來生成各種語言用的接口，特別是動(dòng)態(tài)語言例如javascript和python的
7. 把PDB的內(nèi)容和對(duì)象模型結(jié)合起來，生成C++用的反射代碼
8. 利用反射代碼，設(shè)計(jì)一個(gè)GUI的XML（或者別的什么東西）表示，從而實(shí)現(xiàn)動(dòng)態(tài)加載窗口
9. 制作一個(gè)長得和操作模式都跟Visual Studio差不多的多文檔編輯框架
10. 用上面的框架開發(fā)一個(gè)GUI編輯器，用來拖控件生成xml+資源，就可以嵌入C++的exe，或者提供給腳本語言使用了
11. 提供一個(gè)腳本語言，作為可選的插件，來簡化復(fù)雜GUI的開發(fā)
12. 給這個(gè)語言提供一個(gè)IDE

大家可以看到，這就是為什么我最近要花時(shí)間做著色、parser生成器、用parser生成器來生成xml和json的庫的parsing部分、做一個(gè)linq to C++并且讓xml庫直接支持就像C#的linq to xml一樣。雖然看起來這些東西跟GacUI本身毫無關(guān)系，但是實(shí)際上為了實(shí)現(xiàn)那個(gè)復(fù)雜又得自動(dòng)生成不然寫到孩子出來還人肉不完的反射代碼生成，一定要有配套的基礎(chǔ)設(shè)施才行。

關(guān)于粉絲群，因?yàn)槲壹尤氲拇蟛糠志幊虆^(qū)最后都癟了，所以本來我并沒有創(chuàng)建一個(gè)群用來交流技術(shù)的想法。不過因?yàn)槟橙河颜f找不到人研究我以前的代碼的一篇回復(fù)，我還是創(chuàng)建了這個(gè)群。本來群只有100人的，但是有兩個(gè)人贊助了一下，瞬間變成了500人群。所以以后不斷的有人進(jìn)來的時(shí)候我就再也不需要踢掉不說話的人了。很快群里就開始熱烈的討論起問題，經(jīng)常討論的那么十幾二十個(gè)人也這么固定下來了。這個(gè)群和別的群不一樣的地方在于，所有問傻逼問題和求大作業(yè)的全部被我和鸛貍猿們一個(gè)不留的干掉了，啊哈哈哈哈。

由于我在cppblog廣告的關(guān)系，加入這個(gè)群的人大部分還是做C++的，和S1那群做web的平時(shí)跟技術(shù)有關(guān)的話題完全不同，對(duì)待某些人生底線問題（譬如說大括號(hào)要不要換行等）的態(tài)度也是完全不同。當(dāng)然偶爾有人經(jīng)不住每天幾千個(gè)消息的沖擊退群了，但是群的熱烈程度還是一點(diǎn)也沒有消減。

關(guān)于C++實(shí)用技巧，由于我自詡是一個(gè)做C++基礎(chǔ)類庫的人，對(duì)待C++各種奇技淫巧的態(tài)度自然也是不一樣的。盡管大家都說C++學(xué)起來很難，坑很多，模板根本看不懂，析構(gòu)函數(shù)沒寫程序函數(shù)經(jīng)常要爛掉之類的，不過我的觀點(diǎn)還是很明確的——其實(shí)C++有很多難以理解的功能，都是給寫基礎(chǔ)類庫準(zhǔn)備的。只要程序員們不要本著“我一定要看懂類庫怎么寫才用”的這種無聊觀點(diǎn)的話，其實(shí)壓力并不會(huì)那么大。大多數(shù)人覺得C++難，但其實(shí)難的部分他做項(xiàng)目大概也是用不上的，本質(zhì)原因還是不夠淡定導(dǎo)致。

說到這里我就想起了以前跟人家討論的，為什么C#用起來就那么舒服呢？很重要的一點(diǎn)其實(shí)是，因?yàn)檫x擇少，所以連煩惱都沒有了。反正事情都能完成，但是方法只有一種的話，你永遠(yuǎn)都不需要去比較或者糾結(jié)說，究竟要用什么樣的方法來實(shí)現(xiàn)。而且一個(gè)自帶垃圾收集器+泛型+函數(shù)式編程+continuation的語言，語法懂得少也可以用，語法懂得多用起來還特別省事，這一點(diǎn)的確比C++要好得多。回想起2002在CSDN那個(gè)著名的對(duì)垃圾收集器的大討論，ajoo有一點(diǎn)說得很好，有沒有GC，設(shè)計(jì)出來的架構(gòu)都大不一樣。想想原因其實(shí)也很簡單，語言一旦帶有GC的話，通常都會(huì)對(duì)內(nèi)存做出嚴(yán)格的控制，因此你想干掉一個(gè)對(duì)象就只有一種方法——等他去死了（C#的IDisposable跟這個(gè)其實(shí)沒什么關(guān)系）。因此那些C++里面很執(zhí)著的誰創(chuàng)建誰刪除啊，COM的什么引用計(jì)數(shù)啊，這些亂七八糟的東西統(tǒng)統(tǒng)就沒有了。你可以不顧一起的創(chuàng)建各種細(xì)粒度對(duì)象，不斷地創(chuàng)建各種接口，而根本不用擔(dān)心這些對(duì)象在死的時(shí)候你要干些什么，不僅做出來的設(shè)計(jì)干凈，用起來也省心。

關(guān)于可配置語法分析器開發(fā)紀(jì)事，按照計(jì)劃還剩下兩篇，不過因?yàn)檫@兩篇的內(nèi)容已經(jīng)不怎么重要，所以最近的時(shí)間都用在開發(fā)GacUI上面了。等雜事搞完了之后我就補(bǔ)上這部分內(nèi)容。

關(guān)于GacUI與設(shè)計(jì)模式，這個(gè)系列自從寫了兩篇文章之后，盡管GacUI都是我一手寫出來的，但是我發(fā)現(xiàn)要整理出那個(gè)架構(gòu)清楚的表達(dá)出來，需要花很多的時(shí)間。為了保證文章的質(zhì)量，我干脆就暫時(shí)停下來了，一邊推進(jìn)GacUI的開發(fā)進(jìn)度，一邊 重新整理。雖然我從來都只用VC++來編譯我的代碼，不過GacUI從一開始設(shè)計(jì)架構(gòu)上就有考慮跨平臺(tái)的問題，而且我也把對(duì)Windows.h的依賴也局限在少數(shù)的幾個(gè)cpp文件里，頭文件則完全是沒有污染的。盡管代碼里面肯定有VC++對(duì)標(biāo)準(zhǔn)作出的一點(diǎn)點(diǎn)人性化修改而垃圾GCC故意不支持從而造成代碼不能再GCC上面編譯，不過在計(jì)劃上我大概會(huì)在今年的下半年開始把代碼修改成讓垃圾GCC也可以編譯GacUI了。

關(guān)于2013年，出去開發(fā)GacUI和心目中的那個(gè)腳本引擎，我在2013年最想點(diǎn)的技能樹就是編譯器的后端知識(shí)了。盡管我在09年的時(shí)候做過一個(gè)傻逼C語言編譯器，盡管也是編譯成機(jī)器碼，但是都是用最簡單粗暴的方法來做的。為了以后的腳本引擎，把這件事情做好，掌握編譯器的后端也就變成必要的事情了。不過我在這里還是想說，編譯器的前端知識(shí)也是很重要的。經(jīng)過設(shè)計(jì)語言的語法的訓(xùn)練，和對(duì)設(shè)計(jì)類型系統(tǒng)的訓(xùn)練，不僅可以提高數(shù)學(xué)知識(shí)、提高智商，還可以讓你學(xué)習(xí)新的語言和類庫變得更快。編程都是舉一反三的，并不是直接的針對(duì)他學(xué)習(xí)才是長遠(yuǎn)看來最好的方法。

上一篇博客寫到了如何給一個(gè)非終結(jié)符的文法規(guī)則構(gòu)造出一個(gè)壓縮過的下推狀態(tài)機(jī)，那么今天說的就是如何把所有的文法都連接起來。其實(shí)主要的idea在（三）和他的勘誤（三點(diǎn)五）里面已經(jīng)說得差不多了。但是今天我們要處理的是帶信息的transition，所以還有一些地方要注意一下。

所以在這里我們先把幾條文法的最后的狀態(tài)機(jī)都列出來（大圖）：

接下來的這一步，就是要對(duì)所有靠非終結(jié)符（Exp啊Term這些）進(jìn)行跳轉(zhuǎn)的transition都執(zhí)行上一篇文章所說的傳說中的交叉鏈接。在產(chǎn)生鏈接的時(shí)候，我們給shift和reduce的邊分別加上shift和reduce。而shift和reduce是有參數(shù)的——就是被shift走的狀態(tài)的id。這樣可以在parse的時(shí)候匹配和處理狀態(tài)堆棧。在這里我門對(duì)e3->e1這一步做一下操作做為例子。紅色的邊是被刪掉的，而粗壯的綠色邊是被新加進(jìn)去的：

紅色的邊變成了兩條綠色的邊，紅色的邊附帶的信息則被復(fù)制到了綠色的reduce邊上。當(dāng)我們使用這個(gè)狀態(tài)機(jī)的時(shí)候，shift(s3)就表示往堆棧里面壓入s3，reduce(s3)就表示從堆棧里面彈出(s3)。當(dāng)然彈出不一定會(huì)成功，所以如果不成功的話，這條邊就不能在當(dāng)時(shí)使用。因此這也就是為什么在e3跳轉(zhuǎn)到t0之后，t1知道往回跳的是e1而不是別的什么地方——就如同為什么C++的函數(shù)執(zhí)行完之后總是知道如何跳轉(zhuǎn)回調(diào)用它的地方一樣——因?yàn)榘研畔⑼迫肓硕褩！?/p>

那現(xiàn)在我們就來看一下，當(dāng)所有的非終結(jié)符跳轉(zhuǎn)都處理掉之后，會(huì)變成什么樣子吧（這個(gè)圖真是復(fù)雜和亂到我不想畫?。?，為了讓圖變得不那么糟糕，我把shift都變成紫色，reduce都變成綠色：

在添加shift和reduce邊之前，每一條邊都是有輸入token的。但是我們剛剛添加上去的shift和reduce邊卻是不輸入token的，所以他們是epsilon邊，下一步就是要消除他們。上面這個(gè)圖消除了epsilon邊之后，會(huì)變成一個(gè)狀態(tài)很少，但是每一條邊附帶的信息都會(huì)非常多，而且像n1這種經(jīng)常到達(dá)的狀態(tài)（因?yàn)樗膭t運(yùn)算里面有很多數(shù)字）將恢復(fù)射出無數(shù)條邊。到了這里這個(gè)狀態(tài)機(jī)已經(jīng)再也畫不出來了。所以我下面就只拿兩個(gè)例子來畫。下面要展示的是用Exp來parse單獨(dú)的一個(gè)數(shù)字會(huì)走的邊，當(dāng)然就是Exp –> Term –> Factor –> Number了：

就會(huì)被處理成：

注意邊上面的信息是要按順序重新疊加在一起的。當(dāng)所有的epsilon邊都去掉了之后，我們就得到了最終的一個(gè)狀態(tài)機(jī)。最重要的一件事情出現(xiàn)了。我們知道，發(fā)明LR和LALR這種東西就基本上是為了處理左遞歸的，所以這種圖就可以在去除epsilon邊的過程中自動(dòng)發(fā)現(xiàn)左遞歸。這是怎么做到的呢？只要在去除epsilon邊的時(shí)候，發(fā)現(xiàn)了一條完全由shift這種epsilon邊組成的環(huán)，那么左遞歸就發(fā)現(xiàn)了。為了方便，我們可以只處理直接左遞歸——就是這種環(huán)的長度是1的。不包含間接左遞歸的問法是很容易寫出來的。當(dāng)然這種環(huán)并不一定是首尾相接的，譬如說我們?cè)谔幚韊0的時(shí)候就會(huì)發(fā)現(xiàn)e0->t0->t0這種環(huán)（當(dāng)然嚴(yán)格來說環(huán)只有最后一截的這個(gè)部分）。我們的程序要很好地應(yīng)對(duì)這種情況。因?yàn)槲覀冎唤邮苤苯幼筮f歸，所以類似這種結(jié)構(gòu)的epsilon路徑可以直接的拋棄他，因?yàn)閠0->t0會(huì)被t0狀態(tài)單獨(dú)處理掉。因此這樣做并不會(huì)漏掉什么。

細(xì)心的朋友可能會(huì)發(fā)現(xiàn)，這個(gè)結(jié)構(gòu)的圖是不能直接處理右遞歸的（總之左遞歸和右遞歸總要有一個(gè)會(huì)讓你的狀態(tài)機(jī)傻逼就是了?。?。關(guān)于如何處理有遞歸（其實(shí)內(nèi)容也不復(fù)雜）地方法會(huì)在“下篇”描述出來。那處理左遞歸有什么用呢？舉個(gè)例子，我們的e0->e2就是一個(gè)左遞歸，而他會(huì)在之前的步驟被處理成shift(e0->e0)和reduce(e1->e2)。我們要記下shift和reduce的對(duì)應(yīng)關(guān)系，那么當(dāng)我們找到一個(gè)左遞歸的shift之后，我們就可以把對(duì)應(yīng)的reduce給標(biāo)記成“left-recursive-reduce”。這是一個(gè)在構(gòu)造語法樹的時(shí)候，非常關(guān)鍵的一種構(gòu)造指令。

處理完這些之后，我們可以把左遞歸的shift邊全部刪掉，最后把token和state都統(tǒng)統(tǒng)處理成連續(xù)的數(shù)字，做成一張[state, token] –> [transitions]的二維表，每一個(gè)表的元素是transition的列表。為什么是這樣呢？因?yàn)槲覀儗?duì)一個(gè)state輸入一個(gè)token之后，由于保存著state的堆棧（你還記得嗎？shift==push，reduce==pop）的棧頂若干個(gè)元素的不同，可能會(huì)走不通的路線。于是最后我們就得到了這么一張圖。

下面這張圖可以通過運(yùn)行g(shù)ac.codeplex.com上面的Common\UnitTest\UnitTest.sln（VS2012限定）之后，在Common\UnitTest\TestFiles\Parsing.Calculator.Table.txt里面找到。這一組文件都是我在測試狀態(tài)機(jī)的時(shí)候log下來的。

如果大家有VS2012的話，通過運(yùn)行我準(zhǔn)備的幾個(gè)輸入，譬如說“1*2+3*4”，就可以在Parsing.Calculator.[2].txt里面找到所有狀態(tài)跳轉(zhuǎn)的軌跡。因?yàn)槲覀兛偸切枰猵arse一個(gè)Exp，所以我們從22: Exp.RootStart開始。我們假設(shè)token stream的第一個(gè)和最后一個(gè)分別是$TokenBegin和$TokenFinish。上圖的$TryReduce是為了應(yīng)對(duì)右遞歸而設(shè)計(jì)出來的一種特殊輸入。由于四則運(yùn)算里面并沒有右遞歸，所以這一列就是空的：

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

我們把所有跳轉(zhuǎn)過的transition的信息都記錄下來，就可以構(gòu)造語法蘇了。我們想象一下，在執(zhí)行這些指令的時(shí)候，遇到NUMBER[4]就等于獲得了一個(gè)內(nèi)容為4的token，shift的話就是往堆棧里面push進(jìn)一個(gè)狀態(tài)的名字，而reduce則是彈出。

相對(duì)應(yīng)的，因?yàn)槊恳粋€(gè)文法都會(huì)創(chuàng)建一個(gè)對(duì)象，所以我們?cè)诔跏蓟臅r(shí)候，要先放一個(gè)空對(duì)象在堆棧上。shift一次就再創(chuàng)建一個(gè)空的對(duì)象push進(jìn)去，reduce的時(shí)候就把棧頂?shù)膶?duì)象彈出來作為“待處理對(duì)象”，using了就把待處理對(duì)象和棧頂對(duì)象合并，left-reduce就是把棧頂對(duì)象彈出來作為待處理對(duì)象的同時(shí)，push一個(gè)空對(duì)象進(jìn)去。assign fieldName就是把“待處理對(duì)象”保存到棧頂對(duì)象的叫做fieldName的成員變量里面去。如果棧頂對(duì)象為空，那么被保存的對(duì)象就是剛剛輸入的那個(gè)token了。因此我們從頭到尾執(zhí)行一遍之后，就可以得到下面的一顆語法樹：

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的過程就結(jié)束了。在“下篇”——也就是（六）——里面，我會(huì)講述如何處理右遞歸，然后這個(gè)系列基本上就要完結(jié)了。