C++-Metaprogrammierung
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[1] oder mit Spirit einen mit Hilfe von C++-Templates realisierten Parsergenerator.[2] 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
Potenzberechnung mit Hilfe von Templates
Das folgende Beispiel berechnet die Potenz für positive Exponenten:
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;
Erläuterung: Das Template potenz instanziiert sich selbst rekursiv, wobei der Exponent mit jedem Rekursionsschritt um 1 reduziert wird. Das Template besitzt eine sogenannte Spezialisierung für den Fall, dass der Exponent 0 ist und liefert in dem Fall das Ergebnis 1 zurück. Diese Spezialisierung nimmt die Rolle der Abbruchbedingung der Rekursion ein.
Also lässt sich die Struktur des Codes als Pseudocode
P(B, E) := B * P(B, E-1) P(B, 0) := 1
beschreiben.
Potenzberechnung mit Hilfe konstanter Ausdrücke
Das folgende Beispiel berechnet ebenfalls die Potenz, in diesem Fall mit Hilfe verallgemeinerter konstanter Ausdrücke:
constexpr int potenz(int basis, unsigned int exp) {
return (exp == 0) ? 1 : basis * potenz(basis, exp - 1);
}
const int P = potenz(10, 3);
Erläuterung: Aufrufe einfacher Funktionen können zur Übersetzungszeit durchgeführt und in konstanten Ausdrücken verwendet werden. Die aufzurufende Funktion muss dafür mit constexpr versehen sein. Dies ist eine Neuerung, die in C++11, der Revision der internationalen ISO-Norm von C++ aus dem Jahr 2011, eingeführt wurde.
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.
Typlisten
Sogenannte Typlisten stellen ein einfaches Beispiel für eine mittels Templates zur Übersetzungszeit definierte Datenstruktur dar. Eine typische Implementierung sieht wie folgt aus:
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.
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 die Möglichkeiten zur Metaprogrammierung erst nachträglich entdeckt wurden und für sie keinerlei speziell entworfenen 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 Instanziierung eines Klassentemplates für jede Iteration verarbeitet werden. Typischerweise terminiert die Abarbeitung durch eine Spezialisierung für den Null-Typ.
Variadische Templates
In C++11 haben variadische Templates, also Templates mit einer beliebigen Parameterzahl, Einzug gehalten. Eine solche Funktionalität lässt sich zwar bereits mit Typlisten realisieren, wie etwa in Loki und Boost, die in die Programmiersprache integrierte Unterstützung variadischer Templates bietet aber den Vorteil wesentlich kürzerer Übersetzungszeiten, da das Verarbeiten von Typlisten mit sehr hohem Aufwand verbunden ist. Anstelle der Parameter wählt man hierbei einen einzigen Tupel-Parameter. Die Abarbeitung muss auch mit variadischen Templates über rekursive Instanziierung ablaufen, sodass strukturell starke Ähnlichkeit besteht.
Tupel
Ein elementares Beispiel für die Erzeugung von Datenstrukturen mittels Metaprogrammierung stellen Tupel dar. Diese lassen sich mit variadischen Templates (oder vormals Typlisten) realisieren. Hierfür legt man üblicherweise ein Klassen-Template an, das beliebig viele Typen als Parameter übernimmt und für jeden Typ ein Feld dieses Typs 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 Indexzugriffe implementieren, die während der Übersetzung stattfinden müssen, oder aber Operationen wie Vergleiche und Hashes synthetisieren, die zur Laufzeit auf den Tupeln angewandt werden können.
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
- Metalisp (Memento vom 4. Februar 2003 im Internet Archive)
- Boost Spirit