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 }

purely functional variadic fun

After reading A. Alexandrescu's book (Modern Design Generic Programming Patterns) (chapter on type lists) I decided to do something like that with variadic templates. They give more clear and concise code (no LISP-style conses and TYPELIST_N linearisers). I used lists of ints rather than types to simplify things.
These templates can lookup, append, reverse, sort, print and map functions over lists. Quite useless but purely functional :)

    1 #include <iostream>
    2 #include <limits.h>
    3 
    4 using std::cout;
    5 using std::endl;
    6 
    7 template <int...>
    8 struct int_list {};
    9 
   10 ///
   11 /// length of the list
   12 ///
   13 template <class list>
   14 struct length;
   15 
   16 template <>
   17 struct length<int_list<> > {
   18   enum {
   19     value = 0
   20   };
   21 };
   22 
   23 template <int head, int... tail>
   24 struct length<int_list<head, tail...> > {
   25   enum {
   26     value = 1 + length<int_list<tail...> >::value
   27   };
   28 };
   29 
   30 ///
   31 /// access by index
   32 ///
   33 template <int idx, class list>
   34 struct at;
   35 
   36 template <int head, int... tail>
   37 struct at<0, int_list<head, tail...> > {
   38   enum {result = head};
   39 };
   40 
   41 template <int idx, int head, int... tail>
   42 struct at<idx, int_list<head, tail...> > {
   43   enum {result = at<idx - 1, int_list<tail...> >::result};
   44 };
   45 
   46 ///
   47 /// find in list, returns index or -1 on fail
   48 ///
   49 template <int x, class list>
   50 struct lookup;
   51 
   52 // lookup fail
   53 template <int x>
   54 struct lookup<x, int_list<> > {
   55   enum {
   56     value = -1
   57   };
   58 };
   59 
   60 // step
   61 template <int x, int head, int... tail>
   62 struct lookup<x, int_list<head, tail...> > {
   63 private:
   64   enum {
   65     tmp = lookup<x, int_list<tail...> >::value
   66   };
   67 public:
   68   enum {
   69     value = (tmp == -1) ? -1 : (1 + tmp)
   70   };
   71 };
   72 
   73 // found
   74 template <int x, int... tail>
   75 struct lookup<x, int_list<x, tail...> > {
   76   enum {
   77     value = 0
   78   };
   79 };
   80 
   81 ///
   82 /// concatenate two lists
   83 ///
   84 template <class list1, class list2>
   85 struct concat;
   86 
   87 // even simplier than usually in functional languages
   88 template <int... list1, int... list2>
   89 struct concat<int_list<list1...>, int_list<list2...> > {
   90   typedef int_list<list1..., list2...> result;
   91 };
   92 
   93 ///
   94 /// replace all occurences of x with y
   95 ///
   96 template <int x, int y, class list>
   97 struct replace;
   98 
   99 // empty
  100 template <int x, int y>
  101 struct replace<x, y, int_list<> > {
  102   typedef int_list<> result;
  103 };
  104 
  105 // miss
  106 template <int x, int y, int head, int... tail>
  107 struct replace<x, y, int_list<head, tail...> > {
  108 private:
  109   typedef typename replace<x, y, int_list<tail...> >::result tmp;
  110 public:
  111   typedef typename concat<int_list<head>, tmp>::result result;
  112 };
  113 
  114 // found
  115 template <int x, int y, int... tail>
  116 struct replace<x, y, int_list<x, tail...> > {
  117 private:
  118   typedef typename replace<x, y, int_list<tail...> >::result tmp;
  119 public:
  120   typedef typename concat<int_list<y>, tmp>::result result;
  121 };
  122 
  123 
  124 ///
  125 /// map template over list
  126 ///
  127 template<template<int> class func, class list>
  128 struct map;
  129 
  130 template<template<int> class func>
  131 struct map<func, int_list<> > {
  132   typedef int_list<> result;
  133 };
  134 
  135 template<template<int> class func, int head, int... tail>
  136 struct map<func, int_list<head, tail...> > {
  137 private:
  138   enum {tmp_head = func<head>::value};
  139   typedef typename map<func, int_list<tail...> >::result tmp_tail;
  140 public:
  141   typedef typename concat<int_list<tmp_head>, tmp_tail>::result result;
  142 };
  143 
  144 ///
  145 /// print list contents
  146 ///
  147 
  148 template <class list>
  149 struct printer;
  150 
  151 template <>
  152 struct printer<int_list<> > {
  153   static inline void print()
  154   {
  155     cout << endl;
  156   };
  157 };
  158 
  159 template <int head, int... tail>
  160 struct printer<int_list<head, tail...> > {
  161   static inline void print()
  162   {
  163     cout << head << " ";
  164     printer<int_list<tail...> >::print();
  165   }
  166 };
  167 
  168 ///
  169 /// reverse list
  170 ///
  171 template <class list>
  172 struct reverse;
  173 
  174 template <>
  175 struct reverse<int_list<> > {
  176   typedef int_list<> result;
  177 };
  178 
  179 template <int head, int... tail>
  180 struct reverse<int_list<head, tail...> > {
  181 private:
  182   typedef typename reverse<int_list<tail...> >::result tmp;
  183 public:
  184   typedef typename concat<tmp, int_list<head> >::result result;
  185 };
  186 
  187 ///
  188 /// kill first occurance
  189 ///
  190 template <int x, class list>
  191 struct kill;
  192 
  193 /// good guarantee: will not compile if no occurance.
  194 template <int x, int head, int... tail>
  195 struct kill<x, int_list<head, tail...> > {
  196 private:
  197   typedef typename kill<x, int_list<tail...> >::result tmp;
  198 public:
  199   typedef typename concat<int_list<head>, tmp>::result result;
  200 };
  201 
  202 template <int x, int... tail>
  203 struct kill<x, int_list<x, tail...> > {
  204   typedef int_list<tail...> result;
  205 };
  206 
  207 ///
  208 /// min
  209 ///
  210 template <int cur, class list>
  211 struct min_helper;
  212 
  213 template <int cur>
  214 struct min_helper<cur, int_list<> > {
  215   enum {
  216     result = cur,
  217   };
  218 };
  219 
  220 template <int cur, int head, int... tail>
  221 struct min_helper<cur, int_list<head, tail...> > {
  222 private:
  223   enum {
  224     tmp = (cur < head) ? cur : head,
  225   };
  226 public:
  227   enum {
  228     result = min_helper<tmp, int_list<tail...> >::result,
  229   };
  230 };
  231 
  232 template <class list>
  233 struct min {
  234   enum {
  235     result = min_helper<INT_MAX, list>::result,
  236   };
  237 };
  238 
  239 ///
  240 /// sort a list
  241 ///
  242 template <class list>
  243 struct sort;
  244 
  245 template <>
  246 struct sort<int_list<> > {
  247   typedef int_list<> result;
  248 };
  249 
  250 template <int... ints>
  251 struct sort<int_list<ints...> > {
  252 private:
  253   enum {
  254     tmp_head = min<int_list<ints...>>::result
  255     };
  256   typedef typename sort<
  257     typename kill<tmp_head, int_list<ints...> >::result >::result tmp_tail;
  258 public:
  259   typedef typename concat<int_list<tmp_head>, tmp_tail>::result result;
  260 };
  261 
  262 template <int i>
  263 struct square {
  264   enum {
  265     value = i*i
  266   };
  267 };
  268 
  269 int main(void)
  270 {
  271   typedef int_list<1, 2, 3, 4> list_1234;
  272 
  273   cout << "list consists of values: ";
  274   printer<list_1234>::print();
  275 
  276   cout << "length is " << length<list_1234>::value << endl;
  277 
  278   cout << "at position 2 in the list stands " <<
  279     at<2, list_1234>::result << endl;
  280 
  281   cout << "minimum value is: " <<
  282     min<list_1234>::result << endl;
  283 
  284   typedef concat<list_1234, list_1234>::result list_12341234;
  285   cout << "concatenated with itself: ";
  286   printer<list_12341234>::print();
  287 
  288   cout << "with removed 2: ";
  289   printer<kill<2, list_1234>::result>::print();
  290 
  291   cout << "index of 3 is " <<
  292     lookup<3, list_1234>::value <<
  293     " and of absent 10 is " <<
  294     lookup<10, list_1234>::value << endl;
  295 
  296   cout << "list of squares is: ";
  297   printer<map<square, list_1234>::result>::print();
  298 
  299   typedef replace<2, 5, list_1234>::result list_1534;
  300   typedef replace<1, 8, list_1534>::result list_8534;
  301   cout << "after replacing 2->5 and 1->8 list numbers are: ";
  302   printer<list_8534>::print();
  303 
  304   typedef reverse<list_1234>::result list_4321;
  305   cout << "reversed list looks like this: ";
  306   printer<list_4321>::print();
  307 
  308   typedef int_list<6, 33, 5, 8, 5, 12, 27, 10, 1, 5, 7, 8, 13,
  309     56, 76, 34, 65, 23, 65, 67, 78, 22, 6, 4, 1, 4, 8, 6, 4, 3,
  310     11, 3, 10, 2, 5, 6, 3> long_list;
  311 
  312   cout << "long list is: ";
  313   printer<long_list>::print();
  314   cout << "after sort:   ";
  315   printer<sort<long_list>::result>::print();
  316 }
  317 

