Create a gist now

Instantly share code, notes, and snippets.

Brainfuck interpreter in C++11
/*
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;
}
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
This simple Brainfuck program writes "OK" and a newline
++++[>++++<-]>[<+++++>-]< Put 80 onto tape at position 0
-.----. Write 79 ('O') then 75 ('K')
>+++++ +++++. Write newline
@kristopherjohnson

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.

@kristopherjohnson

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment