模板元編程

模板超編程（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 "