其實我在寫這個系列的第三篇文章的時候就已經發現，距離機器越遠，也就是抽象越高的概念，坑的數量是越少的。但是這并不是說，距離機器越近的概念就越強大或者說越接近本質。這是廣大的程序員對計算理論的一種誤解。大多數人理解編程的知識結構的時候，都是用還原論來理解的，這個方法其實并沒有錯。但問題在于，“還原”的方法并不是唯一的。很多人覺得，反正你多高級的語言編譯完了無非都是機器碼嘛。但是還有另一種解釋，你無論多低級的語言編譯完了無非也就是帶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的過程就結束了。在“下篇”——也就是（六）——里面，我會講述如何處理右遞歸，然后這個系列基本上就要完結了。