泛型编程之类型串及应用介绍

泛型编程：类型串（typelists）及应用
Andrei Alexandrescu

很难讲这是怎么开始的。
我个人只能说：开始我在Usenet新闻组comp.lang.c++.moderated（顺便推荐一下）看到一些帖子，里面有怪异的模板递归。后来，当在自动虚工厂(Abstract Factory)实现中遇到巨大困难时，某种结构出现在我脑海中。
其他人也已经独立做过类似工作，因为各种不同的类型串到处都是。Czarnecki和Eisenecker在[1]里介绍了一个实际包含常量整数值的类型串。MPL库也定义了一个类型串，还加上一些操作类型串的算法。Modem C++ Design也介绍了一个简单的类型串实现并且把它用在至少五个泛型构件中(Functor,Visitor,AbstractFactory,StaticDispatcher,Tuple)，还不算二个自动类层次生成器(GenScatterHierarchy和GenLinearHierarchy)。
现在类型串的适用性已经得到证明。知道类型串肯定能够提高你的技术并帮助你更好理解现在甚至将来的C++库。
这篇文章再次介绍了类型串和能够解决实际问题的有趣程序。你当然不能把类型串当作圣诞老公公来问它要圣诞礼物，但如果你象块海绵一样吸收C++的任何新知识，你还是能够发现很多有趣的东西，所以，继续读下去吧。
那么什么是类型串？
类型串是不是也是奇形怪状的模板怪兽？实际上类型串太简单了，什么值都没有，C++社群不早点使用类型串真的太奇怪了。
Template <class H, class T>
Struct typelist
{
typedef H head;
typedef T tail;
}
这就是类型串的全部，真的根本不用花什么力气。但是用这一小块代码你能建立任意长度的类型串。使用的技术就是很久前LISP率先使用的尾部合成(tail composition)

typedef typelist<float, typelist<double, long double> >
floating_point_types;

你能这样做因为类型串是个类型，这样它能够作为组成大的类型串的一个类型。按照惯例，一个类型串只能出现在另一个类型串的尾部位置，而不能是头部位置；这样就使类型串的操作更简单，却不降低灵活度。
我们几乎要完成了，我们只需要定义一个辅助类型，这个辅助类型作为类型串的结束标志（类似LISP的nil）。我们叫它null_typelist:

class null_typelist {};

这样保存浮点类型的类型串的正确样式是：

typedef typelist<float, typelist<double,
typelist<long double, null_typelist> > >
floating_point_types;

线形生成类型串：三种方式
不用什么好的眼力就能看出来，只要多了几个成员，建立的类型串就变的非常难看。所有的这些：嵌套的模板实例、为了避免和>>操作符混淆在相邻>必须加空格，都使类型串太难用了
有几个处理这个问题的方法，Loki[3]使用宏定义，定义如下：

#define TYPELIST_1(T1) typelist(T1, null_typelist>
#define TYPELIST_2(T1, T2) typelist<T1, TYPELIST_1(T2) >
#define TYPELIST_3(T1, T2, T3 typelist<T1, TYPELIST_2(T2, T3) >

#define TYPELIST_50...

就象你所看到的，每个宏定义都依靠前面一个。Loki定义了最多有50个成员的类型串的“构造器”。超过50个，你要么定义新宏定义，要么把类型串手动连接起来。
我本来应该知道用宏定义并非是很好的解决方案。文本转换是很强大，但C++预处理器太简陋了。当你以为你用它做了些有趣的事，它总是会在背后咬你一口。
在这个例子里，问题在于你不能把这些宏定义和摸板一起用，即使是最简单的摸板。举例来说：

typedef TYPELIST_2 (vector<int, allocator>,
vector<int, my_allocator>)
storage_choices;

预处理器能处理圆括号，但不能处理尖括号<和>。这样的话，TYPELIST_2宏里的文本对预处理器来说包含了4个参数——(!) vector<int,(2) allocator>, (3) vector<int, (4) my_allocator>，而不是想要的二个。更糟糕的是，某些预处理器更本不会报错——只会悄悄地忽略掉参数(3)和(4)并产生一个没用的宏展开来让你头疼。
更好的解决方案是用模板来产生类型串。下面是想法的实现：

template <class T1>
struct cons<T1, null_typelist, null_typelist
null_typelist>
{
typedef typelist<T1, null_typelist> type;
}

template <class T1, class T2>
struct cons<T1, T2, null_typelist, null_typelist>
{
typedef typelist<T1, typelist<T2,
null_typelist> > type;
}

template <class T1, class T2, class T3>
stuct cons<T1, T2, T3, null_typelist>
{
typedef typelist<T1, typelist<T2, typelist<T3,
null_typelist> > > type;
}

