Klassen mit 1.000.000 Zeichen langen Namen

Klassen mit 1.000.000 Zeichen langen Namen – willkommen zu den grausamsten Höllenqualen, die ich meinem Compiler je angetan hab.

Funktionale Programmierung ist heutzutage (mehr oder weniger) der heißeste Scheiß überhaupt. Es geht hierbei, elkatant vereinfacht und sicherlich korrekturbedürftig, um die deklarative Beschreibung eines Problems ohne einen sequentiellen (imperativen) Lösungsansatz. Kurz gesagt: Statt dass ihr dem Computer einzelne, nacheinander abzuarbeitende Schritte vorgebt, gebt ihr ihm eine Beschreibung des Problems an sich (in Form einer Funktion im mathematischen Sinne) und lasst ihn intern einen imperativen Lösungsweg ermitteln. Mehrere solcher Funktionen lassen sich kombinieren und werden letztendlich als ein „gemeinsames Ganzes“ ausgeführt, ohne Zwischenergebnisse die man speichern oder bearbeiten müsste.

Einfach(st)es Beispiel. Ich brauche, warum auch immer, eine Liste der Zahlen von 0 bis n. Heißt in imperativen Sprachen Speicher reservieren, von 0 bis n hochzählen, Ergebnis weiterverarbeiten. In einer funktionalen Programmiersprache wie Haskell hätte man das Problem eher so gelöst:

zahlen_ab x = x : zahlen_ab (x + 1)
zahlen_bis n = take n (zahlen_ab 0)

Wer bei dieser Syntax nicht schon die Fackel angezündet hat, wird erkennen, was hier passiert: zahlen_ab ist nichts anderes als eine mathematische Funktion, welche beschreibt, was wir wirklich wollen: Eine Liste von Zahlen, bei der jedes Element um 1 größer ist als das Vorgängerelement. Erst wenn wir unsere Funktion benutzen, geben wir an, wie viel wir von der Liste wirklich brauchen. Disclaimer: Ja, ich weiß, total unnötig, [0..n] hätte es auch getan.

Das Konzept, Daten on-demand zu generieren, hat in Form von Generatoren inzwischen auch Einzug in imperative Sprachen gefunden. Ein Beispiel ist die yield-Funktion in C#.

Jetzt meine Idee: Kann man Konzepte einer funktionalen Programmiersprache in C++-Metaprogrammierung abbilden, und wenn ja, wie schlagen sie sich im Vergleich?

Statt dass wir mit Variablen rechnen, rechnen wir also mit Templates. Als Pattern Matching Ersatz benutzen wir Template-Spezialisierungen. Das Ziel: Ein Binärbaum ohne Laufzeit-Speicherverbrauch. Er soll eine Höhe von 10 haben und vollständig sein, also 1023 Elemente enthalten.

Wenig überraschend ist, dass sich die Implementation in Haskell doch sehr in Grenzen hält. Folgende Struktur möchte ich also in C++ „nachbilden“:

data Tree a = Nix | Was a (Tree a) (Tree a)

maketree :: Int -> Tree Int
maketree 0 = Nix
maketree n = Was n (maketree (n - 1)) (maketree (n - 1))

testtree = maketree 10

treestr :: Tree Int -> String
treestr Nix = "nix"
treestr (Was val left right) = "(" ++ treestr left ++ "|" ++ show val ++ "|" ++ treestr right ++ ")"

maketree ist hier unser „Baum-Generator“. Er beschreibt einfach einen vollständigen Binärbaum, bei dem jeder Knoten als Wert den Abstand zu seiner Wurzel hat. testtree erzeugt dann einen Baum mit Höhe 10. treestr erzeugt aus einem beliebigen Baum einen String.

Problem 1: Tree ist etwas, das entweder Nix sein kann, oder Was inklusive einem Wert und zwei weiteren Trees. C++ hat keine Enums, in die man Zusatzwerte packen kann. Genau so wenig können wir eine struct auf sich selber referenzieren, so viel Speicher haben wir nicht. Was wir aber machen können, ist den Wert und die linken und rechten Kinder als Template zu definieren:

struct Nix {};

template<int val, typename left, typename right>
struct Was {};

Statt unendlich viel Speicherplatz belegen die Structs jetzt überhaupt keinen Speicher mehr (Instanzen leerer Klassen belegen aus technischen Gründen ein Byte, allerdings werden wir von den Structs keine Instanzen erzeugen).

Problem 2: maketree ist rekursiv, wie sollen wir das abbilden, ohne auf C++-Funktionen zurückzugreifen? Glücklicherweise erlaubt uns der Compiler Rekursion in Templates, sodass wir tatsächlich sehr ähnlich vorgehen können:

template<int n>
struct maketree
{
	using type = Was<n, typename maketree<n - 1>::type, typename maketree<n - 1>::type>;
};

Rufen wir jetzt maketree<10>::type auf, bekommen wir einen Kompilierfehler: Das ganze ist unendlich. Abhilfe schafft „Pattern Matching“ mittels einer zweiten, spezialisierten Version von maketree, außerdem definieren wir uns wieder testtree als Abkürzung auf maketree<10>::type:

template<>
struct maketree<0>
{
	using type = Nix;
};

using testtree = maketree<10>::type;

