C++-Metaprogrammierung

C++-Metaprogrammierung bezeichnet die Technik der Metaprogrammierung innerhalb der Programmiersprache C++, also eine Technik, um in C++ Programmcode von Programmcode generieren zu lassen. Dabei kommen besonders Templates zum Einsatz, daher spricht man auch von Templatemetaprogrammierung (TMP). Es gibt aber auch Metaprogrammierung mittels C-Makros.

Funktionsweise

Bei der Templatemetaprogrammierung macht man sich zu nutze, dass Templates während des Kompilierens ausgewertet werden. So kann man mit Hilfe von Templatespezialisierung Code schreiben, der zur Kompilationszeit ausgewertet wird und erst den eigentlichen Code generiert. Dabei verlängert sich zwar die Dauer des Kompilierens, aber durch optimale Programmpfade kann es zu einer Verkürzung der Laufzeit kommen.

Die Templatemetaprogrammierung ist eine mächtige Programmiertechnik, die für C++ intensiv erforscht und ausentwickelt wurde. So gibt es zum Beispiel eine Implementierung eines Lisp-Derivats [1] oder einen mit Hilfe von C++-Templates realisierten Parsergenerator [2].

Krzysztof Czarnecki und Ulrich W. Eisenecker gelten als die Vordenker dieser Technik. Herausragende Arbeiten zur C++-Metaprogrammierung stammen insbesondere von Andrei Alexandrescu, die er besonders mit seinem Buch Modernes C++ Design – Generische Programmierung und Entwurfsmuster angewendet und die in dem Buch entwickelte Loki-Bibliothek bekannt machte.

Ein Nachteil der Metatemplateprogrammierung besteht darin, dass es in den bestehenden Entwicklungswerkzeugen keine Möglichkeiten gibt, die Metagenerierung schrittweise zu verfolgen. Aufgrund fehlender Sprachmittel ist es bislang auch schwierig, sinnvolle Fehlermeldungen für die Metaprogrammierung auszugeben, so dass man häufig mit einer enormen Menge an Fehlermeldungen konfrontiert wird, aus denen man nur schwer auf den eigentlichen Fehler rückschließen kann.

Die Templatemetaprogrammierung in C++ ist Turing-vollständig, was bedeutet, dass jeder Algorithmus durch Template-Metaprogrammierung umgesetzt werden kann.

In der Templatemetaprogrammierung gibt es keine veränderlichen Variablen, d.h. einmal mit einem bestimmten Wert initialisierte Elemente behalten ihren Wert für immer. Interessanterweise ist eine Konsequenz daraus, dass C++-Template-Metaprogramme generell – anders als C++-Laufzeitprogramme – eine Form der rein funktionalen Programmierung darstellen. Die Flusskontrolle erfolgt in Templatemetaprogrammen deshalb mit Hilfe von Rekursion (so auch in den Beispielen).

Beispiele

Potenzberechnung mit Hilfe von Metatemplates

 #include <iostream>
 
 template<long B, unsigned long E>
 struct pow_helper {
   static long const value = B * pow_helper<B, E - 1>::value;
 };
 
 template<long B>
 struct pow_helper<B, 0> {
   static long const value = 1;
 };
 
 template<long B, long E>
 struct power {
    static double const value;
 };
 
 template<long B, long E>
 double const power<B, E>::value= E < 0 ? 1.0 / pow_helper<B, E < 0 ? -E : 0>::value
                                        : pow_helper<B, E < 0 ? 0 : E>::value;
 
 int main() {
   std::cout << power<10, -3>::value << std::endl;
 }

Der Code funktioniert so, dass das Template power aufgerufen wird. Dieses wertet nun aus, ob der Exponent negativ ist und rechnet in dem Fall $\frac{1.0}{B^{|E|}}$. Zum Berechnen der eigentlichen Potenz wird die Struktur pow_helper benutzt. Diese ruft sich selbst auf („Rekursion“), wobei der Exponent bei jedem Aufruf um 1 reduziert wird. pow_helper besitzt eine so genannte Spezialisierung für den Fall, dass der Exponent 0 ist und liefert in dem Fall das Ergebnis 1 zurück.

Also lässt sich der Code als

P(B, E) := B * P(B, E-1)
P(B,-E) := 1 / P(B, |E|)
P(B, 0) := 1

etwas leserlicher beschreiben.

Konsistenzprüfung mit Hilfe der Metaprogrammierung

