C++ Expression-Templates - Teil 1 - Einführung

Von Detlef Wilkening
01.02.2015
Version: 2

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 detaillierter und die Quelltexte sind viel vollständiger.

Inhaltsverzeichnis

1. Einführung
- 1.1 Beispiel "std::bind"
2. Die Idee
3. Die Umsetzung
4. Fazit
5. Links
6. Versions-Historie

1. Einführung

Expression-Templates sind eine auf Templates basierende Technik in C++, mit der ein C++ Einsteiger oder auch der normale C++ Programmierer selten direkt zu tun hat. Es ist eine Technik mit der primär leistungsfähige und vor allem einfach zu nutzende Bibliotheken geschrieben werden können. Realistisch betrachtet schreiben die Meisten von uns solche Bibliotheken relativ selten, nutzen sie aber häufig. Dieser Artikel soll die zugrunde liegende Technik detailliert erläutern, folgende Artikel (wahrscheinlich werden es insgesamt 8 Artikel) werden die Technik verfeinern, sie ausführlich diskutieren, und vor allem erschöpfend anwenden.

In der Praxis werden C++ Expression-Templates für 3 Anwendungen eingesetzt, die miteinander verwoben und daher recht ähnlich sind:

Erstellen von Funktions-Objekten für aufgeschobene Auswertungen ("lazy evaluation")
Bereitstellung einer Bibliothek mit einer DSEL Schnittstelle
DSEL - domain specific embeded language - domänen-spezifische eingebette Sprache
Performance optimierte Bibliotheken - gerade im mathematischen Umfeld

Falls Sie diese Anwendungen - und ihre Überlappungen - hier noch nicht verstehen: keine Sorge. Sobald wir die ersten Expression-Templates entwickelt haben, kommen wir nochmal hierauf zurück - und dann wird sich alles quasi von alleine klären.

1.1 Beispiel "std::bind"

Schauen wir uns mal ein typisches Beispiel für eine dieser Anwendungen an - z.B. den C++11 Binder "std::bind"^[1]. Bind wird z.B. eingesetzt, wenn man einen STL Algorithmus mit einer Funktion nutzen will, bei der die Signatur nicht mit dem Aufruf matcht - z.B. weil die Funktion einen weiteren Parameter benötigt.


#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
using std::placeholders::_1;

bool myless(int n1, int n2)
{
   return n1<n2;
}

int main()
{
   vector<int> v { 1, 2, 3, 5, 7, 11, 13 };

   auto n = count_if(cbegin(v), cend(v), bind(myless, _1, 4));
   cout << "Anzahl kleiner 4: " << n << endl;

   n = count_if(cbegin(v), cend(v), bind(myless, _1, 8));
   cout << "Anzahl kleiner 8: " << n << endl;
}


Ausgabe:

Anzahl kleiner 4: 3
Anzahl kleiner 8: 5

Hinweis:

Boost.Bind^[2]

Teil 3 dieser Serie über Expression-Templates^[3]

Zurück zum Beispiel - was passiert hier eigentlich? Im Detail wird die Wirkungsweise von "std::bind" in meinem Artikel über Bind und Ref^[1] vorgestellt - hier soll uns eine Kurzbeschreibung genügen.

Der Compiler "erzeugt" zur Compile-Zeit mit etwas Magie (eben die Expression-Template Magie, die wir in diesem Artikel kennen lernen werden) ein Funktions-Objekt, das dann dem Algorithmus übergeben wird und dort für die Elemente im Vektor aufgerufen wird. "bind" ist also gar kein Laufzeit-Aufruf, sondern die Anforderung einer Compiler-Generierung.

Das von Bind erzeugte Funktions-Objekt hätten wir natürlich auch händisch erzeugen können:


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

bool myless(int lhs, int rhs)
{
   return lhs<rhs;
}

struct MyLess
{
   explicit MyLess(int v) : rhs(v) {}

   bool operator()(int lhs) const { return myless(lhs, rhs); }

private:
   int rhs;
};

int main()
{
   vector<int> v { 1, 2, 3, 5, 7, 11, 13 };

   auto n = count_if(cbegin(v), cend(v), MyLess(4));
   cout << "Anzahl kleiner 4: " << n << endl;

   n = count_if(cbegin(v), cend(v), MyLess(8));
   cout << "Anzahl kleiner 8: " << n << endl;
}


Ausgabe:

Anzahl kleiner 4: 3
Anzahl kleiner 8: 5

