C++テンプレートメタプログラミングでbrainfuck

フィボナッチや階乗を計算させるような、一つの整数値が結果になるものは書いた事があったのですが、もっと複雑なものを書いてみたくなったので、チューリング完全性の証明もおまけでついてくるbrainfuckインタプリタを書いてみました。

#include <cstdio>

//////////
// List //
//////////
class Null {};

template<class T, class U>
struct List {
  typedef T Head;
  typedef U Tail;
};

////////////
// Length //
////////////
template<class L>
struct Length;

template<>
struct Length<Null> { enum { value = 0 }; };

template<class T, class U>
struct Length<List<T, U> > { enum { value = 1 + Length<U>::value }; };

/////////////
// Reverse //
/////////////
template<class T, class U>
struct ReverseIter;

template<class T>
struct ReverseIter<Null, T> {
  typedef T Result;
};

template<class T, class U, class V>
struct ReverseIter<List<U, V>, T> {
  typedef typename ReverseIter<V, List<U, T> >::Result Result;
};

template<class L>
struct Reverse {
  typedef typename ReverseIter<L, Null>::Result Result;
};

/////////
// Int //
/////////
template<int v>
struct Int { enum { value = v }; };

//////////
// Char //
//////////
template<char c>
struct Char { static const char value = c; };

////////////////
// MakeMemory //
////////////////
template<unsigned int n>
struct MakeMemory {
  typedef List<Int<0>, typename MakeMemory<n - 1>::Result> Result;
};

template<>
struct MakeMemory<0> {
  typedef Null Result;
};

/////////
// Ref //
/////////
template<class T, unsigned int n>
struct Ref {
  enum { value = Ref<typename T::Tail, n - 1>::value };
};

template<class H, class T>
struct Ref<List<H, T>, 0> {
  enum { value = H::value };
};

///////////////
// BrainFuck //
///////////////
template<class PH, class PT, class MH, class MT, class StdOut>
struct BF;

// Finish
template<class PH, class MH, class MT, class StdOut>
struct BF<PH, Null, MH, MT, StdOut> {
  typedef typename Reverse<StdOut>::Result Result;
};

// > command
template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'>'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BF<List<Char<'>'>, PH>, PT, List<U, MH>, V, StdOut>::Result Result;
};

// < command
template<class PH, class PT, class U, class V, class MT, class StdOut>
struct BF<PH, List<Char<'<'>, PT>, List<U, V>, MT, StdOut> {
  typedef typename BF<List<Char<'<'>, PH>, PT, V, List<U, MT>, StdOut>::Result Result;
};

// + command
template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'+'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BF<List<Char<'+'>, PH>, PT, MH, List<Int<U::value + 1>, V>, StdOut>::Result Result;
};

// - command
template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'-'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BF<List<Char<'-'>, PH>, PT, MH, List<Int<U::value - 1>, V>, StdOut>::Result Result;
};

// . command
template<class PH, class PT, class MH, class MT, class StdOut>
struct BF<PH, List<Char<'.'>, PT>, MH, MT, StdOut> {
  typedef typename BF<List<Char<'.'>, PH>, PT, MH, MT, List<Char<MT::Head::value>, StdOut> >::Result Result;
};

// [ command
template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFOBLOOP {
  typedef typename BFOBLOOP<List<typename PT::Head, PH>, typename PT::Tail, MH, MT, StdOut, level>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFOBLOOP<PH, PT, MH, MT, StdOut, 0> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFOBLOOP<PH, List<Char<'['>, PT>, MH, MT, StdOut, level> {
  typedef typename BFOBLOOP<List<Char<'['>, PH>, PT, MH, MT, StdOut, level + 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFOBLOOP<PH, List<Char<']'>, PT>, MH, MT, StdOut, level> {
  typedef typename BFOBLOOP<List<Char<']'>, PH>, PT, MH, MT, StdOut, level - 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, bool jump>
struct BFOB {
  typedef typename BFOBLOOP<PH, PT, MH, MT, StdOut, 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFOB<PH, PT, MH, MT, StdOut, false> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<'['>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BFOB<List<Char<'['>, PH>, PT, MH, List<U, V>, StdOut, U::value == 0>::Result Result;
};

// ] command
template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFCBLOOP {
  typedef typename BFCBLOOP<typename PH::Tail, List<typename PH::Head, PT>, MH, MT, StdOut, level>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFCBLOOP<PH, PT, MH, MT, StdOut, 0> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFCBLOOP<List<Char<']'>, PH>, PT, MH, MT, StdOut, level> {
  typedef typename BFCBLOOP<PH, List<Char<']'>, PT>, MH, MT, StdOut, level + 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, int level>
struct BFCBLOOP<List<Char<'['>, PH>, PT, MH, MT, StdOut, level> {
  typedef typename BFCBLOOP<PH, List<Char<'['>, PT>, MH, MT, StdOut, level - 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut, bool jump>
struct BFCB {
  typedef typename BFCBLOOP<typename PH::Tail, List<typename PH::Head, PT>, MH, MT, StdOut, 1>::Result Result;
};

template<class PH, class PT, class MH, class MT, class StdOut>
struct BFCB<PH, PT, MH, MT, StdOut, false> {
  typedef typename BF<PH, PT, MH, MT, StdOut>::Result Result;
};

template<class PH, class PT, class MH, class U, class V, class StdOut>
struct BF<PH, List<Char<']'>, PT>, MH, List<U, V>, StdOut> {
  typedef typename BFCB<List<Char<']'>, PH>, PT, MH, List<U, V>, StdOut, U::value != 0>::Result Result;
};

// read other character
template<class PH, class U, class PT, class MH, class MT, class StdOut>
struct BF<PH, List<U, PT>, MH, MT, StdOut> {
  typedef typename BF<List<U, PH>, PT, MH, MT, StdOut>::Result Result;
};

// interface
template<class Program>
struct BrainFuck {
  typedef typename BF<Null, Program, Null, MakeMemory<256>::Result, Null>::Result Result;
};

///////////////
// Execution //
///////////////
typedef List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'['>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'<'>, List<Char<'<'>, List<Char<'<'>, List<Char<'-'>, List<Char<']'>, List<Char<'>'>, List<Char<'.'>, List<Char<'>'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'.'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'>'>, List<Char<'-'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'<'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'+'>, List<Char<'+'>, List<Char<'+'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'-'>, List<Char<'.'>, List<Char<'>'>, List<Char<'+'>, List<Char<'.'>, Null > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > HelloWorld;
typedef BrainFuck<HelloWorld>::Result OutPut;

///////////
// Print //
///////////
template<class L>
inline void Print(L l);

template<>
inline void Print(Null l) { printf("\n"); }

template<class T, class U>
inline void Print(List<T, U> l) { printf("%c", T::value); Print(U()); }

int main() {
  Print(OutPut());
  return 0;
}

HelloWorldというのがbrainfuckプログラム本体です。Charの型リストになっています。
インタプリタ本体は

template<class PH, class PT, class MH, class MT, class StdOut>
struct BF;

で、実行しているプログラムとメモリをzipper(kinabaさんの記事参照)で持っています。PHとPTがプログラム、MHとMTがメモリで、PTの先頭がプログラムポインタ、MTの先頭がメモリポインタです。

標準出力もStdOutという名前でリストで持っていて、実行が終わると

// Finish
template<class PH, class MH, class MT, class StdOut>
struct BF<PH, Null, MH, MT, StdOut> {
  typedef typename Reverse<StdOut>::Result Result;
};

でReverseして返されます。

最後にオーバーローディングされたPrint関数を呼び出す事で結果の型リストを表示しています。-O2をかけるとネストした関数呼び出しがフラットになって、mainではputcharを連続して呼び出すだけのコードになります。

条件分岐のたびに別の特殊化したテンプレートを実体化する必要があり、またg++は末尾呼び出しの最適化を行ってくれないので、あまり実行ステップの多いプログラムを実行する事はできません。HelloWorldを実行するだけでもデフォルトのオプションではだめで、コンパイルは

g++ -ftemplate-depth-1000 brainfuck.cc

のようにしてテンプレート実体化の深さの制限を増やしてやる必要があります。

関数定義があちこちに散らばってしまうのでとても書きづらいですが、引数のパターンマッチングが出来るのはなかなか気持ちがいいですね。