novus log

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的感覺？