[C++] Template metaprogramming (Brainf*ck interpreter)

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Jan 01, 2011 at 18:34

This forum is pretty dead, so I just thought I’d share something I wrote today:

int main()
{
    // Hello, World! in Brainf*ck (from wikipedia):
    /*  
    +++++ +++++             initialize counter (cell #0) to 10
    [                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
    ]                   
    > ++ .                  print 'H'
    > + .                   print 'e'
    +++++ ++ .              print 'l'
    .                       print 'l'
    +++ .                   print 'o'
    > ++ .                  print ' '
    << +++++ +++++ +++++ .  print 'W'
    > .                     print 'o'
    +++ .                   print 'r'
    ----- - .               print 'l'
    ----- --- .             print 'd'
    > + .                   print '!'
    > .                     print '\n' */

    // Template metaprogram translation
    typedef typelist
    <
        inc,inc,inc,inc,inc, inc,inc,inc,inc,inc,
        rep,
            nxt, inc,inc,inc,inc,inc, inc,inc,
            nxt, inc,inc,inc,inc,inc, inc,inc,inc,inc,inc,
            nxt, inc,inc,inc,
            nxt, inc,
            prv,prv,prv,prv, dec,
        end,
        nxt, inc,inc, out,
        nxt, inc, out,
        inc,inc,inc,inc,inc, inc,inc, out,
        out,
        inc,inc,inc, out,
        nxt, inc,inc, out,
        prv,prv, inc,inc,inc,inc,inc, inc,inc,inc,inc,inc, inc,inc,inc,inc,inc, out,
        nxt, out,
        inc,inc,inc, out,
        dec,dec,dec,dec,dec, dec, out,
        dec,dec,dec,dec,dec, dec,dec,dec, out,
        nxt, inc, out,
        nxt, out
    > program;

    print< run<program>::out >();
    std::cout << std::endl;
}

This outputs “Hello World!” when run. The string is computed at compile time by running that variadic template Brainf*ck metaprogram. Of course, you need a variadic template aware compiler, such as GCC version 4.4 and above to compile it.

The whole program is here:

#include <iostream>

//--------------------------------------------------------------
// Type List "Container"
//--------------------------------------------------------------
template <class...>
struct typelist; // GCC workaround

template <class Head, class... Tail>
struct typelist<Head, Tail...>
{
    typedef Head head;
    typedef typelist<Tail...> tail;
};


//--------------------------------------------------------------
// Cons for data
//--------------------------------------------------------------
template <char Head, class Tail>
struct dcons
{
    static const char head = Head;
    typedef Tail tail;
};


//--------------------------------------------------------------
// Data container (list of char)
//--------------------------------------------------------------
template <char...>
struct data; // GCC workaround

template <char Head, char... Tail>
struct data<Head, Tail...>
: dcons<Head, data<Tail...>> {};


//--------------------------------------------------------------
// Gets type N from typelist List.
//--------------------------------------------------------------
template <class List, int N>
struct at
{
    typedef typename at<typename List::tail, N - 1>::ret ret;
};

template <class List>
struct at<List, 0>
{
    typedef typename List::head ret;
};


//--------------------------------------------------------------
// Gets the char at data cell N from Data
//--------------------------------------------------------------
template <class Data, int N>
struct cell
{
    static const char val = cell<typename Data::tail, N - 1>::val;
};

template <class Data>
struct cell<Data, 0>
{
    static const char val = Data::head;
};


//--------------------------------------------------------------
// Data, but with cell N set to C
//--------------------------------------------------------------
template <class Data, int N, char C>
struct dset
: dcons<Data::head, dset<typename Data::tail, N - 1, C> > {};

template <class Data, char C>
struct dset<Data, 0, C>
: dcons<C, typename Data::tail> {};


//--------------------------------------------------------------
// Encapsulation of program state machine.
//--------------------------------------------------------------
template <class Prog, class Data, class Out, int PC, int DP>
struct state
{
    typedef Prog prog; // The program (typelist)
    typedef Data data; // The data
    typedef Out out; // The output (data)
    static const int pc = PC; // The program counter
    static const int dp = DP; // The data pointer

