BrainFuck Interpreter

# JavaScript BrainFuck interpreter A simple [brainfuck](https://esolangs.org/wiki/Brainfuck) interpreter with some optimizations written in JavaScript. ## Language basics 1. The runtime has an infinite tape, representing the memory of the program. 2. The runtime maintains a program counter (`pc`) which tracks the position of the executing command in the program. 3. The runtime maintains a data pointer (cell counter `cc`), which points to a specific location on the tape. 4. There are 8 commands, made of only one character. Here are the commands (the pointer is `cc`): ```bf + : increment value in memory at the pointer by 1 - : decrement value in memory at the pointer by 1 > : move the pointer to the right by 1 < : move the pointer to the left by 1 . : output (print) the byte at the pointer , : read byte input and store it into the cell at the pointer [ : If the byte at the pointer is zero, jump it forward to the command after the matching ] command. ] : If the byte at pointer is nonzero, jump it back to the command after the matching [ command. ``` ## Optimizations 1. Operators `Ops` are introduced to translate the program into a different representation. 2. Each bracket `[` and `]` is associated with the position the pointer will jump to. Precalculating jumps turn the dynamic searches into a simple lookup. 3. Repeated sequences of instructions are replaced with a single operator which stores the number of times it needs to be executed. 4. Sequences of the type `[-]`, which subtract one to the cell the pointer is pointing to, until its value is 0, are directly replaced with a `Zero` operator, which directly assigns the valu of 0 to the current cell. 5. Loop unrolling: patterns of the type `[->++<]`, meaning: "move the pointer to the next cell, add 2, then move it back and subtract 1 to the current cell until its value is 0", can be simply replaced by simple mathematical operations of the type `cc[i+1] += NumberOfAddOperations * cc[i]` ## Tests Experimental results on some standard brainfuck programs (available in test folder) show excellent results after applying all optimizations with respect to an unoptimized interpreter with up to 9 times faster execution. Below is the execution in milliseconds of some sample programs from the unoptimized -> optimized interpreter (note that 'hanoi' and 'mandel' base time is already calculated on some partially optimized version of the interpreter, since a base interpreter encounters memory errors and is not able to run it) ``` 'hello': 206 -> 189 'bench': 38118 -> 7299 'hanoi': 46715 -> 5199 'mandelbrot': 91413 -> 44933 ``` --- Other ideas of optimizations can be found on [this website](http://calmerthanyouare.org/2015/01/07/optimizing-brainfuck.html) togheter with some other test results.