Wer "bind" nicht kennt, und die Funktion "myless" nutzen wollte, hätte sich eben ein solches Funktions-Objekt händisch schreiben müssen - oder alternativ in C++11 Lambda-Ausdrücke genutzt.

Das "bind" hier wirklich ein Objekt erzeugt, das man dann mit einem Int-Wert aufrufen kann, sieht man sehr schön, wenn man sich vom STL Algorithmus löst und einfach ein Bind-Objekt erzeugt und dieses direkt nutzt. Zum Glück leben wir in der Zeit von C++11 und können daher "auto" zur automatischen Typ-Bestimmung^[4] nutzen - denn wir kennen den Typ des Objekts nicht, und er ist auch nicht ganz trivial.


#include <iostream>
#include <functional>
#include <typeinfo>
using namespace std;
using std::placeholders::_1;

bool myless(int lhs, int rhs)
{
   return lhs<rhs;
}

int main()
{
   cout << boolalpha;

   auto obj = bind(myless, _1, 4);

   cout << typeid(obj).name() << '\n' << endl;

   cout << "2<4 => " << obj(2) << endl;
   cout << "3<4 => " << obj(3) << endl;
   cout << "4<4 => " << obj(4) << endl;
   cout << "5<4 => " << obj(5) << endl;
}


Mögliche Ausgabe (denn die genaue Ausgabe von RTTI ist nicht definiert):

class std::_Bind<1,bool,bool(*const)(int,int),class std::_X<1>&,int>

2<4 => true
3<4 => true
4<4 => false
5<4 => false

Oh je, ist das ein komplizierter Typ - man gut, dass C++11 eine automatische Typ-Deduktion mit "auto" hat. Aber unabhängig davon sehen wir, das:

der Typ von "obj" eine Klasse ist,
daher "bind" wohl ein Funktions-Objekt erzeugt hat, und
das man "obj" mit einem Int-Wert aufrufen kann und "obj" dann einen Bool-Wert zurückgibt, der angibt ob der übergebene Int-Wert kleiner "4" ist.

Die Magie, die hier wirkt, gehört zur hellen Seite der C++ Macht und ist eine Nutzung von Expression-Templates.

Hinweise:

Der C++ Binder "std::bind" steht erst seit C++11 zur Verfügung. Von daher benötigen Sie einen halbwegs aktuellen Compiler für diesen Quelltext.
Falls Sie kein C++11 zur Verfügung haben, so können Sie an der Stelle von "std::bind" auch Boost.Bind^[2] nutzen. In Boost existiert "bind" schon sehr lange.
Meine Kleiner-Vergleichs-Funktion heißt "myless" und nicht "less", da es die Funktion "less" im Standard schon gibt - und diese ansonsten aufgrund von "using namespace std" natürlich mit meiner Funktion clashen würde. Alternativ könnte man auf die Using-Anweisung verzichten, oder auf Using-Deklarationen ausweichen.

2. Die Idee

Die Idee von Expression-Templates ist eigentlich ganz einfach. Statt dass Funktionen oder überladene Operatoren direkt den Code ausführen, geben sie in Form von Klassen nur die Informationen über die Operationen zurück, die der Compiler erst dort auswertet, wo die Funktionalität wirklich benötigt wird. Durch diesen Trick kann man Auswertungen z.B. in die Algorithmen verschieben, oder eben auch Performance gewinnen - wie wir später unten noch sehen werden.

So einfach die Idee klingt - ihre Umsetzung ist nicht ganz trivial. Freuen Sie sich also auf ein herausfordernes Stück Gehirnverdreherei mit hoffentlich gutem Ausgang.

3. Die Umsetzung

Fangen wir mit einem ganz einfachen Beispiel an, das zwar sehr einfach ist - dafür aber auch ein bisschen sinnlos wirkt. Aber keine Angst, es wird schon bald komplexer...


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

Variable x;                                        // (3)

Hinweis:

Artikel über die Schlüsselwörter "struct" und "class"^[5]

Wie, nur eine so einfache Klasse (Zeile (1)) mit einem überladenen Funktions-Operator? Und der Funktions-Operator reicht einfach nur die übergebene Int-Variable durch (Zeile (2)). Na ja, und dann wird von der Klasse ein Objekt "x" angelegt (Zeile (3)). Was soll das? Was hat das mit der obigen komplizierten Aufgabe zu tun?