    static const char val = cell<data, dp>::val; // current value at dp
};

// Helper macros to avoid typename nonsense.
#define PROG(S) typename S::prog
#define DATA(S) typename S::data
#define OUT(S) typename S::out


//--------------------------------------------------------------
// Brainf*ck commands
//--------------------------------------------------------------
struct nxt {}; // move pointer right (next)
struct prv {}; // move pointer left (previous)
struct inc {}; // increment at pointer
struct dec {}; // decrement at pointer
struct out {}; // print character
struct rep {}; // while not 0 (repeat)
struct end {}; // end while


//--------------------------------------------------------------
// Next state after performing Cmd on S
//--------------------------------------------------------------
template <class S, class Cmd>
struct cmd { };

//--------------------------------------------------------------
// Performs move right command
//--------------------------------------------------------------
template <class S>
struct cmd<S, nxt>
: state<PROG(S), DATA(S), OUT(S),    S::pc + 1, S::dp + 1> {};

//--------------------------------------------------------------
// Performs move left command
//--------------------------------------------------------------
template <class S>
struct cmd<S, prv>
: state<PROG(S), DATA(S), OUT(S), S::pc + 1, S::dp - 1> {};

//--------------------------------------------------------------
// Performs increment command
//--------------------------------------------------------------
template <class S>
struct cmd<S, inc>
: state<PROG(S), dset<DATA(S), S::dp, S::val + 1>, OUT(S), S::pc + 1, S::dp> {};

//--------------------------------------------------------------
// Performs decrement command
//--------------------------------------------------------------
template <class S>
struct cmd<S, dec>
: state<PROG(S), dset<DATA(S), S::dp, S::val - 1>, OUT(S), S::pc + 1, S::dp> {};

//--------------------------------------------------------------
// Performs output command
//--------------------------------------------------------------
template <class S>
struct cmd<S, out>
: state<PROG(S), DATA(S), dcons<S::val, OUT(S)>, S::pc + 1, S::dp> {};

//--------------------------------------------------------------
// Performs while loop command
//--------------------------------------------------------------
template <class P, int PC>
struct fwd_jmp;

template <class P, int PC, class Cmd>
struct fwd_jmp_impl
: fwd_jmp<P, PC + 1> {};

template <class P, int PC>
struct fwd_jmp_impl<P, PC, rep>
: fwd_jmp<P, fwd_jmp<P, PC + 1>::ret> {};

template <class P, int PC>
struct fwd_jmp_impl<P, PC, end>
{
    static const int ret = PC + 1;
};

template <class P, int PC>
struct fwd_jmp
: fwd_jmp_impl<P, PC, typename at<P, PC>::ret> {};

template <class S, bool Done>
struct cmd_rep
: state<PROG(S), DATA(S), OUT(S), fwd_jmp<PROG(S), S::pc + 1>::ret, S::dp> {};

template <class S>
struct cmd_rep<S, false>
: state<PROG(S), DATA(S), OUT(S), S::pc + 1, S::dp> {};

template <class S>
struct cmd<S, rep>
: cmd_rep<S, S::val == 0> {};

//--------------------------------------------------------------
// Performs end loop command
//--------------------------------------------------------------
template <class P, int PC>
struct ret_jmp;

template <class P, int PC, class Cmd>
struct ret_jmp_impl
: ret_jmp<P, PC - 1> {};

template <class P, int PC>
struct ret_jmp_impl<P, PC, end>
: ret_jmp<P, ret_jmp<P, PC - 1>::ret - 2> {};

template <class P, int PC>
struct ret_jmp_impl<P, PC, rep>
{
    static const int ret = PC + 1;
};

template <class P, int PC>
struct ret_jmp
: ret_jmp_impl<P, PC, typename at<P, PC>::ret> {};

template <class S, bool Done>
struct cmd_end
: state<PROG(S), DATA(S), OUT(S), ret_jmp<PROG(S), S::pc - 1>::ret, S::dp> {};

template <class S>
struct cmd_end<S, true>
: state<PROG(S), DATA(S), OUT(S), S::pc + 1, S::dp> {};

