泛型编程在非C++语言中的实现之探讨
左轻侯
2001.9.22
GP（Generic Programming，泛型编程）号称编程思想的又一次革命。但是，在论述GP的资料中，一般都是以C++语言为基础来讨论。那么，GP是否可以在其它的编程语言中实现呢？这是作者一直在思考的一个问题，因为水平有限和资料匮乏，收获甚微。现将一些不成熟的想法整理出来，请方家不吝指教。
本文以Delphi为例（Java的情况与此类似，可参照），讨论GP的另一种实现思路。代码是随手写出的，未经验证。
根据作者的理解，实现GP的关键之处，在于实现ADT（Abstract Data Type，抽象数据类型）。只有实现了ADT，才能够将具体的数据类型与通用的算法分离开来。
在C++中，ADT的存储是通过模板来实现的。举一个最简单的栈的例子（没有给出实现部分）：
template class Stack{
public:
void Push(const Type &item);
Type Pop;
...
}
栈的应用：
Stack s;
int data;
data = 1;
s.Push(data); //入栈
int out;
out = s.Pop; //出栈
通过建立一个int类型的Stack对象，实现了对int类型数据的存储。
但是，在Delphi/Java中，并没有模板这种机制。那么如何实现ADT呢？与C++不同的是，Delphi/Java的类继承体系是单根结构的，也就是说，在Delphi中，所有的class都通过编译器强制而保证成为TObject的子类（Java中是Object）。这个TObject可以看成是一切类的最高层次的抽象。那么，是否可以认为Delphi/Java中已经先天地提供了对ADT的支持呢？
试着用这种思路建立一个栈：
TStack = class
public
procedure Push(item:TObject);
function Pop:TObject;
...
end;
这个TStack类针对TObject类型的对象进行操作。但是，这个类还不能立即应用，因为在Delphi中，简单数据类型并不是对象。所以必须再建立一个自定义的数据类型。下面建立了只有一个integer成员的自定义数据类型：
TADT = class
public
data:integer;
end;
再来看栈的应用：
var
stack:TStack;
adt1,adt2:TADT;
begin
stack := TStack.create;
adt1 := TADT.create;
stack.Push(adt1); //入栈
adt2 := stack.Pop as TADT; //出栈
stack.free;
这样就完成了对ADT对象的存储。必须注意到，在入栈时，是将adt对象直接入栈的，因为TStack类是对TObject进行操作，由于Delphi的单根结构，可以将任何类型的对象赋给TObject类型的变量。但是，出栈时，返回的也是一个TObject的变量，因此必须用as完成一次向下映射。同样由于单根结构，Delphi/Java提供了对RTTI的强大支持，因此这种向下映射是轻而易举的事情。但是，毫无疑问，RTTI在效率上有所损失。
在实现了ADT的存储之后，如何才能实现对ADT的操作呢？
在C++中，通过运算符重载来解决这个问题。看一个例子：
在一个List类中，执行查找操作：
template class List{
Type* find(Type &value); //查找指定数据项，找到则返回其地址，否则返回NULL
...
}
template Type* List::find(Type &value){
Type* p = first->link;
where(p!=NULL&&!(p->data==value)){
p=p->link;
}
return p;
}
在List类的find函数的实现中，代码抄自链表结构的实现，不需要关心其细节。需要注意的地方只有一个，即判断条件中的p->data==value。由于p->data和value都是ADT，在建立一个List类的对象时，它们可能是简单数据，也可以是任何的自定义数据类型。但是，仍然可以统一使用==这样的运算符，对它们进行操作。为什么呢？原因在于运算符重载。
下面用一个Point类来说明这一点：
class Point{
private:
int x,y;
public:
int operator ==(const Point &point); //判断两个Point对象是否相等
...
}
int Point::operator ==(const Point &point){
if(x==point.x&&y==poing.y){
return 1;
}else{
return 0;
};
}
可以看到，由于重载了==运算符，两个Point对象之间可以进行比较。同理，任何数据类型，只要重载了相应的运算符，就可以被容器类进行统一的操作。
当目光重新转向非C++的时候，问题又出现了：Delphi/Java不支持运算符重载。做为补救措施，可以用函数来代替运算符。例如，统一使用equals函数来代替==。可是，更大的问题在于：容器类操作的对象是TObject，而TObject并没有equals这样的方法。（在Java中，object有equals方法，但并没有其它的完整的运算方法。）
在不改变Delphi/Java现有语法的前提下，作者能想到的解决办法是，建立一个TADT类，作为所有数据结构的基类。TADT中定义了很多象equals、add之类的抽象方法。自定义的数据类型一律从TADT派生，并重载相应方法。而容器类则只需要对TADT进行操作，即可实现通用的算法了。但是，这种解决方法并不理想。
（补充一点，其实Delphi自己提供了一些通用的容器类，如TList、TCollection、TStack、TQueue等。但与本文中所说的不同，它们存储的不是TObject，而是pointer。由于Delphi的“引用对象模型”机制，存储TObject对象，其实也就等于存储一个pointer，不同之处在于，pointer不但可以存储对象，而且可以存储基本数据类型。这应该也是Borland如此设计的原因。但是，这些容器类只提供了add、delete之类的管理方法，并没有提供通用的算法，因为对pointer不能进行复杂的操作。实际操作中，往往是程序员从容器类派生出一个新类，或者在自己的类中维护一个容器类。这也是一种解决办法，但算法就不能独立出来了。）
综上所述，作者的观点如下：
1、C++中通过模板机制来实现ADT的存储，Delphi/Java同样可以通过单根结构+RTTI的机制来实现。其不同之处在于，C++的实现是语法上的，而Delphi/Java是逻辑上的，也就是说，C++是通过一套特殊的语法来实现的，而Delphi/Java是根据OOP的理论和本身的类库体系自然地实现的。作者个人以为，从这个角度来看，Delphi/Java的实现机制更加简单和直观。
2、从运行效率来算，C++肯定要强于Delphi/Java，因为C++的实现是编译期的，而Delphi/java是运行期的。RTTI的使用将对效率造成不小的影响。但是，从另一个角度来考虑，ADT在运行期的实现也带来了好处，那就是可以在运行期随意地改变容器类所存储的数据结构类型。作者还没有考虑过这种“数据类型的多态”会对编程带来什么实质性的后果。不过大胆地设想一下，以后也许可以将标准算法封装在DLL之类已编译的模块中，甚至封装在OS提供的COM对象里，程序员只需要创建自己的数据类型，将其提交给相应的接口？……
3、C++中通过运算符重载，来实现对ADT的操作。在不支持运算符重载的Delphi/Java中，作者未能发现好的代替方法。建立统一的ADT抽象类的解决方法，只能说是一个馊主意。:-(有程序员倾向于Delphi中应该增加运算符重载，这应该是理由之一，不知道Borland是否重视。另外，据说下一版的Java将会全面支持GP，不知道是通过什么机制来实现？请了解内幕的高手介绍一下。
