Brainfuck interpreter in C++11

KJBrainfuck.cpp

/*
 Copyright (c) 2015 Kristopher Johnson

 Permission is hereby granted, free of charge, to any person obtaining
 a copy of this software and associated documentation files (the
 "Software"), to deal in the Software without restriction, including
 without limitation the rights to use, copy, modify, merge, publish,
 distribute, sublicense, and/or sell copies of the Software, and to
 permit persons to whom the Software is furnished to do so, subject to
 the following conditions:

 The above copyright notice and this permission notice shall be
 included in all copies or substantial portions of the Software.

 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include <fstream>
#include <iostream>
#include <stack>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::exception;
using std::ifstream;
using std::ios;
using std::runtime_error;
using std::stack;
using std::string;
using std::unordered_map;
using std::unordered_set;
using std::vector;

namespace KJBrainfuck
{
    template<typename Cell = int8_t>
    class Storage
    {
    public:
        Storage(): cells(ExtensionSize, Cell(0)) {
            pointer = cells.begin();
        }

        Storage(const Storage&) = delete;
        Storage& operator=(const Storage&) = delete;

        Cell value() const        { return *pointer; }

        void setValue(Cell value) { *pointer = value; }

        void incrementValue()     { ++(*pointer); }

        void decrementValue()     { --(*pointer); }

        void movePointerRight() {
            ++pointer;
            if (pointer == cells.end()) {
                auto oldSize = cells.size();
                cells.resize(oldSize + ExtensionSize);
                pointer = cells.begin() + oldSize;
            }
        }

        void movePointerLeft() {
            if (pointer == cells.begin())
                throw runtime_error("attempt to move pointer left of start position");

            --pointer;
        }

    private:
        using Cells = vector<Cell>;
        using Pointer = typename Cells::iterator;

        Cells cells;
        Pointer pointer;

        // Number of cells by which array is extended when necessary
        static const typename Cells::size_type ExtensionSize = 1024;
    };

    template<typename Cell = int8_t>
    class Machine
    {
    public:
        explicit Machine(const string& sourceFilePath) {
            loadProgramFromFilePath(sourceFilePath);
        }

        void executeProgram() {
            Tape tape;
            ProgramCounter pc = 0;
            while (pc < program.size()) {
                auto instruction = program[pc++];
                switch (instruction) {
                    case '>': tape.movePointerRight();                            break;
                    case '<': tape.movePointerLeft();                             break;
                    case '+': tape.incrementValue();                              break;
                    case '-': tape.decrementValue();                              break;
                    case '.': writeValue(tape);                                   break;
                    case ',': readValue(tape);                                    break;
                    case '[': if (tape.value() == 0) pc = matchingCloseBrace[pc]; break;
                    case ']': if (tape.value() != 0) pc = matchingOpenBrace[pc];  break;
                    default:  /* ignore other characters */                       break;
                }
            }
        }

    private:
        using Tape = Storage<Cell>;
        using Instruction = char;
        using Program = vector<Instruction>;
        using ProgramCounter = Program::size_type;
        using ProgramCounterMap = unordered_map<ProgramCounter, ProgramCounter>;

        Program program;

        // Bidirectional mapping of '[' and ']' pairs
        ProgramCounterMap matchingOpenBrace;
        ProgramCounterMap matchingCloseBrace;

        void writeValue(const Tape& tape) const {
            auto c = static_cast<char>(tape.value());
            if (c == '\n')
                cout << endl;
            else
                cout.put(c);
        }

        void readValue(Tape& tape) const {
            // This Brainfuck implementation makes no change to the
            // cell if we hit EOF on input.
            //
            // Other common implementation choices are to set the
            // mark at the tape position to -1 or 0.  These can
            // be enabled by defining the appropriate macro when
            // compiling.

            auto input = cin.get();
            if (input != EOF)
                tape.setValue(static_cast<Cell>(input));
            else {
#if defined(BF_ZERO_ON_EOF)
                tape.setValue(Cell(0));
#elif defined(BF_NEGATIVE_ONE_ON_EOF)
                tape.setValue(Cell(-1));
#else
                // leave cell unchanged
#endif
            }
        }

        void loadProgramFromFilePath(const string& sourceFilePath) {
            auto sourceFile = ifstream(sourceFilePath, ios::in | ios::binary);
            if (sourceFile.fail())
                throw runtime_error(string("unable to open file at path \"")
                                    + sourceFilePath
                                    + "\"");

            stack<ProgramCounter> openBraces;

            char c;
            while (sourceFile.get(c)) {
                if (isInstruction(c)) {
                    program.emplace_back(c);

                    if (c == '[') {
                        openBraces.push(program.size());
                    }
                    else if (c == ']') {
                        if (openBraces.empty()) throw runtime_error("unmatched ]");
                        auto openBrace = openBraces.top();
                        openBraces.pop();
                        matchingOpenBrace[program.size()] = openBrace;
                        matchingCloseBrace[openBrace] = program.size();
                    }                    
                }
            }

            if (!openBraces.empty()) throw runtime_error("ummatched [");
        }

        static bool isInstruction(char c) {
            static const auto validInstructions =
                unordered_set<char> { '<', '>', '+', '-', '.', ',', '[', ']' };

            return validInstructions.find(c) != validInstructions.end();
        }
    };
}

