第三篇草稿講了泛型concept的概念，這篇最終稿可以確定
Vczh Library++ 3.0的NativeX所要支持的泛型concept的比較精確的特性了。
泛型的concept的概念還是比較清晰的，這次我們便通過一個例子來講解他。假如在NativeX里面實現一個列表，顯然因為NativeX只有指針，所以寫起來大概就是：
1 generic<T>
2 structure List
3 {
4 T* items;
5 int count;
6 }
于是我們想寫一個函數判斷兩個List是否相等。因為
NativeX現在已經有模板函數了，所以我們很簡單的一個想法是，傳入兩個List<T>*，然后再傳入一個函數指針function bool(T,T)，就可以寫出下面的函數了：
1 generic<T>
2 function bool ListEquals(List<T>* xs, List<T>* ys, function bool(T,T) comparer)
3 {
4 result=true;
5 if(xs->count!=yx->count)
6 {
7 result=false;
8 }
9 else
10 {
11 variable int current=xs->count-1;
12 while(current>=0)
13 {
14 if(!comparer(xs->items[current], yx->items[current]))
15 {
16 result=false;
17 exit;
18 }
19 current--;
20 }
21 }
22 }
這個做法咋一看好像沒什么問題，但是如果我們要比較List<List<int>>怎么辦呢？我們可以先寫一個function bool IntEquals(int a, int b);，然后再寫一個function bool IntListEquals(List<T> a, List<T> b);，這個函數里面用IntEquals加上ListEquals<int>來實現，最后將他傳進ListEquals<List<int>>。到了這里還好，如果我們還想比較List<List<double>>、List<List<char>>等等，我們就要被迫搞出很多函數了。而且最大的問題是，當我們寫好這么多東西以后，我們想實現一個Find函數來查找List里面的對象的話，面對List<List<int>>、List<List<double>>等等的東西，我們又得重新寫一次了……
這個問題在面向對象的語言里面都很容易做到，只需要在一個類里面實現operator==就可以了。那這兩種方法有什么區別呢？假設我們把C++里面的類去掉，那么我們會發現，ListEquals<T>的comparer參數是通過T自動找到的，而不是我們自己傳進去的。因此如何設計一套可以從類型找到某一組函數的機制，就因為我們把模板函數加入NativeX語言（基本上就是C語言）而變成了一個必須實現的功能了。在這里我準備引入concept這個概念。concept跟
C++0x的concept以及
haskell的type class的概念基本一致。現在就讓我們逐步在NativeX里面實現這套機制。
我們在這里面對的問題是給一些給定的類型（或泛型類型，譬如說List<T>）實現Equals函數，然后每一個Equals函數里面如果需要其他類型U的Equals函數，可以直接找到，而不需要我們自己傳進去。因此這個問題可以抽象為，某些類型具有可以被兩兩比較是否相等的能力。因此定義如下：
1 generic<T>
2 concept Eq
3 {
4 bool Equals(T a, T b);
5 }
當然這些函數不能直接生出來，因此我們對于想比較的每一個類型都需要給出相應的Equals函數。下面的代碼為int類型定義了Equals：
1 instance int : Eq
2 {
3 Equals = IntEquals;
4 }
5
6 generic<T>
7 function bool IntEquals(int a, int b)
8 {
9 result=a==b;
10 }
每比較一次數字就得調用一次函數，這個開銷還是比較大的。在NativeX的所有設施都做好之后，我會開始做指令級別的優化，然后看看要不要實現自動判斷并inline的功能。有了int : Eq之后，我們就可以為List<T>也寫一個Eq了。如果我們給出了List<T>的Equals的話，為了使用這個Equals，T也必須有相應的Equals函數，于是我們可以寫：
1 generic<T>
2 instance List : Eq
3 where T : Eq
4 {
5 Equals = ListEquals<T>;
6 }
最后就是實現ListEquals了，注意ListEquals函數內部是如何拿到類型T的Equals函數的：
1 generic<T>
2 where T : Eq
3 function bool ListEquals(List<T> xs, List<T> ys)
4 {
5 result=true;
6 if(xs->count!=ys->count)
7 {
8 result=false;
9 }
10 else
11 {
12 variable int current=xs->count-1;
13 while(current>=0)
14 {
15 if(!Eq<T>::Equals(xs->items[current], yx->items[current]))
16 {
17 result=false;
18 exit;
19 }
20 current--;
21 }
22 }
23 }
這里引入了一個新的語法：Eq<T>::Equals，用于自動搜索自己dll或者其他dll實現的這個函數。搜索會在虛擬機里面完成，編譯器只負責提供符號，并檢查類型。因此就大功告成了。
這個instance的設計基本上來源于Haskell的type class，其實跟C++0x的那個concept關系還是比較小，畢竟NativeX沒有類，C++有類，Haskell沒有類。當然其缺點是你不能在定義了Eq<List<T>>::Equals的同時，專門為Eq<List<bool>>::Equals定義一個特殊的版本，就如同C++的偏特化一樣，這個就過于復雜了。雖然偏特化在C++的用處非常大，而且也十分常用，但是在NativeX里面就因為NativeX的模板可以編譯成二進制而會因為找不到高性能的實現方法被砍掉。
posted on 2010-07-13 04:26
陳梓瀚(vczh) 閱讀(3015)
評論(8) 編輯 收藏 引用 所屬分類:
VL++3.0開發紀事