Nun, jetzt haben wir ein Element "x" (genau genommen eine Variable "x", ein Funktions-Objekt), das wir z.B. in einen passenden STL Algorithmus hineingeben können, und dort steht das Element dann für den übergebenen "int". Schauen wir uns das mal an:


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

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

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

Variable x;

int main()
{
   vector<int> v { 1, 2, 3 };                                           // (2)
   cout << v << endl;

   transform(cbegin(v), cend(v), begin(v), x);                          // (3)

   cout << v << endl;                                                   // (4)
}


Ausgabe:

1 2 3
1 2 3

Erklärung:

Für die Ausgabe des Vektors überlade ich den Ausgabe-Operator - Zeile (1).
In Zeile (2) legen wir einen Vektor für "int" an und füllen ihn dann mit den Werten "1", "2" und "3". Ich benutze hier mit den geschweiften Klammern die Initialisierungsliste aus C++11. Zur Rückkopplung gebe ich direkt danach den Vektor aus.
In Zeile (3) rufen wir dann den STL Algorithmus "transform"^[6] für den Vektor auf und schreiben den transformierten Wert direkt wieder in den Vektor.
- Die Transformations-Anweisung ist einfach nur unser Element "x" - als viertes Argument an "transform" übergeben.
- Da "x" den übergebenen Wert nur durchreicht, ändert sich unterm Strich der Inhalt des Vektors nicht - dies sehen wir auch an der Ausgabe in Zeile (4) - immer noch "1 2 3".

Das Ganze ist ziemlich einfach, aber auch langweilig - nicht wahr? Vielleicht hat der ein oder andere sogar das Gefühl ich würde schummeln. Im Vektor ändert sich ja nichts. Für all die Zweifler verändern wir unser Beispiel minimal - statt eines Funktions-Objekts "Variable x" das den Wert nicht ändert, nehmen wir eins dass den Wert quadriert ("SquareVariable x_square"):


#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;
}

struct SquareVariable
{
   int operator()(int n) const { return struct n*n; }
};

struct SquareVariable x_square;

int main()
{
   vector<int> v { 1, 2, 3 };
   cout << v << endl;

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

   cout << v << endl;
}


Ausgabe:

1 2 3
1 4 9

Wir sehen anhand der zweiten Ausgabe, dass unser Funktions-Objekt in "transform" zuschlägt und genutzt wird - die Werte im Vektor sind nach dem Aufruf von "transform" durch unser Funktions-Objekt in "transform" quadriert.

Aber wenn wir für jede gewünschte Funktionalität ein eigene Funktions-Klasse erstellen und ein eigenes Funktions-Objekt anlegen - dann sind wir keinen Schritt weiter als früher. Das haben wir schon immer so gemacht - es nur nie so hochtrabend benannt. Bevor wir unser Beispiel aber aufbohren, damit es sinnvoller wird - lassen Sie uns das bisherige noch mehr verstehen.

"x" bzw. "x_square" ist nicht irgendwas Besonderes oder Spezielles oder etwas nur für den Algorithmus "transform" Geschaffenes - es ist ein ganz normales Funktions-Objekt, das man mit einem Integer aufrufen kann und dann einen möglicherweise anderen Integer zurückgibt. Das folgende Beispiel zeigt dies durch einfache Nutzungen von "x":


#include <iostream>
using namespace std;

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

Variable x;

template<class T> void fct(T obj)
{
   cout << "fct -> obj(4) -> " << obj(4) << endl;
}

int main()
{
   fct(x);
}


Ausgabe:

fct -> obj(4) -> 4

Alles ganz harmlos bis hierher.

3.1 Der erste "echte" Ausdruck

Statt eines speziellen Funktions-Objekts für die Quadrierung möchten wir eine Quadrat-Funktion haben, die wir auf "x" anwenden können, und natürlich auch auf sich selber und auf alle späteren Ausdrücke. Wir würden also gerne folgende Ausdrücke z.B. beim "transform" Aufruf schreiben können:


transform(cbegin(v), cend(v), begin(v), square(x));
transform(cbegin(v), cend(v), begin(v), square(square(x)));
transform(cbegin(v), cend(v), begin(v), square(square(square(x))));

Fangen wir beim Obersten an:


transform(cbegin(v), cend(v), begin(v), square(x));

Wir benötigen also eine Funktion "square"

die man mit einem "x" aufrufen kann, und
die ein Funktions-Objekt zurückgibt, das beim Aufruf "x" auswertet und das Ergebnis quadriert zurückgibt - nichts leichter als das.

