Metaprogrammierung

Einleitung

Erst relativ spät entdeckte man eine Eigenschaft von C++, die sich Metaprogrammierung nennt. Die C++ Metaprogrammierung basiert auf Templates und wird deshalb auch als Template Metaprogrammierung oder kurz TMP bezeichnet. Im Gegensatz zu einem gewöhnlichen Programm, welches zur Laufzeit ausgeführt wird, hat das TM-Programm zur Kompilierung seinen großen Auftritt, ja, es ist tatsächlich ein Programm in einem Programm. Das Ziel der Templates ist und bleibt es, Code zu generieren und TMP kann diesen Prozess extrem ausdrucksstark und performant gestalten. Performant deshalb, weil bestimmte Berechnungen und Aktionen, die zur Kompilierungszeit theoretisch feststehen können, auch tatsächlich während dieser ausgeführt bzw. berechnet werden, anstatt später zur Laufzeit. Man verschiebt also einfach nur Berechnungszeiten von der Runtime in die Compiletime und erhält wesentlich schnelleren Code. Das Programmieren in TMP ist nicht jedermanns Sache, da sie sich von „gewöhnlichem“ C++ fundamental unterscheidet. TMP hat keine neuen Sprachmittel oder Schlüsselworte, aber gibt den bestehenden zum Teil neue Bedeutungen. Auch das für gewöhnlich imperativ, strukturierte Paradigma von C++ wird funktional, tatsächlich kann man C++ auch funktional, dank generischem Paradigma, programmieren.

Ein erstes Beispiel

Das wohl älteste und klassische Beispiel eines TM-Programmes ist die Berechnung der Fakultät einer Zahl:

template <int n>
struct fac {
	const static int result = n * fac<n - 1>::result; // rekursiver Aufruf, Multiplikation mit nächst kleinerem Wert
	// konstant deshalb, weil der Wert bereits zur Compiletime feststehen kann
	// statisch deshalb, damit wir auf den nächsten Wert zugreifen können, ohne ein Objekt vom Typ fac<> zur Laufzeit erstellen zu müssen
	// genauso gut kann man auch enum benutzen
};
 
template <>
struct fac<1> { // Abbruch der Rekursion, bei 1 wird einfach 1 zurückgeben, sonst würde eine Multiplikation mit 0 das Ergebnis verfälschen
	const static int result = 1;
};
 
int array[fac<5>::result]; // Erstelle ein statisches (!) Array der Größe 120

Ab jetzt ändern sich Dinge in C++. Das struct wird zu einer Funktion. Deren Parameter werden per Templates übergeben. Statt einem if..else-Konstrukt nutzt man hier die Technik der absoluten Templatespezialisierung, um den Programmfluss der Rekursion, das Schleifenäquivalent, zu beeinflussen. Das dynamische Beispiel wäre:

int fac(int n) {
	return n > 1 ? n * fac(n - 1) : 1;
}
 
unsigned result = fac(5);
int* array = new int[result];
// ...
delete [] array;

Natürlich könnte man es imperativ noch eleganter lösen, indem man die Sprachmittel von C++ nutzt, die zur Laufzeit eingesetzt werden, aber auf diese Weise kann man demonstrieren, wie der Algorithmus funktioniert.

// Eleganter:
unsigned result = 1;
for(unsigned n = 5; n > 0; n--)
	result *= n;
int* array = new int[result];
// ...
delete [] array;

Hierbei werden sofort zwei Nachteile der imperativen Lösung ersichtlich: zum einen findet die Berechnung zur Laufzeit statt (man stelle sich vor, das Programm soll tausende solcher Berechnungen in kurzer Zeit durchführen), zum anderen ist das Ergebnis nicht konstant, man kann logischerweise z.B. kein statisches Array mit dem Ergebnis kreieren. Die einzige Eigenschaft, welche die TMP-Lösung nicht bieten kann, ist die Möglichkeit, den Wert, auf dem die Fakultät angewendet werden soll, zur Laufzeit zu bestimmen, etwa durch die Eingabe des Benutzers.

Blick unter die Haube

Was macht der Compiler nun aus dem TM-Code? Ganz klar, er setzt die Werte in die Templates ein. Es könnte in etwa so aussehen:

struct fac5 {
	const static int result = 5 * fac4::result;
};
 
struct fac4 {
	const static int result = 4 * fac3::result;
};
 
struct fac3 {
	const static int result = 3 * fac2::result;
};
 
struct fac2 {
	const static int result = 2 * fac1::result;
};
 
