C++语言的表达式模板：表达式模板的入门性介绍
C++语言的表达式模板：表达式模板的入门性介绍
原标题：C++ Expression Templates: An Introduction to the Principles of Expression Templates
原作者：Klaus Kreft与Angelika Langer
原文链接： http://www.angelikalanger.com/Articles/Cuj/ExpressionTemplates/ExpressionTemplates.htm
翻译：Magi Su
翻译已经过原作者许可，转载请先征求原作者的许可。图片均取自原文，如果有水印为CSDN所打和老子没关系。出于清晰起见，文章中所有模板中的class都被改为typename。
模板（template）最早是以将类型（type）参数化为目的引入C++语言的。（译注1）链表 （list）是一个典型的例子。实际编码的时候，人们并不希望为保存不同类型变量的链表 分别编码，而是希望在编写的时候能够使用一个占位符（placeholder）来代替具体的类型 （即是模板参数），而让编译器来生成不同的链表类（模板的实例化）。
时至今日，模板的使用已经远远超过C++模板的发明者所预期的范畴。模板的使用已经涵盖 了泛型编程，编译时求值，表达式模板库，模板元编程，产生式编程（generative programming）等诸多领域。在这篇文章中，我们仅限于探讨一些表达式模板的编程知识， 侧重于编写表达式模板程序库这个方面。
我们必须指出：表达式模板库是相当复杂的。出于这个原因，我们读到过的关于表达式模 板的介绍都不是很容易理解的。因此，本文的作者希望能够通过本文为表达式模板提供一 个通俗的介绍，同时又不失对具体实现细节的阐述，从而对读者阅读模板库的代码能够起 到帮助。作者希望提取出表达式模板编码的一些原则性知识。有关于此领域的更多细节可 以参考其他著作。
创世纪时至今日，我仍然能清晰的记起我的同事Erwin Unruh在一次C++标准委员会会议时展 示的得意之作。这是一段并不能通过编译的代码，但是它却给出了质数数列。（参见：UNR ）编译它的过程中产生的错误信息中依次包含了每一个给定范围内的质数。当然，不能够 通过编译的程序是毫无意义的，然而这段代码是有意这样的。它旨在指出，这段计算是在 编译时进行的，没有可执行文件，从而也就没有运行时。质数的计算只是编译时期的副产 物而已。
这段小小的程序引发了之后多年对所谓模板元编程的雪崩般的研究。本文将介绍从中得来 的一些编程技巧和技术。那么，模板元编程的工作原理是什么呢？
从本质上来看，无论是质数的计算，还是本文中所提及的其他技术，都是基于如下原理的 ：模板的实例化是一个递归过程。当编译器实例化一个模板时，它可能会发现在此之前另 外的模板需要首先实例化；在实例化这些模板的时候，又会发现有更多的模板需要实例化 。许多模板元编程的技巧就是基于这个原理，来实现递归式的计算的。
阶乘——编译时计算的第一个例子作为第一个例子，我们来在编译时对N的阶乘进行计算。N的阶乘（记作N!）定义为从1到N 所有整数的积。（译注2），作为一个特例，0的阶乘是1。通常对阶乘的递归计算可以采用 函数递归的方法，如下是一个运行时计算的例子：
的时候。我们知道积分x / (1 + x)可以通过在积分区间中取n个等距离的点（这里是 [1.0, 5.0]）来近似计算。（译注6）如果我们使用表达式模板来实现一个近似求解任意函 数积分的程序，那么它的一个可能的样子如下：
图1：一个典型的组合体结构
著作GOF提出了一个采用虚基类实现的面向对象的组合体设计：定义叶结点和组合体共有的 操作，而叶结点和组合体均从一个基类派生出来。
图2：组合体设计模式的类图
向量的点乘可以看作组合体设计模式的一个特例。点乘可以分成两个部分：叶结点是一维 向量的积，而组合体是剩下N-1维向量的点乘。
图3：点乘的组合结构
显而易见，这是组合体的某种简并（degenerate）形式，每个组合体包含一个叶结点和一 个组合体。使用面向对象编程的技术，我们可以用一个基类和两个派生类来表示点乘：
图4：点乘的组合体的类图
具体的编码实现可以参考列表1-3的内容。列表4给出了一个方便使用的辅助函数，列表5是 一个具体的使用例子。
列表1：基类
图5：简化的点乘模型的类图
点乘（II）——编译时计算现在让我们将面向对象的实现转化成为编译时计算的实现。叶结点和组合体对应的两个类 共用了一个用来表示它们的共同操作的基类——这是面向对象编程的常用技巧：共同点用相 同的基类来表示。在模板编程中，共同点则是用命名的一致性来表现的。在面向对象编程 中的虚函数将不再为虚，而变为一个普通的，有着特定名称的函数。两个派生类不再是从 一个基类中派生的两个类，而是变为独立的，有着相同名称和相通记号成员函数的两个类 。也就是说，我们不再需要基类了。
现在我们来通过在模板的参数中保存结构信息的方式来实现组合体。我们需要保存的结构 信息是这个向量的维度。回忆一下之前我们计算阶乘和平方根的代码：函数实现中函数的 参数变为了编译时处理的模板参数。我们在这里也采用相同的手法，原来在面向对象实现 中传递给求值函数的向量的维度，在这里变为编译时确定的模板参数。因此在组合体中， 这个维度数据将变为模板中的一个常量参数。
叶结点则需要通过组合体类在一维情况下的模板特化类来实现。正如以往一样，我们将运 行时的递归转变为编译时的递归：将对求值虚函数的递归调用转变为模板类在递归实例化 的过程中对一个静态的求值函数的递归调用。如下是编译时计算点乘代码的类图：
图6：编译时计算点乘的类图
具体实现代码在列表7中供参考。使用的例子可以参见列表8。
列表7：编译时点乘的实现
图7：算术表达式的语法树的例子
在GOG中，解释器的经典的面向对象设计如下类图所示：
图8：面向对象方式实现的算术表达式的解释器的类图
与之相关的代码实现可以参见列表9.UnaryExpr的基类与BinaryExpr的类相似，所有的一元 和二元运算均和类Sum相似。
列表9：面向对象方式下的算术表达式的解释器
图9：基于模板实现的表达式求值解释器的类图
源码请参考列表11：
列表11：基于模板的算术表达式解释器
图10：编译时对表达式对象(v + 2) * 3的计算表达式对象的反复计算
读者可能仍然在考虑表达式对象的优势在何处。每个表达式对象代表了一个算术表达式的分解，从而形成了一个语法树，而这个语法树又能够自动求值。简而言之，我们创造了一个机械式的表达式求值途径——虽然这个途径C++语言本身就支持。那么这么做到底有何好处呢？下面我们来考察这一点。
迄今为止，我们所用到的语法树都是静态的。每个语法树在构造之后，只被调用一次。然而我们可以通过给定一个语法树，并传入不同的参数值，来动态的使用这个模型。如上文所述，我们希望能够用如下的近似函数：
为此我们可以用下面的例子给出的方式来调用这个函数：/GOF/
Design Patterns: Elements of Reusable Object-Oriented Software
Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides
Addison-Wesley, January 1995
ISBN: 0201633612/VAN/
C++ Templates – The Complete Guide
DavidVandevoorde and Nicolai Josuttis
Addison-Wesley2003/UNR/
Compile-Time Computation of Prime Numbers
ErwinUnruh
http://www.erwin-unruh.de/Prim.html/DUR/
Design Patterns for Generic Programming in C++
AlexandreDuret-Lutz, Thierry Géraud, and Akim Demaille
http://www.lrde.epita.fr/dload/papers/coots01.html/VEL/
T. Veldhuizen, "Expression Templates," C++ Report,Vol. 7 No. 5 June 1995, pp. 26-31
The article has beenreprinted in the book "C++ Gems" edited by StanleyLippman.
http://osl.iu.edu/~tveldhui/papers/Expression-Templates/exprtmpl.html/JüL/
Research Centre Jülich
http://www.fz-juelich.de/zam/cxx/
An impressive directory of C++ resources such as books,articles, FAQs, other C++ pages, compilers, libraries, etc. See inparticular the links to other C++ libraries athttp://www.fz-juelich.de/zam/cxx/extmain.html#lib/OON/
The Object-Oriented Numerics Page
http://www.oonumerics.org/oon/#libraries
A directory of links to freely available numeric libraries./BLI/
The Blitz Project
http://oonumerics.org/blitz/
A C++ class library for scientific computing which usestemplate techniques to achieve high performance./PET/
PETE (Portable Expression Template Engine)
http://acts.nersc.gov/events/PI1999/pete/
A portable C++ framework to easily add powerful expressiontemplates./POO/
POOMA (Parallel Object-Oriented Methods and Applications)
http://acts.nersc.gov/pooma/
An object-oriented framework for applications in computationalscience requiring high-performance parallel computers./MET/
MET (Matrix Expression Templates)
http://met.sourceforge.net/
A C++ matrix class library. C++ overloaded operators enableone to write the simplest code like u = m*v + w./MTL/
MTL (Matrix Template Library)
http://www.osl.iu.edu/research/mtl/
A high-performance generic component library that provideslinear algebra functionality for a wide variety of matrixformats. Uses an STL-style approach. Provides genericalgorithms corresponding to the mathematical operations thatdefine linear algebra. Containers, adaptors, and iteratorsare used to represent and to manipulate matrices and vectors.
See also the following paper:
The Matrix TemplateLibrary: A Generic Programming Approach to High-Performance
Jeremy G. Siek and Andrew Lumsdaine
http://www.osl.iu.edu/download/research/mtl/papers/iscope_final.pdf/FAC/
FACT! (Functional Additions to C++ through Templates andClasses)
http://www.kfa-juelich.de/zam/FACT/start/index.html
A library that offers lambda expressions built on top of PETE. By using FACT!'s lambda syntax the programmer can definegeneric functions for use with the STL on the fly./FCP/
FC++ (Functional Programming in C++)
http://www.cc.gatech.edu/~yannis/fc++/
A library for functional programming in C++, which you can useto define your own higher-order polymorphic functions./BLL/
BLL (The Boost Lambda Library)
http://www.boost.org/libs/lambda/doc/index.html
A C++ template library, which implements lambda abstractionsfor C++. The primary motivation for the BLL is to provide flexibleand convenient means to define unnamed function objects for STLalgorithms./PHO/
Phoenix (A parser used by Spirit)
http://spirit.sourceforge.net/index.php?doc=docs/phoenix_v1_0/index.html
Phoenix is a framework that opens up functionalprogramming techniques such as Lambda (unnamed functions) andCurrying (partial function evaluation), similar to FC++ and BLL.
作者感谢在C++ UsersJ 阅读了我们文章的Gary Powell。他的邮件中提及了我们之前没有注意到的FACT!，FC++，Boost Lambda Library，以及Phoenix程序库。
译注：
译注1：参见《The Design and Evolution of C++》。
译注2：阶乘在数学上可以用Gamma函数定义。
译注3：C99是允许变长数组的，但是即便是最新的C++11标准也不支持变长数组。
译注4：这其实是使用二分法搜索平方根。作为一个优化，默认的Upp可以定为N的一半甚至 更少。
译注5：编译时数值计算是有相当局限性的，例如浮点数的计算就无法执行，这是因为浮点 数计算是和机器/编译器实现直接相关的。
译注6：参见Riemann积分定义。
译注7：C++11的Lambda语法可能大大减少此类技巧的使用。
译注8：原文中a，b，c均为20x10的矩阵，明显有误，这里更改为一个合理的值。
译注9：原文中>和>之间有一个多余的空格，这是C++03标准的要求。在C++11中这个空格可 以去掉。
译注10：虚函数是通过查询虚表进行的调用的，因此编译时很难确认具体哪个函数会被调 用，然而现在也有编译器可以在一定程度上预测调用的具体函数，参见g++的参数 -fdevirtualize。
