模板元编程

模板超编程（Template metaprogramming，缩写：TMP）是一种超编程技术，编译器使用模板产生暂时性的源码，然后再和剩下的源码混合并编译。这些模板的输出包括编译时期常数、资料结构以及完整的函式。如此利用模板可以被想成编译期的执行。这种技术被许多语言使用，最为知名的当属C++，其他还有Curl、D、Eiffel，以及语言扩展，如Template Haskell。

## 模板元编程的构成要素

使用模板作为元编程的技术需要两阶段的操作。首先，模板必须被定义；第二，定义的模板必须被实体化才行。

模板的定义描述了生成源码的一般形式，而使实体化则导致了某些源码的组合根据该模板而生成。

模板元编程是一般性地图灵完全（Turing-complete），这意味着任何可被电算软件表示的运算都可以透过模板超编程以某种形式去运算。

模板与宏（macros）是不同的。所谓宏只不过是以文字的操作及替换来生成程式码，虽然同为编译期的语言特色，但宏系统通常其编译期处理流的能力（compile-time process flow abilities）有限，且对其所依附之语言的语义及型别系统缺乏认知（一个例外是LISP的宏）。

模板元编程没有可变的变数——也就是说，变数一旦初始化后就不能够改动。因此他可以被视为函数式编程（functional programming）的一种形式。

## 使用模板超编程

模板超编程的语法通常与一般的程式语法迥异，他有其实际的用途。一些使用模板超编程的共同理由是为了实现泛型编程（generic programming）或是展现自动编译期最佳化，像是只要在编译期做某些事一次就好，而无需每次程式执行时去做。

### 编译期类别生成

以下将展示究竟何谓"编译期程式设计"。阶乘是一个不错的例子，在此之前我们先来回顾一下一般C++中阶乘函式的递回写法：

```cpp
int factorial(int n) 
{
    if (n == 0)
       return 1;
    return n * factorial(n - 1);
}

void foo()
{
    int x = factorial(4); // == (4 * 3 * 2 * 1 * 1) == 24
    int y = factorial(0); // == 0! == 1
}
```

以上的程式码会在程式执行时才决定4和0的阶乘。

现在让我们看看使用了模板超编程的写法，模板特化提供了"递回"的结束条件。这些阶乘可以在编译期完成计算。以下源码：

```cpp
template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
}
```

程式码如上在编译时期计算4和0的阶乘值，使用该结果值仿佛他们是预定的常数一般。

虽然从程式功能的观点来看，这两个版本很类似，但前者是在执行期计算阶乘，而后者却是在编译期完成计算。

然而，为了能够以此方式使用模板，编译器必须在编译期知道模板的参数值，也就是`Factorial<X>::value`只有当X在编译期已知的情况下才能使用。换言之，X必须是常数（constant literal）或是常数表示式（constant expression），像是使用`sizeof`运算子。

### 编译期程式码最佳化

以上阶乘的范例便是编译期程式码最佳化的一例，该程式中使用到的阶乘在编译期时便被预先计算并作为数值常数植入执行码当中，节省了执行期的经常开销（计算时间）以及内存足迹（memory footprint）。

编译期循环展开（loop-unrolling）是一个更显著的例子，模板超编程可以被用来产生n维（n-dimensional）的向量类别（当然n必须在编译期已知）。与传统n维向量比较，他的好处是循环可以被展开，这可以使性能大幅度提升。考虑以下例子，n维向量的加法可以被写成：

```cpp
template <int dimension>
Vector<dimension>& Vector<dimension>::operator+=(const Vector<dimension>& rhs) 
{
    for (int i = 0; i < dimension; ++i)
        value[i] += rhs.value[i]。
    return *this;
}
```

当编译器实体化以上的模板函式，可能会生成如下的程式码：

```cpp
template <>
Vector<2>& Vector<2>::operator+=(const Vector<2>& rhs) 
{
    value[0] += rhs.value[0]。
    value[1] += rhs.value[1]。
    return *this;
}
```

因为模板参数`dimension`在编译期是常数，所以编译器应能展开`for`循环。

### 静态多型

多型是一项共通的标准编程工具，衍生类别的物件可以被当作基础类别的物件之实体使用，但能够呼叫衍生物件的函式，或称方法（methods），例如以下的程式码：

