First of all: what the heck is “Brainfuck”?!
Well, Brainfuck is an esoteric programming language composed by just 8 commands: > < + - . , [ ].

Wait, how can a programming language work with just eight characters?
Well, computer works with just 0's and 1's, so we have other 6 characters to use!

Brainfuck is a Turing-complete programming language, so you can really do an incredible amount of things in it! But how does it work?

Brainfuck operates on an array of memory cells, where each cell starts with zero. You can imagine it as a clean and infinite tape.
There is a pointer which is positioned on the first cell, which can perform just eight specific commands:

Command Description
> Move the pointer to the next cell.
< Move the pointer to the previous cell.
+ Increment the current memory cell.
- Decrement the current memory cell.
. Send the resulting cell to the standard output.
, Store a single character input into the cell.
[ If the cell number is 0, jump past the matching ]
] If the cell number is not 0, jump back the matching [

Wow awesome, and how does a Brainfuck program look?

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

Try to guess its meaning! This is an “Hello World” in Brainfuck!

Understanding Brainfuck

Let’s say we want to print “a" to the standard output. Knowing that the ASCII character for “a" is 97, we could just put 97 + commands into a .bf file and then compile it:

++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
++++++++++
+++++++
.

This will work perfectly, it will print a beautiful “a" on our screen. But it would be great to achieve that with a loop! So let’s write it down:

+++++
[
  > 
    +++ +++ +++
    +++ +++ +++ +
  < -
]

>++.

What. the. f**k. is. happening. here.
let’s analyze the flux:

+++++              Increment the cell 0 to 5
[                  Start a loop that will run until cell 0 is not equal to "0"
  >                Move to the cell 1
    +++ +++ +++    Increment cell 1 by 9
    +++ +++ +++ +  Increment cell 1 by 10
  < -              Move to cell 0 and decrement it by one
]                  Repeat

>++.               Move to cell 1, increment by 2, print the result.

It hasn’t been that hard! How can we implement this in JavaScript?

Writing the compiler

The compiler itself will be incredibly easy.
Let’s start by defining our compile function:

function compile(program) {

  let tape = Array(10).fill(0);
  let ptr  = 0;

  for (let char of program) {

    switch (char) {
      case "+":
        tape[ptr]++; 
        break;
      case "-":
        tape[ptr]--;
        break;
      case ">":
        ptr++;
        tape[ptr] = tape[ptr] || 0;
        break;
      case ">":
        ptr--;
        tape[ptr] = tape[ptr] || 0;
        break;
    }

  }
  return tape;
}

First of all, we create an array with 10 0s. The original Brainfuck implementation had 30000 memory cells, but for the moment we can just use 10 cells, we’ll increment ‘em later.

Then we declare a pointer ptr which represent the cell which we’re working. As we said before, it starts from the first cell (cell 0).

So now, for each character of our program, we’ll just increment/decrement or move the pointer on our tape.

Let’s test this by running:

console.log(compile(">>++"));

// => [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0]

great, it works!
Now let’s implement two other commands:

function compile(program) {
  let tape = Array(10).fill(0);
  let ptr  = 0;

  for (let char of program) {

    switch (char) {
      case "+":
        tape[ptr]++; 
        break;
      case "-":
        tape[ptr]--;
        break;
      case ">":
        ptr++;
        tape[ptr] = tape[ptr] || 0;
        break;
      case ">":
        ptr--;
        tape[ptr] = tape[ptr] || 0;
        break;
      case ".":
        console.log(String.fromCharCode(tape[ptr]));
        break;
      case ",":
        tape[ptr] = prompt()[0].charCodeAt()
        break;
    }

  }
}

Now you can test the compiler by running:

console.log(compile(">>,."));

It will open a prompt window on your browser and will store it ASCII value on the second memory cell. At that point, it will print its value to the console.
For instance, if you type “c“ in the input prompt, you’ll get back c on your console.

Now it’s time to implement loops:

function compile(program) {
  let tape       = Array(100).fill(0);
  let ptr        = 0;
  let isLooping  = false;
  let loopStack  = [];
  let innerLoops = 0;

  for( i = 0; i < program.length; i++ ) {
  
  const char = program[i];

    if(isLooping) {
      if(char === "[") innerLoops++;
        if(char === "]") {
          if(innerLoops === 0) isLooping = false;
          else innerLoops--;
        }
      continue;
    }
    
    switch(char){
      case '+':
        tape[ptr]++;
        break;
      case '-':
        tape[ptr]--;
        break;
      case ',':
        tape[ptr] = prompt()[0].charCodeAt()
        break;
      case '.':
        console.log(String.fromCharCode(tape[ptr]));
        break;
      case '>':
        ptr++;
        tape[ptr] = tape[ptr] || 0;
        break;
      case '<':
        ptr--;
        tape[ptr] = tape[ptr] || 0;
        break;
      case '[':
        tape[ptr] === 0 
          ? isLooping = true
          : loopStack.push(i);
        break;
      case ']':
        tape[ptr] !== 0
          ? i = loopStack[loopStack.length-1]
          : loopStack.pop();
        break;
      default:
        break;
      }
    }
}

Loops are a bit trickier.
First of all, we have to declare three new variables:

  1. isLooping, will tell us if we’re currently inside a Brainfuck loop
  2. loopStack, an array which will keep track of every Brainfuck loop
  3. innerLoops, a counter which keeps the number of active Brainfuck loops

we also had to refactor our for loop: we’ve switched to a classic and C-linke for loop ‘cause we need the current index of our program.

Before testing the command itself, we need to detect if we are inside a Brainfuck loop.
If we are inside a loop and the current command is [, let’s add another loop to our innerLoops counter.
If the current command is ], let’s check if that was our last nested loop: if that is the case, let’s exit the loop, otherwise decrement the innerLoops counter.

Great, now let’s move to the command switch/case.
If the current command is [ and the current memory cell is equal to zero, let’s start a loop. Otherwise push the current command index to the loopStack array.
If the command is ] and the current memory cell is not equal to zero, let’s set the current index equal to the last but one element of our loopStack.
Otherwise, remove the last element from loopStack.

Believe it or not, you’re just wrote a complete Brainfuck compiler!
Let’s test it with some programs!

Hello World

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.

99 Bottles

.++>+>++>>+>>>++++++++++[->+>+>++++++++++<<<]>>>>++++++++++[->+++++>++++++++++>+
++++++++++>++++++++>++++++++>+++>++++>+<<<<<<<<]+>->+++>++++++>->+++++>+++>+++++
>+>+>+>+>++>+>+>++[-<]<<<<<<<[->>[>>>>>>>>[<<<<<<<[->[-]>>>>>>>>>>>.<----.>>>.<<
<--.++.+++.+<-.+<<+<<<<<<<<]+>[-<[-]>>>>>[>>>+<<<<+<+<+>>>-]<<<[->>>+<<<]>[>>>>>
>+<<<<<<-]>>>>>[[-]>.<]<<<<[>>>>>-<<<<<-]>>[<<+<+<+>>>>-]<<<<[->>>>+<<<<]>[>>>>>
>+<<<<<<-]>>>>>>.<<<<<[>>>>>-<<<<<-]>>>[-<<<+<+>>>>]<<<<[->>>>+<<<<]>-[[-]>>>>+<
<<<]<<<]+>>>>>>>>>>>>>.<<<<----.>----.+++++..-<++++++++++.-------.<<[[-]>>>.<<<]
>>>>>>.<<<----.<+.>>>>.<<<<----.+++..+>+++.+[>]+>+>[->+<<-<-<<<.<<<----.-.>>>.<<
<++++++.<++.---.>>>>.<<<+++.<----.+++++++++++..------>---->---------------------
----------->>>++.-->..>>>]>>>[->[-]<<<<<<<[<]<[-]>>[>]>>>>>]+>[-<[-]<<<<[->>[->+
<<<<-<<<.<<<----.-.>>>.<<<++++++.<++.---.>>>>.<<<+++.<----.+++++++++++..------>-
--->++++++++++++++++++++++++++++++++>>>.<.>>>>>>]<<]<[->>>>[-<<+<<<<++.-->.[<]<<
<<<<<<[->[-]<]+>[-<[-]>>>>>>>>>>>>>.<<<-----.++++++++++.------.>>>>.<<<----.-.<.
>>>>.<<<<-.>+.++++++++.---------.>>>.<<<<---.>.<+++.>>>>.<<<++.<---.>+++..>>>.<<
<<++++++++.>+.>>>.<<<<--------.>--.---.++++++.-------.<+++.++>+++++>>>>.<.[<]<<<
<<<<]+>>>>>>-<<<+>>[<<[-]<+<+>>>>-]<<<<[>-<[-]]>[->>>+<<<]>[->->+++++++++<<]>>>>
>[>]>>>>]<<<<]>>>>>>]+<<<<<<<[<]<]+<+<<<<<<+<-]>>>>>>>>>>[>]>>>>>[->[-]<]+>[-<[-
]<<<<<<<<<-------------.<<----.>>>.<<<+++++.-----.>>>.<<<+++++.<++.---.>>>>.<<<-
.+.-----.+++.<.>>>>.<<<<----.>----.<+++.>>>>.<<<<--.>+++++++.++++.>>>.<<<------.
----.--.<+++.>>>>.<<<.++.+++.+<.+>>>>>.<.>>>>>>>>>]+<[-]+<[-]<[-]<[-]+<<<[<]<[-]
<[-]<[-]<[-]++++++++++[->+>+>++++++++++<<<]>->->-<<<<<<[-]+<[-]<+<<]

Divide two numbers

,>,>++++++[-<--------<-------->>]<<[>[->+>+<<]>[-<<-[>]>>>[<[>>>-<<<[-]]>>]<<]>>>+<<[-<<+>>]<<<]>[-]>>>>[-<<<<<+>>>>>]<<<<++++++[-<++++++++>]<.

Did you like this article? Consider becoming a Patron!

This article is CC0 1.0 (Public Domain) licensed.