3. brainfuck-Compiler TMP style

brainfuck-Compiler TMP style

  • K

    camper schrieb:

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

    Definitiv 👍

    Das größte Problem ist vermutlich bei den Meisten, dass sie dir nicht folgen können. Ich muss auch ganz ehrlich zugeben, dass ich das Zeug mit Boost.PP gar nicht mehr verstehe, einfach, weil ich die Bibliothek nicht kenne.

    0
  • F

    Ich bin auch immer noch interessiert.

    0

  • Ein TMP Brainfuck Interpreter ist deutlich "schlimmer" als Brainfuck selbst 😃

    0
  • C
    Mod

    Hier eine neue Variante, die weitgehen ohne Rekursion Rekursion auskommt. Selbst der aktuelle Snapshot von g++ 4.8 (01.07.12) kann damit allerdings nicht umgehen, weil constexpr immer noch nicht ausreichend unterstützt wird:

    struct Foo {
    constexpr Foo() : a(0), b(a) {}
    int a, b;
};

constexpr auto x = Foo();

    ergibt

    g++-4.8.0-alpha20120701 (Gentoo 4.8.0_alpha20120701) 4.8.0-alpha20120701 20120701 (experimental)
test.cpp: In constructor ‘constexpr Foo::Foo()’:
test.cpp:2:35: sorry, unimplemented: use of the value of the object being constructed in a constant expression
     constexpr Foo() : a(0), b(a) {}
                                   ^
test.cpp: At global scope:
test.cpp:6:24: error: ‘constexpr Foo::Foo()’ called in a constant expression
 constexpr auto x = Foo();
                        ^

    (ich mag die neue Fehlerformatierung)

    Vorerst muss also clang herhalten, und das hat seine eigenen Probleme, so dass ich leider keine allzu langen bf-Programme testen kann.

    #include <cstddef>
#include <cstdio>
#include <utility>

#include <boost/preprocessor/punctuation/comma_if.hpp>
#include <boost/preprocessor/repetition/repeat.hpp>
#include <boost/preprocessor/repetition/enum_params.hpp>

constexpr char source[] = // Hello world von wikipedia
"+++++ +++++             initialize counter (cell #0) to 10"
"[                       use loop to set the next four cells to 70/100/30/10"
"    > +++++ ++              add  7 to cell #1"
"    > +++++ +++++           add 10 to cell #2"
"    > +++                   add  3 to cell #3"
"    > +                     add  1 to cell #4"
"    <<<< -                  decrement counter (cell #0)"
"]"
"> ++ .                  print 'H'"
"> + .                   print 'e'"
"+++++ ++ .              print 'l'"
".                       print 'l'"
"+++ .                   print 'o'"
"> ++ .                  print ' '"
"<< +++++ +++++ +++++ .  print 'W'"
"> .                     print 'o'"
"+++ .                   print 'r'"
"----- - .               print 'l'"
"----- --- .             print 'd'"
"> + .                   print '!'"
"> .                     print '\n'";

struct Env
{
    unsigned char data[32768];
    unsigned char* ptr;
} env = { {}, env.data };

template <typename T, T... i> struct value_list
{
    typedef T type;
    static constexpr std::size_t size = sizeof...( i );
    static constexpr T data[] = { i... };
};

#define MAKE_LIST_DIVIDER 256

template <typename L, typename M> struct repeat;

#define MAKE_LIST_EXPAND(z, n, text) ( n * sizeof...(i) + i )...,
template <typename T, T... i, T... j> struct repeat<value_list<T, i...>, value_list<T, j...>>
{
    typedef value_list<T, BOOST_PP_REPEAT(MAKE_LIST_DIVIDER, MAKE_LIST_EXPAND,) ( MAKE_LIST_DIVIDER * sizeof...(i) + j )...> type;
};

template <typename T, std::size_t N> struct make_value_list
{
    typedef typename repeat<typename make_value_list<T, N / MAKE_LIST_DIVIDER>::type, typename make_value_list<T, N % MAKE_LIST_DIVIDER>::type>::type type;
};

#define MAKE_LIST_SPECIALIZATION(z, n, text) \
template <typename T> struct make_value_list<T, n> \
{ \
    typedef value_list<T BOOST_PP_COMMA_IF(n) BOOST_PP_ENUM_PARAMS(n,)> type; \
};
BOOST_PP_REPEAT(MAKE_LIST_DIVIDER, MAKE_LIST_SPECIALIZATION,)

/***************************************************************************************************************************/

void at_(...);
constexpr std::size_t find_next_(...) { return std::size_t(-1); }
template <std::size_t N> struct tag {};

template <std::size_t N> struct ordered_tag : ordered_tag<N-1> {};
template <> struct ordered_tag<-1> {};
// 0-->N   ordered_tag::*
// N-->0   ordered_tag*

template <std::size_t N, typename T> struct tagged_value
{
    constexpr tagged_value(T v) : v(v) {}
    T v;
};

template <typename V, typename I = typename make_value_list<std::size_t, V::size>::type> struct partial_sum;
template <typename T, T... i, std::size_t... j> struct partial_sum<value_list<T, i...>, value_list<std::size_t, j...>>
    : tagged_value<j, T>...
{
    constexpr partial_sum() : tagged_value<j, T>( get<j - 1>() + i )... {}

    template <std::size_t N, typename = typename std::enable_if<( N != -1 ), T>::type, typename = void>
    constexpr T get() { return tagged_value<N, T>::v; }

    template <std::size_t N, typename = typename std::enable_if<( N == -1 ), T>::type>
    constexpr T get() { return 0; }
};