template <class T1, class T2, class T3, class T4>
struct cons
{
typedef typelist<T1, typelist<T2, typelist<T3,
typelist<T4, null_typelist> > > > type;
}

上面的示例最多支持四个类型，你能这样使用cons：

typedef cons<float, double, long double>::type
floating_point_types;

cons模板建立在部分特化(partial specilization)基础上。当你实例化cons<float, double, long double>时，首先编译器往cons的第四个参数填充默认值，所以其实是cons<float, double, long double, null_typelist>，然后，编译器把这个实例和四个定义好的特化版本匹配。
第一个特化版本不匹配，因为它要求T2是null_typelist，然而这里的实际T2是double，同样的，第二个特化版本也不匹配，因为T3不对。第三个特化版本是个有效的候选对象，因为它接受T1，T2，T3为任意类型。这还没结束，编译器还会检查第四个特化版本，这个特化版本也能匹配因为它接受T1，T2，T3，T4为任意类型，所以T4为null_typelist也不会有任何问题。但慢着，当你说出“编译期错误”前，第三个特化版本已被选中，因为它比第四个更加适用。
决定“更适用”的算法相当复杂，但直觉上，一个摸板的部分特化版本比另一个更一般化的版本更适合（前者有更小的适用范围）。当用一个实际的参数串去匹配几个模板的部分特化版本时，被选中的是能够接受参数的最特化的版本。在我们的例子中，第三个cons的特化版本被选中，因为它匹配cons<float, double, long double, null_typelist>实例，而且它比第四个更特化。这是因为第四个接受对应T4的任意类型，而第三个至接受T4为null_typelist，所以更加特化。
你能扩展cons使它能接受任意数目的类型，但可惜的是，你除非修改cons，否则你不能扩展cons的上限。要么你再次使用某些预处理器的技巧。
第三个方法采用函数方式，看看下面：

template <class Fun> struct cons;

template <class T1> struct cons<void (*)(T1)>
{
typedef typelist<T1, null_typelist> type;
};

template <class T1, class T2>
struct cons<void (*)(T1, T2)>
{
typedef typelist<T1, typelist<T2,
null_typelist> > type;
};

template <class T1, class T2, class T3>
struct cons<void (*)(T1, T2, T3)>
{
typedef typelist<T1, typelist<T2,
typelist<T3, null_typelist> > > type;
};

template <class T1, class T2, class T3, class T4>
struct cons<void (*)(T1, T2, T3, T4)>
{
typedef typelist<T1, typelist<T2, typelist<T3,
typelist<T4, null_typelist> > > > type;
};

现在如果你定义了一个这样的宏：

#define TYPELIST(a) cons<void (*)a >::type;

你就能这样写：

typedef TYPELIST((float, double, long double))
floating_point_type;

如果你能成功让人们相信两对圆括号是多么漂亮，这真的很不错。
好吧，我知道我需要解释一下。第一件事，void (*)(T1)是个c++类型（我没有打错字！）：一个函数指针，接受一个类型为T1的参数，返回void。这个类型用void (*Fun)(T1)来表达更让人熟悉，它实际上是包含了名称的一个结构。
Cons模板类用返回void接受一个、二个、三个或四个参数的函数指针来特化。然后TYPELIST宏展开这个结构：
TYPELIST((float, double, long double))
变成
cons<void (*) (float, double, long double) >::type
其实就是
typelist<float, typelist<double,
typelist<long double, null_typelist> > >
现在对这节做个小结，上面的解决方法没有哪种是完美的；只有语言本身对可变模板参数支持了，你才会同时得到清晰，方便，可扩展，易使用的优点。
这篇文章的剩余部分我们将使用第二个方法——用cons<...>::type的那一个。
现在是开始使用类型串的时候了。上一篇文章[4]介绍了怎么计算类型串的长度。下面我们看看针对实际问题的类型串的一个新的应用。

即兴访问（Ad-Hoc Visitation）
访问者模式（Visitor design pattern）针对复杂问题为你提供了一个清晰的解决方案。但它的缺陷限制了它的应用。本质上，访问者模式提供给你一个安全地在类层次增加操作的方法，而不用修改这个类层次本身，代价是：当类层次改变时你必须改变所有这些操作。要知道详细情况，看看著名的《设计模式》[5]或者专门讲C++的《Modern C++ Design》[3]。
一个很少被提及的和访问相关的问题是：你必须在类层次中支持访问模式。这种支持指类层次中增加一个Accept成员函数。换句话说，如果你不能改写一个不支持访问的类层次的话，你就不能访问它。
如果类层次不支持访问，而且如果你想在类层次中增加一个操作却不改写它。那你就注定只能用讨厌的switch-on-type方法。真实世界里，很普遍的情况是：你使用旧的类库里的基类来增加你自己的继承类。
设想，比如说，有一个以DocumentItem为根的类层次，实类型为TextArea,VectorGraphics和Bitmap。这些都直接从DocumentItem继承。为了增加一个操作SomeOperation,你能这样做：

