Wilkening-Online Logo

C++ Expression-Templates - Teil 2 - Vertiefung



Von Detlef Wilkening
01.02.2015
Version: 1

Hinweis - die Teile 1-5 dieser Serie entsprechen inhaltlich grob dem Vortrag, den ich am 21.05.2014 auf dem C++ User-Treffen in Düsseldorf gehalten habe. Diese Artikel-Serie ist aber noch umfangreicher und detailierter und die Quelltexte sind viel vollständiger.

1. Wiederholung

In Teil 1 dieser Serie[1] über Expression-Templates haben wir gelernt, was Expression-Templates überhaupt sind, und wie man mit ihnen die Auswertung von Ausdrücken quasi aufschiebt. Dazu haben wir Template-Funktionen und Klassen entwickelt, mit denen wir Ausdrücke in C++ schreiben konnten, die aber die Ausdrücke selber nicht auswerten, sondern Funktions-Objekte mit dem Wissen zur Auswertung zurückgeben. Diese konnten wir dann an Funktionen wie z.B. den STL-Algorithmus "transform" übergeben.

Heute werden wir unser Wissen über Expression-Templates selber und ihre Anwendungen nicht groß vertiefen, sondern uns statt dessen anschauen, welches Problem unsere bisherige Lösung noch hat, und wie wir es beseitigen können. Außerdem werden wir danach noch gleichartige Code-Teile in wiederverwendbare Klassen auszulagern, um unseren Code etwas zu vereinfachen. Und zu guter Letzt werden wir uns dem Thema "Literale" widmen, das wir in Teil 1 noch zurückgestellt hatten.

Gleich vorweg: der Code wird durch die Problem-Beseitigung und die Wiederverwendbarkeit etwas komplizierter, daher die Templates etwas aufwendiger und schwerer zu lesen. Aber im Prinzip bleibt der bisherige Code erhalten, und am Prinzip der Expression-Templates ändert sich auch nichts. Lassen Sie sich also bloß nicht erschrecken, und bleiben Sie locker dabei - nur keine Panik.

2. Problem und Lösung

2.1 Problem

Unsere bishierige Expression-Template Implementation hat leider ein Problem. Schauen wir uns einen kleinen Teil unseres Codes aus Teil 1 nochmal an. Sehen Sie das Problem?

struct Variable
{
   int operator()(int n) const { return n; }
};

Variable x;

template<class Expr> struct Square
{
   Expr expr;
   explicit Square(Expr e) : expr(e) {}
   int operator()(int n) const { n = expr(n); return n*n; }
};

template<class Expr> Square<Expr> square(Expr expr)
{
   return Square<Expr>(expr);
}

In der Praxis könnte die Template-Funktion "square" Probleme bereiten!

Warum?

Nun, diese Funktion ist nicht alleine auf der Welt. Es könnte weitere Square-Funktionen in Ihrem Programm geben, und dann würde unsere Expression-Template Funktion "square" Mit diesen interferieren bzw. kollidieren.

template<class Expr> Square<Expr> square(Expr expr)
{
   return Square<Expr>(expr);
}

double square(double d)
{
   return d*d;
}


square(2.7F);      // => Compiler-Fehler

Unsere Expression-Template Square-Funktion kollidiert hier mit der normalen Square-Funktion.

Werden normale Funktionen mit Template-Funktionen überladen, so greifen die Template-Funktionen nur dann nicht, wenn die Aufruf-Argumente zu den Parametern der normalen Funktionen fast exakt passen - nur noch triviale Wandlungen sind erlaubt. Schon elementare Wandlungen - wie in unserem Beispiel die Wandlung von "float" zu "double" - sind zuviel. Hier geht unsere Template-Funktion vor - und schon haben wir den Salat. Für eine solche einfache direkte Nutzung ist sie eben nicht gedacht.


Nun werden Sie vielleicht sagen, dass Sie nur selten Funktionen "square" nennen, bzw. Sie immer die Möglichkeit haben, die Funktionen anders zu nennen oder in Namespaces zu verschieben. Leider stehen uns diese Optionen in der Praxis nicht immer zur Verfügung.

Schauen Sie sich das nächste Beispiel an. Hier ist keine normale Funktion das Problem, sondern der "Operator +". Normalerweise würde der Konvertierungs-Konstruktor "A(int)" bei den unteren beiden Nutzungen greifen, aber wieder geht hier unsere Expression-Template-Funktion "operator+" vor - und schon haben wir wieder Compiler-Fehler.

template<class LExpr, class RExpr> struct Add
{
   LExpr lexpr;
   RExpr rexpr;
   Add(LExpr le, RExpr re) : lexpr(le), rexpr(re) {}
   int operator()(int n) const { return lexpr(n) + rexpr(n); }
};

template<class LExpr, class RExpr> Add<LExpr, RExpr> operator+(LExpr le, RExpr re)
{
   return Add<LExpr, RExpr>(le, re);
}

class A
{
public:
   A() {}
   A(int) {}
};
A operator+(const A&, const A&) { return A(); }


A a, a1, a2;
a = a1 + a2;       // Okay
a = 1 + a2;        // => Compiler-Fehler
a = a1 + 2;        // => Compiler-Fehler

Bei Expression-Templates - gerade wenn es um DSELs geht - nutzen wir gerne Operatoren, und die können wir nicht umbenennen. Und auch Namespaces sind leider nicht immer eine Lösung. Darum müssen wir uns anders um dieses Problem kümmern.

2.2 Lösung

Die Lösung ist vom Prinzip ganz einfach: die Expression Template-Funktionen dürfen nicht mit den normalen Funktionen interferieren, d.h. sie müssen speziell ausgezeichnet oder markiert werden. Wir müssen die Typen der Expression-Templates also so aufbauen, dass sie schon vom Typ als Expression-Klassen erkannt werden und nicht mit den normalen Funktionen interferieren.

Achtung - im Prinzip ändern wir nichts an den alten Sourcen. Wir bohren nur die Typen etwas auf - markieren sie eindeutig. Leider wird der Code dadurch unleserlicher und damit scheinbar komplizierter - er ist aber im Prinzip noch der alte Code. Lassen Sie sich nicht verwirren.