1. Unser Wunsch-Transform-Aufruf mit "square(x)":


transform(cbegin(v), cend(v), begin(v), square(x));

2. Mit einer Funktion "square", die eine "Variable" als Parameter erwartet, können wir diesen "Wunsch" erfüllen


??? square(Variable v)
{
   ???
}

3. Wichtig ist - die Funktion darf den Parameter "v" nicht auswerten oder das Quadrieren ausführen. Die Funktionalität soll ja nicht hier ausgeführt werden, sondern in den Algorithmus hinein gegeben werden. Sie muss also was zurückgeben, was man in den Algorithmus hinein geben kann - z.B. ein Funktions-Objekt mit Int-Funktion:


struct SquareOfVariable
{
   int operator()(int n) const { ??? }
};

SquareOfVariable square(Variable v)
{
   ???
}

4. Das von "square" erzeugte Funktions-Objekt geht in "transform" hinein - und dort muss dann natürlich der Parameter "v" (im Originalausdruck "x") zur Verfügung stehen. Das Funktions-Objekt muss sich die Variable also merken:


struct SquareOfVariable
{
   Variable var;
   explicit SquareOfVariable(Variable v) : var(v) {}
   int operator()(int n) const { ??? }
};

SquareOfVariable square(Variable v)
{
   ???
}

5. Nun ist klar, was die Funktion "square" machen muss: sie erzeugt einfach nur das entsprechende Funktions-Objekt:


SquareOfVariable square(Variable v)
{
   return SquareOfVariable(v);
}

6. Und der Funktions-Operator in der Funktions-Klasse muss nun die Variable auswerten, und ihre Rückgabe quadrieren und zurückgeben:


struct SquareOfVariable
{
   Variable var;
   explicit SquareOfVariable(Variable v) : var(v) {}
   int operator()(int n) const { n = var(n); return n*n; }
};

Alles zusammen sieht dann so aus - und funktioniert erstaunlicherweise sogar:


#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;
}

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

Variable x;

struct SquareOfVariable
{
   Variable var;
   explicit SquareOfVariable(Variable v) : var(v) {}
   int operator()(int n) const { n = var(n); return n*n; }
};

SquareOfVariable square(Variable v)
{
   return SquareOfVariable(v);
}

int main()
{
   vector<int> v { 1, 2, 3 };
   cout << v << endl;

   transform(cbegin(v), cend(v), begin(v), square(x));

   cout << v << endl;
}


Ausgabe:

1 2 3
1 4 9

Bevor Sie weiterlesen - verstehen Sie dieses Beispiel bitte. Wichtig ist:

Der Ausdruck "square(x)" wertet nichts aus

sondern erzeugt einen Funktions-Objekt

"weiss"

Die Auswertung ist aufgeschoben.

3.2 Der zweite Ausdruck, aber der erste Allgemeine

Wenn wir unsere obige Strategie auch auf den nächsten Wunsch-Transform-Aufruf anwenden, dann landen wir langsam in unschönem Code:


transform(cbegin(v), cend(v), begin(v), square(square(x)));

Hmm - das würde zu einer weiteren Funktion "square(SquareOfVariable)" und einer weiteren Funktions-Klasse "SquareOfSquareOfVariable" führen. Über das Desaster weiterer Square-Schachtelungen wollen wir erst gar nicht nachdenken. Da muss es doch was Besseres geben.

Die Lösung sind wie so oft Templates. Machen wir "square" und "Square" zu einem Funktions-Template bzw. einem Klassen-Template - und schon könnten wir das viel allgemeiner formulieren.


transform(cbegin(v), cend(v), begin(v), square(x));
transform(cbegin(v), cend(v), begin(v), square(square(x)));
transform(cbegin(v), cend(v), begin(v), square(square(square(x))));

In allen Fällen haben wir eine Funktion "square", die mit einem Funktions-Objekt aufgerufen wird (wir nennen das hier mal einen Ausdruck oder neudeutsch "Expression"). Lassen Sie sich das auf der Zunge zergehen: z.B. bei "square(square(x))" wird das innere "square" mit der Variablen "x" aufgerufen (einem Funktions-Objekt) und das äußere "square" mit dem Funktions-Objekt, das das innere "square" zurückgibt. In Template-Schreibweise also:


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

Nun muss natürlich auch die Funktions-Klasse zu einem Template werden, um mit allgemeinen Funktions-Objekten … äh … Ausdrücken … äh … Expressions … uff … umgehen zu können:


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

