Skip to content

Instantly share code, notes, and snippets.

@mickey24
Created September 9, 2010 12:29
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mickey24/571808 to your computer and use it in GitHub Desktop.
Save mickey24/571808 to your computer and use it in GitHub Desktop.
A Brainf*ck interpreter using Boost.MPL
#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