大龍的博客

模板元 --------- 轉

摘要
本文簡述了模板元編程技術的起源、概念和機制， 并介紹了模板元編程技術在Blitz++和Loki程序庫中的應用。  
關鍵字
編譯期計算  模板元編程  Blitz++  Loki  
導言  
1994年，C++標準委員會在圣迭哥舉行的一次會議期間Erwin Unruh展示了一段可以產生質數的代碼。這段代碼的特別之處在于質數產生于編譯期而非運行期，在編譯器產生的一系列錯誤信息中間夾雜著從2到某個設定值之間的所有質數：  
// Prime number computation by Erwin Unruh
template <int i> struct D { D(void*); operator int(); };
template <int p, int i> struct is_prime {
    enum { prim = (p%i) && is_prime<(i > 2 ? p : 0), i -1> :: prim };
};
template < int i > struct Prime_print {
    Prime_print<i-1> a;
    enum { prim = is_prime<i, i-1>::prim };
    void f() { D<i> d = prim; }
};
struct is_prime<0,0> { enum {prim=1}; };
struct is_prime<0,1> { enum {prim=1}; };
struct Prime_print<2> { enum {prim = 1}; void f() { D<2> d = prim; } };
#ifndef LAST
#define LAST 10
#endif
main () {
    Prime_print<LAST> a;
}
類模板D只有一個參數為void*的構造器，而只有0才能被合法轉換為void*。1994年，Erwin Unruh采用Metaware 編譯器編譯出錯信息如下（以及其它一些信息，簡短起見，它們被刪除了）：  
| Type `enum{}&acute; can&acute;t be converted to txpe `D<2>&acute; ("primes.cpp",L2/C25).
| Type `enum{}&acute; can&acute;t be converted to txpe `D<3>&acute; ("primes.cpp",L2/C25).
| Type `enum{}&acute; can&acute;t be converted to txpe `D<5>&acute; ("primes.cpp",L2/C25).
| Type `enum{}&acute; can&acute;t be converted to txpe `D<7>&acute; ("primes.cpp",L2/C25).
如今，上面的代碼已經不再是合法的C++程序了。以下是Erwin Unruh親手給出的修訂版，可以在今天符合標準的C++編譯器上進行編譯：  
// Prime number computation by Erwin Unruh
template <int i> struct D { D(void*); operator int(); };
template <int p, int i> struct is_prime {
    enum { prim = (p==2) || (p%i) && is_prime<(i>2?p:0), i-1> :: prim };
};
template <int i> struct Prime_print {
Prime_print<i-1> a;
    enum { prim = is_prime<i, i-1>::prim };
    void f() { D<i> d = prim ? 1 : 0; a.f();}
};
template<> struct is_prime<0,0> { enum {prim=1}; };
template<> struct is_prime<0,1> { enum {prim=1}; };
template<> struct Prime_print<1> {
    enum {prim=0};
    void f() { D<1> d = prim ? 1 : 0; };
};
#ifndef LAST
#define LAST 18
#endif
main() {
    Prime_print<LAST> a;
    a.f();
}
在GNU C++ (MinGW Special) 3.2中編譯這段程序時，編譯器將會給出如下出錯信息（以及其它一些信息，簡短起見，它們被刪除了）：  
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 17]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 13]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 11]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 7]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 5]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 3]'
Unruh.cpp:12: initializing argument 1 of `D<i>::D(void*) [with int i = 2]'
這個例子展示了可以利用模板實例化機制于編譯期執行一些計算。這種通過模板實例化而執行的特別的編譯期計算技術即被稱為模板元編程。
順便說一句，因為編譯器的出錯信息并未被標準化，所以，如果你在Visual C++、Borland C++等編譯器上看不到這么詳細的出錯信息，請不必訝異。  
一個可以運行的模板元編程例子  
模板元編程（Template Metaprogramming）更準確的含義應該是“編‘可以編程序的’程序”，而模板元程序（Template Metaprogram）則是“‘可以編程序的’程序”。也就是說，我們給出代碼的產生規則，編譯器在編譯期解釋這些規則并生成新代碼來實現我們預期的功能。  
Erwin Unruh的那段經典代碼并沒有執行，它只是以編譯出錯信息的方式輸出中間計算結果。讓我們來看一個可以運行的模板元編程例子 — 計算給定整數的指定次方：  
// xy.h
//原始摸板
template<int Base, int Exponent>
class XY
{
public:
    enum { result_ = Base * XY<Base, Exponent-1>::result_ };
};
//用于終結遞歸的局部特化版
template<int Base>
class XY<Base, 0>
{
public:
    enum { result_ = 1 };
};
模板元編程技術之根本在于遞歸模板實例化。第一個模板實現了一般情況下的遞歸規則。當用一對整數<X, Y>來實例化模板時，模板XY<X, Y>需要計算其result_的值，將同一模板中針對<X, Y-1>實例化所得結果乘以X即可。第二個模板是一個局部特化版本，用于終結遞歸。  
讓我們看看使用此模板來計算5^4 （通過實例化XY<5, 4>）時發生了什么：  
// xytest.cpp
#include <iostream>
#include "xy.h"
int main()
{
    std::cout << "X^Y<5, 4>::result_ = " << XY<5, 4>::result_;
}
首先，編譯器實例化XY<5, 4>，它的result_為5 * XY<5, 3>::result_，如此一來，又需要針對<5, 3>實例化同樣的模板，后者又實例化XY<5, 2>…… 當實例化到XY<5, 0>的時候，result_的值被計算為1，至此遞歸結束。  
遞歸模板實例化的深度和終結條件  
可以想象，如果我們以非常大的Y值來實例化類模板XY，那肯定會占用大量的編譯器資源甚至會迅速耗盡可用資源（在計算結果溢出之前），因此，在實踐中我們應該有節制地使用模板元編程技術。  
雖然 C++標準建議的最小實例化深度只有17層，然而大多數編譯器都能夠處理至少幾十層，有些編譯器允許實例化至數百層，更有一些可達數千層，直至資源耗盡。  
假如我們拿掉XY模板局部特化版本，情況會如何？  
// xy2.h
//原始摸板
template<int Base, int Exponent>
class XY
{
public:
    enum { result_ = Base * XY<Base, Exponent-1>::result_ };
};
測試程序不變：  
// xytest2.cpp
#include <iostream>
#include "xy2.h"
int main()
{
    std::cout << "X^Y<5, 4>::result_ = " << XY<5, 4>::result_;
}
執行如下編譯命令：  
C:\>g++ -c xytest2.cpp  
你將會看到遞歸實例化將一直進行下去，直到達到編譯器的極限。  
GNU C++ (MinGW Special) 3.2的默認實例化極限深度為500層，你也可以手工調整實例化深度：  
C:\>g++ -ftemplate-depth-3400 -c xytest2.cpp  
事實上，就本例而言，g++ 3.2允許的實例化極限深度還可以再大一些（我的測試結果是不超過3450層）。  
因此，在使用模板元編程技術時，我們總是要給出原始模板的特化版（局部特化版或完全特化版或兼而有之），以作為遞歸模板實例化的終結準則。  
利用模板元編程技術解開循環  
模板元編程技術最早的實際應用之一是用于數值計算中的解循環。舉個例子，對一個數組進行求和的常見方法是：  
// sumarray.h
template <typename T>
inline T sum_array(int Dim, T* a)
{
    T result = T();
    for (int i = 0; i < Dim; ++i)
    {
        result += a;
    }
    return result;
}
這當然可行，但我們也可以利用模板元編程技術來解開循環：  
// sumarray2.h
// 原始模板
template <int Dim, typename T>
class Sumarray
{
public:
    static T result(T* a)
    {
        return a[0] + Sumarray<Dim-1, T>::result(a+1);
    }
};
// 作為終結準則的局部特化版
template <typename T>
class Sumarray<1, T>
{
public:
    static T result(T* a)
    {
        return a[0];
    }
};
用法如下：  
// sumarraytest2.cpp
#include <iostream>
#include "sumarray2.h"
int main()
{
    int a[6] = {1, 2, 3, 4, 5, 6};
    std::cout << " Sumarray<6>(a) = " << Sumarray<6, int>::result(a);
}
當我們計算Sumarray<6, int>::result(a)時，實例化過程如下：  
Sumarray<6, int>::result(a)
= a[0] + Sumvector<5, int>::result(a+1)
= a[0] + a[1] + Sumvector<4, int>::result(a+2)
= a[0] + a[1] + a[2] + Sumvector<3, int>::result(a+3)
= a[0] + a[1] + a[2] + a[3] + Sumvector<2, int>::result(a+4)
= a[0] + a[1] + a[2] + a[3] + a[4] + Sumvector<1, int>::result(a+5)
= a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
可見，循環被展開為a[0]  + a[1] + a[2] + a[3] + a[4] + a[5]。這種直截了當的展開運算幾乎總是比循環來得更有效率。  
也許拿一個有著600萬個元素的數組來例證循環開解的優勢可能更有說服力。生成這樣的數組很容易，有興趣，你不妨測試、對比一下。
（感謝一位朋友的測試。他說 ，“據在Visual C++ 2003上實測編譯器應當進行了尾遞歸優化，可以不受上面說的遞歸層次的限制，然而連加的結果在數組個數達到4796之后就不再正確了，程序輸出了空行，已經出錯” — 2003年12月30日補充）
模板元編程在數值計算程序庫中的應用  
Blitz++之所以“快如閃電”（這正是blitz的字面含義），離不開模板元程序的功勞。Blitz++淋漓盡致地使用了元編程技術，你可以到這些文件源代碼中窺探究竟：  
dot.h
matassign.h
matmat.h
matvec.h
metaprog.h
product.h
sum.h
vecassign.h  
讓我們看看Blitz++程序庫dot.h文件中的模板元程序：  
template<int N, int I>
class _bz_meta_vectorDot {
public:
    enum { loopFlag = (I < N-1) ? 1 : 0 };
    template<class T_expr1, class T_expr2>
    static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
    f(const T_expr1& a, const T_expr2& b)
    {
        return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
    }
    template<class T_expr1, class T_expr2>
    static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
    f_value_ref(T_expr1 a, const T_expr2& b)
    {
        return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
    }
    template<class T_expr1, class T_expr2>
    static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, _bz_typename T_expr2::T_numtype)
    f_ref_value(const T_expr1& a, T_expr2 b)
    {
        return a[I] * b[I] + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::f(a,b);
    }
    template<class T_expr1, class P_numtype2>
    static inline BZ_PROMOTE(_bz_typename T_expr1::T_numtype, P_numtype2)
    dotWithArgs(const T_expr1& a, P_numtype2 i1, P_numtype2 i2=0,
                P_numtype2 i3=0, P_numtype2 i4=0, P_numtype2 i5=0, P_numtype2 i6=0,
                P_numtype2 i7=0, P_numtype2 i8=0, P_numtype2 i9=0, P_numtype2 i10=0)
    {
        return a[I] * i1 + _bz_meta_vectorDot<loopFlag * N, loopFlag * (I+1)>::dotWithArgs
                                                                                   (a, i2, i3, i4, i5, i6, i7, i8, i9);
    }
};
template<>
class _bz_meta_vectorDot<0,0> {
public:
    template<class T_expr1, class T_expr2>
    static inline _bz_meta_nullOperand f(const T_expr1&, const T_expr2&)
    { return _bz_meta_nullOperand(); }
    template<class T_expr1, class P_numtype2>
    static inline _bz_meta_nullOperand
    dotWithArgs(const T_expr1& a, P_numtype2 i1, P_numtype2 i2=0,
                P_numtype2 i3=0, P_numtype2 i4=0, P_numtype2 i5=0, P_numtype2 i6=0,
                P_numtype2 i7=0, P_numtype2 i8=0, P_numtype2 i9=0, P_numtype2 i10=0)
    {
        return _bz_meta_nullOperand();
    }
};
這段代碼遠比它乍看上去的簡單。_bz_meta_vectorDot類模板使用了一個臨時變量loopFlag來存放每一步循環條件的評估結果，并使用了一個完全特化版作為遞歸終結的條件。需要說明的是，和幾乎所有元程序一樣，這個臨時變量作用發揮于編譯期，并將從運行代碼中優化掉。  
Todd是在Blitz++數值數組庫的主要作者。這個程序庫（以及MTL和POOMA等程序庫）例證了模板元程序可以為我們帶來更加高效的數值計算性能。Todd宣稱Blitz++的性能可以和對應的Fortran程序庫媲美。  
Loki程序庫：活用模板元編程技術的典范  
模板元編程的價值僅僅在于高性能數值計算嗎？不僅如此。Loki程序庫以對泛型模式的開創性工作聞名于C++社群。它很巧妙地利用了模板元編程技術實現了Typelist組件。Typelist是實現Abstract Factory、Visitor等泛型模式不可或缺的基礎設施。  
就像C++標準庫組件std::list提供對一組數值的操作一樣，Typelist可以用來操縱一組類型，其定義非常簡單（摘自Loki程序庫Typelist.h單元）：  
template <class T, class U>
struct Typelist
{
    typedef T Head;
    typedef U Tail;
};
顯然，Typelist沒有任何狀態，也未定義任何操作，其作用只在于攜帶類型信息，它并未打算被實例化，因此，對于Typelist的任何處理都必然發生于編譯期而非運行期。  
Typelist可以被無限擴展，因為模板參數可以是任何類型（包括該模板的其他具現體）。例如：  
Typelist<char, Typelist<int, Typelist<float, NullType> > >   
就是一個包含有char、int、float三種類型的Typelist。  
按照Loki的約定，每一個Typelist都必須以NullType結尾。NullType的作用類似于傳統C字符串的“\0”，它被聲明于Loki程序庫的NullType.h文件中：  
class NullType;  
NullType只有聲明，沒有定義，因為Loki程序庫永遠都不需要創建一個NullType對象。  
讓我們看看IndexOf模板元程序，它可以在一個Typelist中查找給定類型的位置（摘自Loki程序庫的Typelist.h單元）：  
template <class TList, class T>
struct IndexOf;
template <class T>
struct IndexOf<NullType, T>
{
    enum { value = -1 };
};
template <class T, class Tail>
struct IndexOf<Typelist<T, Tail>, T>
{
    enum { value = 0 };
};
template <class Head, class Tail, class T>
struct IndexOf<Typelist<Head, Tail>, T>
{
private:
    enum { temp = IndexOf<Tail, T>::value };
public:
    enum { value = (temp == -1 ? -1 : 1 + temp) };
};
IndexOf提供了一個原始模板和三個局部特化版。算法非常簡單：如果TList（就是一個Typelist）是一個NullType，則value為-1。如果TList的頭部就是T，則value為0。否則將IndexOf施行于TList的尾部和T，并將評估結果置于一個臨時變量temp中。如果temp為-1，則value為-1，否則value為1 + temp。  
為了加深你對Typelist采用的模板元編程技術的認識，我從Loki程序庫剝離出如下代碼，放入一個typelistlite.h文件中：  
// typelistlite.h
// 聲明Nulltype
class NullType;
// Typelist的定義
template <class T, class U>
struct Typelist
{
    typedef T Head;
    typedef U Tail;
};
// IndexOf的定義
// IndexOf原始模板
template <class TList, class T> struct IndexOf;
// 針對NullType的局部特化版
template <class T>
struct IndexOf<NullType, T>
{
    enum { value = -1 };
};
// 針對“TList頭部就是我們要查找的T”的局部特化版
template <class T, class Tail>
struct IndexOf<Typelist<T, Tail>, T>
{
    enum { value = 0 };
};
// 處理TList尾部的局部特化版
template <class Head, class Tail, class T>
struct IndexOf<Typelist<Head, Tail>, T>
{
private:
    enum { temp = IndexOf<Tail, T>::value };
public:
    enum { value = (temp == -1 ? -1 : 1 + temp) };
};
測試程序如下：  
// typelistlite_test.cpp
#include <iostream>
#include "typelistlite.h"
// 自定義類型Royal
class Royal {};
// 定義一個包含有char、int、Royal和float的Typelist
typedef Typelist<char, Typelist<int, Typelist<Royal, Typelist<float, NullType> > > > CIRF;
int main()
{
    std::cout << "IndexOf<CIRF, int>::value = " << IndexOf<CIRF, int>::value << "\n";
    std::cout << "IndexOf<CIRF, Royal>::value = " << IndexOf<CIRF, Royal>::value << "\n";
    std::cout << "IndexOf<CIRF, double>::value = " << IndexOf<CIRF, double>::value << "\n";
}
程序輸出如下：  
IndexOf<CIRF, int>::value = 1
IndexOf<CIRF, Royal>::value = 2
IndexOf<CIRF, double>::value = -1
結語  
模板元編程技術并非都是優點，比方說，模板元程序編譯耗時，帶有模板元程序的程序生成的代碼尺寸要比普通程序的大，而且通常這種程序調試起來也比常規程序困難得多。另外，對于一些程序員來說，以類模板的方式描述算法也許有點抽象。  
編譯耗時的代價換來的是卓越的運行期性能。通常來說，一個有意義的程序的運行次數（或服役時間）總是遠遠超過編譯次數（或編譯時間）。為程序的用戶帶來更好的體驗，或者為性能要求嚴格的數值計算換取更高的性能，值得程序員付出這樣的代價。  
很難想象模板元編程技術會成為每一個普通程序員的日常工具，相反，就像Blitz++和Loki那樣，模板元程序幾乎總是應該被封裝在一個程序庫的內部。對于庫的用戶來說，它應該是透明的。模板元程序可以（也應該）用作常規模板代碼的內核，為關鍵的算法實現更好的性能，或者為特別的目的實現特別的效果。  
模板元編程技術首次正式亮相于Todd Veldhuizen的《Using C++ Template Metaprograms》論文之中。這篇文章首先發表于1995年5月的C++ Report期刊上，后來Stanley Lippman編輯《C++ Gems》一書時又收錄了它。參考文獻中給出了這篇文章的鏈接，它還描述了許多本文沒有描述到的內容。  
David Vandevoorde和Nicolai M. Josuttis合著的《C++ Templates: The Complete Guide》一書花了一整章的篇幅介紹模板元編程技術，它同樣是本文的參考資料并且也應該作為你的補充閱讀材料。
Andrei Alexandrescu的天才著作《Modern C++ Design: Generic Programming and Design Patterns Applied》的第3章Typelists對Typelist有著更為詳盡的描述。
參考文獻和資源
1. David Vandevoorde, Nicolai M. Josuttis, C++ Templates: The Complete Guide, Addison Wesley, 2002.
2.  Andrei Alexandrescu, Modern C++ Design: Generic Programming and Design Patterns Applied, Addison Wesley, 2001.
3. 侯捷 於春景 譯，《C++設計新思維》，華中科技大學出版社，2003。
4. Todd Veldhuizen, Template Metaprograms, http://osl.iu.edu/~tveldhui/papers/Template-Metaprograms/meta-art.html .
5. Todd Veldhuizen, C++ templates as partial evaluation (PEPM99), http://osl.iu.edu/~tveldhui/papers/pepm99/.
6. Erwin Unruh, Prime numbers(Primzahlen - Original), http://www.erwin-unruh.de/primorig.html .
7. Erwin Unruh, Prime numbers(Primzahlen), http://www.erwin-unruh.de/Prim.html .
8. Blitz++, http://www.oonumerics.org/blitz .
9. Loki, http://sourceforge.net/projects/loki-lib .
10. POOMA, http://www.pooma.com.
11. MinGW - Minimalist GNU for Windows, http://sourceforge.net/projects/mingw.
榮耀
2003年10月
南京師范大學
www.royaloo.com

posted on 2009-02-06 20:43 大龍 閱讀(274) 評論(0)  編輯 收藏 引用