What is Brainfuck?
Brainfuck is a proof-of-concept programming language designed by Urban Müller in 1993 with the goal of having the smallest possible compiler (currently at 240 bytes). Of course, Wikipedia has more information.
Executing Machine
The machine executing Brainfuck consists of a tape (with atleast 30,000 byte cells) initialized to zero, a pointer to a tape cell, a monitor (output stream), and a keyboard (input stream).
Commands
Brainfuck’s commands essentially describe a Turing Machine. There are commands to move the tape head left/right (<>), increment/decrement the current tape cell(+-), read/write the current cell(,.), and a loop construct ([]).
Now the Code (C#)
Op Codes
We simply define an enum to create a mapping between the Brainfuck Command and its symbol.
enum OpCodes : byte
{
IncrementAddress = (byte)'>',
DecrementAddress = (byte)'<',
IncrementValue = (byte)'+',
DecrementValue = (byte)'-',
Output = (byte)'.',
Input = (byte)',',
BeginLoop = (byte)'[',
EndLoop = (byte)']',
}
Partial State Machine
The state machine (shown without its methods) holds our “tape” (the memory array), the current instruction pointer, the data pointer, and a stack of instruction pointers used when we need to loop.
class StateMachine
{
//State
public int InstructionPointer { get; private set; }
private int _dataPointer;
private readonly byte[] _memory;
private readonly Stack<int> _nested;
public StateMachine(int memorySize)
{
InstructionPointer = 0;
_dataPointer = 0;
_memory = new byte[memorySize];
_nested = new Stack<int>();
}
}
BrainfuckRunner Actions
Our BrainfuckRunner class needs to have a mapping between Brainfuck Command (OpCode) and the function to invoke. This dictionary offers perhaps the best description of the Brainfuck language.
_actions = new Dictionary<byte, Action>
{
{(byte) OpCodes.BeginLoop, _stateMachine.BeginLoop},
{(byte) OpCodes.EndLoop, _stateMachine.EndLoop},
{(byte) OpCodes.IncrementValue, _stateMachine.IncrementValue},
{(byte) OpCodes.DecrementValue, _stateMachine.DecrementValue},
{(byte) OpCodes.IncrementAddress, _stateMachine.IncrementAddress},
{(byte) OpCodes.DecrementAddress, _stateMachine.DecrementAddress},
{(byte) OpCodes.Input, InputCurrentByte},
{(byte) OpCodes.Output, OutputCurrentByte},
};
BrainfuckRunner::Run
The run method takes a program, strips non command symbols from the text and treats it as an array of characters, since each command symbol is one byte. Actions are looked up in the dictionary, and invoked. At the end, we must output a new line to clear the output stream buffer.
public void Run(string program)
{
byte[] instructions = program.Select(c => (byte) c).Where(b => _actions.ContainsKey(b)).ToArray();
while (_stateMachine.InstructionPointer < instructions.Length)
{
Action action = _actions[instructions[_stateMachine.InstructionPointer]];
action.Invoke();
}
byte[] newLine = Environment.NewLine.Select(c => (byte) c).ToArray();
_output.Write(newLine, 0, newLine.Length);
}
Download
Download the full source, as well as a few sample Brainfuck scripts.