Zur Markierung nutzen wir einfach eine zusätzliche Expression-Klasse - quasi als Marker-Typ. Unsere bisherigen Expression-Klassen wrappen wir dann in diese. Die Funktions-Signaturen erweiteren wir dann um die Expression-Marker-Klasse - damit greifen sie nur noch bei unseren Expression-Klassen.

Ein kleiner Tipp: wenn Sie mal selber Expression-Templates implementieren, dann sollten Sie vielleicht bei der Entwicklung das Interferenz-Problem einfach ignorieren - und sie erstmal wie in Teil 1 "straight-forward" implementieren. Wenn Sie dann alles fertig haben, dann bohren Sie die Expression-Typen einfach auf.

Expression-Marker-Klasse

Klar ist damit, dass die zusätzliche Expression-Marker-Klasse eine Template-Klasse sein muß, die die eigentliche Expression-Klassen dann als Template-Parameter bekommt:

template<class E> struct Expr
{
   E expr;
   explicit Expr(E e) : expr(e) {}
   int operator()(int n) { return expr(n); }
};

Hinweis - in der Realität heißt die Expression-Marker-Klasse bei mir natürlich "Expression" und nicht "Expr". Ich habe diesen Namen - wie auch einige andere Namen und Template-Parameter-Namen in den folgenden Beispielen - aber gekürzt, damit die Zeilen der Quelltexte nicht zu lang werden und sie daher hier auf der Web-Seite besser lesbar sind.

Variablen-Definition "x"


struct Variable                                // Unveraenderter Code
{
   int operator()(int n) { return n; }
};

// Variable x;                                 // Bisheriger Code

Expr<Variable> x((Variable()));                // Neuer Code

Funktion "square"


template<class E> struct Square                                    // Unveraenderter Code
{
   E expr;
   explicit Square(E e) : expr(e) {}
   int operator()(int n) { int x = expr(n); return x*x; }
};

// template<class E> Square<E> square(E e)                         // Bisheriger Code
// {
//    return Square<E>(e);
// }

template<class E> Expr<Square<E>> square(Expr<E> e)                // Neuer Code
{
   return Expr<Square<E>>(Square<E>(e.expr));
}

Operator +

Die Änderung des "Operators +" sind dann analog zur Funktion "square", nur dass diesmal zwei Parameter vom Wrappen betroffen sind.

template<class LE, class RE> struct Add                               // Unveraenderter Code
{
   LE lexpr;
   RE rexpr;
   explicit Add(LE le, RE re) : lexpr(le), rexpr(re) {}
   int operator()(int n) { return lexpr(n) + rexpr(n); }
};

// template<class LE, class RE> Add<LE, RE> operator+(LE le, RE re)   // Bisheriger Code
// {
//    return Add<LE, RE>(le, re);
// }

template<class LE, class RE> Expr<Add<LE, RE>> operator+(Expr<LE> le, Expr<RE> re)    // Neu
{
   return Expr<Add<LE, RE>>(Add<LE, RE>(le.expr, re.expr));
}

Die Probleme sind weg

Mit den neuen Expression-Funktionen, die nur noch auf Expression-Marker-Klassen ansprechen, ist die gegenseitige Interferenz beseitigt. Unsere Expression-Funktionen matchen nur noch unsere Expression-Typen:

template<class E> Expr<Square<E>> square(Expr<E> e)
{
   return Expr<Square<E>>(Square<E>(e.expr));
}

double square(double d)
{
   return d*d;
}


square(2.7F);      // => Nimmt jetzt wie gewuenscht "square(double)"



template<class LE, class RE> Expr<Add<LE, RE>> operator+(Expr<LE> le, Expr<RE> re)
{
   return Expr<Add<LE, RE>>(Add<LE, RE>(le.expr, re.expr));
}

class A
{
public:
   A() {}
   A(int) {}
};
A operator+(const A&, const A&) { return A(); }


A a, a1, a2;
a = a1 + a2;       // Schon vorher okay
a = 1 + a2;        // => Nimmt jetzt wie gewuenscht "operator+(const A&, const A&)"
a = a1 + 2;        // => Nimmt jetzt wie gewuenscht "operator+(const A&, const A&)"

2.3 Ausrollen

Wir haben mit der Expression-Marker-Klasse nun eine "einfache" Lösung. Jetzt müssen wir sie nur noch auf den gesamten Quelltext ausrollen…

Und vorsichtshalber nochmal der Hinweis: selbst wenn der Code jetzt doch etwas komplizierter aussieht - im Prinzip ist es immer noch der alte Code. Also nur keine Panik

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

//---

ostream& operator<<(ostream& out, const vector<int>& v)
{
   for_each(cbegin(v), cend(v), [&out](int n){ out << n << ' '; });
   return out;
}

//---

template<class E> struct Expr
{
   E expr;
   explicit Expr(E e) : expr(e) {}
   int operator()(int n) { return expr(n); }
};

//---

struct Variable
{
   int operator()(int n) const { return n; }
};

Expr<Variable> x((Variable()));

//---

struct Constant
{
   const int value;
   explicit Constant(int n) : value(n) {}
   int operator()(int) const { return value; }
};

Expr<Constant> c0(Constant(0));
Expr<Constant> c1(Constant(1));
Expr<Constant> c2(Constant(2));
Expr<Constant> c3(Constant(3));
Expr<Constant> c4(Constant(4));
Expr<Constant> c5(Constant(5));

//---

template<class Expr> struct Square
{
   Expr expr;
   explicit Square(Expr e) : expr(e) {}
   int operator()(int n) const { n = expr(n); return n*n; }
};

template<class E> Expr<Square<E>> square(Expr<E> e)
{
   return Expr<Square<E>>(Square<E>(e.expr));
}

//---

template<class Expr> struct Neg
{
   Expr expr;
   explicit Neg(Expr e) : expr(e) {}
   int operator()(int n) const { return -expr(n); }
};

