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のソースによっては、テンプレート再帰数の上限に達してしまうので注意。