brainfuck-Compiler TMP style

314159265358979 schrieb:

Zeig doch mal her den Matheparser.

Wenn du sicher bist, dass dein Magen das aushält... ich mach grad nen neuen Post.

Den Dingensda am Anfang hab ich gebastelt, da mir die Reihenfolge der Speicherfreigabe (und der Destruktor-aufrufe) herzlich egal ist und ich keine lust hab es selbst zu machen... ( boost::ptr_set o. ä. hab ich ja nicht ^^)

314159265358979

Mal abgesehen, dass man da jetzt noch viel verbessern kann: Was hat das mit TMP zu tun?

314159265358979 schrieb:

Mal abgesehen, dass man da jetzt noch viel verbessern kann: Was hat das mit TMP zu tun?

Nein, es ist ein normaler Parser. Aber TMP werd ich jetzt auch mal versuchen Ich wusste nicht, dass du einen TMP wolltest ^^

Aber wie soll ich output zur Compile-Zeit machen? Ein static_assert(0, "..."); oder wie...?

Ah nee, ich werd mich wohl mit boost::mpl auseinandersetzen müssen...

314159265358979

Was willst du denn da ausgeben? Du brauchst doch nur eine Zahl als Ergebnis.

std::cout << eval<'2', '+', '2'>::value;

Oder so ähnlich.

314159265358979 schrieb:

Was willst du denn da ausgeben? Du brauchst doch nur eine Zahl als Ergebnis.
std::cout << eval<'2', '+', '2'>::value;
Oder so ähnlich.

Hmm, gut neues Ziel für die nächsten eineinhalb Stunden.

Tja, schon ein wenig weitergekommen. Aber eigentlich sehe ich so etwas wie temp-programmierung als unnötig - ich mein', wozu brauchst du es in Applikationen? :p Oder es ist einfach lustig, sich in sowas auszukennen

otze

Hacker schrieb:

Tja, schon ein wenig weitergekommen. Aber eigentlich sehe ich so etwas wie temp-programmierung als unnötig - ich mein', wozu brauchst du es in Applikationen? :p Oder es ist einfach lustig, sich in sowas auszukennen

Vielleicht sollte man sich vorher klar sein, warum man etwas tut, bevor man es tut. TMP in dieser Form hat vielleicht eine Handvoll Anwendungen. Hauptsächlich geht es darum, das es geht und das man damit unglaublich schlimme Bugs in einem Code verstecken kann. Dass das hier relativ sinnlos ist, wurde aber schon an anderer Stelle angemerkt.

Die Frage ist: warum machst du es? Von dem was ich bislang so von dir gelesen habe, hab ich nicht den Eindruck, dass das etwas ist was a) in deinem Kerninteressenbereich liegt (im Gegensatz zu Pi) und b) dich in deiner Entwicklung als Programmierer weiter bringt.

Was TMP angeht tüftel ich gerade etwas an einem intelligenteren Ansatz für expression templates rum. Es geht darum, Regeln zu definieren, um ein expression template in eine Normalform zu bringen. Das heißt, anstatt den Ausdruck 1:1 in sein (dummes) expression template umzuformen suche ich eine möglichst einfache Darstellung, die es zum einen dem Compiler einfach macht zu optimieren und zum anderen mir es einfacher macht, die richtigen Algorithmen zu wählen. Anwendung ist lineare Algebra, insbesondere elementweise Transformationen von Vektoren/Matrizen. Long Term überlege ich, ob es nicht sogar möglich ist, aus so einer Normalform einen Kern für GPU-Programmierung zu generieren. Aber wie gesagt: das ist hauptsächlich im Planungsstadium. Ich habe leider kaum Zeit, um das zu Programmieren.

cooky451

Hacker schrieb:

Tja, schon ein wenig weitergekommen. Aber eigentlich sehe ich so etwas wie temp-programmierung als unnötig - ich mein', wozu brauchst du es in Applikationen? :p Oder es ist einfach lustig, sich in sowas auszukennen