constexpr int grad(char c) { return c == '[' ? 1 : c != ']' ? 0 : -1; }
template <typename L = make_value_list<std::size_t, sizeof source>::type> struct get_nesting;
template <typename T, T... i> struct get_nesting<value_list<T, i...>>
{
    static constexpr auto tmp = partial_sum<value_list<int, grad(source[i])...>>();
    typedef value_list<T, tmp.template get<i-1>()...> type;
};

template <std::size_t i, typename T, T v> struct pair
{
    friend constexpr T at_(tag<i>, const pair&) { return v; }
    friend constexpr std::size_t find_next_(tag<v>, const pair&, int ordered_tag<i>::*) { return i; }
};

template <typename V, typename I = typename make_value_list<std::size_t, V::size>::type> struct bimap;
template <typename T, T... i, std::size_t... j> struct bimap<value_list<T, i...>, value_list<std::size_t, j...>>
    : pair<j, T, i>...
{};

constexpr auto nesting = bimap<get_nesting<>::type>();

constexpr bool execute(...) { return false; }

template <std::size_t start, std::size_t... i>
bool run(value_list<std::size_t, i...>)
{
    constexpr int level = at_( tag<start>(), nesting );
    constexpr std::size_t end = find_next_( tag<level-1>(), nesting, static_cast<int ordered_tag<start>::*>( nullptr ) );
    bool isns[] = { execute(tag<source[i]>(),
                            tag<( i >= start ) && ( i < end ) && ( at_( tag<i>(), nesting ) == level )>(),
                            tag<i>())... };
    return false;
}

bool execute(tag<'>'>, tag<true>, ...) { return ++env.ptr, false; }
bool execute(tag<'<'>, tag<true>, ...) { return --env.ptr, false; }
bool execute(tag<'+'>, tag<true>, ...) { return ++*env.ptr, false; }
bool execute(tag<'-'>, tag<true>, ...) { return --*env.ptr, false; }
bool execute(tag<','>, tag<true>, ...) { return *env.ptr = std::getchar(), false; }
bool execute(tag<'.'>, tag<true>, ...) { return std::putchar( *env.ptr ), false; }

constexpr auto index_list = make_value_list<std::size_t, sizeof source>::type();

template <std::size_t N>
bool execute(tag<'['>, tag<true>, tag<N>)
{
    while ( *env.ptr )
        run<N+1>(index_list);
    return false;
}

int main()
{
    run<0>(index_list);
}

    abgesehen von make_list ist ordered_tag die einzige rekursive Struktur, evtl. kann man das auch noch loswerden, falls die Überladungsauflösung anders erledigt werden kann.

    0
  • S

    camper schrieb:

    Hier eine neue Variante, die weitgehen ohne Rekursion Rekursion auskommt. Selbst der aktuelle Snapshot von g++ 4.8 (01.07.12) kann damit allerdings nicht umgehen, weil constexpr immer noch nicht ausreichend unterstützt wird:[cpp]struct Foo {
    constexpr Foo() : a(0), b(a) {}
    int a, b;
    };

    Wieso geht nicht so ein kleiner dirty hack?

    struct Foo
{
    constexpr Foo() {}

    int a = 0, 
        b = 0;
};

    Edit: sry, aber die CPP-Tags sind heute ziemlich stinkig.

    0
  • C
    Mod

    Sone schrieb:

    camper schrieb:

    Hier eine neue Variante, die weitgehen ohne Rekursion Rekursion auskommt. Selbst der aktuelle Snapshot von g++ 4.8 (01.07.12) kann damit allerdings nicht umgehen, weil constexpr immer noch nicht ausreichend unterstützt wird:

    struct Foo {
    constexpr Foo() : a(0), b(a) {}
    int a, b;
};

    Wieso geht nicht so ein kleiner dirty hack?

    struct Foo
{
    constexpr Foo() {}

    int a = 0, 
        b = 0;
};

    Edit: sry, aber die CPP-Tags sind heute ziemlich stinkig.

    Das ist nicht dirty, allerdings auch nicht das was ich will. Mir geht es darum, einen rekursiven Ausdruck direkt auszuschreiben, effektiv also in eine iterative Form zu überführen (und dadurch Speicher und Zeit zu sparen, weil weniger (bzw. billigere) Instantierungen durchgeführt werden (siehe oben Zeile 88).

    z.B.

    template <typename V> struct fib;
template <typename T, T... i> struct fib<value_list<T, i...>>
    : tagged_value<0,T>, tagged_value<1,T>, tagged_value<j+2, T>...
{
    constexpr partial_sum() : tagged_value<0,T>(0), tagged_value<1,T>(1), tagged_value<j+2, T>( tagged_value<j,T>::v + tagged_value<j+1,T>::v )... {}
};

    Ohne constexpr funktioniert das problemlos, das Objekt kann dann aber eben nicht in einem konstanten Ausdruck verwendet werden.
    Eigentlich sollte das auch mit Arrays funktionieren

    constexpr int fib[] = { 0, 1, fib[0]+fib[1], fib[1]+fib[2] /* usw. per packexpansion */ };

    Allerdings macht hier nicht einmal clang mit (wiederum: lässt man constexpr weg, gibt es keine Probleme)

    0
Anmelden zum Antworten