template <class S>
struct cmd<S, end>
: cmd_end<S, S::val == 0> {};

//--------------------------------------------------------------
// Gets the length of a typelist.
//--------------------------------------------------------------
template <class List>
struct len
{
    static const int ret = len<typename List::tail>::ret + 1;
};

template <>
struct len< typelist<> >
{
    static const int ret = 0;
};


//--------------------------------------------------------------
// Runs a program from the given state and produces the final state
//--------------------------------------------------------------
template <class S>
struct run_impl;

template <class S, bool Done>
struct run_next
: run_impl<cmd<S, typename at<PROG(S), S::pc>::ret>> {};

template <class S>
struct run_next<S, true>
: S {};

template <class S>
struct run_impl
: run_next<S, S::pc == len<PROG(S)>::ret> {};

template <class P>
struct run
: run_impl< state<P, data<0, 0, 0, 0, 0>, data<>, 0, 0> > {};

//--------------------------------------------------------------
// Prints the program's output
//--------------------------------------------------------------
template <class Out>
void print()
{
    print<typename Out::tail>();
    std::cout << (char)Out::head;
}

template <>
void print<data<>>() {}


int main()
{
    // Hello, World! in Brainf*ck (from wikipedia):
    /*  
    +++++ +++++             initialize counter (cell #0) to 10
    [                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
    ]                   
    > ++ .                  print 'H'
    > + .                   print 'e'
    +++++ ++ .              print 'l'
    .                       print 'l'
    +++ .                   print 'o'
    > ++ .                  print ' '
    << +++++ +++++ +++++ .  print 'W'
    > .                     print 'o'
    +++ .                   print 'r'
    ----- - .               print 'l'
    ----- --- .             print 'd'
    > + .                   print '!'
    > .                     print '\n' */

    // Template metaprogram translation
    typedef typelist
    <
        inc,inc,inc,inc,inc, inc,inc,inc,inc,inc,
        rep,
            nxt, inc,inc,inc,inc,inc, inc,inc,
            nxt, inc,inc,inc,inc,inc, inc,inc,inc,inc,inc,
            nxt, inc,inc,inc,
            nxt, inc,
            prv,prv,prv,prv, dec,
        end,
        nxt, inc,inc, out,
        nxt, inc, out,
        inc,inc,inc,inc,inc, inc,inc, out,
        out,
        inc,inc,inc, out,
        nxt, inc,inc, out,
        prv,prv, inc,inc,inc,inc,inc, inc,inc,inc,inc,inc, inc,inc,inc,inc,inc, out,
        nxt, out,
        inc,inc,inc, out,
        dec,dec,dec,dec,dec, dec, out,
        dec,dec,dec,dec,dec, dec,dec,dec, out,
        nxt, inc, out,
        nxt, out
    > program;

    print< run<program>::out >();
    std::cout << std::endl;
}

Anyone else got any interesting metaprograms?

I’m thinking of writing a more interesting metaprogramming language next. Brainf*ck is a bit tedious to use ;)

8 Replies

Please log in or register to post a reply.

B2d356f97a3d0dec8ae2d8c1e1fa1c2d
0
Nerd_Skywalker 101 Jan 01, 2011 at 22:37

My brain! What have you done to it?!?!?

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jan 01, 2011 at 22:54

Hmm, I didn’t realize GCC has variadic templates now. Handy. Do you happen to know whether any version of Visual C++’s compiler offers that functionality?

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Jan 01, 2011 at 23:56

@Reedbeta

Hmm, I didn’t realize GCC has variadic templates now. Handy. Do you happen to know whether any version of Visual C++’s compiler offers that functionality?

I don’t think VC++ has it yet, but it does have a few C++0x things. I know they have rvalue references and lambdas in MSVC2010, not sure what else.

Even GCC support for variadic templates is a bit shaky, and you have to use a hack to get them to work properly.

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Jan 02, 2011 at 02:22

Proof!

http://ideone.com/wE7Pr

(I love that site)

