Boost.MPLでBrainf*ckのプログラムをコンパイル時に動かしてみた

C++のテンプレートメタプログラミングライブラリ「Boost.MPL」について勉強中．新しいものを勉強する時はとりあえずそれを使ってBrainf*ckのインタプリタを作るのが学習法の定石なので，早速Boost.MPLを使ってBrainf*ckのインタプリタを書いた．

ソース

コンパイル中にBrainf*ckが実行される．

mpl_brainfuck.cc

#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;
}

Gistはこちら．http://gist.github.com/571808

実行方法

g++ 4.2.1 with Boost 1.40.0で動作確認済み．

$ g++ -ftemplate-depth-2000 -o mpl_brainfuck mpl_brainfuck.cc
$ ./mpl_brainfuck
Hello, world!

Brainf*ckのプログラムによってはテンプレートの再帰の深さが非常に深くなるので，コンパイル時に深さの上限を大きめに指定する必要がある．g++の場合は-ftemplate-depth-Nという引数で再帰の深さの上限を指定できる．
コンパイル時間が非常に長いので注意．私のMacBookで"Hello, world!"のBrainf*ckのプログラムをコンパイルした時は2分くらいかかった．

使ったBoost.MPLのライブラリ

boost::mpl::vector_c
- インタプリタの作業メモリ(Mem)
boost::mpl::string
- Brainf*ckプログラム(Program)や出力結果(Output)の文字列など
boost::mpl::eval_if_c
- テンプレートの特殊化をしなくても条件分岐が書けて便利
イテレータ関連
etc.

処理の流れ

主なテンプレート引数は以下の通り．

Program
- boost::mpl::string
- Brainf*ckのプログラム
Mem
- boost::mpl::vector_c
- Brainf*ckインタプリタの作業メモリ
Pc
- boost::mpl::stringを指すイテレータ
- プログラムカウンタ．次に実行するProgramの命令を指す
Ptr
- int
- 現在指しているMemの要素のインデックス
Output
- boost::mpl::string
- 現在までの出力結果

処理の流れは以下の通り．

Brainf*ckのプログラムをboost::mpl::stringで用意し，brainfuck::run<>のテンプレート引数に渡す．
brainfuck::run<>が内部でbrainfuck::detail::brainfuck_main<>のテンプレート引数にProgram，Mem，Pc，Ptr，Outputの初期状態を渡す．
プログラムカウンタがプログラムの終端に到達していればbrainfuck_main<>はそれまでの出力結果を返し，処理を終了する．そうでなければ次の命令に対応するbrainfuck::detail::brainfuck_one_step<>を呼び出す．
brainfuck_one_step<>が命令をひとつ実行し，Mem，Pc，Ptr，Outputを更新してbrainfuck_main<>を呼び出す．3に戻る．

感想など

今回作ったBrainf*ckのインタプリタ自体は全然役に立たないけど，テンプレートメタプログラミングのやり方やBoost.MPLの使い方がなんとなく理解できたので収穫はあった．
Boost.MPLにはC++テンプレートメタプログラミングをする上で便利な道具がたくさん用意されている．使わない手はないんじゃないかな．
テンプレートメタプログラミング全般に言えることだけど，コンパイル時のエラーメッセージがめちゃくちゃ分かりづらい．細かくテストをしながら進めていかないとデバッグが大変なことになる．
Memへのアクセスはint Ptrを使ってat_cで，プログラムへのアクセスはイテレータPcを使ってderefでやってるけど，混乱しやすいのでどちらかひとつの方法に統一した方がよかったかも．
~~誰かWhitespaceやってください．~~