template<class E> Expr<Neg<E>> operator-(Expr<E> e)
{
   return Expr<Neg<E>>(Neg<E>(e.expr));
}

//---

template<class LExpr, class RExpr> struct Add
{
   LExpr lexpr;
   RExpr rexpr;
   Add(LExpr le, RExpr re) : lexpr(le), rexpr(re) {}
   int operator()(int n) const { return lexpr(n) + rexpr(n); }
};

template<class LE, class RE> Expr<Add<LE, RE>> operator+(Expr<LE> le, Expr<RE> re)
{
   return Expr<Add<LE, RE>>(Add<LE, RE>(le.expr, re.expr));
}

//---

template<class LExpr, class RExpr> struct Sub
{
   LExpr lexpr;
   RExpr rexpr;
   Sub(LExpr le, RExpr re) : lexpr(le), rexpr(re) {}
   int operator()(int n) const { return lexpr(n) - rexpr(n); }
};

template<class LE, class RE> Expr<Sub<LE, RE>> operator-(Expr<LE> le, Expr<RE> re)
{
   return Expr<Sub<LE, RE>>(Sub<LE, RE>(le.expr, re.expr));
}

//---

template<class LExpr, class RExpr> struct Mul
{
   LExpr lexpr;
   RExpr rexpr;
   Mul(LExpr le, RExpr re) : lexpr(le), rexpr(re) {}
   int operator()(int n) const { return lexpr(n) * rexpr(n); }
};

template<class LE, class RE> Expr<Mul<LE, RE>> operator*(Expr<LE> le, Expr<RE> re)
{
   return Expr<Mul<LE, RE>>(Mul<LE, RE>(le.expr, re.expr));
}

//---

template<class LExpr, class RExpr> struct Div
{
   LExpr lexpr;
   RExpr rexpr;
   Div(LExpr le, RExpr re) : lexpr(le), rexpr(re) {}
   int operator()(int n) const { return lexpr(n) / rexpr(n); }  // Achtung: '/0' undefiniert
};

template<class LE, class RE> Expr<Div<LE, RE>> operator/(Expr<LE> le, Expr<RE> re)
{
   return Expr<Div<LE, RE>>(Div<LE, RE>(le.expr, re.expr));
}

//---

template<class LExpr, class RExpr> struct Mod
{
   LExpr lexpr;
   RExpr rexpr;
   Mod(LExpr le, RExpr re) : lexpr(le), rexpr(re) {}
   int operator()(int n) const { return lexpr(n) % rexpr(n); }
};

template<class LE, class RE> Expr<Mod<LE, RE>> operator%(Expr<LE> le, Expr<RE> re)
{
   return Expr<Mod<LE, RE>>(Mod<LE, RE>(le.expr, re.expr));
}

//---

template<class Expr> void execute(const char* msg, Expr expr)
{
   vector<int> v{ 1, 2, 3, 4, 5 };

   transform(cbegin(v), cend(v), begin(v), expr);

   cout << msg << v << endl;
}

//---

int main()
{
   execute("x                ->  ", x);
   execute("x+c1             ->  ", x+c1);
   execute("x-c2             ->  ", x-c2);
   execute("x*c3             ->  ", x*c3);
   execute("x/c2             ->  ", x/c2);
   execute("x%c2             ->  ", x%c2);
   execute("x%c3             ->  ", x%c3);
   execute("c5- -x           ->  ", c5- -x);
   execute("x+square(x*c2)   ->  ", x+square(x*c2));
   execute("x+c3*x           ->  ", x+c3*x);
   execute("(x+c4)*x         ->  ", (x+c4)*x);
   execute("square(x+c2)     ->  ", square(x+c2));
   execute("square(x+c2)%c5  ->  ", square(x+c2)%c5);
}


Ausgabe:

x                ->  1 2 3 4 5
x+c1             ->  2 3 4 5 6
x-c2             ->  -1 0 1 2 3
x*c3             ->  3 6 9 12 15
x/c2             ->  0 1 1 2 2
x%c2             ->  1 0 1 0 1
x%c3             ->  1 2 0 1 2
c5- -x           ->  6 7 8 9 10
x+square(x*c2)   ->  5 18 39 68 105
x+c3*x           ->  4 8 12 16 20
(x+c4)*x         ->  5 12 21 32 45
square(x+c2)     ->  9 16 25 36 49
square(x+c2)%c5  ->  4 1 0 1 4

3. Vereinfachung

Wenn wir mal genau hinschauen, dann sehen wir, dass sich unsere Expression-Klassen jetzt sehr ähneln:

// Zwei Beispiele "Square" und "Neg" fuer unaere Operationen:

template<class E> struct Square
{
   E expr;
   explicit Square(E e) : expr(e) {}
   int operator()(int n) { int x = expr(n); return x*x; }
};

template<class E> struct Neg
{
   E expr;
   explicit Neg(E e) : expr(e) {}
   int operator()(int n) { return -expr(n); }
};


// Zwei Beispiele "Add" und "Sub" fuer binaere Operationen:

template<class LE, class RE> struct Add
{
   LE lexpr;
   RE rexpr;
   explicit Add(LE le, RE re) : lexpr(le), rexpr(re) {}
   int operator()(int n) { return lexpr(n) + rexpr(n); }
};

template<class LE, class RE> struct Sub
{
   LE lexpr;
   RE rexpr;
   explicit Sub(LE le, RE re) : lexpr(le), rexpr(re) {}
   int operator()(int n) { return lexpr(n) - rexpr(n); }
};

Wir sehen - abgesehen vom Namen unterscheiden sich die Expressions nur durch den Inhalt des Operators (). Alles andere ist gleich - wenn wir mal von der unterschiedlichen Anzahl an Parametern und Attributen zwischen den unären und binären Expressions absehen. Alles andere können wir also in eine Art Bibliothek auslagern - nur leicht unterschiedlich für unäre und binäre Expressions.

3.1 Unäre Expresions

