[EliasWatson]

It would be interesting to modify this for optimizing BrainF programs. It has a very simple instruction set and there are lots of example programs available.

To avoid generating useless things like "++--", you could have the optimizer generate instructions that are translated to BrainF operations. So instead of ">>>--", the optimizer would generate "Move +3; Add -2".

[shoo]

there might not be that many opportunities to optimize brainfuck programs as the instruction set of the brainfuck virtual machine is so simple. arithmetic is unary, and staying within the brainfuck virtual machine doesn't provide a way to do any better than unary arithmetic.

on another hand, there are many opportunities for optimization when compiling brainfuck to an actual real world instruction set

e.g. suppose in your program you want to load the integer 36 into the current cell

a naive way to do this is to increment 36 times, e.g. `++++++++++++++++++++++++++++++++++++`.

if you can't guarantee that the initial value of the current cell is zero, then you could zero it first: `[-]++++++++++++++++++++++++++++++++++++`

if we're optimizing for code size, not instruction count, we could express this as a more complex, compact program: `[-]>[-]++++++[-<++++++>]<` -- assuming it is OK to use the cell one to the right of the pointer as working storage. this will run slower than the less compact naive program as it executes more instructions.

if compiling to some reasonable instruction set, there's likely a single non-BF instruction that lets you load the constant 36 into a register.

extra credit: implementing the optimising brainfuck-to-something compiler in brainfuck itself

[Someone]

> arithmetic is unary, and staying within the brainfuck virtual machine doesn't provide a way to do any better than unary arithmetic.

It won’t be efficient (but who cares about that in a true Turing machine?), but you can do binary/octal/decimal/whatever, using a series of cells each containing a number in the right range.

As an optimization, you can postpone any carries until you want to compare or print such numbers. Addition would ‘just’ loop over the cells in the numbers to be added, adding cells pairwise. For example, binary 11001 + 10101 would yield 21102.

[spartanatreyu]

Just as an exercise, you could use brainfuck with genetic algorithms and evolve the program that you want, then try to play with the fitness function to squeeze down whatever you don't want (code size, instruction set, etc...).

Then you could try to superoptimize yourself a solution and compare how close the evolved program was to the superoptimized program.

Could also be interesting with other esoteric languages like befunge or malbolge.