Posted on Sunday, 12th of January 2020

Hi, it's been so long since last post, but i'm still alive. Few days ago I was very bored so I decided to make my own brainfuck interpreter.

Today I'll show you my way of making it. Firstly I made my interpreter and only after that I started looking at other people code, and tbh I think it's all outdated or just bad code. I love modern JavaScript and I will use it.

So let's start from making a class and constructor:

class Brainfuck {
      constructor(program, input = "", size = 30000) { // default input will be empty string, and size of memory will be 30000 just like in original brainfuck
          if(!program) throw new Error("No program to interpret.");
          this.program = program;
          this.input = input;
          this.size = size;
          this.array = new Array(size).fill(0); // our memory filled with zero's
          this.p = 0; // pointer
          this.i = 0; // index
          this.done = false; // when program will be completed, set this to true
      };
  };
  

I want to make my own EventEmitter for sending our data to event listeners. I only will make on and emit, because I don't need huge EventEmitter with once and off. So, let's make new variable in constructor:

this.events = {};
  

And now on and emit methods. They are super simple:

on(name, fn) {
      if(!this.events[name]) this.events[name] = [];
      this.events[name].push(fn);
  };
emit(name, ...args) {
  if(!this.events[name]) return;
  for(let i in this.events[name]) this.events[name][i](...args);
};
  

And now we can do this:

bf.on("test", console.log);
bf.emit("test", "Hello, world!");
  

And we will get "Hello, world!" in console.

Now let's make our step method! It'll be our main method that will be called on every instruction. You'll see why i'm not doing just a normal loop later.

step() {
  let program = this.program; // to make code shorter
  let invalid = false; // if invalid character in code is using then we set this to true
  if(this.done || program[this.i] === undefined) { // if this.done is set to true manually or program have ended then we send event to "done"
      this.done = true;
      return this.emit("done");
  };
  switch(program[this.i]) { // we will implement instructions here later
  
  };
  if(!invalid) this.emit("tick"); // let's call this event just in case if some program will need to get every real tick of program.
  this.i++;
};
  

Now our skeleton of step is done, let's work on instructions of brainfuck. First instruction is >. It moves pointer to the right. If you'll imagine huge array, like this:

[0,0,0,0,0,0,0,0,0,0,0...]
 ^
this.p = 0;
  

then ^ is our pointer, and it'll be moved to second zero. So let's add it to our switch:

case ">":
      this.p++;
      break;
  

And same thing with <:

case "<":
      this.p--;
      break;
  

Seems pretty simple at first, but we missed something very important. I don't really know should it behave like this, but a lot of programs that I see in codegolf did this at the start of brainfuck program:

<
  

What's so special about this? Our pointer is now -1, and if it'll try to call our memory, it'll just return undefined or if we will try to use + or - instructions will just make NaN. But we don't need that! Let's make something like overflow, so when we move it to left it'll actually will be 30000 or other size that we put in size argument instead of -1. Let's make function for this:

this.mod = (a, b) => {
  b += 1;
  return ((a % b) + b) % b;
}
  

And now let's remake our < and > a bit:

case ">": this.p++; this.p = this.mod(this.p, this.size); break;
case "<": this.p--; this.p = this.mod(this.p, this.size); break;
  

Now everything should be fine when programs will do this kind of stuff.

Next instructions are + and -. They increment or decrement current value. But we know that brainfuck uses 8 bit numbers so let's not make same mistake and make overflow here too:

case "+": this.array[this.p] = (this.array[this.p]+1) & 255; break;
case "-": this.array[this.p] = (this.array[this.p]-1) & 255; break;
  

Now if number will be 256 it'll be transformed to 0.

Now we're getting to harder instructions. . instruction will output character to "out" event, we have to make character instead of number, luckily we have String.fromCharCode, so let's do it:

case ".": this.emit("out", String.fromCharCode(this.array[this.p])); break;
  

, instruction reads input and puts ASCII code into memory. Let's make current character variable so we can know what character we should give:

this.char = 0;
  

And now let's implement ,:

case ",":
      this.emit("in"); // let's send event when program requires input
      if(this.input[this.char] === undefined) {
        this.array[this.p] = 0; // if no more stuff in input left, let's just put zero
        break;
      };
      this.array[this.p] = this.input[this.char++].charCodeAt(0);
      break;
  

I should mention about my dumb mistake: I was using charAt instead of charCodeAt and because of that my interpreter was working in weird way, and it took me 2 hours to find a mistake lol.

Now 2 hardest instructions: [ and ]. People usually call them loop. But for some reason they forget to mention their full description of what do they do:

• [ - if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command.
• ] - if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command.

Usually people just say [ - start of loop, ] - if program[p] === 0 then end loop without mentioning important stuff. And because of that I was struggling with it for some time :pensive:

There's a lot of ways implementing loops, but here's mine: since there is also can be nested loops, we should find address of ] that is pair of [. So let's make variable called ignore and set 0. Then just loop though code, and when we find [ add increment ignore and when we find ] then decrement it. And if ignore was 0 at the moment of finding ] then it's our pair! And we can now do stuff with it knowing it's address.

+[->>+[-]+[-++[-]]+>+]
^

this.i = 0;
temp_i = null;
ignore = null;
  

We have to save address of it somewhere, so let's make object for that:

this.loops = {};
  

Since we know address of paired ] we can implement our instruction. If program[p] === 0 then jump to ] and continue executing, else just continue executing here but add it to this.loops so we can know where to jump at ].

case "[":
    let temp_i = this.i;
    let ignore = 0;

    while(1) {
      temp_i++;
      if(!program[temp_i]) throw new Error("Out of bounds.");
      if(program[temp_i] === "[") ignore++;
      if(this.program[temp_i] === "]") {
        if(ignore === 0) {
            // pair found!
            if(this.array[this.p] === 0) this.i = temp_i; // jump to ']' if 0
            else this.loops[temp_i] = this.i; // just continue
            break; // exit loop
        } else ignore--;
      }
    }
    break;
  

And now ] instruction. It's simpler because we don't need to find our pair back: we already saved it in this.loops. So if program[p] !== 0 then just jump back to paired [, else remove our loop from list and continue executing.

case "]":
        if(this.array[this.p] !== 0) this.i = this.loops[this.i];
        else delete this.loops[this.i];
        break;
  

All done! Now the only thing we have to do is just to set invalid to true if it's comment, not instruction:

default: invalid = true;
  

Now we just should make init method. So why did I make step method instead of loop? First off because sometimes you want to debug program, so you can make your own debugger just with stepping. And second off, sometimes programs are very big and laggy, and running loop will freeze page, so I want to use requestAnimationFrame. So let's do it:

init(speed = 1000) {
    const fn = () => {
      for(let i = 0; i < speed; i++) this.step();
      if(!this.done) requestAnimationFrame(fn);
    };
    fn();
}
  

And with this function we can set our speed of execution (default is 1000).

And now our interpreter is done! You can get full code on my GitHub. To run brainfuck code just do this:

const program = "--[>--->->->++>-<<<<<-------]>--.>---------.>--..+++.>----.>+++++++++.<<.+++.------.<-.>>+.";
const bf = new Brainfuck(program);

bf.on("out", o => console.log(o));
bf.init();
  

or little bit smarter way:

const program = "--[>--->->->++>-<<<<<-------]>--.>---------.>--..+++.>----.>+++++++++.<<.+++.------.<-.>>+.";
const bf = new Brainfuck(program);
let out = "";

bf.on("out", o => out += o);
bf.on("done", () => console.log(out));
bf.init();
  

Join my Discord server if you're interested in other stuff like this: dimden.dev/invite.