类型——程序设计语言的核心概念
紫云英
关键字：type, concept, model, refinement, constraint, constrained genericity, interface, boost concept check, OOP, GP, C++
《Object Unencapsulated: Eiffel, Java and C++》的作者Ian Joyner说，Object-Oriented应该正名为Type-Oriented（面向类型）[1][5]；侯捷先生在文章中说，STL 其实是在泛型思维模式之下建立起一个系统化的、条理分明的「软体组件分类学」。噢，什么叫分类学？还是类型。[3]看来“类型”这个概念值得我们一说再说。
在面向对象设计（OOD）中，“归类”是重要步骤，一个精心设计的类层次结构是则是OOD的重要成果。类的层次和界面定义得好，将造福软件系统的实现者、维护者和以后的扩展者：他们会惊喜地发现，许多错综复杂的关系在清晰的类型层次中不言自明；而失败的类层次结构则是灾难的来源：为了绕过不合理的类型设计带来的束缚，编码员不得不把各种能想到的技巧都用了上去[4]——包括强制的类型cast、直接对对象内存的访问等，而这些技巧往往和潜在的bug形影相随。
在数据结构的归纳和发展中，类型也扮演了重要的角色。ADT的引入是一个里程碑，早期的语言就开始struct（C）、record（Pascal）等复合结构类型为ADT提供支持。ADT是什么？抽象数据类型。
在程序设计语言中，类型的概念由来已久，而其内涵也在不断发展之中。语言对类型机制更好效率更高的支持成为语言成熟度的标志。OOP语言对类型的支持机制包括class、interface、inheritance、polymorphism，RTTI，各种cast等，这为编程带来了许多方便，因为所有概念在语言中都有了对应物。关于OOP语言中类型的形象阐释，请参见我写的《漫谈程序设计语言的选择和学习》（发表于《程序员》2001年10月刊）和与朋友合译的《Object Unencapsulated: Eiffel, Java and C++》1.6节。而在泛性程序设计（GP）概念中，所谓“分类学”也就是对类型的一套定义。而模板参数的constraint，则其实是“类型所需符合之类型”，不妨将其与OOP中interface之概念作一对照：一个class需实现某一interface，才可说其属于(is-a)一定类型。C++中无interface直接对应物[2]，可这样表述：一个class需公有继承一个abstract class，则说其属于（is-a）该abstract class所定义之类型。而constrained genericity中，模板参数需符合某一constraint，该模板才能实例化。在GP和STL的著作中是这样表述的：模板参数（这是一个类型）叫model，其需符合的constraint（一个更为抽象的类型）叫做concept。对model更多的constraint叫做refinement。所以，concept-model-refinement可以和interface-class-inheritance对照理解。值得指出的是，Eiffel之父Bertrand Meyer在OOP经典著作Object-Oriented Software Construction 2/e中将泛型定义为类型参数化，并认为泛型技术和OOP中的继承与多态技术并列：泛型描述水平方向的类型关系；而继承则描述垂直方向上的类型关系。（我在《漫谈程序设计语言的选择与学习》一文中对此有具体阐释，见《程序员》2001年10月刊及http://zmelody.myrice.com/articles/pl.htm）。Bertrand认为泛型方法是经典OOP方法的补充，因此也可纳入OOP的范畴。）两者在实现上的不同是，C++中GP采用的是generative template实现方法，这是用空间换时间的方法，所以大量使用模板的程序常体积较大，但运行速度稍快于对应的OOP版本；而OOP则采用增加间接层的方法，增加了时间开销。另外还有一点不同： OOP是成熟的设计方法，interface、class、inheritance等都有语言元素直接对应，而GP的许多概念则缺乏语言级支持。
何谓缺乏语言级支持？举个例子：如果你读STL的源代码，你可能会找到类似这样的定义：
template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void sort(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);
毫无疑问，这里RandomAccessIterator、StrictWeakOrdering都是constraint，或者说它们都是first、last之类型需符合的类型（呵呵，是不是很拗口）。在OOP语言中，OO类型是否匹配是由语言/编译器的类型机制检测和保证的；但这段GP代码中RandomAccessIterator只不过是一个标识符，除了告诉阅读者constraint为RandomAccessIterator外对于编译器毫无影响——你完全可以用你的编辑器的查找且替换功能将其换成ForwardIterator一词，在你看来含义大不一样了（STL中RandomAccessIterator是ForwardIterator的refinement），但编译器可不管这一套。其实，在常见的模板代码中我们常常简单地用“T”表示typename——因为这个标识符只不过是一个place holder嘛，何谓place holder？哦，你在大学自习教室用来占座位的练习本就是place holder，至于最终要使用这个座位的，当然是你本人啦。既然只是占座用的，何必麻烦呢，理论上，一本薄薄的草稿本、一本精美的硬面塑封笔记本，和一辆重型坦克（如果椅子上放得下的话）占座，效果是一样的。
template <class T>
void sort(T first, T last);
template <class T1, class T2>
void sort(T1 first, T1 last, T2 comp);
这样改过的代码对于编译器是换汤不换药，而对于程序员是清晰了还是模糊了？不知道，大家表决一下吧 J
因为编译器对这个constraint标识符的不在意（或者不如说对constraint的缺乏支持），程序员在开发程序时会受不少苦。这样的苦不亚于用早期的无类型语言开发程序而后从中寻找类型错误。比如，你对一个不支持RandomAccessIterator的容器实行sort操作，结果会怎样？不妨写这样一段代码试试：
#include <list>
#include <algorithm>
using namespace std;
int main()
{
list<int> a;
//some operation on a
sort(a.begin(), a.end());
}
编译时，光标停在一个莫名其妙的头文件里，错误信息是：“operator X is not implemented”，噢，我何时包含了这个头文件？我何时要用这个operator了？我干嘛要implement这个operator？真是一头雾水。或许你会以为是随编译器提供头文件中有错而一冲动就给编译器厂商发了bug report。但其实错误真正的原因在于，sort 要求参数之类型（哦，好吧，正规的说法是concept）至少应该是RandomAccessIterator，而list::iterator却是BidirectionalIterator，不满足条件。可是如果没有丰富的经验谁知道原因在此？哪像非GP程序那样直截了当——谁都知道出错信息“Type mismatch – const char * expected in line n of xxx.cpp”是什么意思。
那么，好吧，为了让GP方法的使用更平易近人一点，我们就不得不让GP的实现产品——比如STL——更复杂一点。比方说，concept check宏就是这样一种技术。Boost和SGI STL都提供了这样的宏。其实GP中不少技术都是为了弥补编译器支持力度的不足而提出的，比如type traits。看着Concept Check的实现，看着traits的实现，我不由回忆起以前看MFC源代码的日子。早期的C++语言没有RTTI支持，也没有异常处理机制；MFC用一系列宏实现了；目前微软提供的用于Windows CE嵌入式开发的C++编译器也不支持RTTI和异常处理，有位叫Fedor Sherstyuk的程序员写了个TCU库（参见Dani Carles 的Adding Exceptions & RTTI to the Windows CE Compiler: Part I，Dr. Dobb's Journal August 2002），硬是模拟出了RTTI和异常处理。程序员真是一个充满创造力的群体啊，他们总是将不可能变为可能。那么，如今的C++所缺乏的东西，会不会在以后加上？会不会出现新的支持GP的语言？不知道，但可以看看Bjarne Stroustrup的《The Design and Evolution of C++》和我翻译的《STL之父访谈录》，从中或许能找到一些线索。关于constrained genericity的更多说明，参见我翻译的《Bjarne Stroustrup’s C++ Style and Technique FAQ》中文版[6]，条款名“为什么我无法限制模板的参数”。
附：[1][2]摘自我的《漫谈程序设计语言的选择与学习》，[3][4][5]译自《Object Unencapsulated: Eiffel, Java and C++》1.6节（经授权），[6]译自Bjarne Stroustrup’s C++ Style and Technique FAQ（经授权）。
[1] 面向对象编程提供了两种方法来产生新的复杂类型:继承(hierarchy)和组合(composition)。举两个例子，木头可燃，那么木头做的椅子也可燃。这是继承。水果可吃，那么水果拼盘自然可吃。这是组合。其实现在所说的Object Oriented Programming严格说来应称为Type Oriented Programming。一个object只是一个类型(type，在C++中往往是class，但记住这两个概念不等同)的某个实例(instance)，但是OOP的重心在于设计/抽象出良好的类层次，合理地划分功能，这是在类型层面上的工作，而不是对象层面上的工作。尤其是C++，它的数据封装是以类为单位的，这意味着同一个类的不同实例(也就是不同对象)可以互相访问对方的私有数据成员。例如:
class A {
private:
int z;
void f(A& a) { z = a.z; }
};
而这在某些严格的OO语言是不允许的。“私有”是以对象为分界的私有。一个对象需要访问另一个对象的私有信息必须通过公有的接口。
[2] C++中的class不是type的对等物。在Kayshav Dattatri和Erich Gamma写的《C++: Effective Object-Oriented Software Construction》中有一段话阐释了现代的“type”的含义。一个class可以同时是几种type，只要它实现(implement)了这些type的interface。同样地，几个class可以是一种type的，只要它们实现了同一个interface。但是C++并没有独立而清晰的interface概念，所以C++不是最OO的语言，自然也不是最适合教学的语言。这方面Java就要比它强。
[3] 我们通过检查我们使用的语言是否符合通常的认知来完成语法检查。举例来说，“他喝着电脑，启动了一杯咖啡”，这句话从语法角度上一点错都没有，可是却连小学生都会嘲笑这种牛头不对马嘴的无稽，这违反了我们对电脑和一杯咖啡的通常认知。用面向对象编程的术语来说，错误在于电脑这种“类型”没有“可喝”的属性。因此，在编写程序时我们也要尽量避免类似错误的发生，于是程序设计语言的类型系统便当仁不让的担当了检查这类错误的角色。
[4] C++是一种静态的类型语言，但我们有很多手段可以让程序具有动态类型乃至无类型语言的灵活性，这意味着，我们可以强制让编译器忽略类型系统的强约束，而让一些特殊的程序通过编译。这就好比，有时我们不得不强迫那个可怜的人儿“喝”他的电脑，至于这之后此人是否需要被送往医院则是另一码事。要知道，不允许这种偶尔的例外的语言是缺乏灵活性的。为了做到这一点，我们需要改变一下属性，即电脑是可以喝的 :O) 我们不应该否决整个类型系统，但为了灵活性而允许在类型系统中开个小小的后门则是必要的。
[5] OO语言提供了两种特定方式来生成新的复杂类型：组合和继承。OO语言最重要的特征也许是它的面向类型特性。事实上面向对象的未来应该是面向类型，或者说“面向对象”本来就应该是“面向类型”。面向类型的很重要的一点便是如何定义新类型；怎样利用已有的类型去派生更多的新的类型——OO语言提供了并行不悖的继承和泛型这两种机制；怎样去指定类型之间的继承关系。在一个面向类型的系统中，我们需要一种规范来定义新类型，一种规则去合并已有类型。一旦面向类型成为了一种心理定势，或者文化，我们先前定义的类型规则便会得到更为广泛的应用。
[6]
Q: 为什么我无法限制模板的参数？
A: 呃，其实你是可以的。而且这种做法并不难，也不需要什么超出常规的技巧。
让我们来看这段代码：
template<class Container>
void draw_all(Container& c)
{
for_each(c.begin(),c.end(),mem_fun(&Shape::draw));
}
如果c不符合constraints，出现了类型错误，那么错误将发生在相当复杂的for_each解析之中。比如说，参数化的类型被要求实例化int型，那么我们无法为之调用Shape::draw()。而我们从编译器中得到的错误信息是含糊而令人迷惑的——因为它和标准库中复杂的for_each纠缠不清。
为了早点捕捉到这个错误，我们可以这样写代码：
template<class Container>
void draw_all(Container& c)
{
Shape* p = c.front(); // accept only containers of Shape*s
for_each(c.begin(),c.end(),mem_fun(&Shape::draw));
}
我们注意到，前面加了一行Shape *p的定义（尽管就程序本身而言，p是无用的）。如果不可将c.front()赋给Shape *p，那么就大多数现代编译器而言，我们都可以得到一条含义清晰的出错信息。这样的技巧在所有语言中都很常见，而且对于所有“不同寻常的构造”都不得不如此。[译注：意指对于任何语言，当我们开始探及极限，那么不得不写一些高度技巧性的代码。]
不过这样做不是最好。如果要我来写实际代码，我也许会这样写：
template<class Container>
void draw_all(Container& c)
{
typedef typename Container::value_type T;
Can_copy<T,Shape*>(); // accept containers of only Shape*s
for_each(c.begin(),c.end(),mem_fun(&Shape::draw));
}
这就使代码通用且明显地体现出我的意图——我在使用断言[译注：即明确断言typename Container是draw_all()所接受的容器类型，而不是令人迷惑地定义了一个Shape *指针，也不知道会不会在后面哪里用到]。Can_copy()模板可被这样定义：
template<class T1, class T2> struct Can_copy {
static void constraints(T1 a, T2 b) { T2 c = a; b = a; }
Can_copy() { void(*p)(T1,T2) = constraints; }
};
Can_copy在编译期间检查确认T1可被赋于T2。Can_copy<T,Shape*>检查确认T是一个Shape*类型，或者是一个指向Shape的公有继承类的指针，或者是用户自定义的可被转型为Shape *的类型。注意，这里Can_copy()的实现已经基本上是最优化的了：一行代码用来指明需要检查的constraints[译注：指第1行代码；constraints为T2]，和要对其做这个检查的类型[译注：要作检查的类型为T1] ；一行代码用来精确列出所要检查是否满足的constraints（constraints()函数） [译注：第2行之所以要有2个子句并不是重复，而是有原因的。如果T1，T2均是用户自定义的类，那么T2 c = a; 检测能否缺省构造；b = a; 检测能否拷贝构造] ；一行代码用来提供执行这些检查的机会 [译注：指第3行。Can_copy是一个模板类；constraints是其成员函数，第2行只是定义，而未执行] 。
[译注：这里constraints实现的关键是依赖C++强大的类型系统，特别是类的多态机制。第2行代码中T2 c = a; b = a; 能够正常通过编译的条件是：T1实现了T2的接口。具体而言，可能是以下4种情况：(1) T1，T2 同类型 (2) 重载operator = (3) 提供了 cast operator （类型转换运算符）(4) 派生类对象赋给基类指针。说到这里，记起我曾在以前的一篇文章中说到，C++的genericity实作——template不支持constrained genericity，而Eiffel则从语法级别支持constrained genericity（即提供类似于template <typename T as Comparable> xxx 这样的语法——其中Comparable即为一个constraint）。曾有读者指出我这样说是错误的，认为C++ template也支持constrained genericity。现在这部分译文给出了通过使用一些技巧，将OOP和GP的方法结合，从而在C++中巧妙实现constrained genericity的方法。对于爱好C++的读者，这种技巧是值得细细品味的。不过也不要因为太执著于各种细枝末节的代码技巧而丧失了全局眼光。有时语言支持方面的欠缺可以在设计层面（而非代码层面）更优雅地弥补。另外，这能不能算“C++的template支持constrained genericity”，我保留意见。正如，用C通过一些技巧也可以OOP，但我们不说C语言支持OOP。]
请大家再注意，现在我们的定义具备了这些我们需要的特性：
你可以不通过定义/拷贝变量就表达出constraints[译注：实则定义/拷贝变量的工作被封装在Can_copy模板中了] ，从而可以不必作任何“那个类型是这样被初始化”之类假设，也不用去管对象能否被拷贝、销毁（除非这正是constraints所在）。[译注：即——除非constraints正是“可拷贝”、“可销毁”。如果用易理解的伪码描述，就是template <typename T as Copy_Enabled> xxx，template <typename T as Destructible> xxx 。]
如果使用现代编译器，constraints不会带来任何额外代码
定义或者使用constraints均不需使用宏定义
如果constraints没有被满足，编译器给出的错误消息是容易理解的。事实上，给出的错误消息包括了单词“constraints” (这样，编码者就能从中得到提示)、constraints的名称、具体的出错原因（比如“cannot initialize Shape* by double*”）
既然如此，我们干吗不干脆在C++语言本身中定义类似Can_copy()或者更优雅简洁的语法呢？The Design and Evolution of C++分析了此做法带来的困难。已经有许许多多设计理念浮出水面，只为了让含constraints的模板类易于撰写，同时还要让编译器在constraints不被满足时给出容易理解的出错消息。比方说，我在Can_copy中“使用函数指针”的设计就来自于Alex Stepanov和Jeremy Siek。我认为我的Can_copy()实作还不到可以标准化的程度——它需要更多实践的检验。另外，C++使用者会遭遇许多不同类型的constraints，目前看来还没有哪种形式的带constraints的模板获得压倒多数的支持。
已有不少关于constraints的“内置语言支持”方案被提议和实作。但其实要表述constraint根本不需要什么异乎寻常的东西：毕竟，当我们写一个模板时，我们拥有C++带给我们的强有力的表达能力。让代码来为我的话作证吧：
template<class T, class B> struct Derived_from {
static void constraints(T* p) { B* pb = p; }
Derived_from() { void(*p)(T*) = constraints; }
};
template<class T1, class T2> struct Can_copy {
static void constraints(T1 a, T2 b) { T2 c = a; b = a; }
Can_copy() { void(*p)(T1,T2) = constraints; }
};
template<class T1, class T2 = T1> struct Can_compare {
static void constraints(T1 a, T2 b) { a==b; a!=b; a<b; }
Can_compare() { void(*p)(T1,T2) = constraints; }
};
template<class T1, class T2, class T3 = T1> struct Can_multiply {
static void constraints(T1 a, T2 b, T3 c) { c = a*b; }
Can_multiply() { void(*p)(T1,T2,T3) = constraints; }
};
struct B { };
struct D : B { };
struct DD : D { };
struct X { };
int main()
{
Derived_from<D,B>();
Derived_from<DD,B>();
Derived_from<X,B>();
Derived_from<int,B>();
Derived_from<X,int>();
Can_compare<int,float>();
Can_compare<X,B>();
Can_multiply<int,float>();
Can_multiply<int,float,double>();
Can_multiply<B,X>();
Can_copy<D*,B*>();
Can_copy<D,B*>();
Can_copy<int,B*>();
}
// the classical "elements must derived from Mybase*" constraint:
template<class T> class Container : Derived_from<T,Mybase> {
// ...
};
事实上Derived_from并不检查继承性，而是检查可转换性。不过Derive_from常常是一个更好的名字——有时给constraints起个好名字也是件需细细考量的活儿。
Last Revision: 2002.7
如欲转载请与我联系：[email protected]
本文地址：http://com.8s8s.com/it/it29548.htm