javascriptnested-loopsinfinite-loopinterpreterbrainfuck

Brainfuck Compiler in javascript


I wrote a BrainFuck compiler in JavaScript and it works fine with this input:

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

Expected output: Hello World!

But if I provide the following nested loop input, my code runs into an infinite loop:

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

Expected output: hello world

I see that the values being written to the BF memory just keep decreasing, and more and more memory cells get involved in the process. When I look at it step by step, there is no apparent mistake in the execution of each statement, but I have no idea how the loop is supposed to exit. It looks to me as if the program could not do anything else than loop infinitely as the involved values will never hit zero. Yet when I run it on the tutorialspoint Online Brainfuck Compiler the output is "hello world"!

Where is my mistake?

Here is the code:

class BrainfuckInterpreter {
    constructor() {
      this.memory = new Array(30000).fill(0); // Brainfuck memory tape
      this.pointer = 0; // Memory pointer
      this.inputBuffer = ''; // Input buffer for ,
      this.outputBuffer = ''; // Output buffer for .
      this.loopStack = []; // Stack to keep track of loop positions
    }
  
    interpret(code, input) {
      this.inputBuffer = input;
      this.outputBuffer = '';
      this.pointer = 0;
      this.loopStack = [];
  
      for (let i = 0; i < code.length; i++) {
        const command = code.charAt(i);
  
        switch (command) {
          case '>':
            this.pointer++;
            break;
  
          case '<':
            this.pointer--;
            break;
  
          case '+':
            this.memory[this.pointer]++;
            break;
  
          case '-':
            this.memory[this.pointer]--;
            break;
  
          case '.':
            this.outputBuffer += String.fromCharCode(this.memory[this.pointer]);
            break;
  
          case ',':
            if (this.inputBuffer.length > 0) {
              this.memory[this.pointer] = this.inputBuffer.charCodeAt(0);
              this.inputBuffer = this.inputBuffer.slice(1);
            } else {
              this.memory[this.pointer] = 0;
            }
            break;
  
            case '[':
              if (this.memory[this.pointer] === 0) {
                  let depth = 1;
                  while (depth > 0) {
                      i++;
                      if (code.charAt(i) === '[') depth++;
                      if (code.charAt(i) === ']') depth--;
                  }
              } else {
                  this.loopStack.push(i);
              }
              break;
          
          case ']':
              if (this.memory[this.pointer] !== 0) {
                  i = this.loopStack[this.loopStack.length - 1];
              } else {
                  this.loopStack.pop();
              }
              break;
              
            }
      }
  
      return this.outputBuffer;
    }
  }
  function Compile()
  {
    // Example usage:
    let code = '+[-[<<[+[--->]-[<<<]]]>>>-]>-.---.>..>.<<<<-.<+.>>>>>.>.<<.<-.';
    let input = '';
    const interpreter = new BrainfuckInterpreter();
    let output = interpreter.interpret(code, input);
    // Display the output
    document.getElementById('output_field').innerText = this.output;
    console.log(output);
  }

Solution

  • The problem is that you allow a memory cell to become negative. But the BF memory is supposed to consist of bytes, so you should not allow a value outside the 0..255 range, and instead apply modular arithmetic.

    So change the execution of the - and + commands as follows:

                case '+':
                    this.memory[this.pointer] = (this.memory[this.pointer] + 1) % 256;
                    break;
          
                case '-':
                    this.memory[this.pointer] = (this.memory[this.pointer] + 255) % 256;
                    break;
    

    Corrected snippet:

    class BrainfuckInterpreter {
        constructor() {
            this.memory = new Array(30000).fill(0); // Brainfuck memory tape
            this.pointer = 0; // Memory pointer
            this.inputBuffer = ''; // Input buffer for ,
            this.outputBuffer = ''; // Output buffer for .
            this.loopStack = []; // Stack to keep track of loop positions
        }
      
        interpret(code, input) {
            this.inputBuffer = input;
            this.outputBuffer = '';
            this.pointer = 0;
            this.loopStack = [];
    
            for (let i = 0; i < code.length; i++) {
                const command = code.charAt(i);
          
                switch (command) {
                case '>':
                    this.pointer++;
                    break;
          
                case '<':
                    this.pointer--;
                    break;
          
                case '+':
                    this.memory[this.pointer] = (this.memory[this.pointer] + 1) % 256;
                    break;
          
                case '-':
                    this.memory[this.pointer] = (this.memory[this.pointer] + 255) % 256;
                    break;
          
                case '.':
                    this.outputBuffer += String.fromCharCode(this.memory[this.pointer]);
                    break;
          
                case ',':
                    if (this.inputBuffer.length > 0) {
                        this.memory[this.pointer] = this.inputBuffer.charCodeAt(0);
                        this.inputBuffer = this.inputBuffer.slice(1);
                    } else {
                        this.memory[this.pointer] = 0;
                    }
                    break;
          
                case '[':
                    if (this.memory[this.pointer] === 0) {
                        let depth = 1;
                        while (depth > 0) {
                            i++;
                            if (code.charAt(i) === '[') depth++;
                            if (code.charAt(i) === ']') depth--;
                        }
                    } else {
                        this.loopStack.push(i);
                    }
                    break;
                  
                case ']':
                    if (this.memory[this.pointer] !== 0) {
                        i = this.loopStack[this.loopStack.length - 1];
                    } else {
                        this.loopStack.pop();
                    }
                    break;
                      
                }
            }
          
            return this.outputBuffer;
        }
    }
    
    function Compile()
    {
        // Example usage:
        let code = '+[-[<<[+[--->]-[<<<]]]>>>-]>-.---.>..>.<<<<-.<+.>>>>>.>.<<.<-.';
        let input = '';
        const interpreter = new BrainfuckInterpreter();
        let output = interpreter.interpret(code, input);
        // Display the output
        //document.getElementById('output_field').innerText = this.output;
        console.log(output);
    }
    
    Compile();