8676d29610e6c98d6dd2d9c38528cd9c
0
alphadog 101 Jan 03, 2011 at 14:50

Ugh.

Just when I thought one couldn’t make things more complicated. You could add Ook to the list of futile efforts.

BTW, the worst “Hello, World!” I’ve ever seen is in SPL.

8676d29610e6c98d6dd2d9c38528cd9c
0
alphadog 101 Jan 03, 2011 at 14:52

And, for the “Hello, World!” aficionados:

http://helloworldsite.he.funpic.de/

36b416ed76cbaff49c8f6b7511458883
0
poita 101 Jan 03, 2011 at 18:54

@alphadog

Ugh.

Just when I thought one couldn’t make things more complicated. You could add Ook to the list of futile efforts.

BTW, the worst “Hello, World!” I’ve ever seen is in SPL.

I wrote it in D as well:

import std.stdio;
import std.string;

string brainfuck(string src, string input = "")()
{
  char[30000] d = '\0';
  int i = 0, j = 0;
  string ret = "";
  mixin(src.replace("]", "}")
           .replace("[", "while(d[i] != 0) {")
           .replace("+", "d[i]++;")
           .replace("-", "d[i]--;")
           .replace(">", "i++;")
           .replace("<", "i--;")
           .replace(".", "ret ~= d[i];")
           .replace(",", "d[i] = input[j++];"));
  return ret;
}

void main()
{
  enum hello = brainfuck!("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+."
                          "+++++++..+++.>++.<<+++++++++++++++.>.+++.------.-"
                          "-------.>+.")();
  enum multi = brainfuck!(",>,>++++++++[<------<------>>-]"
                          "<<[>[>+>+<<-]>>[<<+>>-]<<<-]"
                          ">>>++++++[<++++++++>-]<.", "24")();
  pragma(msg, hello); // "Hello World!"
  pragma(msg, multi); // "8"
}

D metaprogramming is too easy (this one gives the output as a compiler message).

Ead7e62802e296c5cb454f7094c1f9ce
0
anon 101 Jan 31, 2011 at 00:19

I did one a few years ago. It doesn’t even use c++0x features.

// This is a compile-time interpreter that runs BrainFuck code with , and .
// instructions removed, because it would be impossible to make the
// compilation interactive. All output and input is done in memory, but this
// restriction has no effect on the Turing-completness of the language. This
// is just a proof of a concept and is not intended to be practical or even
// useful at all.

// "Implementation defined" defined:
// The cell size is currently unsigned short int, but if you need to change
// it, you'll only need to fix the line:
// enum : unsigned short int {value=c};
// The memory is unlimited to the right and to the left, but moving to the
// left is a bit slower, especially when new cells need to be "grown". Even
// so, let's hope that no-one needs to think about performance issues with
// this implementation...

// Sorry for the lack of comments. It was clear to me when i wrote it...

// BEGIN CODE

// General utilities

// I'm quite proud of this is powerfull and simple construct
template <class a, class b>
struct Equal
{
    enum{value=false};
};
template <class a>
struct Equal<a,a>
{
    enum{value=true};
};


// For creating and manipulating a sequence of types.
struct Stopper {};


template <class a,class b>
struct Sequence
{
    typedef a value;
    typedef b tail;
};


template<class a>
struct CalculateLength
{
    enum{value = CalculateLength<typename a::tail>::value+1};
};
template<>
struct CalculateLength<Stopper>
{
    enum{value=0};
};


template<class a, int n>
struct SequenceElementAt
{
    typedef typename SequenceElementAt<typename a::tail,n-1>::value value;
};
template<class a>
struct SequenceElementAt<a,0>
{
    typedef typename a::value value;
};


// Appends b to the other end of the sequence a. The other end is trivial,
// it is Sequence<b,a>. This is the non-trivial case.
namespace NamespaceGrowFromTail
{
    template<class a,class b, int n>
    struct LoopThrough
    {
        typedef Sequence<typename SequenceElementAt<a,CalculateLength<a>::value-n>::value, typename LoopThrough<a,b,n-1>::value> value;
    };
    template<class a,class b>
    struct LoopThrough<a,b,0>
    {
        typedef Sequence<b,Stopper> value;
    };
    template<class a,class b>
    struct GrowFromTail
    {
        typedef typename LoopThrough<a,b,CalculateLength<a>::value>::value value;
    };
}
using NamespaceGrowFromTail::GrowFromTail;


