brainfuck-Compiler TMP style
-
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
#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).
-
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?
-
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.
-
TMP ist wie eine funktionale Sprache, Iterationen muss man als Rekursion umschreiben.
@camper: Das ist mal was interessantes und herrlich sinnloses
. Aber ich mag gerade keinen neuen Compiler installieren, um mögliche Verbesserungen testen zu können. Mein jetziger g++ ist nur 4.4.5. 
-
auf ubuntu sudo apt-get install gcc-snapshot und er packt den 4.7er in ein seperates verzeichnis, alles bleibt wies ist
-
Könntest du erklären, wie du den String in ein template bekommen hast?
-
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.
-
Saubere Arbeit
Leider kenne ich mich mit boost::mpl überhaupt nicht aus, und kann dir daher schwer helfen. (Muss ich mir endlich mal ansehen.)
-
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.
-
*push*
Na, wie siehts aus? :p
-
Ich hab versucht, einen Interpreter zu schreiben... bin fast fertig (bin bei der Schleife
).
-
So, meine erste Version ist jetzt fertig. Bitte Verbesserungsvorschläge!
Das Hello-World Programm von Wikipedia wird problemlos interpretiert/** Brainfuck interpreter with Turing-completeness. @date: 16/05/2012 */ #include <iostream> #include <string> #include <deque> #include <stdexcept> #include <fstream> #include <cstdlib> #include <sstream> #include <unordered_multiset> typedef std::deque<char> list_type; list_type array(1); list_type::iterator iterator(array.begin()); void processString(std::string const& code, std::ostream& output, std::istream& input) { for(auto strIter(code.begin());strIter != code.end();++strIter) switch(*strIter) { case '.': output.put(*iterator); break; case ',': input.get(*iterator); break; case '>': { if(iterator + 1 == array.end()) array.push_back(0); ++iterator; } break; case '<': { if(iterator == array.begin()) array.push_front(0); --iterator; } break; case '+': ++*iterator; break; case '-': --*iterator; break; case '[': { auto braceClosePos = strIter + 1; for(size_t counter(0);;++braceClosePos) { if(*braceClosePos == '[') ++counter; if(*braceClosePos == ']') { if(counter) --counter; else break; } } std::string str(strIter + 1, braceClosePos); while(*iterator) processString(str, output, input); strIter = braceClosePos; } } } int main(int argn, char const** params) try { #ifdef N_DEBUG if(argn < 2) throw std::invalid_argument("No file to interpret. STOP."); std::ifstream stream(params[1]); #else std::ifstream stream("test.bff"); #endif if(!stream) throw std::runtime_error("Stream operation failure. Check, wether file isn't corrupted."); std::ostringstream rdbufstream; rdbufstream << stream.rdbuf(); { std::unordered_multiset<char> characterset(rdbufstream.str().begin(), rdbufstream.str().end()); if(characterset.count('[') != characterset.count(']')) throw std::logic_error("The amounts of opening and closing braces don't match!"); } processString(rdbufstream.str(), std::cout, std::cin); } catch(std::exception& e) { std::cerr << "\nERROR: " << e.what() << '\n'; } catch(...) { std::cerr << "\nAn unknown error occured.\n"; }EDit: Jetzt oben was verbessert...
EDit²: Schleifen-logik Fehler verbessert (danke Ethon)
-
Deine Logik bei Klammern stinkt.
[.........] ... ]Rate mal was da passiert.
-
Ethon schrieb:
Deine Logik bei Klammern stinkt.
[.........] ... ]Rate mal was da passiert.
Ich weiß, die letzte wird ignoriert
Aber das lässt sich einfach korigieren (man müsste nur die Anzahl öffnender und schließender Klammern vergleichen) und ist jetzt nicht wichtig.Das ROT13-Programm von Wikipedia funktioniert nicht
Edit: AHHHH, shit:
[..][..]funktioniert natürlich nicht
-
Kann man die Threads bitte trennen? Ich finde, die haben so ziemlich gar nichts miteinander zu tun.
-
So, editiert ^^
Jetzt dürfte jedes (syntaktisch korrekte) Programm funktionieren (und auch Ethons Problematik ist geklärt).
-
Brainfuck-Interpreter gibts auch hier: http://www.c-plusplus.net/forum/292057
314159265358979 schrieb:
Kann man die Threads bitte trennen?
Ja, bitte.
-
Bashar schrieb:
Brainfuck-Interpreter gibts auch hier: http://www.c-plusplus.net/forum/292057
Gibts da denn einen in C++? Ist doch C#
-
Und schon hab ich ein Ziel für Heute Nacht: Ein TMP-BF-Interpreter, also ein Interpreter im Compiler.
-
314159265358979 schrieb:
Und schon hab ich ein Ziel für Heute Nacht: Ein TMP-BF-Interpreter, also ein Interpreter im Compiler.
Hä? Kannstes nochmal erklären?