```cpp
class Base
{
    public:
    virtual void method() { std::cout << "Base"; }
};

class Derived : public Base
{
    public:
    virtual void method() { std::cout << "Derived"; }
};

int main()
{
    Base *pBase = new Derived;
    pBase->method(); //outputs "Derived"
    delete pBase;
    return 0;
}
```

唤起的 `virtual` 函式是属于位于继承最下位之类别的。这种动态多型（dynamically polymorphic）行为是借由拥有虚拟函式的类别所产生的虚拟函式表（virtual look-up tables）来实行的。虚拟函式表会在执行期被查找，以决定该唤起哪个函式。因此动态多型无可避免地必须承担这些执行期成本。

然而，在许多情况下我们需要的仅是可以在编译期决定，无需变动的多型行为。那么一来，奇怪的递回模板样式（Curiously Recurring Template Pattern；CRTP）便可被用来达成静态多型。如下例：

```cpp
template <class Derived>
struct base
{
    void interface()
    {
         // ...
         static_cast<Derived*>(this)->implementation();
         // ...
    }
};

struct derived : base<derived>
{
     void implementation();
};
```

这里基础类别模板有着这样的优点：成员函式的本体在被他们的宣告之前都不会被实体化，而且它可利用 `static_cast` 并透过自己的函式来使用衍生类别的成员，所以能够在编译时产生出带有多型特性的物件复合物。在现实使用上，Boost迭代器库 便有采用 CRTP 的技法。

其他类似的使用还有"Barton–Nackman trick"，有时候被称作"有限制的模板扩张"，共同的功能被可以放在一个基础类别当中，作为必要的构件使用，以此确保在缩减多余程式码时的一致行为。

## 模板超编程的优缺点

- 编译期对执行期：因为模板的运算以及展开都是在编译期，这会花相对较长的编译时间，但能够获得更有效率的执行码。编译期花费一般都很小，但对于大专案或是普遍依赖模板的程式，也许会造成很大的编译开销。
- 泛型程式设计：模板超编程允许程序员专注在架构上并委托编译器产生任何客户码要求的实作。因此，模板超编程可达成真正的泛用程式码，促使程式码缩小并较好维护。
- 可读性：对于C++来说，模板超编程的语法及语言特性比起传统的C++编程，较难以令人理解。因此对于那些在模板超编程经验不丰富的程序员来说，程式可能会变的难以维护。（这要视各语言对于模板超编程语法的实作）
- 移植性：对于C++来说，由于各编译器的差异，大量依赖模板超编程（特别是最新形式的）的程式码可能会有移植性的问题。

## 关联项目

- 超编程
- 前处理器

## 参照

- Ulrich W. Eisenecker：Generative Programming: Methods, Tools, and Applications, Addison-Wesley, ISBN 0-201-30977-7
- 安德烈·亚历山德雷斯库：：Generic Programming and Design Patterns Applied, Addison-Wesley, ISBN 3-8266-1347-3
- Aleksey Gurtovoy：C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond, Addison-Wesley, ISBN 0-321-22725-5
- David Vandervoorde，Nicolai M. Josuttis：C++ Templates: The Complete Guide, Addison-Wesley, ISBN 0-201-73484-2
- Manuel Clavel：Reflection in Rewriting Logic: Metalogical Foundations and Metaprogramming Applications, ISBN 1-57586-238-7

## 外部链接

- The Boost Metaprogramming Library (Boost MPL) Boost超编程函式库
- The Spirit Library Boost的Spirit函式库（使用模板超编程建构）
- The Boost Lambda library Boost的Lambda函式库（可让你轻松使用STL算法）
- "Using C++ template metaprograms," C++ Report, Vol. 7 No. 4 (May 1995), pp. 36–43
- Template Haskell, type-safe metaprogramming in Haskell
- "Templates Revisited"，一篇关于D程式语言中模板超编程的文章。
- 文章" Metaprogramming in C++"
- 文章" Reflection support by means of template metaprogramming"
- 文章" STATIC DATA STRUCTURES"
- 文章" Template Meta Programming and Number Theory "
- 文章" Template Meta Programming and Number Theory: Part 2 "