Brainfuck interpreter + program generator

bf.ts

import chalk from 'chalk';
import * as fs from 'fs';
import * as term from 'terminal-kit';

function sleep(ms: number) {
  return new Promise(resolve => setTimeout(resolve, ms));
}

namespace BF2 {
  type TraceId = { traceId: number };

  type InstructionWithTraceId = Instruction & TraceId;

  type Instruction =
    | { kind: 'MoveLeft' }
    | { kind: 'MoveRight' }
    | { kind: 'Increment' }
    | { kind: 'Decrement' }
    | { kind: 'Print' }
    | { kind: 'Loop'; instructions: InstructionWithTraceId[] };

  enum Token {
    MoveLeft = '<',
    MoveRight = '>',
    Increment = '+',
    Decrement = '-',
    Print = '.',
    LoopStart = '[',
    LoopEnd = ']'
  }

  interface InterpreterOptions {
    initialMemory: number;
    memoryGrowthFactor: number;
  }

  const defaultOptions: InterpreterOptions = {
    initialMemory: 16,
    memoryGrowthFactor: 1.25
  };

  export class Interpreter {
    private pointer = 0;
    private memory: number[] = [];
    private stdout: string[] = [];
    private options: InterpreterOptions;

    constructor(options: Partial<InterpreterOptions> = {}) {
      this.options = { ...defaultOptions, ...options };
      this.resetMemory();
    }

    async run(sourceCode: string) {
      term.terminal.clear();
      const { instructions } = this.parse(sourceCode);
      for (const instruction of instructions) {
        await this.execute(instruction);
      }
      this.resetMemory();
    }

    private parse(source: string, start: number = 0): { instructions: InstructionWithTraceId[]; last: number } {
      const program: InstructionWithTraceId[] = [];
      for (let index = start; index < source.length; index++) {
        const token = source.charAt(index);
        switch (token) {
          case Token.LoopStart:
            const { instructions, last } = this.parse(source, index + 1);
            program.push({ traceId: index, kind: 'Loop', instructions });
            index = last;
            break;
          case Token.LoopEnd:
            return { instructions: program, last: index };
          case Token.Increment:
            program.push({ traceId: index, kind: 'Increment' });
            break;
          case Token.Decrement:
            program.push({ traceId: index, kind: 'Decrement' });
            break;
          case Token.MoveLeft:
            program.push({ traceId: index, kind: 'MoveLeft' });
            break;
          case Token.MoveRight:
            program.push({ traceId: index, kind: 'MoveRight' });
            break;
          case Token.Print:
            program.push({ traceId: index, kind: 'Print' });
            break;
          default:
            throw new Error(`unknown instruction '${token}'`);
        }
      }
      return { instructions: program, last: source.length };
    }

    private async execute(instruction: InstructionWithTraceId) {
      await this.debugFrame(instruction);

      switch (instruction.kind) {
        case 'Increment':
          this.memory[this.pointer] += 1;
          break;
        case 'Decrement':
          this.memory[this.pointer] -= 1;
          break;
        case 'MoveRight':
          this.pointer += 1;
          if (this.memory.length <= this.pointer) {
            this.extendMemory();
          }
          break;
        case 'MoveLeft':
          this.pointer -= 1;
          if (this.pointer < 0) {
            throw new Error('Unsafe access out of memory area');
          }
          break;
        case 'Print':
          this.write(String.fromCharCode(this.memory[this.pointer]));
          break;
        case 'Loop':
          while (this.memory[this.pointer] !== 0) {
            for (const subInstruction of instruction.instructions) {
              await this.execute(subInstruction);
            }
          }
          break;
        default:
          break;
      }
    }

    private write(value: string) {
      this.stdout.push(value);
    }

    private resetMemory() {
      this.memory = new Array(this.options.initialMemory).fill(0);
    }

    private extendMemory() {
      const additionalMemory =
        (this.memory.length * this.options.memoryGrowthFactor - this.memory.length) | 0 || this.options.initialMemory;
      this.memory = this.memory.concat(new Array(additionalMemory).fill(0));
    }

    private async debugFrame(instruction) {
      const stats = chalk.green(
        `current instruction: ${chalk.bgBlue(
          chalk.bold(chalk.white(` ${instruction.kind} (#${instruction.traceId}) `))
        )}\tmemory size: ${chalk.bgBlue(
          chalk.bold(chalk.white(` ${this.memory.length} (initial ${this.options.initialMemory}) `))
        )}`
      );
      const debugTrace = chalk.bgBlackBright(
        sourceCode.slice(0, instruction.traceId) +
          chalk.bgYellow(chalk.black(` ${sourceCode[instruction.traceId]} `)) +
          sourceCode.slice(instruction.traceId + 1)
      );
      const out = chalk.green(`${chalk.bold('output:')} ${this.stdout.join('')}`);
      term.terminal.moveTo(1, 1);
      term.terminal(`${stats}\n\n${debugTrace}\n\n${out}`);
      await sleep(5);
    }
  }
}

const sourceCode = fs.readFileSync(0).toString();

const interpreter = new BF2.Interpreter();

interpreter
  .run(sourceCode)
  .then(() => process.exit(0))
  .catch(err => {
    console.error(err);
    process.exit(1);
  });

generator.js

const fill = (num, char) => new Array(num).fill(char).join("");

const generateMutation = (amount, operator) => {
  let addition = amount % 5;
  let multiplication = (amount / 5) | 0;
  return `+++++[>${fill(multiplication, operator)}<-]>${fill(
    addition,
    operator
  )}.<`;
};

const generateInstructions = (current, target) => {
  if (current == target) {
    return ">.<";
  } else if (current < target) {
    let diff = target - current;
    return generateMutation(diff, "+");
  } else {
    const diff = current - target;
    return generateMutation(diff, "-");
  }
};

const generateProgram = target => {
  let instructions = [];
  let previous = 0;
  for (let char of target) {
    const current = char.charCodeAt(0);
    instructions.push(generateInstructions(previous, current));
    previous = current;
  }
  return instructions.join("");
};

const program = generateProgram("Hello, world!\n");
console.log(`Generated program:\n\n${program}`);

generator.py

def generate_program(target):
    instructions = []
    previous = 0
    for char in target:
        current = ord(char)
        instructions.append(generate_instructions(previous, current))
        previous = current
    return ''.join(instructions)


def generate_instructions(current, target):
    if current == target:
        return '>.<'
    elif current < target:
        diff = target - current
        return generate_mutation(diff, '+')
    else:
        diff = current - target
        return generate_mutation(diff, '-')


def generate_mutation(amount, operator):
    addition = amount % 5
    multiplication = amount // 5
    return f"+++++[>{''.join([operator] * multiplication)}<-]>{''.join([operator] * addition)}.<"


program = generate_program('Hello, world!\n')
print(f"Generated program:\n{program}")