TMP an sich würde ich nicht als unnötig sehen. Der größte Vorteil ist wohl, dass man mit etwas Getrickse und Operatorüberladungen Dinge bauen kann, die man in der Sprache sonst nur schwer ausdrücken konnte. (Lambdas, Expression Templates, ...)
Aber die Reinform die hier präsentiert wird ist natürlich völlig sinnlos, abgesehen vom Lerneffekt vielleicht, aber erstmal ist es nur Spaß an den vielen <<<<...>...>...>...>

Advanced C++ Metaprogramming | ISBN: 1460966163

Sone

camper, Aufgabe 3 hab ich irgendwie gelöst

**3:
**

template<int...a>
int F()
{
      typedef decltype(std::make_tuple(a...)) tuple_type;
      static tuple_type const tuple(std::make_tuple(a...));
      static constexpr size_t s = std::tuple_size<tuple_type>::value;
      static int rval = std::get<s - 1>(std::make_tuple(a...));
      return rval;
}

Ich hab mal die Aufgabe zu optimieren in meine Hand genommen.

Edit: PI würde mich für diese Lösung ohrfeigen.

otze

so ist das nicht richtig. TMP-Funktionen sind Klassen:

template<int ...a>
struct F{
    static const int value=...;
};

Sone

otze schrieb:

so ist das nicht richtig. TMP-Funktionen sind Klassen:
template<int ...a>
struct F{
    static const int value=...;
};

Same story:

template<int...a>
struct F
{
      typedef decltype(std::make_tuple(a...)) tuple_type;
      static tuple_type const tuple;
      static constexpr size_t s = std::tuple_size<tuple_type>::value;
      static int const value;
};

template<int...a>
typename F<a...>::tuple_type const F<a...>::tuple(a...);
template<int...a>
int const F<a...>::value = std::get<s - 1>(tuple);

Sone

Kannst du mir erklären wie das gehen soll?

F<<5, 5, 5>, 8>

Wie soll man das deklarieren, damit das so verschachtelt werden kann?

GorbGorb

Hacker schrieb:

Kannst du mir erklären wie das gehen soll?
F<<5, 5, 5>, 8>
Wie soll man das deklarieren, damit das so verschachtelt werden kann?

Gar nicht. Das geht schon eher:

F< List< 5 , 5 , 5 > , 8 >

oder, je nach context, auch

F< F< 5 , 5 , 5 > , 8 >

Sone

Ah, alles klar. Das erinnert mich ein wenig an Typlisten, dein letztes Beispiel (auch wenn variadic templates sie natürlich überflüssig machen).

camper

Hacker schrieb:

Ah, alles klar. Das erinnert mich ein wenig an Typlisten, dein letztes Beispiel (auch wenn variadic templates sie natürlich überflüssig machen).

Ja, das ist durchaus kein anderes Problem. Im Übrigen sollen der Code in den Aufgaben nur Pseudo-code darstellen, du kannst dir also z.B. aussuchen, ob die Listen in einem Typ verpackt werden, oder ob es überhaupt ein Klassentemplate sein muss - falls du lieber constexpr-Funktionen verwenden willst: bitte.

Ein bisschen zur Motivation habe ich einmal experimentiert, wie Listen (0...N-1) am effizientes erzeigt werden können. Das kann zum Beispiel ganz simpel linear gemacht werden:

template <std::size_t... i> struct index_list {};
template <std::size_t N, typename L = index_list<>> struct make_index_list;
template <std::size_t N, std::size_t... i> struct make_index_list<N, index_list<i...>>
{
    typedef typename make_index_list<N-1, index_list<i..., sizeof...(i)>>::type type;
};

effizient ist das allerdings nicht. Optimieren könnte man z.B., indem man pro Rekursionsschritt mehr als 1 Element hinzufügt:
Mit ein bisschen Präprozessormagie also so etwas:

