3. Varadic Templates und funktionale Programmierung

Varadic Templates und funktionale Programmierung

  • K

    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.

    0
  • K

    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>
{};
    0
  • K

    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.

    0
  • ?

    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.

    0
  • Mod

    Da hat VC++ Recht.

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

    0
  • ?

    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

    0
  • K

    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.

    0
  • K

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

    0
  • C
    Mod

    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.

    0
  • Mod 

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

    ➡

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

    ?

    0
  • K

    Wende doch mal den identity-Trick an. 🙂

    0
  • K

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

    0
Anmelden zum Antworten