Und das war’s. Irgendein Teil von clang++ ist gerade gestorben. Würde man den Klassennamen ausschreiben, der von testtree definiert wird, wäre dieser fast eine Million Zeichen lang. Viel wichtiger aber: Es funktioniert.

Die Implementation von treestr erfolgt ähnlich wie maketree, mit dem Nachteil dass Strings für C++ leider nicht konstant genug sind und deshalb nicht schön templatebasiert konkateniert werden können. Wäre dies der Fall, würde uns der Compiler das gesamte Programm auf eine Instruktion herunteroptimieren, nämlich die, die das Ergebnis ausgibt. Hier muss leider ausreichen, dass wir den Baum rekursiv direkt auf cout schreiben. Dafür müssen wir zusätzlich die Was-struct leicht aufbohren, damit wir den Wert und die Kinder extrahieren können.

template<int val, typename left, typename right>
struct Was
{
	using left_type = left;
	using right_type = right;

	static const int value = val;
};

template<typename tree>
struct treestr
{
	static void print()
	{
		std::cout << "(";
		treestr<typename tree::left_type>::print();
		std::cout << "|" << tree::value << "|";
		treestr<typename tree::right_type>::print();
		std::cout << ")";
	}
};
template<>
struct treestr<Nix>
{
	static void print()
	{
		std::cout << "nix";
	}
};

Für den const int in Was sollte übrigens kein zusätzlicher Speicher verbraucht werden, da er als Kompilierzeit-Konstante angesehen werden kann. Bockige Compiler kann man per constexpr zu ihrem Glück zwingen.

Vollständiger Code

Das Ergebnis: Wir haben das Problem definiert und wissen, dass testtree die Lösung enthält; die gesamte Datenstruktur wird direkt bei der Kompilierung erzeugt. Das kann man so weit auf die Spitze treiben, dass der Compiler einem die Fibonacci-Folge ausrechnet.

Fazit: Ja, es geht. Ja, es sieht scheiße aus. Vorteil der C++-Lösung: Sie ist wesentlich schneller. Dies liegt aber daran, dass die eigentliche Arbeit bereits während der Kompilierung getan wurde, während Haskell erst noch rechnen muss. Das ist auch gleichzeitig der Nachteil daran: Natürlich können wir das ganze in C++ nur mit konstanten Ausdrücken benutzen. Haskell ist das relativ wurscht.

Wenn man aber wirklich mal solche Konstrukte (sie dürfen auch ruhig etwas weniger makaber dem Compiler gegenüber sein) benötigt, dann sind C++-Templates ein Segen. Die Standard-Library scheint gerade auch in diese Richtung zu expandieren und Boost ist sowieso das Paradebeispiel für Template-Programmierung.

Kleiner zusätzlicher Vorteil: Jedem Disassembler, der C++ Symbole anzeigt, wird von dem obigen Code schwindlig, denn der sieht solche Klassen auch nicht alle Tage. Wenn ihr mal wen ärgern wollt, baut das ein. Das „Opfer“ kann sich dann entscheiden, die Symbole vorher aus der Binary zu strippen und so jede Lesbarkeit zu verlieren, oder stundenlang zu warten bis der Disassembler die Symboltabelle zusammengekratzt hat.

Zum Abschluss ein Beispiel, an dem man sieht, dass so etwas tatsächlich nützlich sein kann. In einem kleinen Tool von mir, welches ein einfacher C++-Wrapper über OpenGL ist, findet sich folgender Code zum Definieren von GLSL-Programmen (welche eine Pipeline an GLSL-Shadern darstellen):

template<typename... Shaders>
struct ProgramShaderHelper;

template<typename First, typename... More>
struct ProgramShaderHelper<First, More...>
{
	static void attach(GLuint program)
	{
		glAttachShader(program, First().compile());
		ProgramShaderHelper<More...>::attach(program);
	}
};

template<>
struct ProgramShaderHelper<>
{
	static void attach(GLuint program) { }
};

template<typename... Shaders>
struct Program
{
	Program()
	{
		//...
		ProgramShaderHelper<Shaders...>::attach(prg);
		//...
	}

	static void use()
	{
		static auto program = Program<Shaders...>();
		glUseProgram(program.prg);
	}

private:
	GLuint prg;
};

namespace Programs
{
	using TerrainProgram = Program<Shaders::TerrainVertexShader, Shaders::TerrainFragmentShader>;
	using BlurProgram = Program<Shaders::BlurComputeShader>;
}

Hiermit bin ich in der Lage, das TerrainProgram durch einen Aufruf von Programs::TerrainProgram::use() zu aktivieren. Brauche ich ein neues Programm, muss ich lediglich eine Zeile im Programs-Namespace hinzufügen. Mittels variadischem Template kann ich eine beliebig große Anzahl von Shadern definieren, welche mittels ProgramShaderHelper nacheinander initialisiert werden. Ich habe dafür kein Array gebraucht welches Speicherplatz der Laufzeit in Anspruch nimmt. Letztendlich wurde, bis auf ein paar kleine „Gedächtnisstützen“, das Problem wieder nur beschrieben – die nötigen Klassen hat sich der Compiler selber gebaut und benutzt.

Und damit willkommen zurück auf meinem Blog.

Advertisements

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s