Quelltext der Seite C++-Metaprogrammierung

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

== Funktionsweise ==
Bei der Templatemetaprogrammierung macht man sich zunutze, dass Templates während des [[Compiler|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 (Informatik)|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<ref>{{Webarchiv | url=http://www.prakinf.tu-ilmenau.de/~czarn/meta/metalisp.cpp | wayback=20030204184347 | text=Metalisp}}</ref> oder mit [[Spirit (Parser)|Spirit]] einen mit Hilfe von C++-Templates realisierten [[Parsergenerator]].<ref>{{Webarchiv|url=http://boost-spirit.com/home/ |wayback=20110223020652 |text=Boost Spirit |archiv-bot=2023-03-27 15:13:27 InternetArchiveBot }}</ref> [[Krzysztof Czarnecki (Informatiker)|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ändigkeit|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.&nbsp;h. einmal mit einem bestimmten Wert initialisierte Elemente behalten ihren Wert für immer. Interessanterweise ist eine Konsequenz daraus, dass C++-Template-Metaprogramme generell –&nbsp;anders als C++-Laufzeitprogramme&nbsp;– eine Form der [[Rein funktionale Programmierung|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:
<syntaxhighlight lang="cpp">
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;
</syntaxhighlight>

Erläuterung: Das Template ''potenz'' instanziiert sich selbst [[Rekursive Programmierung|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:<syntaxhighlight lang="c++">
constexpr int potenz(int basis, unsigned int exp) {
    return (exp == 0) ? 1 : basis * potenz(basis, exp - 1);
}

const int P = potenz(10, 3);
</syntaxhighlight>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++#C++11|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 [[Funktion (Programmierung)|Funktionen]] zur Übersetzungszeit ein.

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

Ausgehend davon lassen sich komplexe Funktionen und [[Datenstruktur]]en 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 (C++-Bibliothek)|Boost]] oder Loki implementieren bestimmte grundlegende Konstrukte, die solche Metaprogrammierung erleichtern, etwa ''[[Bedingte Anweisung und Verzweigung|if]]''- oder ''[[fold (Funktion höherer Ordnung)|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:
<syntaxhighlight lang="cpp">
struct NullType;

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

typedef TypeList<Type1, TypeList<Type2, TypeList<Type3, NullType>>> MyList;
</syntaxhighlight>
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 (C++-Bibliothek)|Loki]] und [[Boost (C++-Bibliothek)|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 [[Vererbung (Programmierung)|erben]]. Anschließend lassen sich Operationen wie Indexzugriffe implementieren, die während der Übersetzung stattfinden müssen, oder aber Operationen wie Vergleiche und [[Hashfunktion|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.

<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>
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).
<syntaxhighlight lang="cpp">
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};
};
</syntaxhighlight>

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

<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>

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.&nbsp;B. uint8_t, uint16_t …) erweitert.

<syntaxhighlight lang="cpp">
#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;
  }
}
</syntaxhighlight>
Auch dieses Beispiel kann seit C++17 deutlich lesbarer geschrieben werden:
<syntaxhighlight lang="cpp">
#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;
  }
}
</syntaxhighlight>

== 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 ==
* {{Literatur|Autor=[[Krzysztof Czarnecki (Informatiker)|Krzysztof Czarnecki]], [[Ulrich W. Eisenecker]]| Titel=Generative Programming – Methods, Tools, and Applications| Verlag=Addison-Wesley| Jahr=2000| ISBN=0-201-30977-7}}
* {{Literatur|Autor=[[Andrei Alexandrescu]]| Titel=Modernes C++ Design| TitelErg=Generische Programmierung und Entwurfsmuster angewendet| Verlag=mitp| Jahr=2003| ISBN=3-8266-1347-3| Originaltitel=Modern C++ Design. Generic Programming and Design Patterns Applied}}
* {{Literatur|Autor=David Abrahams, Aleksey Gurtovoy| Titel=C++ Template Metaprogramming| Verlag=Addison-Wesley| Jahr=2004| ISBN=0-321-22725-5}}
* {{Literatur|Autor=David Vandervoorde, Nicolai M. Josuttis| Titel=C++ Templates| TitelErg=The Complete Guide| Verlag=Addison-Wesley Professional| Jahr=2003| ISBN=0-201-73484-2}}
* {{Literatur|Autor=Michael McCool, Stefanus DuToit| Titel=Metaprogramming GPUs with Sh| Verlag=AK Peters| Jahr=2004| ISBN=1-56881-229-9}}

== Weblinks ==
* [http://sourceforge.net/projects/loki-lib Loki-Lib]
* [https://www.boost.org/libs/mpl/doc/index.html Boost::MPL Bibliothek zur Metaprogrammierung] von [[Boost (C++-Bibliothek)|Boost]]
* Marcus Bäckmann: [http://www.c-plusplus.de/oop_dummies/bonuskapitel1.pdf ''Bonuskapitel Template-Metaprogrammierung''] (PDF; 133&nbsp;kB) zum Buch ''Objektorientierte Programmierung für Dummies''.

== Einzelnachweise ==
<references />

[[Kategorie:C++]]