Brainfuck interpreter in JavaScript, take 2

Question

The previous version is here. This version takes suggestions from that review into account:

• brainfuck is now an object instead of a function, and brainfuck.run(source) kicks off the interpreter.
• There is no built-in support for multiple interpreter instances, but Object.create(brainfuck) will do the trick.
• Stub functions (which throw errors) are provided for the implementation-dependent read and write functions.

This version also addresses the redundancy in the first version by handling loops differently. All loop start and end positions are pre-calculated, so the entire loop is now bypassed when appropriate instead of passing over each operation and no-opping. This also removes the need to keep a stack of loop start positions while the program runs.

Also, this version adds proper exports for AMD script loaders and CJS environments, with a fallback to the global namespace object.

(function(global){

    // Find start and end positions of each loop.
    function findLoops(code) {
        var start;
        var startpoints = {};
        var endpoints = {};
        var stack = [];

        for (var i = 0; i < code.length; i++) {
            if (code[i] == '[') {
                stack.push(i);
            } else if (code[i] == ']') {
                start = stack.pop();
                startpoints[i] = start;
                endpoints[start] = i;
            }
        }

        return { start: startpoints, end: endpoints };
    }

    // Run the brainfuck interpreter.
    function run(source) {
        var brainfuck = this;
        var code = source.replace(/[^-+<>.,[\]]/g, '').split('');  // program code
        var loop = findLoops(code);  // loop start and end positions
        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 () { ++cell; },
            '<': function () { --cell; },
            '+': function () { data[cell] = (data[cell] || 0) + 1; },
            '-': function () { data[cell] = (data[cell] || 0) - 1; },
            '.': function () { brainfuck.write(data[cell]); },
            ',': function () { data[cell] = brainfuck.read(); },
            '[': function () { if (!data[cell]) { next = loop.end[next]; } },
            ']': function () { if (data[cell]) { next = loop.start[next]; } }
        };

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

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

    // Export a module for AMD loaders, CJS environments, or as a global.
    function exportModule(name, module) {
        if (global['define'] && global['define']['amd']) {
            global['define'](module);
        } else if (global['exports']) {
            for (var key in module) if (module.hasOwnProperty(key)) {
                global['exports'][key] = module[key];
            }
        } else {
            global[name] = module;
        }
    }

    // Export brainfuck module. 
    exportModule('brainfuck', { 
        'run': run,
        'read': function() { throw new Error('"read" function not provided'); },
        'write': function() { throw new Error('"write" function not provided'); }
    });

}(this));

Test it out here. I have no specific concerns at this point, I'm just looking for a general review.

Answer 1

I think I said I'd refrain from reviewing, since I reviewed the first take, but I can't help myself.

Again: I like it! It's very neat and tidy. I really can't fault it.

• It's well-formatted
• It's readable
• It's efficient

Hell, it even taught me Brainfuck! Kudos!

If I were to be super nit-picky (and I'll have to be, to find something to write), it's that it'd be nice to use plural form for loop and operation (i.e. loops and operations). I know, I know, loops will ruin the nice 4-letter-aligned formatting that going on, but still.

next should perhaps be called current or similar, since that's what it actually is.

I guess you could skip the split(''), and just loop through the string, but either way works.

I might also prefer a stricter typeof brainfuck.end === 'function' check at the, uh, end, but that's just me being pedantic. OTOH, you could just stub it to a no-op function, and not have a check.

It might be nice to initialize data to [0], and have < and > initialize blank cells instead of doing it lazily in the +/- operations. It'd be a little more correct, and you'd avoid a program like . spitting out undefined instead of 0. You can do it in one (admittedly tricky) assignment:

'>': function () { data[++cell] = data[cell] || 0; }

Lastly, it might be nice to check input from read, since you could basically return whatever you want from your own read function. Worth it? Nah, not really.

I do have some other ideas, though. Less review, and more "what if...".

findJumps (formerly findLoops)

We talked about doing syntax-checking in the comments (and you came up with a nice implementation), so I'll skip that here. Instead, this is just an alternative to the code in the question.

function findJumps(code) {
  var jumps = [],
      stack = [],
      character, i, j;

  for(i = 0 ; character = code[i] ; i++) {
    if(character === '[') {
      stack.push(i);
    } else if(character === ']') {
      j = stack.pop();
      jumps[i] = j;
      jumps[j] = i;
    }
  }

  return jumps;
}

Instead of returning an array of objects, it's enough to just return an array of indices. It doesn't really matter what's start and end.

You could then change the [ and ] instructions to

'[': function () { data[cell] || (next = jumps[next]); },
']': function () { data[cell] && (next = jumps[next]); }

which seems nicely "symmetrical" :)

switch

Yeah, yeah, using a switch statement is boring. Still, it has some (minor) maybe-benefits:

• Illegal characters can be absorbed by the default: case (or no case at all) - no need to sanitize the code string first (though depending on how loop-heavy the code is, it may be more efficient to sanitize it anyway).

• It avoids declaring new operation functions on each call to run, and the calling overhead of those functions (though the impact of those things is in all likelihood zero; it's all optimized away).

Looks ok, I think (works too)

function run(code) {
  var jumps = findJumps(code),
      data = [],
      cell = 0,
      instruction, curr;

  for(curr = 0 ; instruction = code[curr] ; curr++) {
    switch(instruction) {
      case '>': ++cell;                              break;
      case '<': --cell;                              break;
      case '+': data[cell] = (data[cell] || 0) + 1;  break;
      case '-': data[cell] = (data[cell] || 0) - 1;  break;
      case '[': data[cell] || (curr = jumps[curr]);  break;
      case ']': data[cell] && (curr = jumps[curr]);  break;
      case ',': data[cell] = this.read();            break;
      case '.': this.write(data[cell]);              break;
    }
  }

  this.end();
}

The above assumes that this.end is (at least) stubbed. I've left out the cell initialization, but it works fine with that too.

Anyway, this is just me having some fun with it. Again, I can't really fault your code.

Now, how about tackling Befunge? Or maybe just Huh?