2
\$\begingroup\$

I created a brainfuck interpreter in javascript. It works good to me as I have seen no bugs in my compiler. I like to get a suggestion and review from you to what should this compiler improve.

Here's the short code:

function bf(str, input){


var array = str.split("");

var memory = [0];

var pointer = 0;

var result = [];

var open = [];


for(var i = 0; i < array.length; i++){


  if(array[i] == ">"){

    pointer++;

    if(memory.length-1 < pointer){

     memory.push(0);

    }


  }else if(array[i] == "<"){

    if(pointer > 0){

     pointer--;

    }else{

     throw "Overflow Error at " + i

    }

  }else if(array[i] == "+"){

    if(memory[pointer] < 255){

      memory[pointer]++;

    }else{

      memory[pointer] = 0;

    }

  }else if(array[i] == "-"){

    if(memory[pointer] > 0){

      memory[pointer]--;

    }else{

      memory[pointer] = 255;

    }

  }else if(array[i] == "."){

    result.push(String.fromCharCode(memory[pointer]));

  }else if(array[i] == ","){

    memory[pointer] = input.shift().charCodeAt(0);

  }else if(array[i] == "["){

    if(open.length){

      if(open[open.length-1] != i){

        open.push(i);

      }

    }else{

      open.push(i);

    }

  }else if(array[i] == "]"){

    if(open.length){

      if(memory[pointer]){

        i = open[open.length - 1];

      }else{

        open.pop();

      }

    }

  }

}

return result;

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Is there a purpose for the compiler? Or just for the challenge? \$\endgroup\$ – dustytrash Apr 3 at 14:47
  • \$\begingroup\$ Can you test it on my FizzBuzz code ? \$\endgroup\$ – Simon Forsberg Apr 3 at 15:31
  • 1
    \$\begingroup\$ There is a serious bug, you have not implemented the "[" command correctly. "[" is missing if memory[pointer] === 0 goto matching "]" \$\endgroup\$ – Blindman67 Apr 3 at 16:05
1
\$\begingroup\$

General style points

  • No need to split the str into an array, you can access the character directly using bracket notation. eg str[i] === ">"

  • If you want a number to cycle over a range use the remainder operator % to do that. Example to add 1 memory[pointer] = (memory[pointer] + 1) % 255 and to subtract memory[pointer] = (memory[pointer] + 254) % 255.

    However as you want to simulate memory as bytes you may as well use a typed array that has an Unsigned Char. The bytes in the array behave the same as they would on the VM that runs BF commands. Example const memory = new Uint8Array(1024)

  • Not sure why you throw overflow for "<" when you don't throw the same error >. < should just cycle to highest byte in memory.

  • Use "const" for variables that do not change.

  • Use === and !== rather than == and !=

  • Don't double space (every other line empty). It makes the code hard to read as it will not fit to one screen.

  • Naming is rather poor.

    -result could be better as "output"

    • str maybe commands or program
    • i maybe programCounter or commandIndex. I am old school so would use pc
  • Rather than index into an array over and over, as you do with array[i], store it in a variable const command = array[i]; and then if(command === ">") { makes the code more compact and easier to follow.

Design.

You can use a lookup to get the action required for each command. (see example commandList) rather than one long if() {}else if().... This is a lot quicker to run as you don't need to step over else if statements to find the matching block. Also make it easy to add or change commands, and easier to read.

The Bug

As I pointed out in the comments there is a bug. You have not implemented the "[" command correctly. This is a big issue as many programs will fail. To solutions are non trivial.

There are two solutions.

  1. When you need to skip ahead search for the matching close. This can cost a lot of performance.
  2. Compile the code and locate matching open and close [ and ] so that you can quickly locate the match and move to it if required.

Ease of use

The input and output would be better as strings rather than arrays. Makes the BF easier to use.

The halting problem.

There is a fundamental requirement you have missed. You can never know if the program you are running will exit.

As JavaScript is blocking this means there is no way to stop the execution if the bf code goes into infinite loop. You should protect against this problem.

The easiest is to put a limit on the number of instructions, and throw error if reached.

Or you could have the commands execute on a timer.

Example

The function name is bfVM for brainFuckVirtualMachine and requires a compiled program. (as that is how I fixed your bug).

I included the compiler, all it does is find matching blocks and maps them to each other. returns a compiled object.

And two programs as testing fodder.

// Run two comnpiled BF programes.
setTimeout(() => {
console.log(bfVM(helloWorld))
console.log(bfVM(addNums))
},0);
/* Old school naming pc is program counter, ptr is a pointer, and
   inPtr is input pointer */
function bfVM(compiled, input) {
    const program = compiled.program;
    const blocks = compiled.blocks;
    const RAM = compiled.RAM;
    const memory = new Uint8Array(RAM);
    const commandList = {
        ">"(){ ptr = (ptr + 1) % RAM },
        "<"(){ ptr = (ptr + RAM - 1) % RAM },
        "+"(){ memory[ptr]++ },
        "-"(){ memory[ptr]-- },
        "."(){ output += String.fromCharCode(memory[ptr]) },
        ","(){ memory[ptr] = input.charCodeAt(inPtr++) },
        "["(){ pc = !memory[ptr] ? blocks.get(pc)[0] : pc },
        "]"(){ pc = memory[ptr] ? blocks.get(pc)[0] : pc  },
    };    
    
    var cycles = 0, ptr = 0, pc = 0, inPtr = 0, output = ""; 
    while (pc < program.length && cycles++ < MAX_CYCLES) {
        const cmd = commandList[program[pc]];
        cmd && cmd();
        pc ++;        
    }
    if (cycles=== MAX_CYCLES) { throw new Error("Cycle limit reached at PC: " + pc)  }
    return output;
}

const MAX_CYCLES = 1024 * 1024;  // Limit of execution steps.
function compileBF(program, RAM) {
    var pc = 0;
    const blocks = new Map();
    const blockStack = [];
    while (pc < program.length) {
        if (program[pc] === "[") {
            blocks.set(pc, [])
            blockStack.push(pc);
        } else if(program[pc] === "]") {
            const open = blockStack.pop();
            const block = blocks.get(open);
            if (block === undefined) {
                throw new Error("Syntax error: No matching block for ']' at " + pc);
            }
            block[0] = pc;
            blocks.set(pc, [open]);
        }
        pc++;
    }
    if (blockStack.length) {
       throw new Error("Syntax error: Block missmatch at " + pc);
    }
    return {program, blocks, RAM};
}

const nums = ["", "+", "++", "+++", "++++", "+++++", "++++++", "+++++++", "++++++++", "+++++++++"]
const toASCIINum = "++++++++[<++++++>-]<"
const helloWorld = compileBF(("++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."), 14)
const addNums = compileBF(nums[5]+">"+nums[4]+"[<+>-]"+toASCIINum+".",2);

\$\endgroup\$
  • \$\begingroup\$ @Blindmand67 Thanks \$\endgroup\$ – MMJM May 6 at 12:31
0
\$\begingroup\$

Some comments in the code could go a long way.

A switch statement might be more readable here than the if/else chain.

If possible, rename the 'bf' function to something more readable, same for the 'str' parameter.

\$\endgroup\$

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.