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