// By default, the interpreter uses 8-bit values for marks on the tape.
// Define the macro BF_CELL_TYPE to some other type (int16_t, int32_t, etc.)
// to change this.
#if !defined(BF_CELL_TYPE)
#define BF_CELL_TYPE
#endif

int main(int argc, const char* argv[]) {
    if (argc < 2) {
        cerr << "usage: " << argv[0] << " FILENAME ..." << endl;
    }
    else for (auto i = 1; i < argc; ++i) {
        auto sourceFilePath = argv[i];
        try {
            auto machine = KJBrainfuck::Machine<BF_CELL_TYPE>(sourceFilePath);
            machine.executeProgram();
        }
        catch (const exception& ex) {
            cerr << sourceFilePath << ": error: " << ex.what() << endl;
        }
    }

    return 0;
}

Makefile

CXXFLAGS=--std=c++11 -O2 -Wall

all: KJBrainfuck KJBrainfuck16 KJBrainfuck32

# Default implementation with 8-bit words
KJBrainfuck: KJBrainfuck.cpp
	$(CXX) $(CXXFLAGS) $(CPPFLAGS) $(LDFLAGS) $(TARGET_ARCH) $< -o $@

# With 16-bit words
KJBrainfuck16: KJBrainfuck.cpp
	$(CXX) -DBF_CELL_TYPE=int16_t $(CXXFLAGS) $(CPPFLAGS) $(LDFLAGS) $(TARGET_ARCH) $< -o $@

# With 32-bit words
KJBrainfuck32: KJBrainfuck.cpp
	$(CXX) -DBF_CELL_TYPE=int32_t $(CXXFLAGS) $(CPPFLAGS) $(LDFLAGS) $(TARGET_ARCH) $< -o $@

# Each of these tests should print "OK"
test: all
	- ./KJBrainfuck OK.bf
	- ./KJBrainfuck16 OK.bf
	- ./KJBrainfuck32 OK.bf

clean:
	- /bin/rm KJBrainfuck
	- /bin/rm KJBrainfuck16
	- /bin/rm KJBrainfuck32

.PHONY: test clean

OK.bf

This simple Brainfuck program writes "OK" and a newline

++++[>++++<-]>[<+++++>-]<   Put 80 onto tape at position 0
-.----.                     Write 79 ('O') then 75 ('K')
>+++++ +++++.               Write newline

There are other C++ Brainfuck interpreters out there, but most of them look a lot more like C than like C++. My goal here was to write an interpreter using modern C++11/14 style, avoiding C-isms like pointers, fixed-size arrays, global variables, and stdio/UNIX functions.

A bunch of Brainfuck example programs are available at http://esoteric.sange.fi/brainfuck/bf-source/prog/. Please let me know if you find any that don't work correctly with my implementation.

A simplified version of this is available here: https://gist.github.com/kristopherjohnson/55092ba62e82c2166125

It might be useful for people learning C++ who would prefer more-readable code without the optimizations and configurability.