7
\$\begingroup\$

Inspired by this question, I decided to give it a try and implemented a brainfuck interpreter myself. It includes various improvements:

  • It's object-oriented and modular
  • Unlimited tape size
  • It includes a call stack (no seeking for opening parenthesis)
  • It allows stepping and debugging
  • It throws exceptions on errors

Tape

/// <summary>
/// One-sided, infinite, default-initialized Tape. </summary>
public class Tape<T>
{
    List<T> _tape;
    int _pos;

    public Tape()
    {
        _tape = new List<T>();
        _tape.Add(default(T));
        _pos = 0;
    }

    /// <summary>
    /// Currently selected cell's value. </summary>
    public T Value
    {
        get
        {
            return _tape[_pos];
        }
        set
        {
            _tape[_pos] = value;
        }
    }

    /// <summary>
    /// Step one cell to the left. </summary>
    public void StepLeft()
    {
        if (_pos == 0)
            throw new InvalidOperationException();
        else
            _pos--;
    }

    /// <summary>
    /// Step one cell to the right. </summary>
    public void StepRight()
    {
        _pos++;
        if (_pos == _tape.Count)
            _tape.Add(default(T));
    }

    /// <summary>
    /// Return a full snapshot of the tape without altering anything. </summary>
    public T[] ToArray()
    {
        return _tape.ToArray();
    }
}

Interpreter

public class BrainfuckInterpreter
{    
    Stream _program;
    Stream _input;
    Stream _output;
    Tape<byte> _tape;
    Stack<long> _callStack;

    /// <summary>
    /// Create a new BrainfuckInterpreter. </summary>
    /// <param name="program">
    /// Program to be executed. Must be readable and seekable.
    /// <param name="input">
    /// Must be readable. Can be null if the program doesn't take any input. </param>
    /// <param name="output">
    /// Must be writable. Can be null if the program doesn't produce output. </param>
    public BrainfuckInterpreter(Stream program, Stream input, Stream output)
    {
        _program = program;
        _input = input;
        _output = output;
        _tape = new Tape<byte>();
        _callStack = new Stack<long>();
    }

    /// <summary>
    /// Run the program until it terminates. </summary>
    public void Run()
    {
        while (Step());
    }

    /// <summary>
    /// Execute the next command. </summary>
    /// <returns>
    /// False if the program terminated. True otherwise. </returns>
    public bool Step()
    {
        int command = _program.ReadByte();
        switch (command)
        {
            default: throw new ArgumentException(); // Invalid command
            case -1: return false; // End reached
            case '+': _tape.Value++; break;
            case '-': _tape.Value--; break;
            case ',':
                int input = _input.ReadByte();
                if (input == -1) // Null-termination instead of error status
                    _tape.Value = 0;
                else
                    _tape.Value = (byte)input;
                break;
            case '.': _output.WriteByte(_tape.Value); break;
            case '>': _tape.StepRight(); break;
            case '<': _tape.StepLeft(); break;
            case '[': _callStack.Push(_program.Position); break;
            case ']':
                if (_tape.Value == 0)
                    _callStack.Pop();
                else
                    _program.Position = _callStack.Peek();
                break;
        }
        return true;
    }

    /// <summary>
    /// Print the tape for debug purposes.
    /// Format (hex): |XX|XX|XX|...|XX| </summary>
    public string Print()
    {
        string result = "|";
        foreach (var n in _tape.ToArray())
        {
            result += String.Format("{0:X2}|", n);
        }
        return result;
    }
}

Main routine (for testing)

Takes the program directly (not a filename) as first command line argument. Prints the tape's contents to stderr after each step.

public static class Program
{
    public static void Main(string[] args)
    {
        Stream program = new MemoryStream(args[0].Select(c => (byte)c).ToArray());
        var bf = new BrainfuckInterpreter(
            program,
            Console.OpenStandardInput(),
            Console.OpenStandardOutput()
        );
        while (bf.Step())
        {
            Console.Error.WriteLine(bf.Print());
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Did you test your code? The program [+[]] should terminate quickly because the + is never executed, while the program +[] should never terminate. \$\endgroup\$ – Roland Illig Oct 22 '16 at 10:48
  • \$\begingroup\$ @RolandIllig I hadn't read the brainfuck specification thoroughly, so my interpreter uses do {} while() instead of while() {}, as @200_success correctly determined. I indeed tested it with some self-written brainfuck, which I obviously also wrote in my "newly invented" dialect. It therefore works as expected, but it's not standard brainfuck. \$\endgroup\$ – Rainer P. Oct 22 '16 at 11:12
  • \$\begingroup\$ For future reference: Test your interpretation implementation on FizzBuzz in Brainfuck if that doesn't print FizzBuzz, you've done something wrong. \$\endgroup\$ – Simon Forsberg Oct 30 '17 at 19:47
5
\$\begingroup\$
switch (command)
{
    …
    case '[': _callStack.Push(_program.Position); break;
    case ']':
        if (_tape.Value == 0)
            _callStack.Pop();
        else
            _program.Position = _callStack.Peek();
        break;
}

A call stack in a tape-based language? Heresy!

Seriously, though, the code is wrong. You have implemented a do { … } while (_tape.Value != 0) loop instead of a while (_tape.Value != 0) { … } loop.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.