BFO

From Esolang
Jump to: navigation, search

BFO is the first known Brainfuck to Brainfuck optimizer and compression engine. It was created on June 6, 2012 by David Catt (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