template<unsigned char c>
struct MemCell
{
    enum : unsigned short int {value=c};
};


// Changes the value at n in memory to be b. Actually this defines a copy 
// of the memory with the change built in at creation time. This is to work 
// around the fact that our memory is read only.
template<class memory,int n,class b>
struct AssignValue
{
    typedef Sequence<typename memory::value,typename AssignValue<typename memory::tail,n-1,b>::value> value;
};
template<class memory,class b>
struct AssignValue<memory,0,b>
{
    typedef Sequence<b,typename memory::tail> value;
};


// Moving left means that the pointer moves towards the beginning of the
// memory. If the pointer is already 0, which is the smallest value, the
// memory grows another cell before the current "first" cell. In this case,
// the pointer remains zero, but it will now point to a cell that is to the
// left of the cell it pointed before. Because in Brainfuck the actual value of
// of the implicit pointer is inaccessible, this is not a problem.

// Moving right increases the pointer, except when it would be "out of bounds"
// of the current defined memory. In this case, another cell is grown to the
// tail end of the memory and the pointer is icreased so that it will point to
// the newly created cell.

// The Plus and minus instructions are simple in principle, but some details 
// are hidden in the AssignValue utility.
namespace Instructions
{
    struct Plus {}; // +
    struct Minus {}; // -
    struct MoveLeft {}; // <
    struct MoveRight {}; // >
    struct BeginLoop {}; // [
    struct EndLoop {}; // ]
    struct Halt {};
}


// Comments, who needs 'em? Here be confusion.
namespace NamespaceSearchMatchingPair
{
    template<class program,int start,int skip,class instruction>
    struct SearchMatchingBeginLoop
    {
        enum{instructionPointer=
            SearchMatchingBeginLoop<
                program,
                start-1,
                skip,
                typename SequenceElementAt<
                    program,
                    start-1
                >::value
            >::instructionPointer
        };
    };
    template<class program,int start,int skip>
    struct SearchMatchingBeginLoop<program,start,skip,Instructions::BeginLoop>
    {
        enum{instructionPointer=
            SearchMatchingBeginLoop<
                program,
                start-1,
                skip-1,
                typename SequenceElementAt<
                    program,
                    start-1
                >::value
            >::instructionPointer
        };
    };
    template<class program,int start,int skip>
    struct SearchMatchingBeginLoop<program,start,skip,Instructions::EndLoop>
    {
        enum{instructionPointer=
            SearchMatchingBeginLoop<
                program,
                start-1,
                skip+1,
                typename SequenceElementAt<
                    program,
                    start-1
                >::value
            >::instructionPointer
        };
    };
    template<class program,int start>
    struct SearchMatchingBeginLoop<program,start,0,Instructions::BeginLoop>
    {
        enum{instructionPointer=start};
    };

    template<class program,int start,int skip,class instruction>
    struct SearchMatchingEndLoop
    {
        enum{instructionPointer=
            SearchMatchingEndLoop<
                program,
                start+1,
                skip,
                typename SequenceElementAt<
                    program,
                    start+1
                >::value
            >::instructionPointer
        };
    };
    template<class program,int start,int skip>
    struct SearchMatchingEndLoop<program,start,skip,Instructions::BeginLoop>
    {
        enum{instructionPointer=
            SearchMatchingEndLoop<
                program,
                start+1,
                skip+1,
                typename SequenceElementAt<
                    program,
                    start+1
                >::value
            >::instructionPointer
        };
    };
    template<class program,int start,int skip>
    struct SearchMatchingEndLoop<program,start,skip,Instructions::EndLoop>
    {
        enum{instructionPointer=
            SearchMatchingEndLoop<
                program,
                start+1,
                skip-1,
                typename SequenceElementAt<
                    program,
                    start+1
                >::value
            >::instructionPointer
        };
    };
    template<class program,int start>
    struct SearchMatchingEndLoop<program,start,0,Instructions::EndLoop>
    {
        enum{instructionPointer=start};
    };