Für die unären Expression erzeugen wir eine Klasse "UnaryExpr", die neben der eigentlichen Expression noch die auszuführende Operation in Form einer Klasse "Op" mit Klassen-Funktion "apply" bekommt.

Im Prinzip ist diese Expression-Klasse also ein Ersatz aller unären Expression-Klassen, die mit der Expression und der Aktion gefüttert wird. Die Expression-Funktionen erzeugen dann nur noch diese neuen Klassen:

template<class Op, class E> struct UnaryExpr        // Zusaetzlich "Op"
{
   E expr;

   explicit UnaryExpr(E e) : expr(e) {}

   int operator()(int n)
   {
      return Op::apply(expr(n));                    // Verallgemeinert mit "Op::apply"
   }
};

Vergleichen wir nun wieder den alten Code und den neuen Code miteinander:

// template<class E> struct Square                             // Bisheriger Code
// {
//    E expr;
//    explicit Square(E e) : expr(e) {}
//    int operator()(int n) { int x = expr(n); return x*x; }
// };

struct Square                                                  // Neuer Code
{
   static int apply(int n) { return n*n; }
};


// template<class E> Expr<Square<E>> square(Expr<E> e)                  // Bisheriger Code
// {
//    return Expr<Square<E>>(Square<E>(e.expr));
// }

template<class E> Expr<UnaryExpr<Square, E>> square(Expr<E> e)          // Neuer Code
{
   return Expr<UnaryExpr<Square, E>>(UnaryExpr<Square, E>(e.expr));
}

Die Expression-Funktion - hier z.B. "square" - ist ein bißchen komplizierter geworden, dafür ist die Klasse die die eigentliche "Operation" enthält - hier z.B. "Square" - viel einfacher geworden. Unterm Strich also ein Gewinn.

3.2 Binäre Expresions

Für binäre Expressions sieht die Vereinfachung analog aus:

template<class Op, class LE, class RE> struct BinaryExpr                 // Zusaetzlich "Op"
{
   LE lexpr;
   RE rexpr;

   explicit BinaryExpr(LE le, RE re) : lexpr(le), rexpr(re) {}

   int operator()(int n)
   {
      return Op::apply(lexpr(n), rexpr(n));               // Verallgemeinert mit "Op::apply"
   }
};


// template<class LE, class RE> struct Add                           // Bisheriger Code
// {
//    LE lexpr;
//    RE rexpr;
//    explicit Add(LE le, RE re) : lexpr(le), rexpr(re) {}
//    int operator()(int n) { return lexpr(n) + rexpr(n); }
// };

struct Add                                                           // Neuer Code
{
   static int apply(int n1, int n2) { return n1+n2; }
};



// Bisheriger Code
// template<class LE, class RE> Expr<Add<LE, RE>> operator+(Expr<LE> le, Expr<RE> re)
// {
//    return Expr<Add<LE, RE>>(Add<LE, RE>(le.expr, re.expr));
// }

// Neuer Code
template<class LE, class RE> Expr<BinaryExpr<Add, LE, RE>> operator+(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Add, LE, RE>>(BinaryExpr<Add, LE, RE>(le.expr, re.expr));
}

3.3 Ausrollen

Und wieder gilt: ausrollen, ausrollen, ausrollen...

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

//---

ostream& operator<<(ostream& out, const vector<int>& v)
{
   for_each(cbegin(v), cend(v), [&out](int n){ out << n << ' '; });
   return out;
}

//---

template<class E> struct Expr
{
   E expr;
   explicit Expr(E e) : expr(e) {}
   int operator()(int n) { return expr(n); }
};

template<class Op, class E> struct UnaryExpr
{
   E expr;

   explicit UnaryExpr(E e) : expr(e) {}

   int operator()(int n)
   {
      return Op::apply(expr(n));
   }
};

template<class Op, class LE, class RE> struct BinaryExpr
{
   LE lexpr;
   RE rexpr;

   explicit BinaryExpr(LE le, RE re) : lexpr(le), rexpr(re) {}

   int operator()(int n)
   {
      return Op::apply(lexpr(n), rexpr(n));
   }
};

//---

struct Variable
{
   int operator()(int n) const { return n; }
};

Expr<Variable> x((Variable()));

//---

struct Constant
{
   const int value;
   explicit Constant(int n) : value(n) {}
   int operator()(int) const { return value; }
};

Expr<Constant> c0(Constant(0));
Expr<Constant> c1(Constant(1));
Expr<Constant> c2(Constant(2));
Expr<Constant> c3(Constant(3));
Expr<Constant> c4(Constant(4));
Expr<Constant> c5(Constant(5));

//---

struct Square
{
   static int apply(int n) { return n*n; }
};

template<class E> Expr<UnaryExpr<Square, E>> square(Expr<E> e)
{
   return Expr<UnaryExpr<Square, E>>(UnaryExpr<Square, E>(e.expr));
}

//---

struct Neg
{
   static int apply(int n) { return -n; }
};

template<class E> Expr<UnaryExpr<Neg, E>> operator-(Expr<E> e)
{
   return Expr<UnaryExpr<Neg, E>>(UnaryExpr<Neg, E>(e.expr));
}

//---

struct Add
{
   static int apply(int n1, int n2) { return n1+n2; }
};

template<class LE, class RE> Expr<BinaryExpr<Add, LE, RE>> operator+(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Add, LE, RE>>(BinaryExpr<Add, LE, RE>(le.expr, re.expr));
}

//---

struct Sub
{
   static int apply(int n1, int n2) { return n1-n2; }
};

template<class LE, class RE> Expr<BinaryExpr<Sub, LE, RE>> operator-(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Sub, LE, RE>>(BinaryExpr<Sub, LE, RE>(le.expr, re.expr));
}

//---

struct Mul
{
   static int apply(int n1, int n2) { return n1*n2; }
};

template<class LE, class RE> Expr<BinaryExpr<Mul, LE, RE>> operator*(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Mul, LE, RE>>(BinaryExpr<Mul, LE, RE>(le.expr, re.expr));
}

//---

struct Div
{
   static int apply(int n1, int n2) { return n1/n2; }    // Achtung: '/0' undefiniert
};