#include <iostream>
#include <boost/preprocessor/punctuation/comma_if.hpp>
#include <boost/preprocessor/repetition/repeat.hpp>
#include <boost/preprocessor/repetition/enum_params.hpp>
template <std::size_t... i> struct index_list {};
template <std::size_t N, typename L = index_list<>> struct make_index_list;
#define LL(z, n, text) , ( sizeof...(i) + n )
template <std::size_t N, std::size_t... i> struct make_index_list<N, index_list<i...>>
{
    typedef typename make_index_list<N-LIST_APPEND, index_list<i... BOOST_PP_REPEAT(LIST_APPEND,LL,)>>::type type;
};
#define LLL(z, n, text) \
template <std::size_t... i> struct make_index_list<n, index_list<i...>> \
{ \
    typedef index_list<BOOST_PP_ENUM_PARAMS(n,) BOOST_PP_COMMA_IF(n) ( n + i )...> type; \
};
BOOST_PP_REPEAT(LIST_APPEND,LLL,)
int main()
{
    std::cout << sizeof(make_index_list<LIST_LENGTH>::type) << '\n';
}

Alternativ kann man das Ganze auch durch direkte Teilung erzeugen:

#include <iostream>
#include <boost/preprocessor/punctuation/comma_if.hpp>
#include <boost/preprocessor/repetition/repeat.hpp>
#include <boost/preprocessor/repetition/enum_params.hpp>
template <std::size_t... i> struct index_list {};
template <typename L, typename M> struct repeat;
#define LL(z, n, text) ( n * sizeof...(i) + i )...,
template <std::size_t... i, std::size_t...j> struct repeat<index_list<i...>, index_list<j...>>
{
    typedef index_list<BOOST_PP_REPEAT(LIST_DIV,LL,) ( LIST_DIV * sizeof...(i) + j )...> type;
};
template <std::size_t N> struct make_index_list
{
    typedef typename repeat<typename make_index_list<N / LIST_DIV >::type, typename make_index_list<N % LIST_DIV>::type>::type type;
};
#define LLL(z, n, text) \
template <> struct make_index_list<n> \
{ \
    typedef index_list<BOOST_PP_ENUM_PARAMS(n,)> type; \
};
BOOST_PP_REPEAT(LIST_DIV,LLL,)
int main()
{
    std::cout << sizeof(make_index_list<LIST_LENGTH>::type) << '\n';
}

Mit

for (( x=256; x>0; x/=2)); do MEM=0; for (( y=0; MEM<=25000000; y+=y/10+1 )); do echo -n "${x};${y};"; OUTPUT=`/usr/bin/time -f "%U;%M" -o /dev/stdout  g++-4.7.1 -std=c++0x make_list_linear.cpp -ftemplate-depth=100000 -DLIST_LENGTH=$y -DLIST_APPEND=$x`; MEM=`echo $OUTPUT | awk '{ split($1,FOO,";"); print FOO[2] }'`; echo $OUTPUT; done; done > make_list_linear.csv

usw.
lässt sich dann eine Auswertung durchführen.
Man bekommt z.B. heraus, dass clang offenbar erheblich effizienter als g++ mit dem Speicher umgeht (Anm. der gemessene Speicher ist hier nicht der tatsächliche Speicherbrauch, der beträgt nur ungefähr 1/3 des hier gemessenen Wertes). Für die lineare Variante fehlen für kleine N Messungen: clang stürzt bei mir ab einer Rekursionstiefe über 1452 grundsätzlich mit einem segfault ab.
Interessanterweise verhalten sich g++ und clang völlig anders bei der logarithmischen Variante.

camper

Als nächstes habe ich mir mal die 4. Aufgabe vorgenommen, also die Erstellung einer Zugriffsfunktion auf das n-te Elemente einer Liste.
Die Standardbibliothek verfügt bereits über einen einfachen Mechanismus dafür:

...

template <typename L, std::size_t N> struct at;
template <typename T, T... i, std::size_t N> struct at<value_list<T, i...>, N>
{
    static constexpr T value = std::remove_reference<decltype(std::get<N>(std::tuple<std::integral_constant<T, i>...>()))>::type::value;
};

int main()
{
    typedef make_value_list<std::size_t,LENGTH>::type list;
#define INSTANTIATE(z, n, x) (void)at<list,LENGTH*(256*x+n)/8192>::value;
    BOOST_PP_REPEAT(256,INSTANTIATE,0)  BOOST_PP_REPEAT(256,INSTANTIATE,1)  BOOST_PP_REPEAT(256,INSTANTIATE,2)  BOOST_PP_REPEAT(256,INSTANTIATE,3)
    BOOST_PP_REPEAT(256,INSTANTIATE,4)  BOOST_PP_REPEAT(256,INSTANTIATE,5)  BOOST_PP_REPEAT(256,INSTANTIATE,6)  BOOST_PP_REPEAT(256,INSTANTIATE,7)
    BOOST_PP_REPEAT(256,INSTANTIATE,8)  BOOST_PP_REPEAT(256,INSTANTIATE,9)  BOOST_PP_REPEAT(256,INSTANTIATE,10) BOOST_PP_REPEAT(256,INSTANTIATE,11)
    BOOST_PP_REPEAT(256,INSTANTIATE,12) BOOST_PP_REPEAT(256,INSTANTIATE,13) BOOST_PP_REPEAT(256,INSTANTIATE,14) BOOST_PP_REPEAT(256,INSTANTIATE,15)
}

Zum Vergleich habe ich Zugriffe auf alle Listenelement instantiiert, denn das dürfte bei typischer Nutzung auch auftreten, dass jedes einzelne Element einer Liste an irgendeiner Stelle der Berechnung benötigt wird.
Die Liste wird jeweils mit der mit der logarithmischen Variante (DIV=256) aus dem vorherigen Beitrag erzeugt.

Ein andere einfache Möglichkeit, die Funktion zu implementieren, besteht wie bei make_list darin, jeweils die ersten x Elemente der Liste zu entfernen, sofern der gesuchte Listenindex größer ist.

template <typename L, std::size_t N> struct at
{
    static_assert( sizeof(L)==0, "index zu gross!" );
};
template <typename T, T i0, T... i, std::size_t N> struct at<value_list<T, i0, i...>, N>
{
    static const T value = at<value_list<T, i...>, N - 1>::value;
};
template <typename T, T i0, T... i> struct at<value_list<T, i0, i...>, 0>
{
    static const T value = i0;
};

Allgemeiner:

template <typename L, std::size_t N> struct at
{
    static_assert( sizeof(L)==0, "index zu gross!" );
};
template <typename T, BOOST_PP_ENUM_PARAMS(SHIFT,T i), T... i, std::size_t N> struct at<value_list<T, BOOST_PP_ENUM_PARAMS(SHIFT,i), i...>, N>
{
    static const T value = at<value_list<T, i...>, N - SHIFT>::value;
};
#define SPECIALIZE1(z, n, test) \
template <typename T, BOOST_PP_ENUM_PARAMS(BOOST_PP_INC(n),T i), T... i> struct at<value_list<T, BOOST_PP_ENUM_PARAMS(BOOST_PP_INC(n),i), i...>, n> \
{ \
    static const T value = i##n; \
};
BOOST_PP_REPEAT(BOOST_PP_DEC(SHIFT),SPECIALIZE1,)
#define SPECIALIZE2(z, n, test) \
template <typename T, BOOST_PP_ENUM_PARAMS(SHIFT,T i), T... i> struct at<value_list<T, BOOST_PP_ENUM_PARAMS(SHIFT,i), i...>, n> \
{ \
    static const T value = i##n; \
};
BOOST_PP_REPEAT(SHIFT,SPECIALIZE2,)

Schließlich können wir die einzelnen Elemente auch in Klassen verpacken, und diese voneinander ableiten

template <std::size_t> struct tag {};
template <typename L, typename J = typename make_value_list<std::size_t, L::size>::type> struct holder;
template <typename T, T i0, T... i, std::size_t j0, std::size_t... j> struct holder<value_list<T, i0, i...>, value_list<std::size_t, j0, j...>>
    : holder<value_list<T, i...>, value_list<std::size_t, j...>>
{
    using holder<value_list<T, i...>, value_list<std::size_t, j...>>::get;
    static constexpr T get(tag<j0>) { return i0; }
};
template <typename T> struct holder<value_list<T>, value_list<std::size_t>>
{
    static constexpr T get(...);
};

template <typename L, std::size_t N> struct at;
template <typename T, T... i, std::size_t N> struct at<value_list<T, i...>, N>
{
    static constexpr T value = holder<value_list<T, i...>>::get(tag<N>());
};

Keine dieser Varianten ist sonderlich performant. Bei Listen, die mehr als wenige hundert Elemente sind, führen sie zu einem enormen Speicher- und Zeitverbrauch. Das ist auch nicht sonderlich überraschend, schließlich sind durch die Rekursion eine Menge an Instantiierungen durchzuführen.

Kann man es besser machen? z.B. durch Mehrfachvererbung:

template <std::size_t i, typename T, T v> struct holder_helper
{
    template <std::size_t j>
    static constexpr typename std::enable_if<i == j, T>::type get() { return v; };
};

template <typename L, typename J = typename make_value_list<std::size_t, L::size>::type> struct holder;
template <typename T, T... i, std::size_t... j> struct holder<value_list<T, i...>, value_list<std::size_t, j...>>
    : holder_helper<j, T, i>...{};

template <typename L, std::size_t N> struct at;
template <typename T, T... i, std::size_t N> struct at<value_list<T, i...>, N>
{
    static constexpr T value = holder<value_list<T, i...>>::template get<N>();
};

Diese Variante ist zwar einfach, hat aber einen Schönheitsfehler: sie funktioniert nicht.
SFINAE kann nicht dazu benutzt werden, um Mehrdeutigkeiten aufzulösen, die entstehen, weil ein Bezeichner in mehreren verschiedenen Basisklassen gefunden wird!

Wenn es mit Membern nicht geht, müssen friends her (den Compiler dazu zu bringen, die Deklaration zu finden, ist allerdings nicht trivial):

template <std::size_t N> struct tag {};
template <std::size_t i, typename T, T v> struct holder_helper
{
    friend constexpr T get_(tag<i>, ...) { return v; }
};

template <typename L, typename J = typename make_value_list<std::size_t, L::size>::type> struct holder;
template <typename T, T... i, std::size_t... j> struct holder<value_list<T, i...>, value_list<std::size_t, j...>>
    : holder_helper<j, T, i>...
{};

void get_(...);
template <typename L, std::size_t N> struct at;
template <typename T, T... i, std::size_t N> struct at<value_list<T, i...>, N>
{
    static constexpr T value = get_(tag<N>(), holder<value_list<T, i...>>());
//                                             ^ Trick um holder_helper<...> als assozierte Klasse zu gewinnen
};

Alle diese Varianten können auch problemlos auf Typlisten umgeschrieben werden. Im Falle von Wertlisten besteht zusätzlich die Möglichkeit, diese Werte einfach in einem Array zu speichern.

template <typename T, T... i> struct value_list
{
    static constexpr T data[] = { i... };
};

...
template <typename L, std::size_t N> struct at;
template <typename T, T...i, std::size_t N> struct at<value_list<T, i...>, N>
{
    static constexpr T value = value_list<T, i...>::data[N];
};

Wie zuvor habe ich alle Varianten getestet, Hier gibts die Charts dazu.
Wiederum gibt es hierbei interessante Unterschiede zwischen beiden Compilern.

Ich bitte mal um kurze Rückmeldung, ob dieses Thema überhaupt jemanden interessiert...

Sone

Mich nicht wirklich (im Moment (!) ), aber du bist trotzdem ein Gott