template<bool> class StaticAssert;      // Klassentemplate-Deklaration
 
template<> class StaticAssert<true> {}; // Definition der Templatespezialisierung für true
 
void f() {
  const bool test = false;
  StaticAssert<test> t;    // Es existiert keine Klassen''definition'' für StaticAssert<false>. Dies 
                           // führt zu einer Fehlermeldung des Compilers.
}

Dabei gibt ein Compiler eine Fehlermeldung aus. Dies lässt sich zu Konsistenzprüfungen des Programms ausnutzen (vgl. Assertion), kann jedoch nur zum Testen konstanter, zur Kompilationszeit bekannter Ausdrücke verwendet werden.

Typlisten

Templates erlauben in C++ auch Listen-Strukturen, die zur Compile-Zeit verwendet werden können. Eine Struktur für eine sogenannte Typliste (eingeführt von Andrei Alexandrescu) kann wie folgt definiert werden:

struct NullType {};
 
template<typename H, class T>
struct TypeList
{
  typedef H Head;
  typedef T Tail;
};
typedef TypeList< Type1, TypeList< Type2, TypeList< Type3, NullType > > > MyList;

Typlisten können mittels Templates verarbeitet werden, dafür muss jedoch das Ende durch einen 'Null-Typ' gekennzeichnet werden.

Durch Makros lässt sich die Instanziierung einer Typliste linearisieren. Es ist sehr aufwändig, eine Funktionalität auf Basis von Typlisten zu entwickeln. Mit entsprechenden Grundfunktionen ist jedoch eine elegante Nutzung möglich. Die Problematik in der Verwendung ergibt sich daraus, dass sie sich erst aus dem Standard ergeben haben und für sie keinerlei spezielle Sprachkonstrukte existieren.

Verarbeitung von Typlisten

In C++ gibt es keine einfache Zugriffsmöglichkeit auf die Elemente von Typlisten. Soll eine Typliste verarbeitet werden, so muss jede Iteration in einem separaten Funktionsaufruf (mit Tail als Template-Parameter) oder über die Instanzierung eines Klassentemplates für jede Iteration. Typischerweise terminiert die Abarbeitung durch eine Spezialisierung für den Null-Typ. Ein Beispiel für einen Algorithmus mit Typlisten ist der Quicksort, der sich erstaunlicherweise einfacher als viele andere Sortieralgorithmen implementieren lässt:

template<class List1, class List2>
struct TypeListAppend
{
    typedef TypeList<typename List1::Head, typename TypeListAppend<typename List1::Tail, List2>::Result> Result;
};
template<class List2>
struct TypeListAppend<NullType, List2>
{
    typedef List2 Result;
};
// Auf die Implementierung von TypeListBeforePivot und TypeListAfterPivot soll hier verzichtet werden
template<class List, template<typename A, typename B> class Comparator>
struct TypeListSort
{
    typedef typename TypeListAppend<
                        typename TypeListSort<
                            typename TypeListBeforePivot<
                                typename List::Tail,
                                typename List::Head,
                                Comparator>::Result,
                            Comparator>::Result,
                        TypeList<
                            typename List::Head,
                            typename TypeListSort<
                                typename TypeListAfterPivot<
                                    typename List::Tail,
                                    typename List::Head,
                                    Comparator>::Result,
                                Comparator>::Result
                            >
                        >::Result Result;
};

Über Makros lässt sich solche Programmierung vereinfachen, z.B. über STATIC_IF (Auswahl eines von zwei Typen, die allerdings anders als bei einer if-Abfrage des Präprozessors beide definiert sein müssen, anhand eines Booleschen Ausdrucks) und STATIC_FOLD (Iteration über eine Typliste, bei der ein einfaches Klassen-Template eine Berechnung anhand des aktuellen Elements und eines Zwischenergebnisses (dem Ergebnis bei der letzten Iteration) vornimmt). In D sind Typlisten bereits in der Sprache implementiert. Hier ist ein einfacher Zugriff wie bei einem Array ohne zusätzliche Instanziierungen möglich (statische Kontrollstrukturen sind ebenfalls Sprachelemente).

Tupel

Mit Typlisten lassen sich Tupel realisieren. Hierfür legt man üblicherweise ein Klassen-Template an, das ein Daten-Element für jeden Typ in der Typliste enthält. In C++ muss dies wiederum auf rekursive Art und Weise geschehen. Beispielsweise kann ein Tupel von einem Tupel mit einem Element weniger erben. Anschließend lassen sich Operationen wie Kopieren und Indexzugriffe implementieren.

