Boost.MPLでBrainfuckインタプリタを実装してみた
やってみました。まず構文木を作っているのでとても長いです。
ソース
/* Example: typedef brainfuck::interpret< mpl::string<'+++[', '>,-.', '<-]'>, // Source : +++[>,-.<-] mpl::string<'IBM'> // Input : IBM >::type output; // Output : HAL BOOST_MPL_ASSERT((mpl::equal<output, mpl::string<'HAL'> >)); */ #include <iostream> #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS #define BOOST_MPL_LIMIT_VECTOR_SIZE 30 #include <boost/mpl/advance.hpp> #include <boost/mpl/apply.hpp> #include <boost/mpl/at.hpp> #include <boost/mpl/begin_end.hpp> #include <boost/mpl/char.hpp> #include <boost/mpl/comparison.hpp> #include <boost/mpl/empty.hpp> #include <boost/mpl/erase.hpp> #include <boost/mpl/front.hpp> #include <boost/mpl/identity.hpp> #include <boost/mpl/insert.hpp> #include <boost/mpl/list.hpp> #include <boost/mpl/next_prior.hpp> #include <boost/mpl/pair.hpp> #include <boost/mpl/placeholders.hpp> #include <boost/mpl/pop_front.hpp> #include <boost/mpl/push_front.hpp> #include <boost/mpl/size.hpp> #include <boost/mpl/string.hpp> #include <boost/mpl/vector.hpp> namespace mpl = boost::mpl; using namespace boost::mpl::placeholders; namespace brainfuck { template <class F, class Pair> struct apply_first : mpl::pair< typename mpl::apply<F, typename Pair::first>::type, typename Pair::second > {}; // compile struct next {}; struct prev {}; struct inc {}; struct dec {}; struct put {}; struct get {}; template <class Program> struct loop {}; template <class Source, class Depth, bool Empty = mpl::empty<Source>::value> struct parse; template <class Cmd, class S, class Depth> struct parse_cmd : apply_first< mpl::push_front<_, Cmd>, typename parse<S, Depth>::type > {}; template <char C, class S, class Depth> struct parse_command { BOOST_MPL_ASSERT_MSG( false, BRAINFUCK_STRAY_CHARACTER_IN_PROGRAM, (mpl::char_<C>) ); }; template <class S, class Depth> struct parse_command<'>', S, Depth> : parse_cmd<next, S, Depth> {}; template <class S, class Depth> struct parse_command<'<', S, Depth> : parse_cmd<prev, S, Depth> {}; template <class S, class Depth> struct parse_command<'+', S, Depth> : parse_cmd<inc, S, Depth> {}; template <class S, class Depth> struct parse_command<'-', S, Depth> : parse_cmd<dec, S, Depth> {}; template <class S, class Depth> struct parse_command<'.', S, Depth> : parse_cmd<put, S, Depth> {}; template <class S, class Depth> struct parse_command<',', S, Depth> : parse_cmd<get, S, Depth> {}; template <class S, class Depth> struct parse_command<'[', S, Depth> { typedef typename parse<S, typename mpl::next<Depth>::type>::type result1; typedef typename apply_first< mpl::push_front<_, loop<typename result1::first> >, typename parse<typename result1::second, Depth>::type >::type type; }; template <class S, class Depth> struct parse_command<']', S, Depth> : mpl::pair<mpl::list<>, S> { BOOST_MPL_ASSERT_MSG( (mpl::greater<Depth, mpl::int_<0> >::value), BRAINFUCK_CKET_WITHOUT_BRA, () ); }; template <class Source, class Depth, bool Empty> struct parse { typedef typename mpl::front<Source>::type c; typedef typename parse_command< c::value, typename mpl::pop_front<Source>::type, Depth >::type type; }; template <class Source, class Depth> struct parse<Source, Depth, true> : mpl::pair<mpl::list<>, mpl::string<> > { BOOST_MPL_ASSERT_MSG( (mpl::equal_to<Depth, mpl::int_<0> >::value), BRAINFUCK_UNTERMINATED_BRA, () ); }; template <class Source> struct compile : parse<Source, mpl::int_<0> >::type::first {}; // execute template <class Array, class Index> struct memory { typedef memory type; typedef Array array; typedef Index index; }; template <class Memory> struct get_byte : mpl::at<typename Memory::array, typename Memory::index> {}; template <class Memory, class Byte> struct set_byte { typedef typename mpl::erase< typename Memory::array, typename mpl::advance< typename mpl::begin<typename Memory::array>::type, typename Memory::index >::type >::type array1; typedef typename mpl::insert< array1, typename mpl::advance< typename mpl::begin<array1>::type, typename Memory::index >::type, Byte >::type array2; typedef memory<array2, typename Memory::index> type; }; template <class Memory> struct do_next : memory< typename Memory::array, typename mpl::next<typename Memory::index>::type > { BOOST_MPL_ASSERT_MSG( ( mpl::less< typename mpl::next<typename Memory::index>::type, typename mpl::size<typename Memory::array>::type >::value ), BRAINFUCK_INDEX_OUT_OF_RANGE, (typename mpl::next<typename Memory::index>::type) ); }; template <class Memory> struct do_prev : memory< typename Memory::array, typename mpl::prior<typename Memory::index>::type > { BOOST_MPL_ASSERT_MSG( ( mpl::greater_equal< typename mpl::prior<typename Memory::index>::type, mpl::int_<0> >::value ), BRAINFUCK_INDEX_OUT_OF_RANGE, (typename mpl::prior<typename Memory::index>::type) ); }; template <class Memory> struct do_inc : set_byte< Memory, typename mpl::next<typename get_byte<Memory>::type>::type > {}; template <class Memory> struct do_dec : set_byte< Memory, typename mpl::prior<typename get_byte<Memory>::type>::type > {}; template <class Program, class Memory, class Input, class Output> struct machine { typedef machine type; typedef Program program; typedef Memory memory; typedef Input input; typedef Output output; }; template <class F, class Machine> struct apply_memory : machine< typename Machine::program, typename mpl::apply<F, typename Machine::memory>::type, typename Machine::input, typename Machine::output > {}; template < class Machine, bool ProgramEmpty = mpl::empty<typename Machine::program>::value > struct execute; template <class Command, class Machine> struct execute_command; template <class Machine> struct execute_command<next, Machine> : execute<typename apply_memory<do_next<_>, Machine>::type> {}; template <class Machine> struct execute_command<prev, Machine> : execute<typename apply_memory<do_prev<_>, Machine>::type> {}; template <class Machine> struct execute_command<inc, Machine> : execute<typename apply_memory<do_inc<_>, Machine>::type> {}; template <class Machine> struct execute_command<dec, Machine> : execute<typename apply_memory<do_dec<_>, Machine>::type> {}; template <class Machine> struct execute_command<put, Machine> : execute< machine< typename Machine::program, typename Machine::memory, typename Machine::input, typename mpl::push_back< typename Machine::output, typename get_byte<typename Machine::memory>::type >::type > > {}; template < class Machine, bool InputEmtpy = mpl::empty<typename Machine::input>::value > struct execute_get : execute< machine< typename Machine::program, typename set_byte< typename Machine::memory, typename mpl::front<typename Machine::input>::type >::type, typename mpl::pop_front<typename Machine::input>::type, typename Machine::output > > {}; template <class Machine> struct execute_get<Machine, true> : Machine { BOOST_MPL_ASSERT_MSG(false, BRAINFUCK_END_OF_INPUT, (mpl::string<>)); }; template <class Machine> struct execute_command<get, Machine> : execute_get<Machine> {}; template <class Program, class Machine> struct execute_loop { typedef typename execute< machine< Program, typename Machine::memory, typename Machine::input, typename Machine::output > >::type machine1; typedef typename execute_command< loop<Program>, machine< typename Machine::program, typename machine1::memory, typename machine1::input, typename machine1::output > >::type type; }; template <class Program, class Machine> struct execute_command<loop<Program>, Machine> : mpl::eval_if< mpl::equal_to< typename get_byte<typename Machine::memory>::type, mpl::char_<0> >, execute<Machine>, execute_loop<Program, Machine> > {}; template <class Machine, bool ProgramEmpty> struct execute : execute_command< typename mpl::front<typename Machine::program>::type, machine< typename mpl::pop_front<typename Machine::program>::type, typename Machine::memory, typename Machine::input, typename Machine::output > > {}; template <class Machine> struct execute<Machine, true> : Machine {}; // interpret template < class N, class T, bool NonPositive = mpl::less_equal<N, mpl::int_<0> >::value > struct replicate : mpl::push_front< typename replicate<typename mpl::prior<N>::type, T>::type, T > {}; template <class N, class T> struct replicate<N, T, true> : mpl::vector<> {}; template <class Source, class Input = mpl::string<> > struct interpret : execute< machine< typename compile<Source>::type, memory< typename replicate<mpl::int_<30>, mpl::char_<0> >::type, mpl::int_<0> >, Input, mpl::string<> > >::type::output {}; } // namespace brainfuck typedef brainfuck::interpret< mpl::string<'+++[', '>,-.', '<-]'>, mpl::string<'IBM'> >::type output; int main() { std::cout << mpl::c_str<output>::value << "\n"; }
出力
HAL
VC10+Boost1.45.0で動作確認しました。
Brainfuckのソースによっては、テンプレート再帰数の上限に達してしまうので注意。