void SomeOperation (DocumentItem* p)
{
if (TextArea* pTextArea = dynamic_cast<TextArea*>(p))
{
...处理TextArea对象...
}
else if (VectorGraphics* pVectorGraphics =
dynamic_cast<VectorGraphics *>(p))
{
...处理VectorGraphics对象...
}
else if (Bitmap* pBitmap = dynamic_cast<Bitmap *>(p))
{
...处理Bitmap对象...
}
else
{
throw "Unknown type passed";
}
}

除了极其难看外，上面的代码还有概念上的问题：它不能够在编译时发现“忘记处理这种类型”的错误。如果我们的假设的类层次用一个新类型PieChart来扩展，或者上面SomeOperation代码忘记处理一个已经存在的类型，唯一的解决方案只能借助于抛出一个运行时意外
如果存在一处这样的代码还不是太坏，但三处甚至更多肯定是。会慢慢的把你的程序变成莫雷奥医生的小岛[6]
一个对这个问题的部分解决方法是：某种机制来自动生成并从代码中提取出执行动态转换(casts)的部分。这样，当你更改类层次时只有唯一一处地方需要维护。这里正好类型串用得上。
考虑下面代码

template <class tlist> class AdHocVisitor;

template <class H, class T>
class AdHocVisitor< typeList<H, T> >
public AdHocVisitor<T>
{
public:
using AdHocVisitor<T>::Visit;
virtual void Visit(H*) = 0;
template <class SomeClass>
void StartVisit(SomeClass* p)
{
if (H* pFound = dynamic_cast<H*>(p))
{
Visit(pFound);
}
else
{
AdHocVisitor<T>::StartVissit(p);
}
}
};

template <class H>
class AdHocVisitor<typelist<H, null_typelist> >
{
public:
virtual void Visit(H*) = 0;
template <class SomeClass>
void StartVisit (SomeClass* p)
{
if (H* pFound = dynamic_cast<H*>(p))
{
Visit(pFound);
}
else
{
throw "Unknown type passed";
}
}
};

AdHocVisitor接受一个类型串作为它的参数并使用类似于cons 的技术。就是说，AdHocVisitor有二个部分特化版本，一个处理类型串的头并递归处理类型串的尾，另一个的作用是停止递归。
第一个特化版本定义一个纯虚函数Visit(H*)，H是类型串的头。另外，AdHocVisitor继承它本身，就是用这个类型串的尾来实例化的AdHocVisito。本质上，AdHocVisitor<tl>为类型串中的每个类型定义一个纯虚函数Visit。
这是一个不错的开端，因为这正是访问者模式的要求。但我们也需要实际的分派调用Visit，这是StartVisit的工作，这个函数的实现非常有趣。
我们从AdHocVisitor的第一个特化版本的StartVisit的实现开始。在这里尝试用dynamic_cast作用于传入的指针（值得注意的是这个指针可以是任意类型）。如果转换成功，StartVisit就调用纯虚函数Visit并把转换结果传入Visit来执行访问。如果转换不成功，StartVisit调用AdHocVisitor<T>::StartVisit。AdHocVisitor<T>是AdHocVisitor<typelist<H,T> >的基类。所以上面的那个调用其实只不过是对基类成员函数的直接调用。而基类成员函数会继续执行dynamic_cast来寻找正确的类型。
递归必须在某处停止，这就是第二个AdHocVisitor特化版本的任务。那个特化版本处理只有一个成员的类型串（另一个是null_typelist）。这里的不同之处是，当dynamic_cast失败，StartBisit抛出意外。你马上就会看到，这其实不象看上去那样坏。
现在让我们看看怎么用新定义的AdHocVisitor。假设我们用一个简单的main函数代替上面的定义。

Int main()
{
typedef cons<TextArea, VectorGraphics,
Bitmap>::type MyHierarchy;
DocElement *p = new Bitmap;
Struct ConcreteVisitor :AdHocVisitor<MyHierarchy>
{
void Visit(TextArea* p)
{
...
}
void Visit(VectorGraphics* p)
{
...
}
void Visit(Bitmap* p)
{
...
}
};
ConcreteVisitor visitor;
Visitor.StartVisit(p);
}

让我们看看这是怎么工作的。第一行定义一个类型串MyHierarchy包含了TextArea,VectorGraphics和Bitmap。注意根类DocElement不是类型串的一部分。
ConcreteVisitor类直接定义在main函数里——这正体现了具体实现的名字“即兴(ad hoc)”。正如你猜到的，ConcreteVisitor从AdHocVisitor<MyHierarchy>继承并重载AdHocVisitor<MyHierarchy>声明的三个纯虚函数。
当main函数用p调用StartVisit时，上面描述的机制开始运行并顺利地执行正确的Visit重载版本。

分析即兴访问
和探索代码细节一样重要的是分析代码的运行结果，
效率
不得不承认，对比最前面展现的笨拙的if/else解决方案，我们仍旧用dynamic_cast，而且我们做了额外的虚函数调用(Visit)。
虚函数调用可以用下面的步骤简单的消除：
* 在AdHocVisitor接受第二个模板参数Effector，并从它继承
* 让AdHocVisitor假设这些Visitor函数定义在Effector里并使用它们，而不是在AdHocVisitor定义虚函数。
* （可选）在每个成功的dynamic_cast分支，编译时保证Effector::Visit有正确的形式（返回值和参数列表）。通过获得Effector::Visit的地址，编译时测试能很简单地实现。
* 把ConcreteVisitor从main里拿出。把ConcreteVisitor放在函数里面概念上讲没有错误。但是，唉，C++不允许本地类型作为模板参数传递。
* 使用AdHocVisitor模板，将类型串和你的ConcreteVisitor类作为模板参数传入，你可以调用StartVisitation来开始访问。
在这里为什么不从头开始讨论这个优化解决（而不是把它作为给读者的讨厌的练习）
呢？这个优化解决版本需要处理一些其他非常棘手的问题，而这篇文章只关注类型串使用问题/。

耦合
所有方案都需要有类层次的信息。但是非常重要的是。你必须注意到那个蛮干（switch-on-type）的解决方案要求你把类层次的信息分散到代码各处，基于类型串的解决让你把这些信息集中到一处，你只需要提供一个typedef，然后你只有在修改类层次时才会修改它。

维护
不要忘记我们的讨论是在一个特殊环境下：你不能往你想修改的类层次里添加函数。那样从开始时就强加给我们一些缺陷。
这就是说，基于类型串的解决带来了非常重要的维护上的好处。假设你忘记在你的ConcreteVisitor类里处理Bitmap类型：

struct ConcreteVisitor : AdHocVisitor<MyHierarchy>
{
void Visit(TextArea* p)
{
...
}
void Visit(VectorGraphics* p)
{
...
}
};

这样编译器不会让你实例化ConcreteVisitor，因为AdHocVisitor<MyHierarchy>定义了一个纯虚函数void Visit(Bitmap*)，正如你所知，纯虚函数必须被重载。
换句话说，你得到保证，一旦你正确定义了MyHierarchy类型串，所有代码中一切被忘记的部分都会在编译时被指出。这个只有唯一一处需要维护的设计非常有吸引力。（然而不幸的是，这个解决不能处理在ConcreteVisitor有个假造的处理函数（比如说void Visit(IrrelevantType*)的情况）

结论
这篇文章介绍了一个用C++实现的类型串，附带了一个完整的使用范例。类型串强大而重要，大部分是因为用它可以实现全新的常用法(idioms)。这样针对复杂问题就有更好的解决方案。最重要的是，类型串通过让你提取乏味的重复代码来鼓励你实现复用。

参考书目
[1] K. Czarnecki 和 U. Eisenecker. Generative Programming: Methods, Tools, and Applications (Addison-Wesley Longman, 2000).
[2] 参见 <www.boost.org>.
[3] A. Alexandrescu. Modern C++ Design (Addison-Wesley Longman, 2001).
[4] J. Vlissides 和 A. Alexandrescu. "To Code or Not to Code II," C++ Report, June 2000, <www.research.ibm.com/designpatterns/pubs/ph-jun00.pdf>.
[5] E. Gamma, et al. Design Patterns (Addison-Wesley Longman, 1995).
[6] H.G. Wells' novel The Island of Dr. Moreau (Dover, 1996) 描写了一位疯狂的医生在一个孤立的小岛上把动物变形为人。然后，他没有预料到的是他的生物逐渐变回原形，在此期间给它们和他都带来许多伤害。

Andrei Alexandrescu 是位于西雅图的华盛顿大学的博士生，也是受到好评的《Modern C++ Design》一书的作者。可以通过www.moderncppdesign.com. 来联系他。Andrei同时也是C++研讨会 (<www.gotw.ca/cpp_seminar>).的一名有号召力的讲师。