Jetzt ist ja auch klar, wie das Funktions-Template komplett aussehen muss:


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

Alles zusammen sieht dann so aus - und es funktioniert erstaunlicherweise wieder auf Anhieb problemlos:


#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;
}

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);
}

int main()
{
   vector<int> v { 1, 2, 3 };
   cout << v << endl;

   transform(cbegin(v), cend(v), begin(v), square(x));

   cout << "^2 -> " << v << endl;

   v ={ 1, 2, 3 };

   transform(cbegin(v), cend(v), begin(v), square(square(x)));

   cout << "^4 -> " << v << endl;

   v ={ 1, 2, 3 };

   transform(cbegin(v), cend(v), begin(v), square(square(square(x))));

   cout << "^8 -> " << v << endl;
}


Ausgabe:

Ori:  1 2 3
^2 -> 1 4 9
^4 -> 1 16 81
^8 -> 1 256 6561

Und wieder ist es wichtig, dass Sie diesen Quelltext verstehen. Alles weitere basiert direkt oder indirekt hierauf. Im Prinzip gilt hier das Gleiche wie oben: die Elemente der Ausdrücke - hier "x" und "square" führen den eigentlichen Code nicht aus, sondern geben die Aktion als Funktions-Objekt zurück. Aufgrund der Nutzung von Templates können "square" und "Square" jetzt mit beliebigen Ausdrücken als Input umgehen - daher läßt sich "square" hier so schön verschachteln. Dabei entstehen schnell recht komplexe Typen. Wir können uns die ja mal direkt von C++ ausgeben lassen:


#include <iostream>
#include <typeinfo>
using namespace std;

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);
}

int main()
{
   auto obj1 = square(x);
   cout << "obj1 = square(x)\n";
   cout << "obj1 = " << typeid(obj1).name() << '\n';
   cout << "obj1(2) -> " << obj1(2) << '\n' << endl;

   auto obj2 = square(square(x));
   cout << "obj2 = square(square(x))\n";
   cout << "obj2 = " << typeid(obj2).name() << '\n';
   cout << "obj2(2) -> " << obj2(2) << '\n' << endl;

   auto obj3 = square(square(square(x)));
   cout << "obj3 = square(square(square(x)))\n";
   cout << "obj3 = " << typeid(obj3).name() << '\n';
   cout << "obj3(2) -> " << obj3(2) << '\n' << endl;
}


Mögliche Ausgabe (denn die genaue Ausgabe von RTTI ist nicht definiert):

obj1 = square(x)
obj1 = struct Square<struct Variable>
obj1(2) -> 4

obj2 = square(square(x))
obj2 = struct Square<struct Square<struct Variable> >
obj2(2) -> 16

obj3 = square(square(square(x)))
obj3 = struct Square<struct Square<struct Square<struct Variable> > >
obj3(2) -> 256

Hinweis - wie Sie sehen, werden die Typen schnell sehr komplex und lang. In der Praxis hat man bei Expression-Templates schon Typ-Namen mit über 10.000 Zeichen Länge beobachtet.

3.3 Der nächste allgemeine unäre Ausdruck

Jetzt den nächsten unären Ausdruck hinzuzufügen ist relativ leicht. Einfach copy&paste vom Square Klassen-Template und "square" Funktions-Template und das wenige ändern, was geändert werden muss. Für unsere Int-Bearbeitung fügen wir das negative Vorzeichen hinzu.


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

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

Damit wir nicht immer (wie in den bisherigen Beispielen) eine riesige Main-Funktion schreiben müssen, lagere ich die eigentliche Expression-Nutzung mit "transform" und die Ausgabe in ein Funktions-Template "execute" aus. Ich hoffe, Sie glauben mir mittlerweile, dass das unsere Expressions semantisch nicht ändert. Alles zusammen ergibt das hier:


#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;
}

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);
}

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

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

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

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

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

int main()
{
   execute(" x       ->  ", x);
   execute("-x       ->  ", -x);
   execute("(-x)^2   ->  ", square(-x));                        // (1)
   execute("-(x^2)   ->  ", -square(x));
   execute("--(x^2)  ->  ", - -square(x));                      // (2)
}


Ausgabe:

x        ->  1 2 3 4
-x       ->  -1 -2 -3 -4
(-x)^2   ->  1 4 9 16
-(x^2)   ->  -1 -4 -9 -16
--(x^2)  ->  1 4 9 16

