Adding some of my favorite toys

1 files changed, 226 insertions, 0 deletions

diff --git a/src/toys/godel/js/compiler.js b/src/toys/godel/js/compiler.js
new file mode 100644
index 0000000..d15c0f4
--- /dev/null
+++ b/src/toys/godel/js/compiler.js
@@ -0,0 +1,226 @@
+const INDENT_SIZE = 2;
+
+class CodeBuilder {
+  constructor(indentSize = INDENT_SIZE) {
+    this.indentSize = indentSize;
+    this.indentLevel = 0;
+    this.parts = [];
+  }
+
+  addLine(line = "") {
+    const indent = " ".repeat(this.indentLevel * this.indentSize);
+    this.parts.push(line ? `${indent}${line}` : "");
+  }
+
+  open(line) {
+    if (line) {
+      this.addLine(line);
+    }
+    this.indentLevel += 1;
+  }
+
+  close(line) {
+    this.indentLevel = Math.max(0, this.indentLevel - 1);
+    if (line) {
+      this.addLine(line);
+    }
+  }
+
+  toString() {
+    return this.parts.join("\n");
+  }
+}
+
+const compileGoto = (gotoNode, builder) => {
+  builder.addLine(`this.followGoto("${gotoNode.label.symbol}");`);
+  builder.addLine("return;");
+};
+
+const compileConditional = (conditionalNode, builder) => {
+  const variable = conditionalNode.variable.symbol;
+  builder.addLine(`if (this.get("${variable}") !== 0) {`);
+  builder.open();
+  compileGoto(conditionalNode.goto, builder);
+  builder.close("}");
+};
+
+const compileAssignment = (assignmentNode, builder) => {
+  const variable = assignmentNode.variable.symbol;
+  const expr = assignmentNode.expr || {};
+
+  if (expr.opr === "+") {
+    builder.addLine(`this.addOne("${variable}");`);
+  } else if (expr.opr === "-") {
+    builder.addLine(`this.subtractOne("${variable}");`);
+  } else {
+    builder.addLine("// noop");
+  }
+};
+
+const compileInstruction = (instruction, builder) => {
+  if (instruction.goto) {
+    compileGoto(instruction.goto, builder);
+    return;
+  }
+
+  if (instruction.conditional) {
+    compileConditional(instruction.conditional, builder);
+  } else if (instruction.assignment) {
+    compileAssignment(instruction.assignment, builder);
+  }
+
+  builder.addLine("this.instructionPointer++;");
+};
+
+const emitMethod = (builder, signature, bodyFn) => {
+  builder.addLine(`${signature} {`);
+  builder.open();
+  bodyFn();
+  builder.close("}");
+  builder.addLine("");
+};
+
+const emitConstructor = (builder, ast, godelSequence, methodCatalog) => {
+  emitMethod(builder, "constructor()", () => {
+    builder.addLine("this.variables = new Map();");
+    builder.addLine("this.labelInstructions = new Map();");
+    builder.addLine("this.instructions = new Map();");
+    builder.addLine("this.instructions.set(0, () => this.main());");
+    builder.addLine("this.instructionPointer = 0;");
+    builder.addLine('this.variables.set("Y", 0);');
+    builder.addLine(`this.finalInstruction = ${ast.instructions.length + 1};`);
+    builder.addLine('this.labelInstructions.set("E1", this.finalInstruction);');
+    builder.addLine("");
+    builder.addLine("// instruction bindings");
+
+    ast.instructions.forEach((entry, index) => {
+      const instructionNode = entry.instruction;
+      const instructionIdx = index + 1;
+      godelSequence.push(entry.godel);
+
+      if (instructionNode.label) {
+        const labelName = instructionNode.label.symbol;
+        builder.addLine(
+          `this.instructions.set(${instructionIdx}, () => this.${labelName}());`
+        );
+        builder.addLine(
+          `this.labelInstructions.set("${labelName}", ${instructionIdx});`
+        );
+        methodCatalog.push({
+          name: labelName,
+          index: instructionIdx,
+          node: instructionNode.instruction
+        });
+      } else {
+        const methodName = `instruction${instructionIdx}`;
+        builder.addLine(
+          `this.instructions.set(${instructionIdx}, () => this.${methodName}());`
+        );
+        methodCatalog.push({
+          name: methodName,
+          index: instructionIdx,
+          node: instructionNode
+        });
+      }
+    });
+  });
+};
+
+const emitRuntimeHelpers = (builder, instructionCount) => {
+  emitMethod(builder, "get(variable)", () => {
+    builder.addLine("if (!this.variables.has(variable)) {");
+    builder.open();
+    builder.addLine("this.variables.set(variable, 0);");
+    builder.close("}");
+    builder.addLine("return this.variables.get(variable);");
+  });
+
+  emitMethod(builder, "addOne(variable)", () => {
+    builder.addLine("const val = this.get(variable);");
+    builder.addLine("this.variables.set(variable, val + 1);");
+  });
+
+  emitMethod(builder, "subtractOne(variable)", () => {
+    builder.addLine("const val = this.get(variable);");
+    builder.addLine("this.variables.set(variable, val - 1);");
+  });
+
+  emitMethod(builder, "followGoto(label)", () => {
+    builder.addLine("this.instructionPointer = this.labelInstructions.get(label);");
+  });
+
+  emitMethod(builder, "step()", () => {
+    builder.addLine("if (!this.isCompleted()) {");
+    builder.open();
+    builder.addLine("const procedure = this.instructions.get(this.instructionPointer);");
+    builder.addLine("procedure();");
+    builder.close("}");
+    builder.addLine("return this.instructionPointer;");
+  });
+
+  emitMethod(builder, "isCompleted()", () => {
+    builder.addLine("return this.instructionPointer === this.finalInstruction;");
+  });
+
+  emitMethod(builder, "getResult()", () => {
+    builder.addLine('return this.variables.get("Y");');
+  });
+
+  emitMethod(builder, "run(maxIter = 500_000)", () => {
+    builder.addLine("let iter = 0;");
+    builder.addLine("while (!this.isCompleted() && ++iter < maxIter) {");
+    builder.open();
+    builder.addLine("this.step();");
+    builder.close("}");
+    builder.addLine("if (iter < maxIter) {");
+    builder.open();
+    builder.addLine("return this.getResult();");
+    builder.close("}");
+    builder.addLine(
+      'throw new Error("Program exceeded iteration limit. Try optimizing your instructions or increasing the cap.");'
+    );
+  });
+
+  emitMethod(builder, "main()", () => {
+    if (instructionCount > 0) {
+      builder.addLine("this.instructionPointer = 1;");
+    } else {
+      builder.addLine("this.instructionPointer = this.finalInstruction;");
+    }
+  });
+};
+
+const emitInstructionMethods = (builder, catalog) => {
+  catalog.forEach((entry) => {
+    emitMethod(builder, `${entry.name}()`, () => {
+      builder.addLine(`this.instructionPointer = ${entry.index};`);
+      compileInstruction(entry.node, builder);
+    });
+  });
+};
+
+export const compileProgram = (ast) => {
+  const builder = new CodeBuilder();
+  const godelSequence = [];
+  const methodCatalog = [];
+
+  builder.addLine("class Program {");
+  builder.open();
+  emitConstructor(builder, ast, godelSequence, methodCatalog);
+  emitRuntimeHelpers(builder, ast.instructions.length);
+  emitInstructionMethods(builder, methodCatalog);
+  builder.close("}");
+  builder.addLine("");
+  builder.addLine("// bootstrap");
+  builder.addLine("const program = new Program();");
+  builder.addLine('// program.variables.set("X1", 2);');
+  builder.addLine('// program.variables.set("X2", 3);');
+  builder.addLine("program.run();");
+  builder.addLine("console.log(program.variables);");
+  builder.addLine("program.getResult();");
+
+  return {
+    js: builder.toString(),
+    godelSequence
+  };
+};