Brainfuck is an esoteric programming language created by Urban Müller. It was originally developed as a toy language to create interpreters and compilers for and it is an example of a Turing tarpit(a language designed to be Turing complete while using the smallest possible number of commands).

Brainfuck operates on an array of 30,000 cells, each initially set to zero. The language uses a Turing tape model, where each cell can hold a single byte of data, and a data pointer starts at the beginning of this array. The language consists of only eight commands, minimalist yet Turing complete, meaning it can simulate any Turing machine and therefore perform any computation given enough time and memory.

anything other than these commands are considered comments and ignored.

to build and run: (don't forget to resize your terminal window)

$ cargo run --release -- <path-to-file>

or

$ cargo build --release
$ ./target/release/fucker examples/hanoi.b

to install the binary

$ cargo install --path .
$ fucker examples/mandel.b

You can enable debug mode with the -d or --debug flag to see how long parsing, optimizing, and executing take.

$ fucker examples/gold.b -d

if you want to disable some of the optimizations, you can use the following flags

$ fucker -f-no-optmize-scan  ...
$ fucker -f-no-optmize-clear ...
$ fucker -f-no-optmize-loops ...

you have always the option to check yourself

$ fucker --help

coming soon ✨

There are 12 node types, including Comment and NoOp, which are removed before execution

pub enum ASTNode {
    Incr(u8),
    Decr(u8),
    Next(usize),
    Prev(usize),
    Loop(Vec<ASTNode>),
    Input,
    Output,
    Set(u8),
    ScanLeft,
    ScanRight,
    Comment(char),
    NoOp,
}

consecutive Incr, Decr, Next, Prev nodes are optimized into single operand during parsing

[->>>+++<<]

can be thought of as

ASTNode::Loop(
    [
        ASTNode::Decrement(1),
        ASTNode::Next(3),
        ASTNode::Increment(3),
        ASTNode::Prev(2),
    ]
)

this reduces number of operations to be executed

[-]

the brainfuck snippet above is equivalent of the c code below, we can optimize this into a single operation, ASTNode::Set(0)

while(*ptr) --*ptr;

first  [<]
second [>]

these can be transpiled to C like this

// first
while(*ptr) --ptr;

// second
while(*ptr) ++ptr;

we can optimize these into ASTNode::ScanLeft and ASTNode::ScanRight, therefore reducing number of instructions

unused loops should be removed, such as

first [[[-]]]
second [[ ]]

can be thought of as

first  [-]
second

tested on Apple M1 silicon

• ARM compiler
• JIT compiler
• x86 compiler
• more AST optimizations