BFO

BFO is the first known Brainfuck to Brainfuck optimizer and compression engine. It was created on June 6, 2012 by user:David.werecat. The most recent version can be downloaded from here.
== Optimization ==
The optimizer can optimize both standard Brainfuck and BF Joust code. Compressed files must be explicitly expanded for optimization with the -x option. There are several types of optimization available. Each level of optimization enables certain passes of optimization:
Level	Name 	Code Trimming	Redundant Bracket Removal	Short Range Optimization	Long Range Optimization	Other Optimizations
0 	Null Optimizer 	No 	No 	No 	No 	n/a
1 	Trimming Optimizer 	Yes 	No 	No 	No 	n/a
2 	Short Range Optimizer	Yes 	Yes 	Yes 	No 	n/a
3 	Long Range Optimizer 	Yes 	Yes 	No 	Yes 	n/a
4 	Full Optimizer 	Yes 	Yes 	Yes 	Yes 	Chooses either short range or long range
5 	Maximum Optimizer 	Yes 	Yes 	Yes 	Yes 	Checks all pass combinations
=== Code Trimming ===
The code trimming pass removes all comment characters and whitespace.
=== Redundant Bracket Removal ===
Redundant bracket removal is an optimization pass that checks for double brackets (eg. .). If double brackets are found, they are reduced to single brackets. Triple/quadruple/etc... brackets are also reduced.
=== Short Range Optimization ===
Short range optimization runs each subsection of the program on a temporary tape and rewrites all pointer movement and cell increment/decrement operations into the smallest possible form. Program subsections are separated by the ,.[] instructions. When the end of a section is reached, the optimizer finds the modified values on the tape and replaces the original subsection with code that optimally performs the same operations. This will automatically remove any NOPs (eg. +- or <>) and trim any extra operations at the end of the program. It also removes any unread changes to a cell that will be input to.
=== Long Range Optimization ===
Long range optimization is the same as short range optimization, but subsections are divided by loops only. When an IO operation occurs, the cell on which the IO is performed is updated and the pointer is left at that cell. Therefore, complete tape flushes only occur on loop bounds.
== Compression ==
BFO also has functions for encoding and decoding a type of compressed notation. BFO 1.0 only supports encoding with zeroing reduction and single instruction RLE. The compressed notation is as follows:
Notation 	Description
~ 	Represents a "set cell to zero operation". This is defined as identical to [-].
_# 	Represents a single instruction RLE. When expanded, the instruction will be repeated # times.
(___)# 	Represents a block RLE. When expanded, the block will be repeated # times.
/___/___/	Represents a macro definition. This statement must precede any use of the macro. The first blank holds the name of the macro and the second block holds the code for that macro. Note that macro names are case sensitive.
\___\ 	Represents a macro replacement. Expands to the code stored in macro name ___. Note that macro names are case sensitive.
Note that # represents a number, _ represents a single instruction and ___ represents any number of instructions.
== Interpreters ==
Starting in version 1.1, BFO can also interpret Brainfuck code. At present, it only has the fast (bounded tape) and huge (unbounded tape) interpreters. Future versions may also have debugging interpreters.
== External resources ==
* Version 1.0 of the optimizer
* Version 1.1 of the optimizer
Category:Implementations
Category:2012
Category:Brainfuck
Category:Ideas
Category:Programming techniques‏‎