C++-Metaprogrammierung bezeichnet die Technik der Metaprogrammierung innerhalb der Programmiersprache C++, also eine Technik, um in C++ Programmcode von anderem Programmcode generieren zu lassen. Dabei kommen vor allem Templates zum Einsatz (in diesem Fall spricht man auch von Templatemetaprogrammierung), aber auch Metaprogrammierung mit Hilfe konstanter Ausdrücke sowie mittels sogenannter Präprozessor-Makros.

Funktionsweise

Bei der Templatemetaprogrammierung macht man sich zunutze, dass Templates während des Kompilierens ausgewertet werden. So kann man Code schreiben, der zur Übersetzungszeit ausgewertet wird, sodass erst dann der eigentliche Code generiert wird. Obwohl sich so die Dauer des Kompilierens verlängert, hat das Verfahren den Vorteil, dass es zu einer Verkürzung der Laufzeit kommen kann.

Die Templatemetaprogrammierung ist eine Programmiertechnik, die für C++ intensiv erforscht und auch konkret umgesetzt wurde. So gibt es zum Beispiel eine Implementierung eines Lisp-Derivats oder mit Spirit einen mit Hilfe von C++-Templates realisierten Parsergenerator. Krzysztof Czarnecki und Ulrich W. Eisenecker gelten als die Vordenker dieser Art des Programmierens. Herausragende Arbeiten zur C++-Metaprogrammierung stammen von Andrei Alexandrescu, die er besonders mit seinem Buch Modernes C++ Design – Generische Programmierung und Entwurfsmuster angewendet bekannt machte.

Die Templatemetaprogrammierung in C++ ist Turing-vollständig, was bedeutet, dass jeder Algorithmus durch Template-Metaprogrammierung umgesetzt werden kann. Gleichzeitig folgt daraus, dass es keinen korrekten C++-Compiler geben kann, der jedes C++ Programm übersetzt, beziehungsweise nicht mehr allgemein entscheidbar ist, ob ein C++-Programm korrekt ist.

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. Der Kontrollfluss erfolgt in Templatemetaprogrammen deshalb mit Hilfe von Rekursion.

Beispiele

template<int B, unsigned int E>
struct potenz {
    enum { value = B * potenz<B, E - 1>::value };
};

template<int B>
struct potenz<B, 0> {
    enum { value = 1 };
};

const int P = potenz<10, 3>::value;

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

constexpr int potenz(int basis, unsigned int exp) {
    return (exp == 0) ? 1 : basis * potenz(basis, exp - 1);
}

const int P = potenz(10, 3);

Verwendete Konstrukte

Klassentemplates nehmen in der C++-Templatemetaprogrammierung die Rolle von Funktionen zur Übersetzungszeit ein.

Sie können Typen und konstante Werte, einschließlich Verweise auf Funktionen, als Parameter entgegennehmen, sodass sie die Rolle eines Rückgabetyps einnehmen. Spezialisierungen von Templates entsprechen Verzweigungen und ermöglichen auf diese Weise die Steuerung des Programmflusses.

Ausgehend davon lassen sich komplexe Funktionen und Datenstrukturen implementieren, die zur Übersetzungszeit ausgewertet werden. Solche können verwendet werden, um etwa Klassenstrukturen zu erzeugen und damit etwa die Umsetzung gewisser Entwurfsmuster zu vereinfachen, oder um Funktionen zu synthetisieren.

Bibliotheken wie Boost oder Loki implementieren bestimmte grundlegende Konstrukte, die solche Metaprogrammierung erleichtern, etwa if- oder fold-ähnliche Konstrukte zur Übersetzungszeit oder etwa Datenstrukturen.

struct NullType;

template<typename H, class T>
struct TypeList {
    typedef H Head;
    typedef T Tail;
};

typedef TypeList<Type1, TypeList<Type2, TypeList<Type3, NullType>>> MyList;

Generierung statischer Tabellen zur Kompilierungszeit

Der Vorteil statischer Tabellen ist der Ersatz von „teuren“ Berechnungen durch eine einfache Array-Indizierung (Beispiele siehe Lookup-Tabelle). In C++ gibt es mehr als eine Möglichkeit, eine statische Tabelle zur Kompilierungszeit zu erzeugen. Das folgende Beispiel demonstriert die Erstellung einer sehr einfachen Tabelle mit Hilfe von rekursiven Strukturen und Variadischen-Templates. Die Tabelle hat eine Größe von zehn und jeder Wert ist einfach der mit sich selbst multiplizierte Index.

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 10;