syntax hihglighting while posting code

While making previous post I had some problems with highlighting the code. I used emacs htmlize.el to highlight those piece. But it is bound to current emacs colors so I've even selected dark blogspot template to match my emacs colors. Emacs muse also uses highlight.el to produce highlighted source with tag. I googled a bit and found very small and useful utility to solve this problem. It is named "highlight" and can be found here. (all major Linux distros have it)

It can be used as simple as this:

% highlight -ls ide-anjuta variadic.cpp -o variadic.cpp.html 


where -l means put line numbers and "-s ide-anjuta" sets style

My previous post is already re-highlighted with it.

It generates quite readable css and html files. I've pasted (and tuned a bit to remove bright red comments) css in my blogspot template so I will be able to repaint my code in case of background color change in future.

And the last... Why the fuck there is no automatic code highlighter here? Hey Google, it would make lots of nerds very happy!

exploring variadic templates of C++0x

Yesterday I was thiking about how to try using variadic templates.

First thing that came to my mind was to define something 

like binary literals. It can be implemented without any variadic 

templates, but not too general or too verbose: link.

Variadic solution looks a bit better. Compilation time is almost

unaffected compared to numeric constant version. Also I had to use

some trickery to make it substitute "tail..." well as described here. 

Here is my code.

    1 #include <iostream>
    2 
    3 template <class Num, Num val, int... bitlist>
    4 class binary;
    5 
    6 template <class Num, Num val, int head, int... tail>
    7 class binary<Num, val, head, tail...>
    8 {
    9 public:
   10   static const Num value =
   11     binary<Num, val * 2 + head, tail...>::value;
   12 };
   13 
   14 template <class Num, Num val>
   15 class binary<Num, val> {
   16 public:
   17   static const Num value = val;
   18 };
   19 
   20 int main()
   21 {
   22 
   23   // large positive
   24   unsigned long long k = binary<unsigned long long,
   25     1, 1, 1, 1, 1, 1, 1, 1,
   26     1, 1, 1, 1, 1, 1, 1, 1,
   27     1, 1, 1, 1, 1, 1, 1, 1,
   28     1, 1, 1, 1, 1, 1, 1, 1,
   29     1, 1, 1, 1, 1, 1, 1, 1,
   30     1, 1, 1, 1, 1, 1, 1, 1,
   31     1, 1, 1, 1, 1, 1, 1, 1,
   32     1, 1, 1, 1, 1, 1, 1, 1>::value;
   33   std::cout << "k is " << k << std::endl;
   34 
   35   //small negative:
   36   char c = binary<char, 1, 1, 1, 1, 1, 1, 1, 1>::value;
   37   std::cout << "c is " << (int)c << std::endl;
   38 }