c++.de :: brainfuck-Compiler TMP style

camper Mitglied 01:41:24 11.08.2011 Titel:

Da nichts los ist, habe ich mal zum Spass eine brainfuck-Compiler mittels TMP geschrieben. Leider ist die Template-Instantiierungstiefe sehr hoch, vielleicht hat ja jemand eine Idee, wie man das ein bisschen reduzieren kann

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168	#include <cstddef> #include <cstdio> #include <utility> #include <type_traits> #include <boost/mpl/at.hpp> #include <boost/mpl/if.hpp> #include <boost/mpl/front.hpp> #include <boost/mpl/has_key.hpp> #include <boost/mpl/identity.hpp> #include <boost/mpl/map.hpp> #include <boost/mpl/pair.hpp> #include <boost/mpl/pop_front.hpp> #include <boost/mpl/push_front.hpp> #include <boost/mpl/vector.hpp> using boost::mpl::at; using boost::mpl::if_; using boost::mpl::if_c; using boost::mpl::front; using boost::mpl::has_key; using boost::mpl::identity; using boost::mpl::map; using boost::mpl::pair; using boost::mpl::pop_front; using boost::mpl::push_front; using boost::mpl::vector; 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'"; template <std::ptrdiff_t N> struct mod_ptr_cmd { template <typename Env> static void run(Env& env) { env.ptr += N; } }; template <unsigned char N> struct mod_data_cmd { template <typename Env> static void run(Env& env) { env.ptr += N; } }; struct get_cmd { template <typename Env> static void run(Env& env) { env.ptr = std::getchar(); } }; struct put_cmd { template <typename Env> static void run(Env& env) { std::putchar( env.ptr ); } }; struct block_begin { template <typename Env> static void run(Env&) {} }; struct block_end { template <typename Env> static void run(Env&) {} }; typedef map< pair<std::integral_constant<char, '>'>, mod_ptr_cmd<1>>, pair<std::integral_constant<char, '<'>, mod_ptr_cmd<-1>>, pair<std::integral_constant<char, '+'>, mod_data_cmd<1>>, pair<std::integral_constant<char, '-'>, mod_data_cmd<-1>>, pair<std::integral_constant<char, ','>, get_cmd>, pair<std::integral_constant<char, '.'>, put_cmd>, pair<std::integral_constant<char, '['>, block_begin>, pair<std::integral_constant<char, ']'>, block_end>> commands; template <typename Command, char... Tail> struct fuse; template <typename Command, typename Next, char... Tail> struct compile : compile<Next, void, Tail...> { template <typename Env> static void run(Env& env) { Command::run( env ); compile<Next, void, Tail...>::run( env ); } }; template <typename Command, char... Tail> struct compile<Command, void, Tail...> : fuse<Command, Tail...> {}; template <char... Tail> struct compile<block_begin, void, Tail...> { typedef compile<void, void, Tail...> base; typedef typename front<typename base::tails>::type this_tail; typedef typename pop_front<typename base::tails>::type tails; template <typename Env> static void run(Env& env) { while ( env.ptr != 0 ) { base::run( env ); } this_tail::run( env ); } }; template <char... Tail> struct compile<block_end, void, Tail...> { typedef compile<void, void, Tail...> base; typedef typename push_front<typename base::tails, base>::type tails; template <typename Env> static void run(Env&) {} }; template <typename T, typename U> struct fuse_command : pair<T, U> {}; template <std::ptrdiff_t a, std::ptrdiff_t b> struct fuse_command<mod_ptr_cmd<a>, mod_ptr_cmd<b>> : pair<mod_ptr_cmd<a+b>, void> {}; template <unsigned char a, unsigned char b> struct fuse_command<mod_data_cmd<a>, mod_data_cmd<b>> : pair<mod_data_cmd<a+b>, void> {}; template <typename U> struct fuse_command<void, U> : pair<U, void> {}; template <typename Command, char c, char... Tail> struct fuse<Command, c, Tail...> : compile< typename fuse_command<Command, typename if_<has_key<commands, std::integral_constant<char, c>>, typename at<commands, std::integral_constant<char, c>>::type, void>::type>::first, typename fuse_command<Command, typename if_<has_key<commands, std::integral_constant<char, c>>, typename at<commands, std::integral_constant<char, c>>::type, void>::type>::second, Tail...> {}; template <typename Command> struct fuse<Command> { typedef vector<> tails; template <typename Env> static void run(Env& env) { Command::run( env ); } }; template <> struct fuse<void> { typedef vector<> tails; template <typename Env> static void run(Env&) {} }; template <char... src> struct program { template <typename Env> static void run(Env& env) { compile<void, void, src...>::run( env ); } }; // Ein bisschen Hilfsmagie um den String ins Template zu bekommen // wird irgendwann überflüssig template <std::size_t... i> struct indexes : identity<indexes<i...>> {}; template <typename T, typename U> struct concat : concat<typename T::type, typename U::type> {}; template <std::size_t... i, std::size_t... j> struct concat<indexes<i...>, indexes<j...>> : indexes<i..., ( j + sizeof... i )...> {}; template <typename T> struct twice : concat<T, T> {}; template <std::size_t N> struct make_indexes : concat<twice<make_indexes<(N / 2)>>, if_c<(N % 2 == 1), indexes<0>, indexes<>>> {}; template <> struct make_indexes<0> : indexes<> {}; template <typename = typename make_indexes<sizeof source - 1>::type> struct source_to_program; template <std::size_t... i> struct source_to_program<indexes<i...>> : identity<program<source[ i ]...>> {}; struct Environment { unsigned char data[32768]; unsigned char* ptr; }; int main() { Environment env = { {}, env.data }; source_to_program<>::type p; p.run( env ); };