template<class LE, class RE> Expr<BinaryExpr<Div, LE, RE>> operator/(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Div, LE, RE>>(BinaryExpr<Div, LE, RE>(le.expr, re.expr));
}

//---

struct Mod
{
   static int apply(int n1, int n2) { return n1%n2; }
};

template<class LE, class RE> Expr<BinaryExpr<Mod, LE, RE>> operator%(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Mod, LE, RE>>(BinaryExpr<Mod, LE, RE>(le.expr, re.expr));
}

//---

template<class Expr> void execute(const char* msg, Expr expr)
{
   vector<int> v{ 1, 2, 3, 4, 5 };

   transform(cbegin(v), cend(v), begin(v), expr);

   cout << msg << v << endl;
}

//---

int main()
{
   execute("x                ->  ", x);
   execute("x+c1             ->  ", x+c1);
   execute("x-c2             ->  ", x-c2);
   execute("x*c3             ->  ", x*c3);
   execute("x/c2             ->  ", x/c2);
   execute("x%c2             ->  ", x%c2);
   execute("x%c3             ->  ", x%c3);
   execute("c5- -x           ->  ", c5- -x);
   execute("x+square(x*c2)   ->  ", x+square(x*c2));
   execute("x+c3*x           ->  ", x+c3*x);
   execute("(x+c4)*x         ->  ", (x+c4)*x);
   execute("square(x+c2)     ->  ", square(x+c2));
   execute("square(x+c2)%c5  ->  ", square(x+c2)%c5);
}


Ausgabe:

x                ->  1 2 3 4 5
x+c1             ->  2 3 4 5 6
x-c2             ->  -1 0 1 2 3
x*c3             ->  3 6 9 12 15
x/c2             ->  0 1 1 2 2
x%c2             ->  1 0 1 0 1
x%c3             ->  1 2 0 1 2
c5- -x           ->  6 7 8 9 10
x+square(x*c2)   ->  5 18 39 68 105
x+c3*x           ->  4 8 12 16 20
(x+c4)*x         ->  5 12 21 32 45
square(x+c2)     ->  9 16 25 36 49
square(x+c2)%c5  ->  4 1 0 1 4

Hinweis - es ist okay, wenn Sie die Vereinfachung am Anfang nicht als solche empfinden. Template-Code ist nie wirklich einfach, und von daher wirken diese Templates schon recht abschreckend. Aber auch hier gilt wiedermal der Hinweis: im Prinzip ist es der alte Code. Also keine Panik.

4. Literale

Nachdem unsere Expressions nun "alltags-tauglich" geworden sind, kommen wir endlich zum Thema "Literale":

Statt Konstanten zu benutzen:

Expr<Constant> c2(Constant(2));
Expr<Constant> c3(Constant(3));

transform(cbegin(v), cend(v), begin(v), c3+x+c2);

würden wir lieber direkt Literale in unsere Ausdrücke schreiben:

transform(cbegin(v), cend(v), begin(v), 2+x+3);

4.1 Problem

Das Problem ist natürlich, dass Literale wie "2" oder "3" keine Expressions sind. Daher benötigen wir hierzu eine benutzerdefinierte Wandlung - in unserem Beispiel eine von einem "int" zu einem "Expr<Literal>".

template<class E> struct Expr                             // Bisheriger Code
{
   E expr;
   /*explicit*/ Expr(E e) : expr(e) {}                    // Achtung - nicht mehr "explizit"
   int operator()(int n) { return expr(n); }
};

struct Literal                                            // Neuer Code
{
   const int value;
   Literal(int n) : value(n) {}
   int operator()(int) const { return value; }
};

template<class LE, class RE> Expr<BinaryExpr<Add, LE, RE>> operator+(Expr<LE> le, Expr<RE> re);


transform(cbegin(v), cend(v), begin(v), x+3);    // Compiler-Fehler - keine implizite Wandlung
                                                 // von "int" => "Expr<Literal>" vorhanden

Leider besteht die Wandlung von "int" zu einem "Expr<Literal>" aus zwei benutzer-definierten Wandlungen:
  1. "int => Literal" mit dem non-expliziten Konstruktor "Literal(int)"
  2. "Literal => Expr<Literal>" mit dem nun non-expliziten Konstruktor "Expr(E)"
Selbst wenn der "Expr(E)" Konstruktor nun nicht mehr "explizit" ist - der Compiler darf pro Funktions-Argument nur max. eine benutzer-definierte Wandlung vornehmen - und dies hier sind zwei. Die Wandlung von "int" zu einem "Expr<Literal>" kann daher nicht implizit vom Compiler ausgeführt werden. Daher erhalten wir völlig zurecht einen Compiler-Fehler.

Eine wirklich einfache, schöne und gut funktionierende Lösung kenne ich leider nicht. Statt dessen kann ich nur 2 Lösungen anbieten, die entweder dem Programmierer oder dem Benutzer etwas mehr Arbeit machen: Wir wollen uns beide Lösungen anschauen.

4.2 Überladen

Um nicht auf eine implizite Konvertierungen angewiesen zu sein, müssen wir den Operator "+" entsprechend überladen und die notwendigen Funktionen zur Verfügung stellen. Hierfür gibt es zwei Möglichkeiten - dargestellt am Beispiel des Operators "+":

... operator+(Expr<LE> le, Literal r)
... operator+(Expr<LE> le, int r)

Um die Vor- bzw. Nachteil der jeweiligen Lösung beurteilen zu können, setzen wir sie mal beispielhaft für die Funktion "square" und den Operator "+" um. Achtung - beim Operator "+" müssen natürlich zwei weitere Operatoren erstellt werden, da das Problem sowohl für den ersten als auch den zweiten Parameter vorhanden ist.

Lösung 1: "Literal" in der Schnittstelle

Zum Code gibt es eigentlich nicht viel zu sagen:

struct Literal                 // Wie Klasse "Constant" - nur mit implizitem Int-Konstruktor
{
   const int value;
   Literal(int n) : value(n) {}
   int operator()(int) const { return value; }
};