    template<class program,int start, class instruction>
    struct ChooseDirectionAndSearch{};
    template<class program,int start>
    struct ChooseDirectionAndSearch<program,start,Instructions::BeginLoop>
    {
        enum{instructionPointer=
            SearchMatchingEndLoop<
                program,
                start,
                -1,
                typename SequenceElementAt<
                    program,
                    start
                >::value
            >::instructionPointer
        };
    };
    template<class program,int start>
    struct ChooseDirectionAndSearch<program,start,Instructions::EndLoop>
    {
        enum{instructionPointer=
            SearchMatchingBeginLoop<
                program,
                start,
                -1,
                typename SequenceElementAt<
                    program,start
                >::value
            >::instructionPointer
        };
    };

    template<class program,int start>
    struct SearchMatchingPair
    {
        enum{instructionPointer=ChooseDirectionAndSearch<program,start,typename SequenceElementAt<program,start>::value>::instructionPointer};
    };
}
using NamespaceSearchMatchingPair::SearchMatchingPair;


namespace NamespaceExecuteInstruction
{
    template<class memory,int pointer,class instruction>
    struct ExecuteInstruction {};

    template<class mem,int pntr>
    struct ExecuteInstruction<mem,pntr,Instructions::MoveLeft>
    {
        typedef mem memory;
        enum{pointer=pntr-1};
    };
    template<class mem>
    struct ExecuteInstruction<mem,0,Instructions::MoveLeft>
    {
        typedef Sequence<MemCell<0>,mem> memory;
        enum{pointer=0};
    };

    template<class mem,int pntr,bool needToGrow>
    struct ExecuteMoveRight{};
    template<class mem,int pntr>
    struct ExecuteMoveRight<mem,pntr,false>
    {
        typedef mem memory;
    };

    template<class mem,int pntr>
    struct ExecuteMoveRight<mem,pntr,true>
    {
        typedef typename GrowFromTail<mem,MemCell<0> >::value memory;
    };

    template<class mem,int pntr>
    struct ExecuteInstruction<mem,pntr,Instructions::MoveRight>
    {
        typedef typename ExecuteMoveRight<mem,pntr,(CalculateLength<mem>::value==pntr+1)>::memory memory;
        enum{pointer=pntr+1};
    };

    template<class mem,int pntr>
    struct ExecuteInstruction<mem,pntr,Instructions::Minus>
    {
        typedef typename AssignValue<mem,pntr,MemCell< SequenceElementAt<mem,pntr>::value::value-1> >::value memory;
        enum{pointer=pntr};
    };

    template<class mem,int pntr>
    struct ExecuteInstruction<mem,pntr,Instructions::Plus>
    {
        typedef typename AssignValue<mem,pntr,MemCell< SequenceElementAt<mem,pntr>::value::value+1> >::value memory;
        enum{pointer=pntr};
    };

    template<class program,int instructionPntr,class memValue>
    struct ExecuteBeginLoop
    {
        enum{instructionPointer=instructionPntr+1};
    };

    template<class program,int instructionPntr>
    struct ExecuteBeginLoop<program,instructionPntr,MemCell<0> >
    {
        enum{instructionPointer=SearchMatchingPair<program,instructionPntr>::instructionPointer+1};
    };

    template<class program,int instructionPntr>
    struct ExecuteEndLoop
    {
        enum{instructionPointer=SearchMatchingPair<program,instructionPntr>::instructionPointer};
    };
}


namespace NamespaceExecuteProgram
{
    using NamespaceExecuteInstruction::ExecuteInstruction;
    using NamespaceExecuteInstruction::ExecuteBeginLoop;
    using NamespaceExecuteInstruction::ExecuteEndLoop;

