Brainfuck interpreter in JavaScript

Question

Just what it says on the tin: a brainfuck interpreter in JavaScript.

function brainfuck(source) {
    var code = source.replace(/[^-+<>.,[\]]/g, '').split('');  // program code
    var loop = [];  // stack of loops created by bracket operators
    var data = [];  // array of data cells stored by the program code
    var cell = 0;   // index in the data array representing one "cell" of data
    var next = 0;   // index in the code array of the next instruction to run 
    var operation = {
        '>': function () {
            if (~loop[0]) {
                ++cell;
            }
        },
        '<': function () {
            if (~loop[0]) {
                --cell;
            }
        },
        '+': function () {
            if (~loop[0]) {
                data[cell] = (data[cell] || 0) + 1;
            }
        },
        '-': function () {
            if (~loop[0]) {
                data[cell] = (data[cell] || 0) - 1;
            }
        },
        '.': function () {
            if (~loop[0]) {
                brainfuck.write(data[cell]);
            }
        },
        ',': function () {
            if (~loop[0]) {
                data[cell] = brainfuck.read();
            }
        },
        '[': function () {
            loop.unshift(data[cell] ? next : -1);
        },
        ']': function () {
            if (~loop[0] && data[cell]) {
                next = loop[0];
            } else {
                loop.shift();
            }
        }
    };

    while (next < code.length) {
        operation[code[next++]]();
    }

    if (brainfuck.end) {
        brainfuck.end();
    }
}

Just call brainfuck(source), where source is some brainfuck source code, to run the interpreter.

Notice the references to brainfuck.read, brainfuck.write and brainfuck.end. Since input and output are heavily dependent on the host environment, it's up to the implementation to provide these. Here's some code for a browser-based implementation, using console.log for output and prompt for input (node was too straightforward and boring).

(function () {

    var inputBuffer = [];
    var outputBuffer = [];

    function flush() {
        console.log(outputBuffer.splice(0).join(''));
    }

    brainfuck.read = function () {
        if (!inputBuffer.length) {
            inputBuffer = prompt().split('');
            inputBuffer.push(String.fromCharCode(0));
        }
        return inputBuffer.shift().charCodeAt(0) || -1;
    };

    brainfuck.write = function (character) {
        if (character == 10) {
            flush();
        } else {
            outputBuffer.push(String.fromCharCode(character));
        }
    };

    brainfuck.end = function() {
        flush();
        inputBuffer = [];
    };

}());

This has been tested with the two examples on Wikipedia and Simon's FizzBuzz program. You can test it out here, just paste some code in the box and hit "go." This implementation uses -1 as an end-of-input character to accommodate the ROT13 example on Wikipedia (which the test comes pre-loaded with).

---

I'm looking for reviews on the usual stuff. Specific concerns are:

• The if (~loop[0]) conditions look sort of repetitive.
• Maybe loop operators [ and ] can be handled more cleanly.
• Not really sure what to call anything since I couldn't find any formal spec.

---

Note on apparent repetition of if (~loop[0]): I'm still trying to decide if this is really repetition or not. Moving it to the main loop seems like breaking separation of concerns in a way... the main loop has to know more about the operators than it should. If you decided to add more operators (brainfuck++?), then you might have to change the main loop instead of only worrying about your new operators. It seems to me that it's each operator's job to worry about its own behavior, and it shouldn't be controlled from somewhere else.

That being said, an even better option might be to analyze the program beforehand to determine where each loop starts and ends. Then, if a loop isn't meant to be executed, next can simply be set to the operation after end of the loop, instead of moving to each operation on the way there and having it no-op. This should improve performance, and would also allow for detecting broken programs and throwing an error early early instead of trying to run them and probably getting caught in an infinite loop.

---

New version here: Brainfuck interpreter in JavaScript, take 2

Answer 1

It's nice and clean; I like it. I won't even try to figure out if its interpretation is correct, since I don't know Brainfuck, so I'll take your word for that and just look at the JS :)

As you yourself pointed out, the [ and ] operators might be handled differently, which would also allow you avoid the if(~loop[0]), since that's used in all the other operators.

For instance:

switch(code[next++]) {
  case '[':
    loop.unshift(data[cell] ? next : -1);
    break;
  case ']':
    if (~loop[0] && data[cell]) {
      next = loop[0];
    } else {
      loop.shift();
    }
    break;
  default:
    if(~loop[0]) operations[op]();
}

Not super clean by itself, but it'll clean up the operator functions. Anyway, that's low-hanging fruit, and there are more - and no doubt cleaner - ways to solve it.

However, I'd be more concerned about the fact that there's only the single interpreter. I'd seem cleaner to me to:

1. Return an object from brainfuck (it doesn't have to be a construtor function; returning an object literal would work fine) that allows you to attach the read, write and end functions to just that instance. This would of course also necessitate a run function or something, to kick off the interpretation.

2. And that read, write and end are stubbed out/have default implementations, so I don't have to supply 'em, if I don't care. E.g. maybe I just want to see if the code runs but the output can go to /dev/null for all I care (or, in this case, a no-op function).

I imagine something like:

var interpreter = brainfuck(source);
interpreter.read = ...
interpreter.write = ...
interpreter.run();

(if this was for Node-only, it might be fun to base it off of EventEmitter, and use the usual event handling for IO)

Or run the code immediately, but provide the read/write functions as arguments, e.g.: brainfuck(source, reader, writer [, end]).

Point is just to avoid having one single brainfuck function that will operate on any source code you pass, but has a single, "global" set of I/O functions.

Ok, ok, you're not going to be running interpreters in parallel or anything, but it just seems cleaner to me to let each run have clean slate.

But really, I can't find much to comment on. It's pretty clean as it is.