C++裡面有很多神奇的技術,如果要依令人驚奇的程度列個表,我想Expression Template一定榜上有名。

先來看個例子,假如有個陣列,我們希望將每個元素先平方之後再加上10,在C++我們可以這樣寫:

int a[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
transform(a, a+10, a, SquarePlus10);

其中的 SquarePlus10 是我們在別處定義的函式,或者是其他行為像函式的東西。雖然寫這樣的小東西沒甚麼大不了的,但有時候這些小函式實在不太容易命名,命了名也不見得直接看得出用途,導致閱讀者必須捲動編輯畫面去查看看函式定義。所以很多程式語言都支援匿名函式,也就是在需要用到函式的場合可以隨手捏造一個,不必正經八百的定義函式。底下探討C++中如何模擬這種語法。

首先我們需要一個生成函數的引擎,template很適合這些工作。先建立這個叫做Actor的struct,作用在於提供一個統一的動作介面:

template <class T>
struct Actor {
    Actor(T t) : act(t) {}     int operator()(int arg) const {
        return act(arg);
    }
    T act;
};

接下來我們定義一些基礎的語法元素。其中的 Argument 代表的是這個「隨手函式」的引數,而 Constant 則是函數中固定的值,為求簡化這裡只單純處理int,不過也可以設計成用template吃下任意type。重點在於所有元素都得提供統一的operator()介面。

struct Argument {
    int operator()(int arg) const {
        return arg;
    }
}; struct Constant {
    Constant(int v) : val(v) {}     int operator()(int arg) const {
        return val;
    }     const int val;
}; inline Actor<Constant> Val(int n) {
    return Actor<Constant>(Constant(n));
} const Actor<Argument> arg = Argument();

有了基本元素,接下來就可以設計「文法」。這裡只提供二元運算子。

template <class OP, class E1, class E2>
struct BinaryOperator {
    BinaryOperator(E1 e1, E2 e2) : expr1(e1), expr2(e2) {}     int operator()(int arg) const {
        return OP::Eval(expr1(arg), expr2(arg));
    }     E1 expr1;
    E2 expr2;
}; struct Add {
    static int Eval(int left, int right) {return left + right;}
}; struct Mul {
    static int Eval(int left, int right) {return left * right;}
}; template <class A, class B>
Actor<BinaryOperator<Add, Actor<A>, Actor<B> > >
operator+(Actor<A> a, Actor<B> b) {
    typedef BinaryOperator<Add, Actor<A>, Actor<B> > T;
    return Actor<T>(T(a, b));
} template <class A, class B>
Actor<BinaryOperator<Mul, Actor<A>, Actor<B> > >
operator*(Actor<A> a, Actor<B> b) {
    typedef BinaryOperator<Mul, Actor<A>, Actor<B> > T;
    return Actor<T>(T(a, b));
}

其他二元運算子用同樣的方式即可完成,有興趣者自行補完吧。上面一大串<<>>非常礙眼,其實可以用一些template技術如type generator來簡化,這裡不再介紹。

 


 

有了上面的設施,我們欲將一個陣列每個元素先平方再加10,只要這樣即可:

 

transform(a, a + 10, a, arg * arg + Val(10));

有趣的地方在於 arg * arg + Val(10) 這串運算實際上沒有對資料進行處理,而是「算」出了一個函數,然後將這個函數傳給 transform,其中arg代表此函數的引數。這樣的函數也可以單獨使用

cout << (arg * arg + Val(10)) (5);   // 印出35

Val(10)這樣的數值表示法看起來似乎有點不自然,其實只要在operator接受的type上動點手腳,就可以讓operator自動吃下int(或任意type)然後轉型,最後可寫成

transform(a, a + 10, a, arg * arg + 10);
cout << (arg * arg + 10) (5);   // 印出35

像這種運用template來表現文法結構的技術稱為Expression Template,主要的特點在於程式碼並不真正去執行計算,而是生成內部的表式法,到真正需要的時候才透過生成出來的產物去執行。主要的目的有

1.函式或物件生成器,如上所述。最有名的應用大概是Boost.phoenix,他差不多實作了一個C++子集,甚至包含了if、while、new等等。phoenix允許你用這樣的方式寫函式

for_each(c.begin(), c.end(),
    if_(arg1 > 5) [
        cout << arg1 << " > 5\n"
    ].else_[
        if_(arg1 == 5) [             cout << arg1 << " == 5\n"         ].else_[             cout << arg1 << " < 5\n"         ]
    ]
);


2.在C++底下建立特定用途的子語言,即 Domain specific language,並且可透過標準C++ Compiler編譯。這點就不得不提一下Boost.spirit,透過spirit我們可以直接用C++撰寫BNF規則,而編譯結果會產生一個 LL(K) Parser。

3.Lazy Evaluation。像是矩陣或向量連續相乘、字串連續相加都會產生不必要的暫時物件,即使有返回值優化(RVO)也無法消除

str1 = str2 + str3 + str4;
Norm(vec1 * vec2* vec3);

解決的方法之一是在這些運算式出現的時候不要執行動作,而是紀錄下這個運算結構,等到真正需要值的時候才一次配足空間把答案算出來。線性代數程式庫Blitz++就是用這個方是大幅提升效能,這可能是Expression Template最早期的應用

4.有些讀者可能已經想到,Expression Template「算」出來的東西是函式,和且函式可以彼此互相嵌套,是不是頗有functional language的感覺?

novus 發表在 痞客邦 PIXNET 留言(3) 人氣()


留言列表 (3)

發表留言
  • damody
  • 讓人感到新奇開心的有趣,哈!
    不過想學C++的人愈來愈少的感覺,唉。
  • 因為C++的學習曲線比較陡峭,這也是沒辦法的事

    以教學者的立場,必須在有限時間內傳授最重要的核心知識,而非鑽入無止盡的細節。但教C++不可能不提細節。

    學習者比較在意的是盡快能應用,C++大概很難滿足這種需求。

    novus 於 2009/12/26 14:09 回覆

  • guest
  • 少了template的C++是殘缺不全的,但我覺得沒有必要把許多進階應用加到課程裡面,如type_traits,expression template, CRTP,SFINAE,policy base design這些東西可以留到進階課程(如果有的話)再教,或者只需要稍微秀一下並解釋他們的好處就可以了,有心學習的人自己自然會去找資料吧.

    ps : c++11的lambda expression不錯用,如果支援[](auto x) { return x;}這種寫法就更好了
  • 同意,Stroustrup 建議的 C++ 學習過程就是這樣。

    我最初學的 C++ 和現在已經很不一樣了,和剛出爐的 C++ 11 根本是兩種不同的語言。那時候 template 還只是編譯器的擴充功能,雖然已經有現在 STL 的前身,卻幾乎沒有書本教導要如何去使用這些東西。

    反正即使沒有這些東西,照樣可以寫出完整的程式。有了核心能力後,隨時可以把新觀念、新技術納入工具箱。

    novus 於 2012/03/20 00:14 回覆

  • 顏駿凱
  • 不好意思可,可以請問你我的code出了什麼問題嗎 ?
    我complie都不會過 ... 是寫template的


    #ifndef ARRAY_H
    #define ARRAY_H

    #include <iostream>
    using namespace std ;

    template <class T>
    class Array
    {
    friend ostream &operator<<(ostream &out , const Array &) ;
    friend istream &operator>>(istream &input,Array &) ;

    public :
    Array(int = 10);
    Array(const Array &);
    ~Array() ;

    int getSize() const ;

    Array &operator=(const Array &);
    bool operator==(const Array &) const ;
    bool operator!=(const Array &right) const
    {
    return !(*this == right) ;
    }

    T &operator[](int) ;
    T operator[](int) const ;

    private :
    int size ;
    T *ptr ;
    };


    template <class T>
    Array<T>::Array(int arraySize)
    {
    size = (arraySize > 0 ? arraySize : 10) ;
    ptr = new int [size] ;

    for (int i=0 ; i<size ; i++)
    ptr[i] = 0 ;
    }

    template <class T>
    Array<T>::Array(const Array &arrayToCopy) : size (arrayToCopy.size)
    {
    ptr = new int [size] ;
    for (int i=0 ; i<size ; i++)
    ptr [i] = arrayToCopy.ptr[i] ;
    }

    template <class T>
    Array<T>::~Array()
    {
    delete [] ptr ;
    }

    template <class T>
    int Array<T>::getSize() const
    {
    return size ;
    }

    template <class T>
    Array &Array::operator=(const Array &right)
    {
    if (&right != this)
    {
    if (size != right.size)
    {
    delete [] ptr ;
    size = right.size ;
    ptr = new int [size] ;
    }

    for (int i=0 ; i<size ; i++)
    ptr [i] = right.ptr[i] ;
    }
    return *this ;
    }

    template <class T>
    bool Array<T>::operator==(const Array<T> &right) const
    {
    if (size != right.size)
    return false ;

    for (int i=0 ; i<size ; i++)
    if (ptr[i] != right.ptr[i])
    return false ;

    return true ;
    }

    template <class T>
    T &Array<T>::operator[](int subscript)
    {
    if(subscript <0 || subscript >= size)
    {
    cerr <<"\nError: Subscript " << subscript << " out of range\n" ;
    exit(1) ;
    }

    return ptr[subscript] ;
    }

    template <class T>
    T Array<T>::operator[](int subscript) const
    {
    if (subscript < 0 || subscript >= size)
    {
    cerr << "\nError: Subscript " << subscript << " out of range\n" ;
    exit(1) ;
    }
    return ptr[subscript] ;
    }

    template <class T>
    istream &operator>>(istream &input , Array<T> &a)
    {
    for (int i=0 ; i <a.size ; i++)
    input >> a.ptr[i] ;
    return input ;
    }

    template <class T>
    ostream &operator<<(ostream &output, const Array &a)
    {
    int i ;
    for (i=0 ; i <a.size ; i++)
    {
    output << setw(12) << a.ptr[i] ;
    if ((i+1) % 4 == 0)
    output << endl ;
    }

    if (i%4 != 0)
    output<<endl ;

    return output ;
    }
    #endif

    程式會說

    1>c:\users\hydrogen\desktop\test\test\array.h(67): error C2955: 'Array' : 使用類別 樣板 必須有 樣板 引數清單
    1> c:\users\hydrogen\desktop\test\test\array.h(9) : 請參閱 'Array' 的宣告
    1>c:\users\hydrogen\desktop\test\test\array.h(67): error C2955: 'Array' : 使用類別 樣板 必須有 樣板 引數清單
    1> c:\users\hydrogen\desktop\test\test\array.h(9) : 請參閱 'Array' 的宣告
    1>c:\users\hydrogen\desktop\test\test\array.h(82): error C2244: 'Array<T>::operator =' : 函式定義不符合現有的宣告
    1> c:\users\hydrogen\desktop\test\test\array.h(20) : 請參閱 'Array<T>::operator =' 的宣告
    1> 定義
    1> 'Array &Array::operator =(const Array &)'
    1> 現有宣告
    1> 'Array<T> &Array<T>::operator =(const Array<T> &)'
    1>
    1>建置失敗。

    請問這要怎麼解決 ?
  • 你的問題我沒興趣。

    最起碼先把編譯訊息提示的錯誤改一改吧。

    novus 於 2012/05/15 18:30 回覆