11
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You have a typo in exportModulo for the exports case. Also most people do module.exports = smt \$\endgroup\$ – megawac Jul 26 '14 at 16:09
  • \$\begingroup\$ @megawac module.exports = only works in node (afaik), it's not a standard CJS modules thing. Where is the typo, I'm not seeing it? \$\endgroup\$ – Dagg Jul 26 '14 at 16:41
  • \$\begingroup\$ (var key in value) you want module \$\endgroup\$ – megawac Jul 26 '14 at 16:44
  • \$\begingroup\$ @megawac ahh, good catch, that was originally value everywhere but I changed it at the last minute. Fixed. :) \$\endgroup\$ – Dagg Jul 26 '14 at 16:45
  • 1
    \$\begingroup\$ Do Brainfuck interpreters throw syntax errors or does code just fail at runtime if there is one? I'm just thinking that an unmatched ] will result in stack.pop() => undefined in findLoops which could lead to some breakage. I think. Point is, it'd be easy to check for unmatched brackets and complain upfront - but I'm not saying it's worth it. I mean, it is Brainfuck after all \$\endgroup\$ – Flambino Jul 26 '14 at 21:34
4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Some really good points here, like the first data cell not being initialized if it's never modified, and using a single object for both the loop start-to-end and end-to-start mappings. I actually wanted to do the short-circuit conditions for [ and ] but thought someone would yell at me for it. Personally I think it looks much nicer. \$\endgroup\$ – Dagg Jul 31 '14 at 13:15
  • \$\begingroup\$ The switch thing is... interesting. I'm not sure how I feel about it yet, need to let it sink in. I think maybe leaving all those comment characters in the code and no-opping on them could be a runtime performance hit, as well as checking those conditions instead of indexing an object. Don't know how significant these performance hits would be, though. I actually considered going the other direction and precomputing a chain of commands for the program, condensing something like <<<<< into something like { command: changeActiveCell, amount: -5 }. Probably overkill though. \$\endgroup\$ – Dagg Jul 31 '14 at 13:20
  • \$\begingroup\$ @Dagg Happy to hear you found it interesting! I definitely prefer the short-circuiting, too. Don't know how I feel about the switch either to be honest. It's certainly less flexible than functions, right now when everything is one statement it feels a little like overkill to bring functions into it. And yeah, I don't know if no-op'ing is faster or slower. Well, it depends on the code, I guess. The pre-compiler (if you will) idea is interesting. No idea if it's practical, but could be fun to try. Or meet it halfway and do a Brainfuck dialect: +3.4 would print 3333 :) \$\endgroup\$ – Flambino Jul 31 '14 at 14:37
  • \$\begingroup\$ @Dagg By the way, I tried figuring out what should happen if you go out-of-bounds on the data array (here, of course, you just get a -1 property, and things keep working), but there doesn't seem to be a standard. Expanding the array (which is sort of what this does) appears to be a common solution (cf. wikipedia), so no need to change anything there, yay. \$\endgroup\$ – Flambino Jul 31 '14 at 18:08
  • \$\begingroup\$ Yeah, apparently there is no standard way of handling end-of-input situations either... I got around that by not addressing it and leaving it up to the implementation ;) \$\endgroup\$ – Dagg Jul 31 '14 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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