A type-level brainfuck interpreter for the GNU C++ compiler

MetaBF.cpp

struct Z {};
template <typename N> struct S {};

struct Nil {};
template <typename X, typename Xs> struct Cons {};

template <typename Ls, typename C, typename Rs> struct Tape {};

struct Inc {};
struct Dec {};
struct Shl {};
struct Shr {};
template <typename Is> struct Loop {};


template <typename I, typename T> struct ExecOne_;
template <typename I, typename T> using ExecOne = typename ExecOne_<I,T>::type;

template <typename Is, typename T> struct ExecAll_;
template <typename Is, typename T> using ExecAll = typename ExecAll_<Is,T>::type;

template <typename Ls, typename C, typename Rs> struct ExecOne_<Inc,Tape<Ls,C,Rs>> { using type = Tape<Ls,S<C>,Rs>; };
template <typename Ls, typename C, typename Rs> struct ExecOne_<Dec,Tape<Ls,S<C>,Rs>> { using type = Tape<Ls,C,Rs>; };
template <typename C, typename Rs> struct ExecOne_<Shl,Tape<Nil,C,Rs>> { using type = Tape<Nil,Z,Cons<C,Rs>>; };
template <typename Ls, typename L, typename C, typename Rs> struct ExecOne_<Shl,Tape<Cons<L,Ls>,C,Rs>> { using type = Tape<Ls,L,Cons<C,Rs>>; };
template <typename Ls, typename C> struct ExecOne_<Shr,Tape<Ls,C,Nil>> { using type = Tape<Cons<C,Ls>,Z,Nil>; };
template <typename Ls, typename C, typename R, typename Rs> struct ExecOne_<Shr,Tape<Ls,C,Cons<R,Rs>>> { using type = Tape<Cons<C,Ls>,R,Rs>; };
template <typename Is, typename Ls, typename Rs> struct ExecOne_<Loop<Is>,Tape<Ls,Z,Rs>> { using type = Tape<Ls,Z,Rs>; };
template <typename Is, typename Ls, typename C, typename Rs> struct ExecOne_<Loop<Is>,Tape<Ls,S<C>,Rs>> { using type = ExecOne<Loop<Is>,ExecAll<Is,Tape<Ls,S<C>,Rs>>>; };

template <typename T> struct ExecAll_<Nil,T> { using type = T; };
template <typename I, typename Is, typename T> struct ExecAll_<Cons<I,Is>,T> { using type = ExecAll<Is,ExecOne<I,T>>; };

template <typename T> struct Result_;
template <typename T> using Result = typename Result_<T>::type;
template <typename Ls, typename C, typename Rs> struct Result_<Tape<Ls,C,Rs>> { using type = C; };

template <typename Is, typename T> using Eval = Result<ExecAll<Is,T>>;


using Times = Cons<Loop<Cons<Shr,Cons<Loop<Cons<Shr,Cons<Inc,Cons<Shr,Cons<Inc,Cons<Shl,Cons<Shl,Cons<Dec,Nil>>>>>>>>,Cons<Shr,Cons<Loop<Cons<Shl,Cons<Inc,Cons<Shr,Cons<Dec,Nil>>>>>,Cons<Shl,Cons<Shl,Cons<Dec,Nil>>>>>>>>,Cons<Shr,Cons<Shr,Cons<Shr,Nil>>>>;
using TimesTest = Tape<Nil,S<S<S<Z>>>,Cons<S<S<S<S<S<Z>>>>>,Nil>>;

template <typename N> int constexpr asInt {};
template <> int constexpr asInt<Z> {0};
template <typename N> int constexpr asInt<S<N>> {1 + asInt<N>};

static_assert(asInt<Eval<Times,TimesTest>> == 15);