Varadic Templates und funktionale Programmierung

knivil

Danke, da ich Vollnoob bin und das verstehen will, gibt es eine gute Einfuehrung in variadic templates, die nicht bei den trivialen Sachen aufhoert? Going Native 2012 und "Variadic Templates are Funadic" steht schon auf meiner Liste.

Kellerautomat

template <typename, typename>
struct cons;

template <typename T, typename... L>
struct cons<T, seq<L...>>
{
    typedef seq<T, L...> type;
};

Sowas?

Columbo

knivil schrieb:

Danke, da ich Vollnoob bin und das verstehen will, gibt es eine gute Einfuehrung in variadic templates, die nicht bei den trivialen Sachen aufhoert?

Nicht soweit ich weiß. camper sollte vielleicht mal ein kleines Tutorial schreiben, leider hat er für so etwas keine Zeit...

template<typename... List>
struct seq
{
	static const unsigned length = sizeof...(List);
	typedef seq_car<List...> car;
	typedef typename seq_cdr<List...>::cdr cdr;

	using type = seq; // Eine nützliche Konvention
};

template<typename, typename> struct cons;

template<typename... s, typename to_append>
struct cons<seq<s...>, to_append> :
	seq<to_append, s...> {};

#include <iostream>
int main()
{
	typedef seq<int_<1>, int_<2>, int_<3>> s;

	using new_s = cons<s, int_<1>>::type;

	std::cout << new_s::length << '\n';
}

Alternativ kannst du auch eine concat-Funktion schreiben.
Ich habe übrigens eine kleine Lib mit solchen Funktionen geschrieben, VTMPL. (Ohne maps o.ä., nur fundamentalere Sachen)

P.S.: Hast du den Code eigentlich mal getestet?

knivil

Also ich habe jetzt den Code von Kellerautomat genommen und er funktioniert wie erwartet.

template <typename T, typename... L>
struct cons<T, seq<L...>>

Wohoo, magic. Sowas aehnliches hatte ich auch schon mal, leider ohne Vorwaertsdeklaration.

P.S.: Hast du den Code eigentlich mal getestet?

Nur Kellerautomats Code bis jetzt.

Columbo

knivil schrieb:

P.S.: Hast du den Code eigentlich mal getestet?

Nur Kellerautomats Code bis jetzt.

Ja, denn dein Post aus dem OP ist völliger Unsinn.

typename typedef seq_car<List...> car;

?

Wohoo, magic. Sowas aehnliches hatte ich auch schon mal, leider ohne Vorwaertsdeklaration.

Das ist eine Spezialisierung, und ohne Primärtemplate ist das auch nicht erlaubt. Daher sieht in TMP der Code meistens so aus:

Primärtemplate, kein vollständiger Typ
Spezialisierung für den gewünschten Typ, bspw. Typliste
ggf. Weitere Spezialisierungen
ggf. Eine Spezialisierung die die Rekursion unterbricht und einen Endfall definiert; Diese leitet dann vom "Rückgabetyp" ab.

Daher ist es Konvention, allen Typen einen Typedef mit sich selbst reinzustecken, damit man dann später auf den Basisklassentyp, von dem die letzte Spezialisierung ableitet, zugreifen kann.

Besonders elegant sind daher die Konstrukte, die 1. keine Spezialisierung benötigen (da kürzer) 2. Ohne Template-Rekursion auskommen (das hat, wie camper schon einmal erklärt hat, gute Gründe!).

Besonders nützlich für letzteres sind Arrays mit den Werten in der Werte-Klasse. Da kann man superschnell und mit O(1) auf die Elemente der Liste zugreifen. Meine Lib macht es genauso.

knivil

Ja, denn dein Post aus dem OP ist völliger Unsinn.

Also er funktioniert, bzw. wird von VS 2013 compiliert und ausgefuehrt. Er macht, das was er soll, die zusaetzlichen Indirektionen sind wahrscheinlich nicht noetig bei der neuen Magie. Die Zahlen kannst du gern durch int_<n> ersetzen.

typename typedef seq_car<List...> car;

Dient dazu, eben wie in Scheme zu programmieren ...

seg<1,2,3>::cdr;
cdr<seg<1,2,3>> // Scheme mit eckigen Klammern

Da ich jetzt ein cons habe, werde ich car und cdr (oder fuer manche head / tail ) nochmals ueberdenken. Ich bin fuer jeden Vorschlag zur Implementation von head / car offen.

Beispielsweise habe ich jetzt car so:

template<typename> struct car;

template<typename Car, typename... Cdr>
struct car< seq<Car, Cdr...>>
{
    typedef Car result;
};

Was leider bei seq<> empty; car<empty>; keinen Compilerfehler generiert, nun ich kann auch immerhin auf nicht auf result zugreifen. Das passt ins Konzept, da car<empty>::result bzw. eval<car<empty>> den Fehler ausloest.

Kellerautomat

Bei typename typedef hast du wohl einfach die beiden Keywords verdreht, sollte typedef typename heissen. Wobei du typename nicht brauchst, wenn du nicht auf einen nested-type (T::type) zugreifst.

Edit: Mit dem folgenden kannst du abfangen, dass Objekte von car<empty<>> erzeugt werden. typedefs kann man aber nicht verhindern.

Wenn du bereits bei Instanzierung einen Compilerfehler haben moechtest, musst du etwas tiefer in die Trickkiste greifen. Grundsaetzlich kann man mit static_assert zur Compilezeit Fehler erzeugen, allerdings wird dir der Compiler folgende Spezialisierung um die ohren Werfen, auch wenn du sie nicht verwendest:

template <>
struct car<seq<>>
{
    static_assert(false, "car of empty seq");
};

Der Compiler sieht die Spezialisierung und denkt sich "Super, diesen Ausdruck kann ich direkt auswerten!". Man muss den Compiler also dazu zwingen, erst bei Instanzierung das static_assert zu pruefen.

Damit der Compiler den Ausdruck erst bei Instanzierung ueberprueft, muss er von Template-Parametern abhaengen. Die Idee ist also, einen Ausdruck hinzuschreiben, der zumindest einen Template-Parameter enthaelt und immer false ergibt.

Das laesst sich mit folgender Metafunktion erledigen:

template <typename>
struct always_false
{
	static constexpr bool value = false;
};

Jetzt haben wir das Werkzeug, nur dummerweise befinden wir uns in einer vollstaendigen Spezialisierung, haben also keinen Template-Parameter, den man einsetzen koennte.

Als Workaround verpassen wir dem car-Template einen Dummy-Parameter, der einen Defaultwert bekommt. Diesen Dummy-Parameter koennen wir dann an always_false uebergeben:

template <typename, typename = void>
struct car;

template <typename head, typename... tail, typename dummy>
struct car<Seq<head, tail...>, dummy>
{
	typedef head type;
};

template <typename dummy>
struct car<Seq<>, dummy>
{
	static_assert(always_false<dummy>::value, "car of empty Seq");
};

http://ideone.com/VC5LFv

Uebrigens finde ich car als Namen sehr irrefuerhend, bin fuer head/tail.

P.S.: Um sich bei allen Metafunktionen das typedef ersparen zu koennen, gibt es einen Shorthand:

template <typename T>
struct identity
{
    typedef T type;
};

Dann Metafunktionen einfach von identity<T> ableiten:

template <typename head, typename... tail, typename dummy>
struct car<Seq<head, tail...>, dummy>
    : identity<head>
{};

knivil

Mein Hintergrund ist, ein einfaches Scheme in C++ TMP zu programmieren. Die Basis steht. car<empty<>> passt dahingehend ins Konzept, dass es erstmal ein Ausdruck ist, ohne Bedeutung. Erst wenn er evaluiert wird, soll es zum Fehler kommen. Das ist der Fall.

Um die Herrn Abelson und Sussmann gluecklich zu machen, habe ich apply schnell hinzugefuegt, damit der eval-apply-Kreis geschlossen ist. Beide sind sehr trivial, da wesentliche Elemente wie "Environment" etc. zur Kompilezeit nicht benoetigt warden und alle Ausdruecke selbstevaluierend sind.

Aktuell sieht es so aus: http://ideone.com/2W0eE7

Sehr vorteilhaft ist, dass Werte durch integral_constant auf Typebene geliftet werden. Spart laesstige Unterscheidungen. Naechster Schritt ist ein if_ bzw. cond zu implementieren und erste Schritte Richting filter zu wagen. Das soll in der Verallgemeinerung von fold-left gipfeln, aus denen alle weiteren Funktionen wie map, filter, concat, ... abgeleitet werden koennen. Letztendlich weiss ich nicht, ob dasausreichend ist. Es soll ja ueber Typ(transformationen) irgendwann echter Code generiert werden .... traeum ...

Natuerlich ist das alles recht neu fuer mich und scheitert an Kleinigkeiten. Beispielsweise:

template<typename Seq> using concat_fix = apply<concat, s2, Seq>;

ist innerhalb von main definiert. Der Kompiler (VS 2013) beschwert sich vermutlich zurecht:

error C2951: template declarations are only permitted at global, namespace, or class scope

Gibt es ein aequivalentes typedef etc. , so dass die Definition nur lokal ist. Zur Not kann man ich sowas auch in einen anonymen Namensraum stecken.

In Funktionen darfst du Klassen/structs definieren, in denen wiederum typedefs stehen dürfen.

Das meiste TMP passiert aber sowieso auf Namespace-Ebene, ich kann mich nicht erinnern, wann ich dieses Problem mal hatte.

Columbo

Da hat VC++ Recht.

A template-declaration can appear only as a namespace scope or class scope declaration.

Hallo!
Eine kleine Warnung, ich weiß nicht ob sie überhaupt zutrifft: Im Moment ist aber echt noch keine gute Zeit, um sich mit VC++ eine TMP-Bibliothek zu schreiben. Deren alias-typedef-Implementierung ("using X =") ist dermaßen anfällig, dass man bestimmte Dinge so einfach nicht ausdrücken kann (interne Compiler-Crashes). Will meinen: Wenn das fehlerfrei funktioniert, dann darf man das alles wieder umschreiben.

Und nun wieder zum Thema: Gibt es eigentlich irgendeinen Grund, warum man etwas sequenzielles wie eine Liste als etwas behandeln sollte, dass ein Head-Element hat und dann noch irgendwas als Schwanz, das wieder ein Head-Element hat? Also gibt es einen Vorteil wenn man einer Sequenz eine "Tail-Rekursion" aufzwingt? Ich bin ja jetzt nicht so der funktionale Programmierer, ich ging eigentlich davon aus, dass das eher immer notgedrungen geschehen ist, weil man eben keine Variadic-Templates zur Verfügung hatte.

Viele Grüße

knivil

Du brauchst keinen Zaehler/Index/Iterator. Explizite Rekursion wird nur selten benutzt, eher Rekursionsschemas. Das universellste ist fold_right (naja, eigentlich der Fixpunktoperator). Damit koennen dann viele andere Funktionen als Spezialisierung implementiert werden. Weiterhin bietet sich an, recursive Funktionen im Zusammenhang mit rekursiven Datenstrukturen zu benutzen, Baeume, Listen Arrays, ... . Desweiteren ist es einfacher Schlussfolgerungen ueber bspw. die Korrektheit des Programms abzuleiten (Induktion) oder gar Algorithmen zu berechnen. Die mathematische Basis ist viel staerker.

Das Gegenstueck in C++ sind explizite for-Schleifen als primitivstes Iterationsschema aehnlich expliziter Rekursion. In <algorithm> wird durch accumulate, transform, etc. von dieser expliziten Iteration abstrahiert und bietet vorgefertigte Iterationsschema an.

Uebrigens finde ich car als Namen sehr irrefuerhend, bin fuer head/tail.

Nun, cddr = cdr( cdr( ... )) oder caddr. Bei geschachtelten Listen kann es auch zu caddaddr kommen, besser zu lesen als wenn es ausgeschrieben wird oder c011011r. Aber head/tail ist auch okay, man braucht es sowieso selten.

dann darf man das alles wieder umschreiben.

Ich mache das nur zum Spass.

knivil

Nachtrag: http://ideone.com/wP1GQN

Interessanter Teil:

template<typename B, typename C, typename A> struct cond;

template<typename C, typename A>
struct cond<std::true_type, C, A>
{
    typedef C type;
};

template<typename C, typename A>
struct cond<std::false_type, C, A>
{
    typedef A type;
};

template <typename S, template<typename B> class F> struct filter_t;

//template <template <typename B> class F, typename... Es>
template <typename... Es, template <typename B> class F>
struct filter_t <seq<Es...>, F >
{
    typedef typename car<seq<Es...>>::type Car;
    typedef typename cdr<seq<Es...>>::type Cdr;
    typedef eval< cond < eval < F < Car > >
                       , eval < cons < Car, eval< filter_t < Cdr, F > > > >
                       , eval < filter_t < Cdr, F > >
                       > > type;
};

template <template <typename B> class F>
struct filter_t <seq<>, F >
{
    typedef seq<> type;
};

template<typename A> struct even;

template<int I>
struct even<std::integral_constant<int, I> >
{
    typedef std::integral_constant<bool, I % 2 == 0> type;
};

D.h. Filter funktioniert genauso wie es in Einstiegsliteratur fuer funktionale Programmierung beschrieben wird. Praedikate sind aehnlich einfach umzusetzen. Wie sie sich von campers Methode unterscheidet, weiss ich nicht. Habe campers Ansatz nicht verstanden, er sieht nicht ser "kanonisch" aus. Das staendige eval kann man sich sparen, mit entsprechendem using . Cooler ist aber ein eigener Evaluator. Andere Teile wie map_t funktionieren wahrscheinlich nicht, da ich mir nicht die Muehe der Korrektur gemacht habe. Vielleicht mache ich bei fold_left weiter, aber nicht so bald ...

camper

knivil schrieb:

Nachtrag: http://ideone.com/wP1GQN
...

Ja, so macht man das normalerweise. Genaugenommen könntest du auf die parteillen Spezialisierungen mit seq<Es...> auch verzichten, die notwendige Arbeit hast du durch car und cdr bereits erledigt.

Columbo

template<typename B, typename C, typename A> struct cond; 
// ...

template<typename B, typename C, typename A> 
using cond = std::conditional< B::value, C, A >;

?

Kellerautomat

Wende doch mal den identity-Trick an.

knivil

@Arcoth: Der Plan war ... ebenfalls zu entfernen und Richtung C++03 zu gehen. Auch wusste ich nicht, dass es conditional schon gibt.

Zu den Spezialisierungen: Ich habe einfach Schema F verfolgt. Allgemeine Definition + Spezialisierung bei allem.