Und wir sehen - es funktioniert. Wir können jetzt beliebig negative Vorzeichen in unseren Ausdruck einstreuen, selbst wenn es z.B. in Zeile (1) keine Auswirkung hat, denn Quadratzahlen sind halt immer positiv. Und auch Zeile (2) besticht durch Sinnlosigkeit, denn eine doppelte Negation ist wieder der alte Wert. Aber wir sehen, es funktioniert - und das ist das Wichtige. Ach ja, und passen Sie in Zeile (2) auf, dass Sie nicht "--square(x)" ohne Leerzeichen zwischen den beiden Strichen machen - das wäre dann der Minus-Minus-Operator (oder auch Prä-Decrement-Operator) und nicht zwei negative Vorzeichen.

3.4 Ein binärer Ausdruck - die Addition

Nachdem wir nun zwei ünäre Ausdrücke erstellt haben, ist ein binärer Ausdruck auch nicht schwierig. Wir implementieren die Addition, und zwar zuerst als freie Funktion "add". Wer sich fragt, warum wir die Addition nicht direkt als Operator "+" implementieren - Geduld, das kommt als nächstes. Ich habe nur die Erfahrung gemacht, dass Operatoren bei manchen Programmierern was magisch-mystisches sind, und man sie damit gut abschrecken kann. Ich weiss, dass das nicht der Fall ist - aber ich will hier niemanden verlieren. Darum die Addition erstmal als Funktion, und dann als Operator.

Was wollen wir hier erreichen? Zum Beispiel:


transform(cbegin(v), cend(v), begin(v), add(x, x));
transform(cbegin(v), cend(v), begin(v), add(x, square(x)));
transform(cbegin(v), cend(v), begin(v), add(-square(x), x));

Wir benötigen also eine Funktion "add", die man mit zwei unterschiedlichen Ausdrücken (Expressions, Funktions-Objekten) aufrufen kann, und die dann wieder ein Funktions-Objekt zurückgeben. Im Prinzip alles wie bei "square" oder "operator-" - hier aber eben mit zwei Ausdrücken.


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> add(LExpr le, RExpr re)
{
   return Add<LExpr, RExpr>(le, re);
}

Und alles zusammen (aber der Übersichtlichkeit ohne "square" und "operator-"):


#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;
}

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

Variable x;

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> add(LExpr le, RExpr re)
{
   return Add<LExpr, RExpr>(le, re);
}

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

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

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

int main()
{
   execute("x                  ->  ", x);
   execute("add(x, x)          ->  ", add(x, x));
   execute("add(x, add(x, x))  ->  ", add(x, add(x, x)));
   execute("add(add(x, x), x)  ->  ", add(add(x, x), x));
}


Ausgabe:

x                  ->  1 2 3 4
add(x, x)          ->  2 4 6 8
add(x, add(x, x))  ->  3 6 9 12
add(add(x, x), x)  ->  3 6 9 12

Okay, und jetzt das Ganze mit binärem Operator "+" statt der Funktion "add":


#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;
}

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

Variable x;

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);
}

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

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

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

int main()
{
   execute("x        ->  ", x);
   execute("x+x      ->  ", x+x);
   execute("x+x+x    ->  ", x+x+x);
   execute("x+x+x+x  ->  ", x+x+x+x);
}


Ausgabe:

x        ->  1 2 3 4
x+x      ->  2 4 6 8
x+x+x    ->  3 6 9 12
x+x+x+x  ->  4 8 12 16

Noch mehr binäre Operatoren z.B. in Form der Subtraktion, Multiplikation und Division bekommen wir zwei Kapitel später. Aber da ist nichts Neues mehr dran - für uns alles nur kalter Kaffee.

3.5 Konstanten, aber noch keine Literale

Der nächste Schritt ist die Integration von Konstanten, d.h. konstanter benannter Zahlen für unsere Ausdrücke. Genau genommen erwarten Sie wahrscheinlich Literale (d.h. Zahlen, die wir direkt in die Ausdrücke schreiben können) - das Thema möchte ich aber in Teil 2 dieser Serie^[7] verschieben - Sie werden darauf also noch warten müssen. Außerdem beschränken wir uns hier erstmal nur auf Int-Konstanten.

Für die Konstanten benötigen wir wieder eine Klasse "Constant". Da Konstanten nix erwarten, ist "Constant" eine normale Klasse, und kein Template. Der einzige Trick liegt darin, dass der Funktions-Aufruf-Operator jetzt den Parameter ignoriert und einfach nur den konstanten Wert zurückgibt. Diesen müssen wir uns natürlich in jedem Objekt merken:


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