    template<class program,int instructionPntr,class mem,int pntr,class instruction>
    struct ExecuteOneCycle
    {
        typedef typename ExecuteInstruction<mem,pntr,instruction>::memory memory;
        enum{pointer=ExecuteInstruction<mem,pntr,instruction>::pointer};
        enum{instructionPointer=instructionPntr+1};
    };
    template<class program,int instructionPntr,class mem,int pntr>
    struct ExecuteOneCycle<program,instructionPntr,mem,pntr,Instructions::BeginLoop>
    {
        typedef mem memory;
        enum{pointer=pntr};
        enum{instructionPointer=ExecuteBeginLoop<program,instructionPntr,typename SequenceElementAt<memory,pntr>::value>::instructionPointer};
    };
    template<class program,int instructionPntr,class mem,int pntr>
    struct ExecuteOneCycle<program,instructionPntr,mem,pntr,Instructions::EndLoop>
    {
        typedef mem memory;
        enum{pointer=pntr};
        enum{instructionPointer=ExecuteEndLoop<program,instructionPntr>::instructionPointer};
    };

    template<class program,int instructionPntr,class mem,int pntr,bool shouldHalt>
    struct ExecuteUntilHalt
    {
        typedef ExecuteOneCycle<program,instructionPntr,mem,pntr,typename SequenceElementAt<program,instructionPntr>::value> StateAfterOneCycle;
        typedef typename ExecuteUntilHalt<
            program,
            StateAfterOneCycle::instructionPointer,
            typename StateAfterOneCycle::memory,
            StateAfterOneCycle::pointer,
            Equal<
                typename SequenceElementAt<
                    program,
                    StateAfterOneCycle::instructionPointer
                >::value,
                Instructions::Halt
            >::value
        >::memory memory;
    };
    template<class program,int instructionPntr,class mem,int pntr>
    struct ExecuteUntilHalt<program,instructionPntr,mem,pntr,true>
    {
        typedef mem memory;
    };

    template<class program,class memory>
    struct ExecuteProgram
    {
        typedef typename ExecuteUntilHalt<
            program,
            0,
            memory,
            0,
            Equal<
                typename program,
                Instructions::Halt
            >::value
        >::memory memory;
    };
}
using NamespaceExecuteProgram::ExecuteProgram;


// Use a script to translate your BrainFuck source into this format.
typedef Sequence<Instructions::BeginLoop,Sequence<Instructions::MoveRight,Sequence<Instructions::MoveRight,Sequence<Instructions::MoveRight,Sequence<Instructions::Plus,Sequence<Instructions::MoveLeft,Sequence<Instructions::MoveLeft,Sequence<Instructions::MoveLeft,Sequence<Instructions::Minus,Sequence<Instructions::EndLoop,Sequence<Instructions::MoveRight,Sequence<Instructions::MoveRight,Sequence<Instructions::MoveRight,Sequence<Instructions::BeginLoop,Sequence<Instructions::MoveLeft,Sequence<Instructions::MoveLeft,Sequence<Instructions::BeginLoop,Sequence<Instructions::MoveLeft,Sequence<Instructions::Plus,Sequence<Instructions::MoveRight,Sequence<Instructions::MoveRight,Sequence<Instructions::Plus,Sequence<Instructions::MoveLeft,Sequence<Instructions::Minus,Sequence<Instructions::EndLoop,Sequence<Instructions::MoveRight,Sequence<Instructions::BeginLoop,Sequence<Instructions::MoveLeft,Sequence<Instructions::Plus,Sequence<Instructions::MoveRight,Sequence<Instructions::Minus,Sequence<Instructions::EndLoop,Sequence<Instructions::MoveRight,Sequence<Instructions::Minus,Sequence<Instructions::EndLoop,Sequence<Instructions::MoveLeft,Sequence<Instructions::MoveLeft,Sequence<Instructions::MoveLeft,Sequence<Instructions::Halt,Stopper> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > TestProgram;
typedef Sequence<MemCell<2>,Sequence<MemCell<13>,Sequence<MemCell<0>,Stopper> > > TestMemory;
int main()
{
    // This will cause a warning about an unreferenced local variable.
    ExecuteProgram<TestProgram,TestMemory>::memory result;
}
// phear teh powa ov recursin!