第三篇草稿讲了泛型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) 阅读(2989)
评论(8) 编辑 收藏 引用 所属分类:
VL++3.0开发纪事