Constant c1(1);
Constant c2(2);
Constant c3(3);

Integriert in unser letztes Beispiel mit dem binären Plus-Operator ergibt sich folgendes Bild:


#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;
}

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

Variable x;

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

Constant c1(1);
Constant c2(2);
Constant c3(3);

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);
}

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

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

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

int main()
{
   execute("c1      ->  ", c1);
   execute("c2      ->  ", c2);
   execute("c3      ->  ", c3);
   execute("c1+c3   ->  ", c1+c3);
   execute("x       ->  ", x);
   execute("x+c1    ->  ", x+c1);
   execute("c2+x    ->  ", c2+x);
   execute("x+c3+x  ->  ", x+c3+x);
}


Ausgabe:

c1      ->  1 1 1 1
c2      ->  2 2 2 2
c3      ->  3 3 3 3
c1+c3   ->  4 4 4 4
x       ->  1 2 3 4
x+c1    ->  2 3 4 5
c2+x    ->  3 4 5 6
x+c3+x  ->  5 7 9 11

3.6 Alles zusammen und noch viel mehr

Was soll ich sagen - was jetzt kommt, ist doch wohl klar, oder? Jetzt ist Fleißarbeit angesagt. Wir werfen alles zusammen und rollen unser Wissen aus auf:

die Subtraktion (Klasse "Sub" und Operator "-"),
die Multiplikation (Klasse "Mul" und Operator "*"),
die Division (Klasse "Div" und Operator "/"),
- Achtung, Division durch "0" wird nicht abgefangen
die Modulo-Division (Klasse "Mod" und Operator "%"),
und aktivieren wieder "square" und das negative Vorzeichen.

Ich glaube nicht, dass sich dazu was zu sagen lohnt. Es ist einfach viel copy&paste mit Änderungen an wenigen Stellen:


#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;
}

//---

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

Variable x;

//---

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

