Encode the compiled file into the given path.

Use the given CompilerOptions to parse, compile and optimize the text representation of a Brainfuck program into the IR. cOptsSource and cOptsOut in the compiler options are ignored.

Compilation summary for the user. It contains overview information and statistics about the compilation result.

Summarize a compiled program creating the CompilationSummary

Use CompilerOptions to read, compile, optimize, and save a program from/to the filesystem. Input and output files are provided by cOptsSource and cOptsOut.

Apply optimizations to the Unoptimized program turning. The optimizations that will be available are the ones specified by the CompilerOptions given.

Given a parsed program, turn it into an optimized one, but with the null optimization. Effectively this is only a type change.

Helper type to apply the Fuse optimization using a Monoid.

Apply the fusion optimization using the FusedProgram Monoid instance.

The fusion optimization consist of turning multiple instructions into one. For example if the original Brainfuck code contains ++++, this would be parsed as

Program [Inc 1 0, Inc 1 0, Inc 1 0, Inc 1 0]
 

but it would be fused to a single IR instruction: Inc 4 0.

>>> fusionOpt $ Program [Inc 1 0, Inc 1 0, Inc 1 0, Inc 1 0]
[Inc 4 0]

Similarly, other instructions, like Move, In, Out, Clear and Scan can be fused as long as the offset at which they must be applied is the same.

Non fusable operation remain unchanged:

>>> fusionOpt $ Program [Inc 1 0, Inc 1 1]
[Inc 1 0,Inc 1 1]

Helper function used to implement optimizations Iterate over all Program instructions searching for Loops. For each Loop apply f. If f returns a list of new operations, replace the original loop with the new instructions. If f returns Nothing, process recursively the loop instructions.

Basic optimization that turns the loop [-] into a single instruction Clear. Useful because clearing a memory position is a pretty common operation in Brainfuck and very expensive if treated as a loop.

>>> :set -XOverloadedStrings
>>> Right (res, _) = inMemoryCompile defaultCompilerOptions "[-]"
>>> res
[Clear 0]

Copy and multiply optimization. A very common usage of loops is to copy the value of a memory position to a different: [->>+<<] this will move the contents of the current memory position to places to the right, also clearing the original position to zero. If we change the number of + operations we get multiplication, if we have several groups of ++.. operations we get multiple copies. In the general case, for example:

>>> :set -XOverloadedStrings
>>> Right (res, _) = inMemoryCompile defaultCompilerOptions "[->+>++>++++<<<]"
>>> res
[Mul 1 0 1,Mul 2 0 2,Mul 4 0 3,Clear 0]

The original Brainfuck copies the current position one place to the right, doubles the current position two places to the right, and quadruples the current position three places to the right; finally zeroing the current position. With the mul optimization in this function, all that loop would be replaced by 4 instructions.

Implement the scan optimization. Another common operation in Brainfuck is to search for the first zero in the neighboring memory, either to the right or to the left [>] or [<]. These loops can be replaced for a more optimal search, represented as a single Scan Up or Scan Down instruction.

>>> scanOpt $ Program [Loop [Move 1]]
[Scan Up 0]

Helper datastructure to implement a stateful transformation in offsetInstructionOpt.

Start state for offsetInstructionOpt.

Implement the offset instruction optimization. This is probably the most complex optimization implemented in the library.

In streams of instructions between loops, there is no need to keep updating the current position if we can keep track of where the different operations should be applied. This is a trade-off of time (not updating the pointer) by space (keeping track of the offset in every operation). For example the following unoptimized code

>>> offsetInstructionOpt  $ Program [Loop [], Move 1, Inc 1 0, Move 2, Clear 0, Mul 2 0 1, Loop []]
[Loop [],Inc 1 1,Clear 3,Mul 2 3 1,Move 3,Loop []]

And the optimization eliminated one Move instruction. In general, for larger programs the gain will be more noticeable.

An important detail to take into account is that Scan operations break the stream of operations that can be optimized together, and turn the accumulated offset back to zero:

>>> offsetInstructionOpt  $ Program [Loop [], Move 1, Inc 1 0, Scan Up 0, Inc 0 2, Loop []]
[Loop [],Inc 1 1,Scan Up 1,Inc 0 2,Loop []]

Load a compiled program from saveCompilerOutput output.

Load a compiled program saved with saveCompilerOutput.

Command line flags to the Brainfuck compiler

Default compiler options: all optimizations, not verbose, no input or output files.

Compiler options: all optimizations off.

Parse a list of command line arguments

Parse a list of command line arguments printing errors to the stderr

Parse command line arguments printing errors to the stderr

This parser is used to implement the mul optimization. See mulOpt.

Parse successfully if the token satisfies the predicate.

Parse movement to the right (>), returning the offset value.

>>> Parsec.parse mrightP "" [Move 3]
Right 3

>>> Data.Either.isLeft $ Parsec.parse mrightP "" [Move (-1)]
True

Parsemovement to the left (<), returning the offset value.

>>> Parsec.parse mleftP "" [Move (-3)]
Right 3

>>> Data.Either.isLeft $ Parsec.parse mleftP "" [Move 1]
True

Parse increment, returning total increment.

>>> Parsec.parse plusP "" [Inc 3 0]
Right 3

>>> Data.Either.isLeft $ Parsec.parse plusP "" [Inc (-2) 0]
True

Parse decrement, returning total decrement.

>>> Parsec.parse minusP "" [Inc (-3) 0]
Right 3

>>> Data.Either.isLeft $ Parsec.parse minusP "" [Inc 2 0]
True

Sum the result of a parser applied repeatedly

>>> Parsec.parse (summedP plusP) "" [Inc 3 0, Inc 1 0, Inc (-4) 0]
Right 4

Full multiple copy/multiply operation parser. Returns the set of factors and relative, incremental offsets.

>>> Parsec.parse mulP "" [Inc (-1) 0, Move 1, Inc 2 0, Move 3, Inc 1 0, Move (-4)]
Right [(2,1),(1,3)]

Is the instruction a right movement?

Is the instruction a left movement?

Is the instruction an increment?

Is the instruction a decrement?

The abstract data type ParseError represents parse errors. It provides the source position (SourcePos) of the error and a list of error messages (Message). A ParseError can be returned by the function parse. ParseError is an instance of the Show and Eq classes.