struct fac1 {
	const static int result = 1;
};

Nun sieht man auch, was uns dieser Spaß kostet: das alles muss der Compiler machen, d.h., dass Projekte, die einen intensiven Gebrauch von TMP machen, auch u.U. recht lange zum Kompilieren benötigen. Gott sei dank gibt es jedoch bei vielen Compilern vorkompilierte Header, welche einem auch dieses Problem abnehmen können.

Ein kleines Schmankerl

Nun ist dieses Fakultätsbeispiel doch recht abstrakt. TMP kann jedoch viel mehr, als es den Anschein hat. Hier ein Beispiel von einem Programm, welches ermittelt, ob ein Typ von einem anderen Typ abgeleitet wurde:

template <typename Base, typename Derived>
class is {
	struct yes { char y; };
	struct no { char n[2]; };
 
	static yes test_derived(Base);
	static no test_derived(...);
 
public:
	static const bool derived = sizeof(test_derived(Derived())) == sizeof(yes);
};
 
std::cout << std::boolalpha << is<Base, Derived>::derived // true
			    << ' '
			    << is<int, Base>::derived // false
			    << std::endl;

Hierbei werden gleich mehrere Tricks hintereinander verwendet. Zunächst brauchen wir 2 Typen, die sich in ihrer Größe unterscheiden. Da char und char[2] auf jeden Fall immer unterschiedlich groß sind, kapseln wir sie in den beiden structs yes und no. Eine Elementfunktion test_derived nimmt ein Basisobjekt als Parameter entgegen und gibt ein yes-Objekt zurück. Genau diese Funktion wird aufgerufen, wenn sie als Parameter ein Objekt vom Typ Base oder ein Objekt, welches in Base implizit konvertierbar ist, wie es bei öffentlicher Vererbung möglich ist (siehe „ist ein“-Beziehung), vom Aufrufer erhält. Damit das passiert, kümmert sich statische Typprüfung des Compilers um all diese Probleme. Die Überladung dieser Funktion schluckt als Parameter einfach alles, ob int, char oder Auto, und das wird durch den Ellipsen-Operator ausgedrückt, der vielleicht aus der C-Funktion printf() bekannt ist. Egal was kommt, diese Funktion gibt immer ein Objekt vom Typ no zurück. Der Kniff ist der, dass der Operator sizeof schon mit Typen statt mit Objekten als Parameter zufrieden ist. Der Compiler prüft also, ob test_derived(Base) oder test_derived(…) aufgerufen werden soll. (Indem er schaut, was am besten passt. Hierfür gibt es eine genau festgelegte Aufrufshierachie) Anschließend schaut der Compiler auf die Rückgabetypen und vergleicht die Größen der Objekte , welche von test_derived zurückgegeben werden, die ebenfalls zur Kompilierzeit fest stehen. Durch den Ausdruck Derived() erzeugen wir uns ein lokales, temporäres Objekt dieses Typs, welcher ebenfalls durch die statische Typprüfung kontrolliert wird und den wir der Funktion übergeben.

Nachteile von TMP

Wie oben genannt, kann ein Programm, welches viel TMP nutzt, sehr viel Zeit benötigen, um zu kompilieren, wenn man auf vorkompilierte Header verzichten sollte. 2 andere Nachteile wären, dass Fehler und -meldungen nur schwer zu lokalisieren sind, da C++ keine gesonderten Sprachmittel für TMP bietet (was sich mit C++0x etwas ändert). Last but not least ist die TMP noch nicht sehr verbreitet, was schlicht daran liegt, dass sie ungewohnt ist und in vielen Augen weniger interessant als kompliziert angesehen wird.

Abschluss

Das ist nur eine kleine Einführung in die Template Metaprogrammierung. Jeder, der zum ersten mal mit TMP konfrontiert wird, ist erstaunt o. ärgert sich einfach nur, dass er es nicht auf Anhieb versteht. Aber das ist normal. Anderen, die evtl. schon Erfahrungen mit der Funktionalen Programmierung haben (etwa z.B. mit Erlang), werden hier ein Déjà-vu haben und sich freuen, dass C++ auch diese Paradigmen anbieten kann. Demjenigen, welcher sich weiter über dieses Thema informieren will, sei auf folgende Literatur hingewiesen:

http://en.wikipedia.org/wiki/Template_metaprogramming
http://www.amazon.com/Template-Metaprogramming-Concepts-Techniques-Beyond/dp/0321227255
http://www.amazon.de/gp/product/0201704315/ref=sib_rdr_dp