Brainf--k Interpreter

I'm a big fan of Brainf--k. In case you didn't know, Brainf--k (I'll just call it BF from now on) is a tiny esoteric language that only has 8 simple single-character commands, but managed to remain Turing Complete. (So anything that could be computed by a computed by a computer, can be computed by BF.) That's pretty neat! I knew I wanted a BF interpreter in Toast OS, but I didn't want a simple naive one that would take forever to do anything. So I set out to make an optimizing one.

Quick BF Overview

BF gives an array of 8-bit unsigned integers to a program, to function as the memory. It has a single pointer aiming at the first element, and this pointer can be moved left and right. Attempts to move beyond the bounds of this array will cause the program to crash.

BF only has 8 commands available to the program. Those 8 commands are:

• < / >: Move the pointer either to the left or right.
• + / -: Increment or decrement the current cell by one. The numbers wrap around, so 255 + 1 gives 0.
• [: If the current cell is non-zero, skip past the matching ].
• ]: Jump back to matching [.
• .: Print the current cell's value (as ASCII) to STDOUT.
• ,: Read a single byte from STDIN, storing it in the current cell.

That's it! Any other character is deemed a "comment" and will be ignored.

Optimizations

First things first, I parse the bf script into a full AST, and then apply optimizations directly to that AST using a method that recursively looks for known optimizable patterns in the source code, and swaps the nodes out.

Optimizations that the interpreter looks for:

• +++++ -> Add(5)
  Adjacent + or - chars can be simplified into a single arithmetic statement. This is the easiest optimization, and also among the most effective.

• >>>>> -> Move(5)
  Same thing with shifts - adjacent pointer moves can be combined into a single step.

• [-] -> Assign(0)
  This common pattern resets a cell to zero by looping and decrementing.

• Assign(x) Add(y) -> Assign(x + y)
  An add operation after any assignment can be merged into that assignment.

• Add(0) or Move(0)
  These can simply be trimmed. (They sometimes arise after optimizations.)

• [->+>+++<<] -> AddMultiply(1,1) AddMultiply(2,3) Assign(0)
  This bit of code will add 1x the current cell's value to the cell to the right, and 3x the current cell's value to the cell two to the right, whilst resetting the current cell to zero. This pattern is used a lot in math-heavy code, and so we optimize it.