Eindeutig funktional

Es zeigt sich: Das Programm hat alles zu bieten, was die funktionale Programmierung auszeichnet (siehe den Artikel "Funktionale Grundzüge" auf Linux-Magazin Online [4].)

Metafunktionen sind:

• Funktionen erster Ordnung, denn als Klassentemplates können Aliase (Zeile 71) auf sie erzeugt und im weiteren Programmverlauf verwendet werden.
• Funktionen höherer Ordnung, denn sie lassen sich als Argument (Zeile 56) oder Returnwert einer Metafunktion verwenden.
• Reine Funktionen, denn es gibt zur Compilezeit keinen veränderlichen Zustand.

Die Kontrollstruktur der funktionalen Programmierung ist die Rekursion über eine Liste. Dabei wird das erste Element verarbeitet und über den Rest weiter iteriert. In der funktionalen Programmierwelt haben sich »head« für den Beginn der Liste und »tail« für deren kompletten Rest etabliert. Diesem Muster folgt »showMe« ab Zeile 49.

Die Struktur »struct Int2Type« in Zeile 7 nimmt eine natürliche Zahl an und verpackt diese in einem Typ. Über »const static int value= v« in Zeile 8 stellt der Typ seinen Wert wieder als integrale Konstante zur Verfügung. Was wie obfuscated C++-Code wirkt, hat einen einfachen Grund: Um das Alias »constNumbers« in Zeile 67 zu definieren, werden Typen benötigt. Der Kunstgriff, eine natürliche Zahl in einem Typ zu verpacken, geht auf Andrei Alexandrescu [5] zurück.

Neben Alexandrescu, der die Mächtigkeit der Template-Metaprogrammierung auf einzigartige Weise in seinem Werk "Modern C++ Design" [6] angewendet hat, sind insbesondere Krzysztof Czarnecki und Ulrich W. Eisenecker zu nennen, die wegen ihrer Veröffentlichung "Generative Programming" [7] als Pioniere dieser neuen Programmiertechnik gelten.

Ungewohnt und neu sind auch die oft verwendeten drei Punkte (Ellipse), die sowohl in »showMe« als auch in »map« auftauchen. Dies sind die so genannten Variadic Templates [3]. Sie bezeichnen Templates, die beliebig viele Argumente annehmen dürfen. Stehen die drei Punkte links vom Bezeichner, werden die Argumente gepackt, rechts entpackt.

Der wohl befremdlichste Ausdruck ist »std::tuple<typename F::template apply <Elements>::type ... > type« in Zeile 60. Durch das Entfernen der Schlüsselwörter, die dem C++-Parser bei der Evaluierung des Ausdrucks helfen, wird dieser schon deutlich lesbarer: »std::tuple <F::apply<Elements>::type ... > type« . Die Metafunktion »F« und besonders deren Klassentemplate »apply« werden auf jeden Typ von »std::tuple« angewandt. Das Ergebnis ist, dass für jeden Typ »Int2Type« ein neuer Typ erklärt wird.

Im Falle der Metafunktion »DoubleMe« besitzt dieser neue Typ die Eigenschaft, dass seine integrale Konstante verdoppelt ist »typedef Int2Type<2*(T::value)>« . Um das Ergebnis mit »showMe( doubleMeConstNumbers() )« auszugeben, muss der neue Typ instanziiert werden. Dies geschieht zur Laufzeit.

Dieser Ausflug in die Tiefen der C++-Syntax zeigt, dass Template Metaprogramming eine eingebettete, rein funktionale Subsprache in der imperativen Sprache C++ ist.

Gedächtnis inklusive

Der Vergleich einer Laufzeit- und einer Compilezeit-Funktion bringt überraschende Eigenschaften der Template-Instanziierung ans Tageslicht. Als Beispiel dient im Folgenden der klassische Fibonacci-Algorithmus, als Funktion und als Metafunktion implementiert. Der Algorithmus lässt sich in wenigen Zeilen Code ausdrücken (Listing 5). Zudem lässt er sich fast eins zu eins als Compilezeit-Algorithmus implementieren. Lediglich die Bedingungen »if (n==0)« und »if (n==1)« muss der funktionale Programmierer durch die Templatespezialisierung »template<> struct fib<0>« und »template<> struct fib<1>« abbilden (Listing 6).

01 long int fib(int n){
02   if (n==0) return 0;
03   if (n==1) return 1;
04   return fib(n-1)+fib(n-2);
05 }

01 template <int n>
02 struct fib{
03   const static long int value= fib<n-1>::value + fib<n-2>::value;
04 };
05
06 template <>
07 struct fib<0>{
08   const static long int value= 0;
09 };
10
11 template <>
12 struct fib<1>{
13   const static long int value= 1;
14 };

Dann ein kleines Hauptprogramm um die beiden Funktionen geschrieben – und es zeigen sich bei Ausführung die Ergebnisse in Abbildung 5 für die zwei Variationen des Fibonacci-Algorithmus. Während die Laufzeit von »FibonacciDynamic« bei höheren Werten von »n« exponentiell wächst, scheint das Verhalten von »FibonacciStatic« konstant zu sein. Das verwundert nicht, muss doch die statische Version ihre Berechnungen zur Compilezeit ausführen, während die dynamische dies zur Laufzeit erledigt.

Abbildung 5: Vergleich der Laufzeit- und der Compilezeit-Umsetzung des Fibonacci-Algorithmus.

Ein Blick auf den Zeitbedarf beim Übersetzen verblüfft aber doch: Die statische Variante benötigt eine ähnlich kurze Compilezeit wie die dynamische (Abbildung 6). Das Rätsel ist schnell gelöst: Während die dynamische Variante in jeder Rekursion beide Werte nochmals berechnet, verwendet die statische einmal berechnete Werte wieder. Sie baut ein Gedächtnis auf. Dadurch besitzt sie ein lineares Compilezeit-Verhalten.

Abbildung 6: Das Übersetzen von Template-Programmen benötigt nicht zwangsläufig mehr Zeit: Compilezeit-Vergleich der verschiedenen Fibonacci-Implementierungen.

Der wichtigste Anwendungsbereich der Template-Metaprogrammierung besteht aber nicht darin, numerische Werte zur Compilezeit zu ermitteln, sondern Programme zu schreiben, die sich selbst optimieren.