Varadic Templates und funktionale Programmierung

[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.

[mapfold]

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.

[decimad]

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.