struct Square
{
   static int apply(int n) { return n*n; }
};

template<class E> Expr<UnaryExpr<Square, E>> square(Expr<E> e)
{
   return Expr<UnaryExpr<Square, E>>(UnaryExpr<Square, E>(e.expr));
}

Expr<UnaryExpr<Square, Literal>> square(Literal l)
{
   return Expr<UnaryExpr<Square, Literal>>(UnaryExpr<Square, Literal>(l));
}


struct Add
{
   static int apply(int n1, int n2) { return n1+n2; }
};

template<class LE, class RE> Expr<BinaryExpr<Add, LE, RE>> operator+(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Add, LE, RE>>(BinaryExpr<Add, LE, RE>(le.expr, re.expr));
}

template<class RE> Expr<BinaryExpr<Add, Literal, RE>> operator+(Literal l, Expr<RE> re)
{
   return Expr<BinaryExpr<Add, Literal, RE>>(BinaryExpr<Add, Literal, RE>(l, re.expr));
}

template<class LE> Expr<BinaryExpr<Add, LE, Literal>> operator+(Expr<LE> le, Literal r)
{
   return Expr<BinaryExpr<Add, LE, Literal>>(BinaryExpr<Add, LE, Literal>(le.expr, r));
}


int main()
{
   execute("x+12             ->  ", x+12);
   execute("21+x             ->  ", 21+x);
   execute("square(3)        ->  ", square(3));
}


Ausgabe:

x+12             ->  13 14 15 16 17
21+x             ->  22 23 24 25 26
square(3)        ->  9 9 9 9 9


Lösung 2: "int" in der Schnittstelle

Auch hier ist der Code ziemlich selbsterklärend:

struct Value                                         // Ehemals Klasse "Constant"
{
   const int value;
   explicit Value(int n) : value(n) {}
   int operator()(int) const { return value; }
};

typedef Value Constant;
typedef Value Literal;


struct Square
{
   static int apply(int n) { return n*n; }
};

template<class E> Expr<UnaryExpr<Square, E>> square(Expr<E> e)
{
   return Expr<UnaryExpr<Square, E>>(UnaryExpr<Square, E>(e.expr));
}

Expr<UnaryExpr<Square, Literal>> square(int n)
{
   return Expr<UnaryExpr<Square, Literal>>(UnaryExpr<Square, Literal>(Literal(n)));
}


struct Add
{
   static int apply(int n1, int n2) { return n1+n2; }
};

template<class LE, class RE> Expr<BinaryExpr<Add, LE, RE>> operator+(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Add, LE, RE>>(BinaryExpr<Add, LE, RE>(le.expr, re.expr));
}

template<class RE> Expr<BinaryExpr<Add, Literal, RE>> operator+(int l, Expr<RE> re)
{
   return Expr<BinaryExpr<Add, Literal, RE>>(BinaryExpr<Add, Literal, RE>(Literal(l), re.expr));
}

template<class LE> Expr<BinaryExpr<Add, LE, Literal>> operator+(Expr<LE> le, int r)
{
   return Expr<BinaryExpr<Add, LE, Literal>>(BinaryExpr<Add, LE, Literal>(le.expr, Literal(r)));
}


int main()
{
   execute("x+12             ->  ", x+12);
   execute("21+x             ->  ", 21+x);
   execute("square(3)        ->  ", square(3));
}


Ausgabe:

x+12             ->  13 14 15 16 17
21+x             ->  22 23 24 25 26
square(3)        ->  9 9 9 9 9


Vergleich

Prinzipiell sind beide Lösungen identisch - ich bevorzuge aber Lösung 1 mit "Literal" in der Schnittstelle.

4.3 Benutzer-Definierte Literale

Eine ganz andere Möglichkeit in unserem Expression-Code Literale zu unterstützen bietet sich seit C++11 an: benutzer-definierte Literale[2]. Seit C++11 kann man in C++ eigene Suffixe definieren, die dann eigene compilezeit-konstante Literal-Typen erzeugen.

Der Umbau ist ziemlich einfach - benötigt aber einen C++11 Compiler. Zuerst müssen wir sowohl den Konstruktor von "Expr" und "Constant" "constexpr" machen. Danach definieren wir z.B. das Suffix "_expr", und schon können wir in "main" in unseren Ausdrücken alle Konstanten durch Expr-Literale ersetzen. Fertig!

template<class E> struct Expr
{
   E expr;
   constexpr explicit Expr(E e) : expr(e) {}
   int operator()(int n) { return expr(n); }
};


struct Constant
{
   const int value;
   constexpr explicit Constant(int n) : value(n) {}
   int operator()(int) const { return value; }
};


constexpr Expr<Constant> operator"" _expr(unsigned long long n)
{
   return Expr<Constant>(Constant(static_cast<int>(n)));
}


int main()
{
   execute("x                ->  ", x);
   execute("x+1              ->  ", x + 1_expr);
   execute("x-2              ->  ", x - 2_expr);
   execute("x*3              ->  ", x*3_expr);
   execute("x/2              ->  ", x / 2_expr);
   execute("x%2              ->  ", x%2_expr);
   execute("x%3              ->  ", x%3_expr);
   execute("5- -x            ->  ", 5_expr - -x);
   execute("x+12             ->  ", x + 12_expr);
   execute("21+x             ->  ", 21_expr + x);
   execute("square(3)        ->  ", square(3_expr));
   execute("x+square(x*2)    ->  ", x + square(x*2_expr));
   execute("x+3*x            ->  ", x + 3_expr*x);
   execute("(x+4)*x          ->  ", (x + 4_expr)*x);
   execute("square(x+2)      ->  ", square(x + 2_expr));
   execute("square(x+2)%5    ->  ", square(x + 2_expr) % 5_expr);
}


Ausgabe:

x                ->  1 2 3 4 5
x+1              ->  2 3 4 5 6
x-2              ->  -1 0 1 2 3
x*3              ->  3 6 9 12 15
x/2              ->  0 1 1 2 2
x%2              ->  1 0 1 0 1
x%3              ->  1 2 0 1 2
5- -x            ->  6 7 8 9 10
x+12             ->  13 14 15 16 17
21+x             ->  22 23 24 25 26
square(3)        ->  9 9 9 9 9
x+square(x*2)    ->  5 18 39 68 105
x+3*x            ->  4 8 12 16 20
(x+4)*x          ->  5 12 21 32 45
square(x+2)      ->  9 16 25 36 49
square(x+2)%5    ->  4 1 0 1 4

4.4 Fazit Literale

So hübsch auch die Nutzung von benutzer-definierten Literalen ist, in der Praxis möchte ich sie den Benutzern nicht zumuten. Für mich als Programmierer sind sie schön einfach und schnell implementiert: nur zwei zusätzliche "constexpr" und einen neuen überladenen Operator - und fertig. Aber für den Benutzer ist die Anwendung mit "_expr" nicht wirklich intuitiv und hilfreich.

Von daher bleibt uns nur, in den sauren Apfel zu beißen, und alle Funktionen und Operatoren entsprechend mit "Literal"-Parametern zu überladen. Es tut mir leid, aber manchmal sind die Lösungen zwar trivial, aber doch viel Schreibarbeit - dies scheint so ein Fall zu sein. Wir werden noch eine ähnliche Situation in Teil 3 der Expression-Serie[3] erleben, wenn wir unser eigenes "bind" implementieren.

4.5 Ausrollen

Damit Sie einen wirklich vollständigen Eindruck von unserer bisherigen Arbeit haben - hier nochmal der komplette Quelltext mit allen überladenen Funktionen und Operatoren für die Lösung 2 mit den "Literal"-Parametern.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

//---

ostream& operator<<(ostream& out, const vector<int>& v)
{
   for_each(cbegin(v), cend(v), [&out](int n){ out << n << ' '; });
   return out;
}

//---

template<class E> struct Expr
{
   E expr;
   explicit Expr(E e) : expr(e) {}
   int operator()(int n) { return expr(n); }
};

template<class Op, class E> struct UnaryExpr
{
   E expr;

   explicit UnaryExpr(E e) : expr(e) {}

   int operator()(int n)
   {
      return Op::apply(expr(n));
   }
};

template<class Op, class LE, class RE> struct BinaryExpr
{
   LE lexpr;
   RE rexpr;

   explicit BinaryExpr(LE le, RE re) : lexpr(le), rexpr(re) {}

   int operator()(int n)
   {
      return Op::apply(lexpr(n), rexpr(n));
   }
};

//---

struct Variable
{
   int operator()(int n) const { return n; }
};

Expr<Variable> x((Variable()));

//---

struct Constant
{
   const int value;
   explicit Constant(int n) : value(n) {}
   int operator()(int) const { return value; }
};

Expr<Constant> c0(Constant(0));
Expr<Constant> c1(Constant(1));
Expr<Constant> c2(Constant(2));
Expr<Constant> c3(Constant(3));
Expr<Constant> c4(Constant(4));
Expr<Constant> c5(Constant(5));

//---

struct Literal
{
   const int value;
   Literal(int n) : value(n) {}
   int operator()(int) const { return value; }
};

//---

struct Square
{
   static int apply(int n) { return n*n; }
};

template<class E> Expr<UnaryExpr<Square, E>> square(Expr<E> e)
{
   return Expr<UnaryExpr<Square, E>>(UnaryExpr<Square, E>(e.expr));
}

Expr<UnaryExpr<Square, Literal>> square(Literal l)
{
   return Expr<UnaryExpr<Square, Literal>>(UnaryExpr<Square, Literal>(l));
}

//---

struct Neg
{
   static int apply(int n) { return -n; }
};

template<class E> Expr<UnaryExpr<Neg, E>> operator-(Expr<E> e)
{
   return Expr<UnaryExpr<Neg, E>>(UnaryExpr<Neg, E>(e.expr));
}

Expr<UnaryExpr<Neg, Literal>> operator-(Literal l)
{
   return Expr<UnaryExpr<Neg, Literal>>(UnaryExpr<Neg, Literal>(l));
}

//---

struct Add
{
   static int apply(int n1, int n2) { return n1+n2; }
};

template<class LE, class RE> Expr<BinaryExpr<Add, LE, RE>> operator+(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Add, LE, RE>>(BinaryExpr<Add, LE, RE>(le.expr, re.expr));
}

template<class RE> Expr<BinaryExpr<Add, Literal, RE>> operator+(Literal l, Expr<RE> re)
{
   return Expr<BinaryExpr<Add, Literal, RE>>(BinaryExpr<Add, Literal, RE>(l, re.expr));
}

template<class LE> Expr<BinaryExpr<Add, LE, Literal>> operator+(Expr<LE> le, Literal r)
{
   return Expr<BinaryExpr<Add, LE, Literal>>(BinaryExpr<Add, LE, Literal>(le.expr, r));
}

//---

struct Sub
{
   static int apply(int n1, int n2) { return n1-n2; }
};

template<class LE, class RE> Expr<BinaryExpr<Sub, LE, RE>> operator-(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Sub, LE, RE>>(BinaryExpr<Sub, LE, RE>(le.expr, re.expr));
}

template<class RE> Expr<BinaryExpr<Sub, Literal, RE>> operator-(Literal l, Expr<RE> re)
{
   return Expr<BinaryExpr<Sub, Literal, RE>>(BinaryExpr<Sub, Literal, RE>(l, re.expr));
}

template<class LE> Expr<BinaryExpr<Sub, LE, Literal>> operator-(Expr<LE> le, Literal r)
{
   return Expr<BinaryExpr<Sub, LE, Literal>>(BinaryExpr<Sub, LE, Literal>(le.expr, r));
}

//---

struct Mul
{
   static int apply(int n1, int n2) { return n1*n2; }
};

template<class LE, class RE> Expr<BinaryExpr<Mul, LE, RE>> operator*(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Mul, LE, RE>>(BinaryExpr<Mul, LE, RE>(le.expr, re.expr));
}

