Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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

share|improve this question
5  
At least it's not the other way around: a JavaScript interpreter written in Brainfuck –  Alex L Jul 26 at 0:36

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
Nice suggestions. I thought about a more "classical" design like you mention here, but decided to go for simplicity instead. Providing some stubs would probably be a good idea, though, even if they just throw errors or do nothing and spit out warnings. –  Dagg Jul 26 at 1:44
    
Also thought about moving the ~loop[0] check into the main loop, but I really like the idea of the loop doing almost nothing; this way you don't really need to think about the main loop and can just focus on the operations. I think it might be nice to have some kind of "fast forward" that would skip to the end of the loop and avoid the ~loop[0] check altogether, though... –  Dagg Jul 26 at 1:45
    
I like the interpreter idea, except it looks backwards to me. Doesn't it make more sense to use interpreter.run(source) instead of having to make a new interpreter for each source? –  Izkata Jul 26 at 3:08
    
@Dagg I agree that the loop is nice and clean as it is, but the cost is the repetition in the functions. Personally, I'd prefer less repetition at the cost of a not-as-clean loop, but either way works. Besides, the loop can probably be cleaner than my attempt above. –  Flambino Jul 26 at 11:03
    
@Izkata Yeah, good point. I think I would probably prefer your suggestion, or the 2nd form above, where you pass in the callbacks as arguments, and it runs immediately. –  Flambino Jul 26 at 11:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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