/**
 * Variadisches Template für die rekursive Hilfs-Struktur.
 */
template<int INDEX = 0, int ...D>
struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> { };

/**
 * Spezialisierung des Templates um bei einer Größe von TABLE_SIZE die Rekursion zu beenden.
 */
template<int ...D>
struct Helper<TABLE_SIZE, D...> {
  static constexpr std::array<int, TABLE_SIZE> table = { D... };
};

constexpr std::array<int, TABLE_SIZE> table = Helper<>::table;

enum  {
  FOUR = table[2] // Nutzung zur Kompilierungszeit
};

int main() {
  for(int i=0; i < TABLE_SIZE; i++) {
    std::cout << table[i]  << std::endl; // Nutzung zur Laufzeit
  }
  std::cout << "FOUR: " << FOUR << std::endl;
}

Die Idee dahinter ist, dass die Hilfs-Struktur rekursiv von einer Struktur mit einem weiteren Template-Argument (in diesem Beispiel berechnet als INDEX * INDEX) erbt, bis die Spezialisierung des Templates die Rekursion bei einer Größe von zehn Elementen beendet. Die Spezialisierung verwendet schließlich die variable Argumentenliste als Elemente für das Array. Der Compiler erzeugt Code ähnlich dem folgenden (Auszug aus Ausgabe von Clang mit folgenden Aufrufparametern -Xclang -ast-print -fsyntax-only).

template <int INDEX = 0, int ...D> struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> {
};
template<> struct Helper<0, <>> : Helper<0 + 1, 0 * 0> {
};
template<> struct Helper<1, <0>> : Helper<1 + 1, 0, 1 * 1> {
};
template<> struct Helper<2, <0, 1>> : Helper<2 + 1, 0, 1, 2 * 2> {
};
template<> struct Helper<3, <0, 1, 4>> : Helper<3 + 1, 0, 1, 4, 3 * 3> {
};
template<> struct Helper<4, <0, 1, 4, 9>> : Helper<4 + 1, 0, 1, 4, 9, 4 * 4> {
};
template<> struct Helper<5, <0, 1, 4, 9, 16>> : Helper<5 + 1, 0, 1, 4, 9, 16, 5 * 5> {
};
template<> struct Helper<6, <0, 1, 4, 9, 16, 25>> : Helper<6 + 1, 0, 1, 4, 9, 16, 25, 6 * 6> {
};
template<> struct Helper<7, <0, 1, 4, 9, 16, 25, 36>> : Helper<7 + 1, 0, 1, 4, 9, 16, 25, 36, 7 * 7> {
};
template<> struct Helper<8, <0, 1, 4, 9, 16, 25, 36, 49>> : Helper<8 + 1, 0, 1, 4, 9, 16, 25, 36, 49, 8 * 8> {
};
template<> struct Helper<9, <0, 1, 4, 9, 16, 25, 36, 49, 64>> : Helper<9 + 1, 0, 1, 4, 9, 16, 25, 36, 49, 64, 9 * 9> {
};
template<> struct Helper<10, <0, 1, 4, 9, 16, 25, 36, 49, 64, 81>> {
  static constexpr std::array<int, TABLE_SIZE> table = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
};

Seit C++17 kann dies deutlich lesbarer geschrieben werden:

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 10;

constexpr std::array<int, TABLE_SIZE> table = [] { // Oder: constexpr auto table
  std::array<int, TABLE_SIZE> A = {};
  for (unsigned i = 0; i < TABLE_SIZE; i++) {
    A[i] = i * i;
  }
  return A;
}();

enum  {
  FOUR = table[2] // Nutzung zur Kompilierungszeit
};

int main() {
  for(int i=0; i < TABLE_SIZE; i++) {
    std::cout << table[i]  << std::endl; // Nutzung zur Laufzeit
  }
  std::cout << "FOUR: " << FOUR << std::endl;
}

Um ein anspruchsvolleres Beispiel zu zeigen, wurde der folgende Code um einen Helfer für die Wertberechnung (als Vorbereitung für deutlich kompliziertere Berechnungen), einen tabellenspezifischen Offset und ein Template-Argument für den Typ der Tabellenwerte (z. B. uint8_t, uint16_t …) erweitert.

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 20;
constexpr int OFFSET = 12;

/**
 * Helfer für die Berechnung der einzelnen Tabellenelemente.
 */
template <typename VALUETYPE, VALUETYPE OFFSET, VALUETYPE INDEX>
struct ValueHelper {
  static constexpr VALUETYPE value = OFFSET + INDEX * INDEX;
};

/**
 * Variadisches Template für die rekursive Hilfs-Struktur.
 */
template<typename VALUETYPE, VALUETYPE OFFSET, int N = 0, VALUETYPE ...D>
struct Helper : Helper<VALUETYPE, OFFSET, N+1, D..., ValueHelper<VALUETYPE, OFFSET, N>::value> { };

/**
 * Spezialisierung des Templates um bei einer Größe von TABLE_SIZE die Rekursion zu beenden.
 */
template<typename VALUETYPE, VALUETYPE OFFSET, VALUETYPE ...D>
struct Helper<VALUETYPE, OFFSET, TABLE_SIZE, D...> {
  static constexpr std::array<VALUETYPE, TABLE_SIZE> table = { D... };
};

constexpr std::array<uint16_t, TABLE_SIZE> table = Helper<uint16_t, OFFSET>::table;

int main() {
  for(int i = 0; i < TABLE_SIZE; i++) {
    std::cout << table[i] << std::endl;
  }
}

Auch dieses Beispiel kann seit C++17 deutlich lesbarer geschrieben werden:

#include <iostream>
#include <array>

constexpr int TABLE_SIZE = 20;
constexpr int OFFSET = 12;

template<typename VALUETYPE, VALUETYPE OFFSET>
constexpr std::array<VALUETYPE, TABLE_SIZE> table = [] { // Oder: constexpr auto table
  std::array<VALUETYPE, TABLE_SIZE> A = {};
  for (unsigned i = 0; i < TABLE_SIZE; i++) {
    A[i] = OFFSET + i * i;
  }
  return A;
}();

int main() {
  for(int i = 0; i < TABLE_SIZE; i++) {
    std::cout << table<uint16_t, OFFSET>[i] << std::endl;
  }
}

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 haben.
• Generische Programmierung: Templatemetaprogrammierung ermöglicht eine höhere Abstraktion. Daher kann Templatemetaprogrammierung zu kürzerem Quelltext und besserer Wartbarkeit führen.
• Lesbarkeit: Verglichen mit konventioneller C++-Programmierung wirken Syntax und Schreibweisen der Templatemetaprogrammierung zunächst 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, insbesondere entspricht die rein funktionale Struktur nicht der üblichen Struktur von C++. Letzteres hängt allerdings auch davon ab, wie die Templatemetaprogrammierung im speziellen Fall umgesetzt wurde.
• Schlechte Unterstützung durch Entwicklungswerkzeuge: In den bestehenden Entwicklungswerkzeugen ist es nicht möglich, die Metagenerierung schrittweise zu verfolgen. Aufgrund fehlender Sprachmittel ist es bislang auch schwierig, sinnvolle Fehlermeldungen für die Metaprogrammierung zu erzeugen. Die meisten Compiler geben Fehlermeldungen aus, aus denen sich nur schwer auf den eigentlichen Fehler schließen lässt.

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, ISBN 3-8266-1347-3 (Originaltitel: Modern C++ Design. Generic Programming and Design Patterns Applied.). 
• 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-201-73484-2. 
• Michael McCool, Stefanus DuToit: Metaprogramming GPUs with Sh. AK Peters, 2004, ISBN 1-56881-229-9. 

Weblinks

• Loki-Lib
• Boost::MPL Bibliothek zur Metaprogrammierung von Boost
• Marcus Bäckmann: Bonuskapitel Template-Metaprogrammierung (PDF; 133 kB) zum Buch Objektorientierte Programmierung für Dummies.

Einzelnachweise

1. ↑ Metalisp (Memento vom 4. Februar 2003 im Internet Archive)
2. ↑ Boost Spirit (Memento des Originals vom 23. Februar 2011 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/boost-spirit.com