Template-Metaprogrammierung: Wie alles begann

Modernes C++ Rainer Grimm  –  0 Kommentare

Metaprogrammierung ist Programmierung auf Programmen. C++ wendet Metaprogrammierung zur Compilezeit an. Es begann in C++98 mit der Template-Metaprogrammierung, wurde in C++11 mit der Type-Traits-Bibliothek formalisiert und hat sich seit C++11 stetig verbessert. Die wichtigste treibende Kraft sind konstante Ausdrücke. In diesem Beitrag möchte ich über ihre Ursprünge schreiben.

Template Metaprogrammierung: Wie alles began

Meine Motivation, über Template-Metaprogrammierung zu schreiben, besteht darin, ihre Techniken zu entmystifizieren, um Dir zu helfen, die Funktionen der Type-Traits-Bibliothek besser zu verstehen und insbesondere constexpr zu schätzen. Der schlechte Ruf der Template-Metaprogrammierung rührt vor allem daher, dass ihre Fehlermeldungen epische Länge besitzen können. Template-Metaprogrammierung wurde nicht entworfen, sie begann mit einem Unfall.

Der Unfall

1994 stellte Erwin Unruh von Siemens auf einer C++-Ausschusssitzung ein Programm vor, das sich nicht compilieren ließ. Dieses wohl berühmteste Programm, das sich nicht compilieren ließ, sah folgendermaßen aus:

// Prime number computation by Erwin Unruh
template <int i> struct D { D(void*); operator int(); };

template <int p, int i> struct is_prime {
enum { prim = (p%i) && is_prime<(i > 2 ? p : 0), i -1> :: prim };
};

template < int i > struct Prime_print {
Prime_print<i-1> a;
enum { prim = is_prime<i, i-1>::prim };
void f() { D<i> d = prim; }
};

struct is_prime<0,0> { enum {prim=1}; };
struct is_prime<0,1> { enum {prim=1}; };
struct Prime_print<2> { enum {prim = 1}; void f() { D<2> d = prim; } };
#ifndef LAST
#define LAST 10
#endif
main () {
Prime_print<LAST> a;
}

Unruh hat den Metaware Compiler benutzt, aber das Programm ist nicht mehr für C++ gültig. Eine neuere Variante hält der Autor ebenfalls bereit. Okay, warum ist dieses Programm so berühmt? Werfen wir einen Blick auf die ursprünglichen Fehlermeldungen, die type als txpe schrieb.

Template Metaprogrammierung: Wie alles began

Ich habe die wichtigen Teile in Rot hervorgehoben. Ich denke, du erkennst das Muster. Das Programm berechnet zur Compilezeit die ersten Primzahlen bis 30. Das bedeutet, dass die Instanziierung von Templates verwendet werden kann, um zur Compilezeit Mathematik zu betreiben. Es ist sogar noch besser. Die Template-Metaprogrammierung ist Turing-komplett und kann daher zur Lösung jedes Rechenproblems verwendet werden. Natürlich gilt die Turing-Vollständigkeit für die Template-Metaprogrammierung nur in der Theorie, denn die Instanziierungstiefe der Rekursion (mindestens 1024 bei C++11) und die Länge der Namen, die bei der Template-Instanziierung erzeugt werden, setzen einige Grenzen.

Wie funktioniert die Magie?

Lasse mich Schritt für Schritt aufschlüsseln, was vor sich geht.

Berechnen zur Compilezeit

Die Berechnung der Fakultät einer Zahl ist das "Hello World" der Template-Metaprogrammierung:

// factorial.cpp

#include <iostream>

template <int N> // (2)
struct Factorial{
static int const value = N * Factorial<N-1>::value;
};

template <> // (3)
struct Factorial<1>{
static int const value = 1;
};

int main(){

std::cout << '\n';

std::cout << "Factorial<5>::value: " << Factorial<5>::value << '\n'; // (1)
std::cout << "Factorial<10>::value: " << Factorial<10>::value << '\n';//(4)

std::cout << '\n' ;

}

Der Aufruf factorial<5>::value in Zeile (1) bewirkt die Instanziierung des primären oder allgemeinen Templates in Zeile (2). Während dieser Instanziierung wird Factorial<4>::value erzeugt. Diese Rekursion endet, wenn das vollständig spezialisierte Klassen-Template Factorial<1> in Zeile (3) verwendet wird. Vielleicht magst du es etwas bildhafter.

Template Metaprogrammierung: Wie alles began

Hier folgt die Ausgabe des Programms:

Template Metaprogrammierung: Wie alles began

Dank der C++ Insights und des Compiler Explore kannst und solltest du das Programm weiter analysieren. Das sollte dir helfen, dein Gespür für Template-Instanziierung und Template-Metaprogrammierung zu schärfen.

Lasse mich mit C++ Insights beginnen:

C++ Insights

Der Aufruf Factorial<5>::value (Zeile 1) bewirkt die Instanziierung der Klassen-Templates für die Zahlen 5 bis 2. Die vollständige Spezialisierung für 1 ist bereits vorhanden. Der Aufruf Factorial<10>::value (Zeile 2) bewirkt die Instanziierung der Funktions-Templates für die Zahlen 10 - 6, da alle anderen voll spezialisierten Funktions-Templates bereits verfügbar sind. Die folgende Ausgabe zeigt die Instanziierung für die Zahlen 5 bis 2.

Template Metaprogrammierung: Wie alles began

Jetzt geht meine Analyse mit dem Compiler Explorer weiter.

Compiler-Explorer

Der Einfachheit halber stelle ich nur einen Screenshot des Hauptprogramms und der entsprechenden Assembler-Anweisungen zur Verfügung.

Der Compiler Explorer ermöglicht es dir, diese Compilezeitberechnung zu visualisieren.

Template Metaprogrammierung: Wie alles began
Template Metaprogrammierung: Wie alles began

Die Ausgabe zeigt es. Die Fakultäten von 5 und 10 sind nur Konstanten und werden während der Compilezeit berechnet. Du kannst das Ergebnis direkt in der ersten und letzten Zeile der Assembler-Anweisungen sehen.

CppCon 2021

Glücklicherweise konnte ich einen früheren Beitrag als Ausgangspunkt für die heutigen Ausführungen zur Template-Metaprogrammierung verwenden. Ich habe diese Woche vier Vorträge auf der CppCon gehalten und ehrlich gesagt, war das zu viel. Hier sind meine Vorträge, die in ein paar Wochen aus CppCons Youtube-Kanal hier veröffentlicht werden.

Wie geht's weiter?

In meinem nächsten Artikel setze ich meine Reise mit der Template-Metaprogrammierung fort und gebe dir weitere Einblicke.