Compiliert mit g++-4.6.1 -std=c++0x -Wall -Wextra -ftemplate-depth=2000 main.cpp (gcc 4.6 ist mindestens erfoderlich).

Unregistrierter

Hm

Mit TMP kann man Iteration aber auch nur mit "Rekursion" (also tiefer intantiieren) umsetzen, oder? Oder könnte man evtl die Befehle in eine Typliste transformieren und die iterativ abarbeiten?

Unregistrierter

fdfdg schrieb:

Hm

Mit TMP kann man Iteration aber auch nur mit "Rekursion" (also tiefer intantiieren) umsetzen, oder? Oder könnte man evtl die Befehle in eine Typliste transformieren und die iterativ abarbeiten?

Ne, die Tiefe der Typliste wäre ja auch linear zur Eingabe.

SeppJ Moderator 12:51:49 11.08.2011 Titel:

TMP ist wie eine funktionale Sprache, Iterationen muss man als Rekursion umschreiben.

@camper: Das ist mal was interessantes und herrlich sinnloses :live:

. Aber ich mag gerade keinen neuen Compiler installieren, um mögliche Verbesserungen testen zu können. Mein jetziger g++ ist nur 4.4.5. :-/

Unregistrierter

auf ubuntu sudo apt-get install gcc-snapshot und er packt den 4.7er in ein seperates verzeichnis, alles bleibt wies ist

GorbGorb Mitglied 20:17:43 11.08.2011 Titel:

Könntest du erklären, wie du den String in ein template bekommen hast?

SeppJ Moderator 21:05:38 11.08.2011 Titel:

GorbGorb schrieb:

Könntest du erklären, wie du den String in ein template bekommen hast?

Das ist das Geheimnis der constexpr (und warum man den GNU-Compiler 4.6 braucht). Damit wird der String zur Compilezeit auswertbar.

314159265358979 Mitglied 21:45:58 11.08.2011 Titel:

Saubere Arbeit :live:

Leider kenne ich mich mit boost::mpl überhaupt nicht aus, und kann dir daher schwer helfen. (Muss ich mir endlich mal ansehen.)

camper Mitglied 02:37:18 12.08.2011 Titel:

Ich habe eine Idee wie man das Ganze 1000mal effektiver machen kann (kein Scherz, damit wären dann auch kompliziertere Sachen machbar). Dummerweise unterstützt g++ noch keine constexpr Literale als statische Member, deshalb muss die Implementation noch ein bisschen warten.

314159265358979 Mitglied 10:05:26 16.05.2012 Titel:

*push*

Na, wie siehts aus?