Created
September 9, 2010 12:29
-
-
Save mickey24/571808 to your computer and use it in GitHub Desktop.
A Brainf*ck interpreter using Boost.MPL
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
// change this parameter according to the length of your program | |
#define BOOST_MPL_LIMIT_STRING_SIZE 128 | |
#include <boost/mpl/at.hpp> | |
#include <boost/mpl/comparison.hpp> | |
#include <boost/mpl/erase.hpp> | |
#include <boost/mpl/equal.hpp> | |
#include <boost/mpl/insert.hpp> | |
#include <boost/mpl/string.hpp> | |
#include <boost/mpl/vector_c.hpp> | |
namespace brainfuck { | |
namespace detail { | |
// memory (with 8 cells) | |
typedef boost::mpl::vector_c<char, 0, 0, 0, 0, 0, 0, 0, 0> mem; | |
// error messages | |
// Invalid character in the program! | |
typedef boost::mpl::string< | |
'Inva', 'lid ', 'char', 'cter', ' in ', 'the ', 'prog', 'ram!' | |
> invalid_character; | |
// comma is not supported! | |
typedef boost::mpl::string< | |
'Comm','a is',' not',' sup','port','ed!' | |
> comma_error; | |
// forward declaration | |
template <class Program, class Mem, class Pc, int Ptr, class Output> | |
struct brainfuck_main; | |
// utility functions | |
// replace Mem[Ptr] with T | |
template <class Mem, int Ptr, class T> | |
struct replace_one { | |
// delete an old element | |
typedef typename boost::mpl::advance< | |
typename boost::mpl::begin<Mem>::type, boost::mpl::int_<Ptr> | |
>::type erase_itr; | |
typedef typename boost::mpl::erase<Mem, erase_itr>::type tmp_mem; | |
// insert a new element T | |
typedef typename boost::mpl::advance< | |
typename boost::mpl::begin<tmp_mem>::type, boost::mpl::int_<Ptr> | |
>::type insert_itr; | |
typedef typename boost::mpl::insert<tmp_mem, insert_itr, T>::type type; | |
}; | |
// increment Mem[Ptr] | |
template <class Mem, int Ptr> | |
struct increment_mem { | |
typedef typename replace_one< | |
Mem, Ptr, boost::mpl::char_<boost::mpl::at_c<Mem, Ptr>::type::value + 1> | |
>::type type; | |
}; | |
// decrement Mem[Ptr] | |
template <class Mem, int Ptr> | |
struct decrement_mem { | |
typedef typename replace_one< | |
Mem, Ptr, boost::mpl::char_<boost::mpl::at_c<Mem, Ptr>::type::value - 1> | |
>::type type; | |
}; | |
// while loop | |
// NextT should be boost::mpl::next or boost::mpl::prior | |
template <class Pc, template<class Iterator> class NextT, int Level = 0> | |
struct while_loop { | |
typedef typename NextT<Pc>::type next_pc; | |
typedef typename boost::mpl::deref<Pc>::type ins; | |
static const int next_level = | |
Level + (ins::value == '[' ? 1 : ins::value == ']' ? -1 : 0); | |
typedef typename boost::mpl::eval_if_c< | |
next_level == 0, | |
boost::mpl::identity<Pc>, | |
while_loop<next_pc, NextT, next_level> | |
>::type type; | |
}; | |
// operator functions | |
// invalid character | |
template <class Program, class Mem, class Pc, int Ptr, class Output, char Ins> | |
struct brainfuck_one_step { | |
typedef invalid_character::type type; | |
}; | |
// + | |
template <class Program, class Mem, class Pc, int Ptr, class Output> | |
struct brainfuck_one_step<Program, Mem, Pc, Ptr, Output, '+'> { | |
typedef typename brainfuck_main< | |
Program, typename increment_mem<Mem, Ptr>::type, | |
typename boost::mpl::next<Pc>::type, Ptr, Output | |
>::type type; | |
}; | |
// - | |
template <class Program, class Mem, class Pc, int Ptr, class Output> | |
struct brainfuck_one_step<Program, Mem, Pc, Ptr, Output, '-'> { | |
typedef typename brainfuck_main< | |
Program, typename decrement_mem<Mem, Ptr>::type, | |
typename boost::mpl::next<Pc>::type, Ptr, Output | |
>::type type; | |
}; | |
// > | |
template <class Program, class Mem, class Pc, int Ptr, class Output> | |
struct brainfuck_one_step<Program, Mem, Pc, Ptr, Output, '>'> { | |
typedef typename brainfuck_main< | |
Program, Mem, typename boost::mpl::next<Pc>::type, Ptr + 1, Output | |
>::type type; | |
}; | |
// < | |
template <class Program, class Mem, class Pc, int Ptr, class Output> | |
struct brainfuck_one_step<Program, Mem, Pc, Ptr, Output, '<'> { | |
typedef typename brainfuck_main< | |
Program, Mem, typename boost::mpl::next<Pc>::type, Ptr - 1, Output | |
>::type type; | |
}; | |
// . | |
template <class Program, class Mem, class Pc, int Ptr, class Output> | |
struct brainfuck_one_step<Program, Mem, Pc, Ptr, Output, '.'> { | |
typedef typename brainfuck_main< | |
Program, Mem, typename boost::mpl::next<Pc>::type, Ptr, | |
typename boost::mpl::push_back< | |
Output, typename boost::mpl::at_c<Mem, Ptr>::type | |
>::type | |
>::type type; | |
}; | |
// , | |
template <class Program, class Mem, class Pc, int Ptr, class Output> | |
struct brainfuck_one_step<Program, Mem, Pc, Ptr, Output, ','> { | |
// not implemented yet | |
typedef typename comma_error::type type; | |
}; | |
// [ | |
template <class Program, class Mem, class Pc, int Ptr, class Output> | |
struct brainfuck_one_step<Program, Mem, Pc, Ptr, Output, '['> { | |
typedef typename brainfuck_main< | |
Program, Mem, typename boost::mpl::next< | |
typename boost::mpl::eval_if_c< | |
boost::mpl::at_c<Mem, Ptr>::type::value == 0, | |
while_loop<Pc, boost::mpl::next>, | |
boost::mpl::identity<Pc> | |
>::type | |
>::type, | |
Ptr, Output | |
>::type type; | |
}; | |
// ] | |
template <class Program, class Mem, class Pc, int Ptr, class Output> | |
struct brainfuck_one_step<Program, Mem, Pc, Ptr, Output, ']'> { | |
typedef typename brainfuck_main< | |
Program, Mem, typename boost::mpl::next< | |
typename boost::mpl::eval_if_c< | |
boost::mpl::at_c<Mem, Ptr>::type::value != 0, | |
while_loop<Pc, boost::mpl::prior>, | |
boost::mpl::identity<Pc> | |
>::type | |
>::type, | |
Ptr, Output | |
>::type type; | |
}; | |
// brainf*ck main | |
template <class Program, class Mem, class Pc, int Ptr, class Output> | |
struct brainfuck_main { | |
typedef typename boost::mpl::eval_if_c< | |
boost::is_same<Pc, typename boost::mpl::end<Program>::type>::value, | |
Output, | |
brainfuck_one_step< | |
Program, Mem, Pc, Ptr, Output, boost::mpl::deref<Pc>::type::value | |
> | |
>::type type; | |
}; | |
} // namespace detail | |
// brainf*ck runner | |
// run a brainf*ck program and return a result string | |
template <class Program> | |
struct run { | |
typedef typename detail::brainfuck_main< | |
Program, detail::mem, typename boost::mpl::begin<Program>::type, | |
0, boost::mpl::string<> | |
>::type type; | |
}; | |
} // namespace brainfuck | |
// brainf*ck examples | |
// A | |
// +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++. | |
typedef boost::mpl::string< | |
'++++','++++','++++','++++','++++','++++','++++','++++','++++','++++','++++', | |
'++++','++++','++++','++++','++++','+.' | |
> A; | |
// A with a loop | |
// ++++++++[>++++++++<-]>+. | |
typedef boost::mpl::string< | |
'++++','++++','[>++','++++','++<-',']>+.' | |
> A_with_loop; | |
// Hello, world! | |
// +++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-. | |
// ------------.<++++++++.--------.+++.------.--------.>+. | |
typedef boost::mpl::string< | |
'++++','++++','+[>+','++++','+++>','++++','++++','+++>','++++','+<<<','-]>.', | |
'>++.','++++','+++.','.+++','.>-.','----','----','----','.<++','++++','++.-', | |
'----','---.','+++.','----','--.-','----','---.','>+.' | |
> hello; | |
// main | |
int main(int argc, const char *argv[]) { | |
// run a brainf*ck program | |
typedef brainfuck::run<hello>::type result; | |
std::cout << boost::mpl::c_str<result>::value << std::endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment