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 }
Is it the most perversive usage of C++ language? At least it is the one I have ever seen. I haven't read the STL sources, however :)
ReplyDeleteSTL is a piece of cake compared to some Boost libraries with heavy use of boost::mpl :)
ReplyDeleteYou probably win this codegolf by default : http://codegolf.stackexchange.com/questions/5359/implement-a-model-of-computation-using-a-type-system lol
ReplyDelete