Variadische Funktions-Templates

In C++0x sollen variadische Funktions-Templates, also Funktions-Templates mit einer beliebigen Parameter-Zahl, Einzug erhalten. Eine solche Funktionalität lässt sich jedoch bereits mit Typlisten realisieren. Anstelle der Parameter wählt man hierbei einen einzigen Tupel-Parameter. Die Abarbeitung wird auch in C++0x (im Gegensatz zu D) über rekursive Instanziierung ablaufen müssen. Mit einigen Makros zur Tupel-Erzeugung und Funktoren, die durch Spezialisierunugen wie variadisch erscheinen, lässt sich auch äußerlich fast dasselbe Verhalten wie im kommenden Standard simulieren.

Vor- und Nachteile der Templatemetaprogrammierung

• Abwägung zwischen Übersetzungszeit und Ausführungszeit: Da der gesamte Template-Quelltext während der Übersetzung verarbeitet, ausgewertet und eingesetzt wird, dauert die Übersetzung insgesamt länger, während der ausführbare Code dadurch an Effizienz gewinnen kann. Obwohl dieser Zusatzaufwand im Allgemeinen sehr gering ausfällt, kann er auf große Projekte oder Projekte, in denen intensiv Templates eingesetzt werden, großen Einfluss auf die Dauer der Übersetzung besitzen.
• Generische Programmierung: Templatemetaprogrammierung erlaubt es dem Programmierer, sich auf die Architektur des Programms zu konzentrieren und dem Compiler die Erzeugung von jeglichen Implementierungen, die vom aufrufenden Quelltext benötigt werden, zu überlassen. Daher kann Templatemetaprogrammierung zu kürzerem Quelltext und erhöhter Wartbarkeit führen.
• Lesbarkeit: Verglichen mit konventioneller C++-Programmierung wirken Syntax und Schreibweisen der Templatemetaprogrammierung ungewohnt. Fortgeschrittene oder sogar die meiste nicht-triviale Templatemetaprogrammierung kann daher schwer zu verstehen sein. Dadurch können Metaprogramme von Programmierern, die in Templatemetaprogrammierung unerfahren sind, schwer zu pflegen sein. Letzteres hängt allerdings auch davon ab, wie die Templatemetaprogrammierung im speziellen Fall umgesetzt wurde.
• Portierbarkeit: Die Portierbarkeit von Quelltext, der von Template-Metaprogrammierung starken Gebrauch macht, kann auf Grund von Unterschieden zwischen den verschiedenen Compilern eingeschränkt sein.
• Durch die rein-funktionale Struktur der Templates wären zwar theoretisch Optimierungen wie etwa in Haskell (Glasgow Haskell Compiler) möglich, praktisch werden solche Vorteile jedoch von keinem Compiler ausgenutzt und statt dessen verursacht diese Struktur in erster Linie (insbesondere für Programmierer, die strukturierte Programmierung aus C++ gewohnt sind) schwer verständlichen Code.

Siehe auch

• Metaprogrammierung
• C++
• Template (Programmierung)
• Boost (C++-Bibliothek)

Weblinks

• Loki-Lib
• Boost::MPL
• Andrei Alexandrescus Homepage
• Objektorientierte Programmierung für Dummies - Bonuskapitel Template-Metaprogrammierung (PDF-Datei; 133 kB)

Literatur

• Krzysztof Czarnecki, Ulrich W. Eisenecker: Generative Programming - Methods, Tools, and Applications. Addison-Wesley, 2000, ISBN 0-201-30977-7.
• Andrei Alexandrescu: Modernes C++ Design. Generische Programmierung und Entwurfsmuster angewendet. mitp, 2003 (Originaltitel: Modern C++ Design. Generic Programming and Design Patterns Applied), ISBN 3-8266-1347-3.
• David Abrahams, Aleksey Gurtovoy: C++ Template Metaprogramming. Addison-Wesley, 2004, ISBN 0-321-22725-5.
• David Vandervoorde, Nicolai M. Josuttis: C++ Templates. The Complete Guide. Addison-Wesley Professional, 2003, ISBN 0-2017-3484-2.
• Michael McCool, Stefanus DuToit: Metaprogramming GPUs with Sh. AK Peters, 2004, ISBN 1568812299.