template brainfuck compiler

Dreamt of being able to use inline brainfuck code snippets in your C++ applications? Dreams come true with this template brainfuck compiler!

These templates translate brainfuck code into many C++ inline functions.

First I started writing this by implementing umlimited memory (as tape in Turing machine) container which extended itself in both directions when needed. But then I realized that it is much more useful and flexible to follow the STL way and use iterators instead something concrete. They make it possible to use simple arrays as memory when user is sure that his program will never go out of range. Or even some persistent memory for enterprise brainfuck solutions :)

This code was tested on some examples from this collection. Unfortunately it is not possible to compile really large programs. At least with gcc which eats all my 2Gb of RAM in a few seconds. gcc-4.5 snapshot didn't make any observable difference. Maybe there is something that can be optimised in these templates... Comments are welcome!

p.s. program.b in the source below contains brainfuck source converted to template-friendly format: "[+-.]-" becomes "'[', '+', '-', '.', ']', '-'". This can be easily accomplished with sed.

    1 #include <iostream>
    2 #include <iterator>
    3 #include <algorithm>
    4 
    5 using namespace std;
    6 
    7 /// brainfuck program - a list of opcodes
    8 template <char... Ops>
    9 struct prog;
   10 
   11 ///
   12 /// separate loop body (text between matching '[' and ']')
   13 /// and remaining code. first opening brace should not be passed
   14 /// will fail to compile if no matching brace found.
   15 /// ex: "+>>]-->." input will give "+>>" and "-->."
   16 ///
   17 
   18 /// helper function
   19 /// <accumulator, nesting level, non-processed tail of code>
   20 template <class Acc, int Level, class Prog>
   21 struct split_helper;
   22 
   23 template <class Code>
   24 struct split {
   25   typedef typename split_helper<prog<>, 0, Code>::body body;
   26   typedef typename split_helper<prog<>, 0, Code>::remnant remnant;
   27 };
   28 
   29 /// case 1: found matching closing bracket
   30 template <char... Acc, char... Tail>
   31 struct split_helper<prog<Acc...>, 0, prog<']', Tail...> > {
   32   typedef prog<Acc...> body;
   33   typedef prog<Tail...> remnant;
   34 };
   35 
   36 /// case 2: found opening bracket
   37 template <char... Acc, int Level, char... Tail>
   38 struct split_helper<prog<Acc...>, Level, prog<'[', Tail...> > {
   39 private:
   40   typedef split_helper<prog<Acc..., '['>, Level + 1, prog<Tail...> > rec;
   41 public:
   42   typedef typename rec::body body;
   43   typedef typename rec::remnant remnant;
   44 };
   45 
   46 /// case 3: found non-matching closing bracket
   47 template <char... Acc, int Level, char... Tail>
   48 struct split_helper<prog<Acc...>, Level, prog<']', Tail...> > {
   49 private:
   50   typedef split_helper<prog<Acc..., ']'>, Level - 1, prog<Tail...> > rec;
   51 public:
   52   typedef typename rec::body body;
   53   typedef typename rec::remnant remnant;
   54 };
   55 
   56 /// case 4: general case, something other than braces
   57 template <char... Acc, int Level, char Head, char...Tail>
   58 struct split_helper<prog<Acc...>, Level, prog<Head, Tail...> > {
   59 private:
   60   typedef split_helper<prog<Acc..., Head>, Level, prog<Tail...> > rec;
   61 public:
   62   typedef typename rec::body body;
   63   typedef typename rec::remnant remnant;
   64 };
   65 
   66 ///
   67 /// main routine
   68 /// compile brainfuck program, producing class with static inline void
   69 /// member function with name 'run' which takes three parameters:
   70 /// bidirectional iterator which is used as memory, input iterator,
   71 /// used as source for ',' operations and output iterator that is used
   72 /// as destination for '.' operations.
   73 ///
   74 template <class Program>
   75 struct compile_helper;
   76 
   77 /// empty program case
   78 template <>
   79 struct compile_helper<prog<>> {
   80   template <class Mem, class In, class Out>
   81     static inline void run(Mem &mem, In &in, Out &out) {}
   82 };
   83 
   84 // '+' opcode
   85 template <char... Tail>
   86 struct compile_helper<prog<'+', Tail...> > {
   87   template <class Mem, class In, class Out>
   88   static inline void run(Mem &mem, In &in, Out &out) {
   89     ++*mem;
   90     compile_helper<prog<Tail...> >::run(mem, in, out);
   91   }
   92 };
   93 
   94 // '-' opcode
   95 template <char... Tail>
   96 struct compile_helper<prog<'-', Tail...> > {
   97   template <class Mem, class In, class Out>
   98   static inline void run(Mem &mem, In &in, Out &out) {
   99     --*mem;
  100     compile_helper<prog<Tail...> >::run(mem, in, out);
  101   }
  102 };
  103 
  104 // '>' opcode
  105 template <char... Tail>
  106 struct compile_helper<prog<'>', Tail...> > {
  107   template <class Mem, class In, class Out>
  108   static inline void run(Mem &mem, In &in, Out &out) {
  109     ++mem;
  110     compile_helper<prog<Tail...> >::run(mem, in, out);
  111   }
  112 };
  113 
  114 // '<' opcode
  115 template <char... Tail>
  116 struct compile_helper<prog<'<', Tail...> > {
  117   template <class Mem, class In, class Out>
  118   static inline void run(Mem &mem, In &in, Out &out) {
  119     --mem;
  120     compile_helper<prog<Tail...> >::run(mem, in, out);
  121   }
  122 };
  123 
  124 // '.' opcode
  125 template <char... Tail>
  126 struct compile_helper<prog<'.', Tail...> > {
  127   template <class Mem, class In, class Out>
  128   static inline void run(Mem &mem, In &in, Out &out) {
  129     *out = *mem;
  130     ++out;
  131     compile_helper<prog<Tail...> >::run(mem, in, out);
  132   }
  133 };
  134 
  135 // ',' opcode
  136 template <char... Tail>
  137 struct compile_helper<prog<',', Tail...> > {
  138   template <class Mem, class In, class Out>
  139   static inline void run(Mem &mem, In &in, Out &out) {
  140     *mem = *in;
  141     ++in;
  142     compile_helper<prog<Tail...> >::run(mem, in, out);
  143   }
  144 };
  145 
  146 // '[' opcode
  147 template <char... Tail>
  148 struct compile_helper<prog<'[', Tail...> > {
  149 private:
  150   typedef typename split<prog<Tail...> >::body body;
  151   typedef typename split<prog<Tail...> >::remnant remnant;
  152 public:
  153   template <class Mem, class In, class Out>
  154   static inline void run(Mem &mem, In &in, Out &out)
  155   {
  156     while (*mem) {
  157       compile_helper<body>::run(mem, in, out);
  158     }
  159     compile_helper<remnant>::run(mem, in, out);
  160   }
  161 };
  162 
  163 /// useful wrapper whose only function is to create copies of memory,
  164 /// input and output iterators to isolate changes by brainfuck code
  165 /// that uses them by reference
  166 template <class Program>
  167 struct compile {
  168   template <class Mem, class In, class Out>
  169   static inline void run(Mem mem, In in, Out out)
  170   {
  171     compile_helper<Program>::run(mem, in, out);
  172   }
  173 };
  174 
  175 int main(void)
  176 {
  177   const int memsize = 1000;
  178 
  179   char mem[memsize];
  180 
  181   fill(mem, mem + memsize, 0);
  182 
  183   typedef prog<
  184 #include "program.b"
  185   > program;
  186 
  187   compile<program>::run(mem, 0, ostream_iterator<char>(cout));
  188 }