template<class RE> Expr<BinaryExpr<Mul, Literal, RE>> operator*(Literal l, Expr<RE> re)
{
   return Expr<BinaryExpr<Mul, Literal, RE>>(BinaryExpr<Mul, Literal, RE>(l, re.expr));
}

template<class LE> Expr<BinaryExpr<Mul, LE, Literal>> operator*(Expr<LE> le, Literal r)
{
   return Expr<BinaryExpr<Mul, LE, Literal>>(BinaryExpr<Mul, LE, Literal>(le.expr, r));
}

//---

struct Div
{
   static int apply(int n1, int n2) { return n1/n2; }    // Achtung: '/0' undefiniert
};

template<class LE, class RE> Expr<BinaryExpr<Div, LE, RE>> operator/(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Div, LE, RE>>(BinaryExpr<Div, LE, RE>(le.expr, re.expr));
}

template<class RE> Expr<BinaryExpr<Div, Literal, RE>> operator/(Literal l, Expr<RE> re)
{
   return Expr<BinaryExpr<Div, Literal, RE>>(BinaryExpr<Div, Literal, RE>(l, re.expr));
}

template<class LE> Expr<BinaryExpr<Div, LE, Literal>> operator/(Expr<LE> le, Literal r)
{
   return Expr<BinaryExpr<Div, LE, Literal>>(BinaryExpr<Div, LE, Literal>(le.expr, r));
}

//---

struct Mod
{
   static int apply(int n1, int n2) { return n1%n2; }
};

template<class LE, class RE> Expr<BinaryExpr<Mod, LE, RE>> operator%(Expr<LE> le, Expr<RE> re)
{
   return Expr<BinaryExpr<Mod, LE, RE>>(BinaryExpr<Mod, LE, RE>(le.expr, re.expr));
}

template<class RE> Expr<BinaryExpr<Mod, Literal, RE>> operator%(Literal l, Expr<RE> re)
{
   return Expr<BinaryExpr<Mod, Literal, RE>>(BinaryExpr<Mod, Literal, RE>(l, re.expr));
}

template<class LE> Expr<BinaryExpr<Mod, LE, Literal>> operator%(Expr<LE> le, Literal r)
{
   return Expr<BinaryExpr<Mod, LE, Literal>>(BinaryExpr<Mod, LE, Literal>(le.expr, r));
}

//---

template<class Expr> void execute(const char* msg, Expr expr)
{
   vector<int> v{ 1, 2, 3, 4, 5 };

   transform(cbegin(v), cend(v), begin(v), expr);

   cout << msg << v << endl;
}

//---

int main()
{
   execute("x                ->  ", x);
   execute("x+1              ->  ", x+1);
   execute("x-2              ->  ", x-2);
   execute("x*3              ->  ", x*3);
   execute("x/2              ->  ", x/2);
   execute("x%2              ->  ", x%2);
   execute("x%3              ->  ", x%3);
   execute("5- -x            ->  ", 5- -x);
   execute("x+12             ->  ", x+12);
   execute("21+x             ->  ", 21+x);
   execute("square(3)        ->  ", square(3));
   execute("x+square(x*2)    ->  ", x+square(x*2));
   execute("x+3*x            ->  ", x+3*x);
   execute("(x+4)*x          ->  ", (x+4)*x);
   execute("square(x+2)      ->  ", square(x+2));
   execute("square(x+2)%5    ->  ", square(x+2)%5);
}


Ausgabe:

x                ->  1 2 3 4 5
x+1              ->  2 3 4 5 6
x-2              ->  -1 0 1 2 3
x*3              ->  3 6 9 12 15
x/2              ->  0 1 1 2 2
x%2              ->  1 0 1 0 1
x%3              ->  1 2 0 1 2
5- -x            ->  6 7 8 9 10
x+12             ->  13 14 15 16 17
21+x             ->  22 23 24 25 26
square(3)        ->  9 9 9 9 9
x+square(x*2)    ->  5 18 39 68 105
x+3*x            ->  4 8 12 16 20
(x+4)*x          ->  5 12 21 32 45
square(x+2)      ->  9 16 25 36 49
square(x+2)%5    ->  4 1 0 1 4

5. Fazit

Hiermit endet Teil 2 der Expression-Template Serie.

Schon in Teil 1 hatten wir hoffentlich verstanden, was Expression-Templates sind: unsere Funktionen führen keinen Code zur Laufzeit aus. Statt dessen liefern sie nur Information über den auszuführenden Code zurück. Dies geschieht durch entsprechende Expression-Typen. Die Expression-Template-Magie wird zur Compile-Zeit ausgeführt, nur der verbleibende Code erst zur Laufzeit.

Hier in Teil 2 haben wir unsere Expression-Templates so verbessert, dass sie nicht mehr mit anderem Code interferieren. Außerdem haben wir gleiche Code-Teile in eine Art Expression-Bibliothek ausgelagert, und zu guter Letzt noch das Problem der Literale gelöst.

Nun sollten Sie Expression-Templates zumindest fließend lesen können - selbst wenn es mit dem Schreiben sicher noch stottert. Dem wollen wir uns in den nächsten 3 Teilen widmen, in denen wir unser neues Wissen anwenden und damit auch fleißig üben werden:

6. Links

  1. Artikel "C++ Expression-Templates - Teil 1 - Einführung" von Detlef Wilkening

  2. Artikel "Benutzer-definierte Literale in C++11 & C++14" von Detlef Wilkening
    • Noch nicht veröffentlicht

  3. Artikel "C++ Expression-Templates - Teil 3 - Bind" von Detlef Wilkening
    • Noch nicht veröffentlicht

  4. Artikel "C++ Expression-Templates - Teil 4 - Mathe-Klassen" von Detlef Wilkening
    • Noch nicht veröffentlicht

  5. Artikel "C++ Expression-Templates - Teil 5 - DSELs" von Detlef Wilkening
    • Noch nicht veröffentlicht

7. Versions-Historie

Die Versions-Historie dieses Artikels:
Expression-Serie:
Schlagwörter: