In diesem Eintrag will ich zeigen, wie man einige Konzepte aus LISP direkt in C++ Templates übertragen kann.
Zu Beginn folgender Scheme-Code:
(define (cons a b) (lambda (f) (f a b))) (define (car l) (l (lambda (a b) a))) (define (cdr l) (l (lambda (a b) b)))
Das ist eine Möglichkeit, ein Listensystem in Scheme zu implementieren. Das sieht folgendermaßen aus: Eine Liste ist ein Paar bestehend aus einem Element und dem Rest, wobei der Rest wiederum eine Liste ist, bis irgendwann ein Element am Ende steht, das nichts repräsentiert.
(cons 1 (cons 2 (cons 3 (cons 4 nil))))
erstellt eine Liste mit den Zahlen von 1 bis 4. Mit car besteht die Möglichkeit, auf das Element zuzugreifen, mit cdr auf den Rest. (Die eben konstruierte Liste ist hier l):
(cdr l) sind die Zahlen 2 bis 4.
(car l) ist die 1.
Unsere Implementation in Scheme funktioniert so:
cons gibt eine Funktion zurück, die eine Funktion als Parameter übernimmt, ihr das Element und Rest der Liste als Parameter übergibt, und ihren Rückgabewert zurückgibt. car übergibt der mit cons erzeugten Funktion eine Funktion, die ihren ersten Parameter zurückgibt, also das Element. cdr tut das gleiche, allerdings gibt es den Rest zurück. Das will ich nun in C++ umsetzen.
Um alles mögliche in einer Liste zu speichern, benötigen wir eine allgemeine Schnittstelle, wie Listenelemente aussehen sollen. In der Metaprogrammierung in C++ verwendet man dafür normalerweise Typen. Wir brauchen also eine Möglichkeit, um aus Zahlen Typen zu machen. Das ist relativ simpel:
template<typename T, T Value>
struct integral_constant
{
typedef integral_constant<T, Value> type;
typedef T value_type;
static const T value = Value;
};
template<int Value>
struct int_ : integral_constant<int, Value>{};
integral_constant speichert den übergebenen Wert im statischen Member value. Dadurch können wir aus dem Typen auch jederzeit die Zahl wieder herausholen. int_ ist hier nur dazu da, damit wir über eine kürzere Schreibweise aus einem Integer einen Typen machen können.
Nun zum komplizierten Teil: Wie setzt man Lambdas in C++ um? Dazu benötigen wir zunächst das Konzept der Metafunktion. Eine Metafunktion ist grundsätzlich so aufgebaut:
struct mul
{
template<typename Param1, typename Param2>
struct apply
{
typedef int_<Param1::value * Param2::value> type;
};
};
Die Metafunktion muss ein Strukturentemplate mit dem Namen apply besitzen. apply ist die eigentliche Funktion. Ihr Rückgabewert stellt sich über einen Typen mit dem Namen type dar. Die hier gezeigte Funktion nimmt an, dass die Parameter das integral_constant Konzept unterstützen und hat als Rückgabewert einen Integer, in dem das Produkt der beiden Parameter steht. Ein Aufruf inklusive Ausgabe könnte z.B. so aussehen:
std::cout << mul::apply<int_<3>, int_<2> >::type::value;
Die Ausgabe ist 6.
Eine Lambda können wir in C++ als einfache lokale Metafunktion umsetzen. Damit wird unser cons – übrigens auch eine Metafunktion – zu:
struct cons
{
template<typename A, typename B>
struct apply
{
struct type
{
template<typename F>
struct apply
{
typedef typename F::template apply<A, B>::type type;
};
};
};
};
Das Ganze sieht erstmal etwas kompliziert aus, ist es aber eigentlich gar nicht. apply kennen wir ja schon, es beinhaltet praktisch die eigentliche Funktion. Es bekommt hier das Element (A) und den Rest der Liste (B) als Parameter. Der Rückgabewert type ist hier erneut eine Metafunktion, die eine Metafunktion (F) erwartet. Dessen Rückgabewert ist auch der Rückgabewert der Metafunktion type.
Nun benötigen wir erst einmal die Funktion car, um auf das erste Element der Liste zugreifen zu können.
struct car
{
template<typename L>
struct apply
{
struct lambda
{
template<typename A, typename B>
struct apply
{
typedef A type;
};
};
typedef typename L::template apply<lambda>::type type;
};
};
Auch hier ist wieder in apply die eigentliche Funktion. Sie erwartet die Liste L, eigentlich eine Metafunktion und übergibt ihr eine Lambdafunktion, die ihr erstes Argument zurückgibt. Also genau das Prinzip wie in der Schemeimplementation. cdr, die Funktion die den Rest der Liste zurückgibt, sieht ähnlich aus und unterscheidet sich nur in der Lambdafunktion:
struct cdr
{
template<typename L>
struct apply
{
struct lambda
{
template<typename A, typename B>
struct apply
{
typedef B type;
};
};
typedef typename L::template apply<lambda>::type type;
};
};
Als Markierung für das Ende einer Liste nehmen wir einfach einen Typen, der nil darstellt.
struct nil {};
Das Ganze nun in einem Programm angewandt:
#include <iostream>
typedef cons::apply<int_<1>,
cons::apply<int_<2>,
cons::apply<int_<3>,
cons::apply<int_<4>,
nil>::type>::type>::type>::type list;
template<typename L>
struct print_list
{
static void run()
{
std::cout << car::apply<L>::type::value << std::endl;
print_list<typename cdr::apply<L>::type>::run();
}
};
template<>
struct print_list<nil>
{
static void run()
{
}
};
int main()
{
print_list<list>::run();
}
print_list<>::run gibt das erste Element der Liste aus, und ruft sich rekursiv mit dem Rest der Liste auf. Die Rekursion stoppt, wenn der Parameter nur noch nil ist.
Eine Liste zur Compilezeit geht in C++ natürlich auch einfacher, aber hier wollte ich nur die direkte Umsetzung eines LISP Konzepts in C++ zeigen, auch wie Lambdas möglich sind und wie man eine Allgemeine Schnittstelle für Zahlen, Typen oder Funktionen findet.
