GP技術的展望——先有鴻鈞后有天
莫華楓
自從高級語言出現以來，類型始終是語言的核心。幾乎所有語言特性都要以類型作為先決條件。類型猶如天地，先于萬物而存在。但是，是否還有什么東西比類型更加原始，更加本質，而先于它存在呢？請往下看。:)
泛型和類型
泛型最簡短最直觀的描述恐怕應該是：the class of
type。盡管這樣的描述不算最完備，但也足以說明問題。早在60年代，泛型的概念便已經出現。最初以“參數化類型”的名義存在。70年代末期發展起來的
恐龍級的Ada（我的意思不是說
Augusta Ada Byron Lovelace伯爵夫人是恐龍，從畫像上看，這位程序員的祖師奶長得相當漂亮:)），尚未擁有oop（Ada83），便已經實現了泛型（Generic)。盡管泛型歷史悠久，但真正全面地發展起來，還是在90年代初，
天才的
Alexander A. Stepanov創建了stl，促使了“
泛型編程”（
Generic Programming）的確立。
出于簡便的目的，我套用一個老掉牙的“通用容器”來解釋泛型的概念。（就算我敷衍吧:P，畢竟重頭戲在后面，具體的請看前面給出的鏈接）。假設我在編程時需要一個int類型的棧，于是我做了一個類實現這個棧：
class IntStack {...};
用的很好。過了兩天，我又需要一個棧，但是類型變成了double。于是，我再另寫一個：
class DoubleStack {...};
不得了，好象是通了馬蜂窩，不斷地出現了各種類型的棧的需求，有string的，有datetime的，有point的，甚至還有一個Dialog的。每
種類型都得寫一個類，而且每次代碼幾乎一樣，只是所涉及的類型不同而已。于是，我就熱切地期望出現一種東西，它只是一個代碼的框架，實現了stack的所
有功能，只是把類型空著。等哪天我需要了，把新的類型填進去，便得到一個新的stack類。
這便是泛型。
但是，僅僅這些，還不足以成就GP的威名。
我有一個古怪的需求（呵呵，繼續敷衍。:)）：
做一個模板，內部有一個vector<>成員：
template<typename T> A
{
...
vector<T> m_x;
};
可是，如果類型實參是int類型的話，就得用set<>。為了使用的方便，模板名還得是A。于是，我們就得使用下面的技巧：
template<> A<int>
{
...
set<T> m_x;
};
這叫特化（specialization），相當于告訴編譯器如果類型實參是int，用后面那個。否則，用前面的。特化實際上就是根據類型實參由編譯器執行模板的選擇。換句話說，特化是一種編譯期分派技術。
這里還有另一個更古怪需求：如果類型實參是指針的話，就用list<>。這就得用到另一種特化了：
template<typename T> A<T*>
{
...
list<T> m_x;
}
這是局部特化（partial specialization），而前面的那種叫做顯式特化（explicit specialization），也叫全特化。局部特化則是根據類型實參的特征（或者分類）執行的模板選擇。
最后，還有一個最古怪的需求：如果類型實參擁有形如void func(int a)成員函數的類型，那么就使用deque。這個...，有點難。現有的C++編譯器，是無法滿足這個要求的。不過希望還是有的，在未來的新版C++09中，我們便可以解決這個問題。
Concept和類型
concept是GP發展必然結果。正如前面所提到的需求，我們有時候會需要編譯器能夠鑒識出類型的某些特征，比如擁有特定的成員等等，然后執行某種操作。下面是一個最常用的例子：
swap()是一個非常有用的函數模板，它可以交換兩個對象的內容，這是
swap手法的基礎。swap()的基本定義差不多是這樣：
template<typename T> swap(T& lhs, T& rhs) {
T tmp(lhs);
lhs=rhs;
rhs=tmp;
}
但是，如果需要交換的對象是容器之類的大型對象，那么這個swap()的性能會很差。因為它執行了三次復制，這往往是O(n)的。標準容器都提供了一個
swap成員函數，通過交換容器內指向數據緩沖的指針，獲得O(1)的性能。因此，swap()成員是首選使用的。但是，這就需要程序員識別對象是否存在
swap成員，然后加以調用。如果swap()函數能夠自動識別對象是否存在swap成員，那么就可以方便很多。如果有swap成員，就調用成員，否則，
就是用上述通過中間變量交換的版本。
這就需要用到concept技術了：
template<Swappable T> void swap(T& lhs, T& rhs) {
lhs.swap(rhs);
}
這里，Swappable是一個concept：
concept Swappable<typename T> {
void T::swap(T&);
}
于是，如果遇到擁有swap成員函數的對象，正好符合Swappable concept，編譯器可以使用第二個版本，在O(1)復雜度內完成交換。否則，便使用前一個版本：
vector a, b;
... //初始化a和b
swap(a,b); //使用后一個版本
int c=10, d=23;
swap(c, d); //使用前一個版本
這里的swap()也是運用了特化，所不同的是在concept的指導下進行的。這樣的特化有時也被稱作concept based overload。
從上面的例子中可以看到，原先的特化，無論是全特化，還是局部特化，要么特化一個類型，要么特化一個大類（如指針）的類型。但無法做到更加精細。比如，我
希望一個模板能夠針對所有的整數（int，long，short，char等）進行特化，這在原先是無法做到的。但擁有了concept之后，我們便可以
定義一個代表所有整數的concept，然后使用這個整數concept執行特化。換句話說，concept使得特化更加精細了，整個泛型系統從原來“離
散”的變成了“連續”的。
不過上面那個concept特化的模板看起來實在不算好看，頭上那一坨template...實在有礙觀瞻。既然是concept based overload，那么何不直接使用重載的形式，而不必再帶上累贅的template<...>：
void fun(anytype a){...} //#1，anytype是偽造的關鍵字，表示所有類型。這東西最好少用。
void fun(Integers a){...} //#2，Integers是concept，表示所有整型類型
void fun(Floats a){...} //#3，Floats是concept，表示所有浮點類型
void fun(long a){...} //#4
void fun(int a){...} //#5
void fun(double a){...} //#6
...
int x=1;
long y=10;
short z=7;
string s="aaa";
float t=23.4;
fun(x); //選擇#5
fun(y); //選擇#4
fun(z); //選擇#2
fun(s); //選擇#1
fun(t); //選擇#3
這種形式在語義上與原來的模板形式幾乎一樣。注意，是幾乎。如下的情形是重載形式無法做到的：
template<Integers T> T swap(T lhs, T rhs) {
T temp(lhs);
...
}
這里，模板做到了兩件事：其一，模板萃取出類型T，在函數體中，可以使用T執行一些操作，比如上述代碼中的臨時對象temp的構造。這個問題容易解決，因為萃取類型T還有其他的方法，一個typeof()操作符便可實現：
Integers swap(Integers lhs, Integers rhs) {
typeof(lhs) temp(lhs);
...
}
其二，模板保證了lhs，rhs和返回值都是同一類型。這個問題，可以通過施加在函數上的concept約束解決：
Integers swap(Integers lhs, Integers rhs)
requires SameType<lhs, rhs>
&& SameType<lhs, retval> { //retval是杜撰的關鍵字，用以表示返回值
typeof(lhs) temp(lhs);
...
}
相比之下，重載形式比較繁瑣。總體而言，盡管重載形式冗長一些，但含義更加明確，更加直觀。并且在concept的接口功能作用下，對參數類型一致的要求
通常并不多見（一般在基本類型，如整型等，的運算處理中較多見。因為這些操作要求類型有特定的長度，以免溢出。其他類型，特別是用戶定義類型，通常由于封
裝的作用，不會對類型的內部特性有過多要求，否則就不應使用泛型算法）。如果可以改變語法的話，那么就能用諸如@代替typeof，==代替
SameType的方法減少代碼量：
Integers swap(Integers lhs, Integers rhs)
requires @lhs == @rhs && @lhs == @retval {
@lhs temp(lhs);
...
}
Concept、類型和對象
事情還可以有更加夸張的發展。前面對泛型進行了特化，能不能對類型也來一番“特化”呢？當然可以：
void fun(int a);
void fun(int a:a==0); //對于類型int而言，a==0便是“特化”了
更完整的，也可以有“局部特化”：
void fun(int a); //#1
void fun(int a:a==0); //#2
void fun(int a:a>200); //#3
void fun(int a:a<20&&a>10); //#4
void fun(int a:(a>70&&a<90)||(a<-10)); //#5
...
int a=0, b=15, c=250, d=-50;
fun(80); //使用#5
fun(50); //使用#1
fun(a); //使用#2
fun(b); //使用#4
fun(c); //使用#3
fun(d); //使用#5
實際上，這無非是在參數聲明之后加上一組約束條件，用以表明該版本函數的選擇條件。沒有約束的函數版本在沒有任何約束條件匹配的情況下被選擇。對于使用立
即數或者靜態對象的調用而言，函數的選擇在編譯期執行，編譯器根據條件直接調用匹配的版本。對于變量作為實參的調用而言，則需要展開，編譯器將自動生成如
下代碼：
//首先將函數重新命名，賦予唯一的名稱
void fun_1(int a); //#1
void fun_2(int a); //#2
void fun_3(int a); //#3
void fun_4(int a); //#4
void fun_5(int a); //#5
//然后構造分派函數
void fun_d(int a) {
if(a==0)
fun_2(a);
else if(a>200)
fun_3(a);
...
else
fun_1(a);
}
在某些情況下，可能需要對一個對象的成員做出約束，此時便可以采用這種形式：
struct A
{
float x;
};
...
void fun(A a:a.x>39.7);
...
這種施加在類型上的所謂“特化”實際上只是一種語法糖，只是由編譯器自動生成了分派函數而已。這個機制在Haskell等語言中早已存在，并且在使用上帶
來很大的靈活性。如果沒有這種機制，那么一旦需要增加函數分派條件，那么必須手工修改分派函數。如果這些函數，包括分派函數，是第三方提供的代碼，那么修
改將是很麻煩的事。而一旦擁有了這種機制，那么只需添加一個相應的函數重載即可。
當concept-類型重載和類型-對象重載混合在一起時，便體現更大的作用：
void fun(anytype a);
void fun(Integers a);
void fun(Floats a);
void fun(long a);
void fun(int a);
void fun(double a);
void fun(double a:a==0.8);
void fun(short a:a<10);
void fun(string a:a=="abc");
...
concept-類型-對象重載體系遵循一個原則：優先選擇匹配的函數中最特化的。這實際上是類型重載規則的擴展。大的來說，所有類型比所屬的
concept更加特化，所有對象約束比所屬的類型更加特化。對于concept而言，如果concept A refine自concept
B，那么A比B更加特化。同樣，如果一個類型的約束強于另一個，那么前一個就比后一個更加特化，比如a==20比a>10更加特化。綜合起來，可以
有這樣一個抽象的規則：兩個約束（concept，或者施加在對象上的約束）A和B，作用在類型或者對象上分別產生集合，如果A產生的集合是B產生的集合
的真子集，那么便認為A比B更加特化。
根據這些規則，實際上可以對一個函數的重載構造出一個“特化樹”：
越接近樹的根部，越泛化，越接近葉子，越特化。調用時使用的實參便在這棵“特化樹”上搜索，找到最匹配的函數版本。
concept-類型-對象體系將泛型、類型和對象統一在一個系統中，使得函數的重載（特化）具有更簡單的形式和規則。并且，這個體系同樣可以很好地在類模板上使用，簡化模板的定義和使用。
類模板
C++的類模板特化形式并不惹人喜愛：
template<typename T> A{...}; //基礎模板
template<> A<int>{...}; //顯式特化（全特化）
template<typename T> A<T*>{...}; //局部特化
在C++09中，可以直接用concept定義模板的類型形參：
template<Integers T> A{...};
實質上，這種形式本身就是一種局部特化，因而原本那種累贅局部特化形式可以廢除，代之以concept風格的形式：
template<Pointer T> A{...}; //Pointer表示此處采用指針特化模板
同樣，如果推廣到全特化，形式也就進一步簡單了：
template<int> A{...}; //這個形式有些突兀，這里只打算表達這個意思，應該有更“和諧”的形式
如果模板參數是對象，則使用現有的定義形式：
template<int a> A{...};
更進一步，可以引入對象的約束：
template<int a:a>10> A{...};
此外，C++中在模板特化之前需要有基礎模板。但實際上這是多余的，D語言已經取消了這個限制，這對于簡化模板的使用有著莫大的幫助。
從本質上講...
從本質上講，我們可以把所有類型看作一個集合T={ti}，而concept則是施加在類型集合上的約束。通過concept這個約束，我們便可以獲得類
型集合T的一個子集C。理論上，所有concept所對應的類型子集Cj構成了類型集合的冪集{Cj}。在{Cj}中，有兩類類型子集是很特殊的。一組是
T本
身，即所有類型。存在一個concept不對T施加任何約束，便得到了C0=T。第二類則是另一個極端，存在一組concept，施加在T上之后所得的類
型子集僅包含一個類型：Ci={ti}。由于這組concept與類型存在一一對應的關系，那么我們便可以用這組concept來指代類型。也就是把類型
作為特殊的concept處理。如此，concept便同類型統一在一個體系中。這種處理可以使我們獲得極大的好處。
這組特殊的concept仍舊使用對應的類型名作為稱謂，仍舊稱之為“類型”，但其本質上還是concept。任何一個類型，一旦創建，也就創建了相應的特殊concept。如果在模板特化中使用一個類型的時候，實際上就是在使用相對應的那個特殊concept：
void func(typeA a); //盡管使用了類型名typeA，但實際上這里所指的是typeA所對應的那個特殊concept。
在這個concept體系的作用下，函數模板的特化和重載整個地統一起來（concept based overload）。
至于作用在類型上的那種“特化”，也是同樣的道理。對于一個類型T而言，它所有的對象構成一個集合O。如果存在一組約束作用于O，那么每
一個約束對應著O的一個子集。理論上，我們可以構造出一組約束，使得他們同O的每一個子集一一對應。同樣，這些子集中有兩類子集比較特殊。一類是所有對象
的集合。另一類便是只有一個對象的子集。于是，我們可以使用這組特殊對象子集所對應的約束指代相應的對象。也就是將對象看作特殊的約束。如此，類型和對象
也被統一在一個系統中了。
進而，類型在邏輯上被作為特殊concept處理，對象則被作為特殊的類型處理。于是，這三者便可以統一在一個體系下，一同參與特化。
總結
盡管形式不能代表本質，但形式的變化往往會帶來很多有益的進步。更重要的是，很多本質上的變化總會伴隨著形式上的改變。通過將concept、類型和對象
在邏輯上整合到統一的體系之中，便可以促使模板、特化、函數重載等機制在形式上達成統一。從而能夠簡化這些功能的使用。這也是當前重視語言（工具）易用性
的潮流的一個必然訴求。這個形式上的統一并非語法糖之類的表面變化。而是完全依賴于concept這個新型的類型描述（泛型）系統的確立和發展。
concept的出現，彌補了以往泛型的不足，找回了泛型系統缺失的環節，彌補了泛型同類型之間的裂痕。在此作用下，便可以構建起concept-類型-
對象的抽象體系，用統一的系統囊括這三個原本分立的概念。在這個新的三位一體的系統下，使得模板的特化和重載擁有了相同的形式，進而獲得更直觀的語義，和
更好的易用性。