Constant c0(0);
Constant c1(1);
Constant c2(2);
Constant c3(3);
Constant c4(4);
Constant c5(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 Expr> Square<Expr> square(Expr expr)
{
   return Square<Expr>(expr);
}

//---

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

template<class Expr> Neg<Expr> operator-(Expr expr)
{
   return Neg<Expr>(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 LExpr, class RExpr> Add<LExpr, RExpr> operator+(LExpr le, RExpr re)
{
   return Add<LExpr, RExpr>(le, re);
}

//---

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 LExpr, class RExpr> Sub<LExpr, RExpr> operator-(LExpr le, RExpr re)
{
   return Sub<LExpr, RExpr>(le, re);
}

//---

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 LExpr, class RExpr> Mul<LExpr, RExpr> operator*(LExpr le, RExpr re)
{
   return Mul<LExpr, RExpr>(le, re);
}

//---

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 LExpr, class RExpr> Div<LExpr, RExpr> operator/(LExpr le, RExpr re)
{
   return Div<LExpr, RExpr>(le, re);
}

//---

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 LExpr, class RExpr> Mod<LExpr, RExpr> operator%(LExpr le, RExpr re)
{
   return Mod<LExpr, RExpr>(le, re);
}

//---

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

Diese Lösung sieht auf den ersten Blick schon sehr schön aus. In Teil 2 dieser Serie^[7] werden wir aber sehen, dass die Lösung noch ein Problem enthält, und sich die Expression-Infrastruktur von den Operator-Implementierungen trennen läßt. Außerdem werden wir uns dann noch um Literale kümmern. Die endgültige Lösung wird dann dadurch prinzipiell gleich, aber im Detail etwas komplizierter sein.

4. Fazit

Ich hoffe, dass Sie nach diesem ersten Artikel über C++ Expression-Templates verstanden haben, was Expression-Templates sind, und warum Sie keine Angst vor ihnen haben müssen. In den weiteren Folgen dieser Artikel-Serie werden wir sie noch ausführlicher kennen lernen, und uns dann gemeinsam einige Anwendungs-Beispiele erarbeiten.

Bevor wir diesen Artikel aber beenden, lassen Sie uns zum Abschluß mit unserem neuen Wissen noch mal die typischen "Anwendungen" von Expression-Templates diskutieren, die ich ganz am Anfang vorgestellt hatte:

Erstellen von Funktions-Objekten für aufgeschobene Auswertungen ("lazy evaluation")
- Das haben wir die ganze Zeit gemacht. Wir haben Ausdrücke z.B. an transform oder execute übergeben, die vom Compiler zu Funktions-Objekten übersetzt wurden, die dann in die Funktionen hineingegeben wurden. Unsere eigentlichen Ausdrücke sind nicht vor dem Funktions-Aufruf ausgewertet worden - sondern über den Umweg Compiler und Funktions-Objekt in die Funktion gelangt und erst dort genutzt (ausgewertet) worden - wir hatten also eine aufgeschobene Auswertung.
Bereitstellung einer Bibliothek mit einer DSEL
DSEL - domain specific embeded language - eingebette domänen-spezifische Sprache
- Im Prinzip - nein, nicht nur im Prinzip - wir haben unsere eigene DSEL entwickelt. Man kann jetzt auf einfache lesbare Art mathematische Ausdrücke an Funtktionen übergeben, die dann dort drin (aufgeschoben) ausgewertet werden. Bislang hätten wir für jeden mathematischen Ausdruck eine extra Funktions-Objekt-Klasse schreiben und ein Objekt übergeben müssen - oder in C++11 einen Lambda-Ausdruck verwenden können. Selbst im Verhältnis zu C++11 Lambda-Ausdrücken ist unsere Mathe-Ausdrucks-Bibliothek leserlicher und einfacher zu nutzen - willkommen in der schönen Welt der DSELs.
Performance optimierte Bibliotheken - gerade im mathematischen Umfeld
- Okay, hierzu können wir noch nichts sagen. Das werden wir erst in Teil 4 der Serie^[8] sehen. Was uns aber - auch ohne nähere Betrachtung, die noch folgen wird - jetzt schon klar sein sollte: die Ausdrucks-Objekte existieren nur zur Compile-Zeit und können - da sie keinen auszuführenden Code enthalten - vom Compiler komplett wegoptimiert werden. Am Schluß bleibt ein einziges einfaches Funktions-Objekt über - als hätten wir dies händisch geschrieben oder mit einem C++11 Lambda Ausdruck erzeugt.

Sie sehen also, wir haben unsere ersten Funktions-Auswertungen aufgeschoben und unsere erste eigene DSEL geschrieben.

Im nächsten Teil werden wir ein Problem unserer aktuellen Lösung analysieren und beseitigen. Außerdem werden wir zur Vereinfachung des Codes einige immer wiederkehrende Code-Teile in Template-Klassen auslagern. Und zu guter Letzt werden wir uns dem Thema "Literale" widmen, das wir in diesem Teil noch zurückgestellt haben. Mit diesem Rüstzeug werden wir uns in den darauf folgenden Teilen 3-5 an echte Beispiele heranwagen.

5. Links

Artikel "Bind und Ref in C++11" von Detlef Wilkening
- "std::bind" bei C++ Reference:
  http://de.cppreference.com/w/cpp/utility/functional/bind
- "std::ref" bei C++ Reference:
  http://en.cppreference.com/w/cpp/utility/functional/ref

Boost.Bind
- Auf boost.org - hier in der Version 1.55.0
  http://www.boost.org/doc/libs/1_55_0/libs/bind/bind.html

Artikel "C++ Expression-Templates - Teil 3 - Unser eigenes Bind" von Detlef Wilkening
- Artikel noch nicht freigegeben

Artikel über die Schlüsselwörter "struct" und "class" in C++ von Detlef Wilkening
- Artikel noch nicht freigegeben

Artikel "C++ Expression-Templates - Teil 2 - Vertiefung" von Detlef Wilkening
- http://www.wilkening-online.de/programmieren/c++-expression-templates-teil2.html

Artikel "C++ Expression-Templates - Teil 4 - Performance-Optimierte Mathe-Klassen" von Detlef Wilkening
- Artikel noch nicht freigegeben

6. Versions-Historie

Die Versions-Historie dieses Artikels:

Version 1
- 30.08.2014
- Initiale Version
Version 2
- 01.02.2015
- Den Verweis auf Teil 2 der Artikel-Serie integriert, kleinere Korrekturen, und außerdem einige kleine Anpasssungen vorgenommen, damit Teil 1 und 2 stimmig zueinander passen.

Home
News
Vorlesungen
C++ User-Treffen
- Aachen
- Düsseldorf
- Köln
Links
Impressum

Expression-Serie:

1. Einführung
2. Vertiefung
3. Bind
4. Mathe-Klassen
5. DSELs
6. Performance
7. Boost.Proto
8. Fazit

Schlagwörter: