diff options
Diffstat (limited to 'src/toys/godel/js')
| -rw-r--r-- | src/toys/godel/js/compiler.js | 226 | ||||
| -rw-r--r-- | src/toys/godel/js/godel-worker.js | 42 | ||||
| -rw-r--r-- | src/toys/godel/js/main.js | 5 | ||||
| -rw-r--r-- | src/toys/godel/js/parser.js | 1059 | ||||
| -rw-r--r-- | src/toys/godel/js/ui.js | 228 |
5 files changed, 1560 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 + }; +}; diff --git a/src/toys/godel/js/godel-worker.js b/src/toys/godel/js/godel-worker.js new file mode 100644 index 0000000..1ba9da4 --- /dev/null +++ b/src/toys/godel/js/godel-worker.js @@ -0,0 +1,42 @@ +const isPrime = (n) => { + if (n < 2) { + return false; + } + if (n === 2) { + return true; + } + if (n % 2 === 0) { + return false; + } + const limit = Math.floor(Math.sqrt(n)); + for (let i = 3; i <= limit; i += 2) { + if (n % i === 0) { + return false; + } + } + return true; +}; + +const primes = [2]; +const primeAt = (index) => { + while (primes.length < index) { + let candidate = primes[primes.length - 1] + 1; + while (!isPrime(candidate)) { + candidate += 1; + } + primes.push(candidate); + } + return primes[index - 1]; +}; + +const computeGodelNumber = (sequence) => { + return sequence.reduce((acc, exponent, idx) => { + const prime = BigInt(primeAt(idx + 1)); + return acc * prime ** BigInt(exponent); + }, BigInt(1)) - BigInt(1); +}; + +self.addEventListener("message", (event) => { + const result = computeGodelNumber(event.data); + self.postMessage(result.toString()); +}); diff --git a/src/toys/godel/js/main.js b/src/toys/godel/js/main.js new file mode 100644 index 0000000..b752206 --- /dev/null +++ b/src/toys/godel/js/main.js @@ -0,0 +1,5 @@ +import { GodelPlayground } from "./ui.js"; + +document.addEventListener("DOMContentLoaded", () => { + new GodelPlayground(); +}); diff --git a/src/toys/godel/js/parser.js b/src/toys/godel/js/parser.js new file mode 100644 index 0000000..a9436b6 --- /dev/null +++ b/src/toys/godel/js/parser.js @@ -0,0 +1,1059 @@ +const parser = /* + * Generated by PEG.js 0.10.0. + * + * http://pegjs.org/ + */ +(function() { + "use strict"; + + function peg$subclass(child, parent) { + function ctor() { this.constructor = child; } + ctor.prototype = parent.prototype; + child.prototype = new ctor(); + } + + function peg$SyntaxError(message, expected, found, location) { + this.message = message; + this.expected = expected; + this.found = found; + this.location = location; + this.name = "SyntaxError"; + + if (typeof Error.captureStackTrace === "function") { + Error.captureStackTrace(this, peg$SyntaxError); + } + } + + peg$subclass(peg$SyntaxError, Error); + + peg$SyntaxError.buildMessage = function(expected, found) { + var DESCRIBE_EXPECTATION_FNS = { + literal: function(expectation) { + return "\"" + literalEscape(expectation.text) + "\""; + }, + + "class": function(expectation) { + var escapedParts = "", + i; + + for (i = 0; i < expectation.parts.length; i++) { + escapedParts += expectation.parts[i] instanceof Array + ? classEscape(expectation.parts[i][0]) + "-" + classEscape(expectation.parts[i][1]) + : classEscape(expectation.parts[i]); + } + + return "[" + (expectation.inverted ? "^" : "") + escapedParts + "]"; + }, + + any: function(expectation) { + return "any character"; + }, + + end: function(expectation) { + return "end of input"; + }, + + other: function(expectation) { + return expectation.description; + } + }; + + function hex(ch) { + return ch.charCodeAt(0).toString(16).toUpperCase(); + } + + function literalEscape(s) { + return s + .replace(/\\/g, '\\\\') + .replace(/"/g, '\\"') + .replace(/\0/g, '\\0') + .replace(/\t/g, '\\t') + .replace(/\n/g, '\\n') + .replace(/\r/g, '\\r') + .replace(/[\x00-\x0F]/g, function(ch) { return '\\x0' + hex(ch); }) + .replace(/[\x10-\x1F\x7F-\x9F]/g, function(ch) { return '\\x' + hex(ch); }); + } + + function classEscape(s) { + return s + .replace(/\\/g, '\\\\') + .replace(/\]/g, '\\]') + .replace(/\^/g, '\\^') + .replace(/-/g, '\\-') + .replace(/\0/g, '\\0') + .replace(/\t/g, '\\t') + .replace(/\n/g, '\\n') + .replace(/\r/g, '\\r') + .replace(/[\x00-\x0F]/g, function(ch) { return '\\x0' + hex(ch); }) + .replace(/[\x10-\x1F\x7F-\x9F]/g, function(ch) { return '\\x' + hex(ch); }); + } + + function describeExpectation(expectation) { + return DESCRIBE_EXPECTATION_FNS[expectation.type](expectation); + } + + function describeExpected(expected) { + var descriptions = new Array(expected.length), + i, j; + + for (i = 0; i < expected.length; i++) { + descriptions[i] = describeExpectation(expected[i]); + } + + descriptions.sort(); + + if (descriptions.length > 0) { + for (i = 1, j = 1; i < descriptions.length; i++) { + if (descriptions[i - 1] !== descriptions[i]) { + descriptions[j] = descriptions[i]; + j++; + } + } + descriptions.length = j; + } + + switch (descriptions.length) { + case 1: + return descriptions[0]; + + case 2: + return descriptions[0] + " or " + descriptions[1]; + + default: + return descriptions.slice(0, -1).join(", ") + + ", or " + + descriptions[descriptions.length - 1]; + } + } + + function describeFound(found) { + return found ? "\"" + literalEscape(found) + "\"" : "end of input"; + } + + return "Expected " + describeExpected(expected) + " but " + describeFound(found) + " found."; + }; + + function peg$parse(input, options) { + options = options !== void 0 ? options : {}; + + var peg$FAILED = {}, + + peg$startRuleFunctions = { Program: peg$parseProgram }, + peg$startRuleFunction = peg$parseProgram, + + peg$c0 = /^[\n]/, + peg$c1 = peg$classExpectation(["\n"], false, false), + peg$c2 = function(lines) { + return { instructions: lines.filter((line) => typeof line !== "string" || line.trim() != "") }; + }, + peg$c3 = function(instruction) { + let x = 0; + let y = 0; + if (instruction.label) { + x = instruction.label.godel; + y = instruction.instruction.godel; + } else { + y = instruction.godel; + } + return { instruction, godel: ((2 ** x) * ((2 * y) + 1) - 1) }; + }, + peg$c4 = function(label, instruction) { + return { label, instruction }; + }, + peg$c5 = "[", + peg$c6 = peg$literalExpectation("[", false), + peg$c7 = "]", + peg$c8 = peg$literalExpectation("]", false), + peg$c9 = function(label) { + return label; + }, + peg$c10 = function(conditional) { return { conditional, godel: conditional.godel }; }, + peg$c11 = function(assignment) { return { assignment, godel: assignment.godel }; }, + peg$c12 = function(goto) { return { goto, godel: goto.godel }; }, + peg$c13 = function(label) { + return { label, godel: label.godel + 2 }; + }, + peg$c14 = "IF", + peg$c15 = peg$literalExpectation("IF", false), + peg$c16 = "!=", + peg$c17 = peg$literalExpectation("!=", false), + peg$c18 = "0", + peg$c19 = peg$literalExpectation("0", false), + peg$c20 = function(variable, goto) { + const y = variable.godel - 1; + const x = goto.godel; + return { variable, goto, godel: ((2 ** x) * ((2 * y) + 1) - 1) }; + }, + peg$c21 = "<-", + peg$c22 = peg$literalExpectation("<-", false), + peg$c23 = function(variable, expr) { + if (expr.left.symbol != variable.symbol) { + error("left hand variable must match right hand"); + } + const x = expr.instructionNumber; + const y = variable.godel - 1; + return { variable, expr, godel: ((2 ** x) * ((2 * y) + 1) - 1) }; + }, + peg$c24 = "1", + peg$c25 = peg$literalExpectation("1", false), + peg$c26 = function(left, opr) { + const instructionNumber = { "+" : 1, "-" : 2 }[opr]; + return { left, opr, instructionNumber }; + }, + peg$c27 = function(left) { + return { left, instructionNumber: 0 }; + }, + peg$c28 = "Y", + peg$c29 = peg$literalExpectation("Y", false), + peg$c30 = function(symbol) { return { symbol, godel: 1 }; }, + peg$c31 = "X", + peg$c32 = peg$literalExpectation("X", false), + peg$c33 = "Z", + peg$c34 = peg$literalExpectation("Z", false), + peg$c35 = function(symbol, ind) { + const index = parseInt(ind); + const order = ["X", "Z"]; + const godel = index * order.length + order.indexOf(symbol); + return { symbol: symbol + ind, godel }; + }, + peg$c36 = "GOTO", + peg$c37 = peg$literalExpectation("GOTO", false), + peg$c38 = "+", + peg$c39 = peg$literalExpectation("+", false), + peg$c40 = "-", + peg$c41 = peg$literalExpectation("-", false), + peg$c42 = /^[A-E]/, + peg$c43 = peg$classExpectation([["A", "E"]], false, false), + peg$c44 = function(symbol, ind) { + const index = parseInt(ind); + const godel = (symbol.charCodeAt(0) - "A".charCodeAt(0) + 1) + 5*(index-1); + return { symbol: symbol + ind, godel }; + }, + peg$c45 = peg$otherExpectation("integer"), + peg$c46 = /^[0-9]/, + peg$c47 = peg$classExpectation([["0", "9"]], false, false), + peg$c48 = function() { return parseInt(text(), 10); }, + peg$c49 = peg$otherExpectation("whitespace"), + peg$c50 = /^[ \t]/, + peg$c51 = peg$classExpectation([" ", "\t"], false, false), + peg$c52 = function() { }, + + peg$currPos = 0, + peg$savedPos = 0, + peg$posDetailsCache = [{ line: 1, column: 1 }], + peg$maxFailPos = 0, + peg$maxFailExpected = [], + peg$silentFails = 0, + + peg$result; + + if ("startRule" in options) { + if (!(options.startRule in peg$startRuleFunctions)) { + throw new Error("Can't start parsing from rule \"" + options.startRule + "\"."); + } + + peg$startRuleFunction = peg$startRuleFunctions[options.startRule]; + } + + function text() { + return input.substring(peg$savedPos, peg$currPos); + } + + function location() { + return peg$computeLocation(peg$savedPos, peg$currPos); + } + + function expected(description, location) { + location = location !== void 0 ? location : peg$computeLocation(peg$savedPos, peg$currPos) + + throw peg$buildStructuredError( + [peg$otherExpectation(description)], + input.substring(peg$savedPos, peg$currPos), + location + ); + } + + function error(message, location) { + location = location !== void 0 ? location : peg$computeLocation(peg$savedPos, peg$currPos) + + throw peg$buildSimpleError(message, location); + } + + function peg$literalExpectation(text, ignoreCase) { + return { type: "literal", text: text, ignoreCase: ignoreCase }; + } + + function peg$classExpectation(parts, inverted, ignoreCase) { + return { type: "class", parts: parts, inverted: inverted, ignoreCase: ignoreCase }; + } + + function peg$anyExpectation() { + return { type: "any" }; + } + + function peg$endExpectation() { + return { type: "end" }; + } + + function peg$otherExpectation(description) { + return { type: "other", description: description }; + } + + function peg$computePosDetails(pos) { + var details = peg$posDetailsCache[pos], p; + + if (details) { + return details; + } else { + p = pos - 1; + while (!peg$posDetailsCache[p]) { + p--; + } + + details = peg$posDetailsCache[p]; + details = { + line: details.line, + column: details.column + }; + + while (p < pos) { + if (input.charCodeAt(p) === 10) { + details.line++; + details.column = 1; + } else { + details.column++; + } + + p++; + } + + peg$posDetailsCache[pos] = details; + return details; + } + } + + function peg$computeLocation(startPos, endPos) { + var startPosDetails = peg$computePosDetails(startPos), + endPosDetails = peg$computePosDetails(endPos); + + return { + start: { + offset: startPos, + line: startPosDetails.line, + column: startPosDetails.column + }, + end: { + offset: endPos, + line: endPosDetails.line, + column: endPosDetails.column + } + }; + } + + function peg$fail(expected) { + if (peg$currPos < peg$maxFailPos) { return; } + + if (peg$currPos > peg$maxFailPos) { + peg$maxFailPos = peg$currPos; + peg$maxFailExpected = []; + } + + peg$maxFailExpected.push(expected); + } + + function peg$buildSimpleError(message, location) { + return new peg$SyntaxError(message, null, null, location); + } + + function peg$buildStructuredError(expected, found, location) { + return new peg$SyntaxError( + peg$SyntaxError.buildMessage(expected, found), + expected, + found, + location + ); + } + + function peg$parseProgram() { + var s0, s1, s2; + + s0 = peg$currPos; + s1 = []; + s2 = peg$parseProgramInstruction(); + if (s2 === peg$FAILED) { + s2 = peg$parse_(); + if (s2 === peg$FAILED) { + if (peg$c0.test(input.charAt(peg$currPos))) { + s2 = input.charAt(peg$currPos); + peg$currPos++; + } else { + s2 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c1); } + } + } + } + while (s2 !== peg$FAILED) { + s1.push(s2); + s2 = peg$parseProgramInstruction(); + if (s2 === peg$FAILED) { + s2 = peg$parse_(); + if (s2 === peg$FAILED) { + if (peg$c0.test(input.charAt(peg$currPos))) { + s2 = input.charAt(peg$currPos); + peg$currPos++; + } else { + s2 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c1); } + } + } + } + } + if (s1 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c2(s1); + } + s0 = s1; + + return s0; + } + + function peg$parseProgramInstruction() { + var s0, s1, s2, s3, s4; + + s0 = peg$currPos; + s1 = peg$parse_(); + if (s1 === peg$FAILED) { + s1 = null; + } + if (s1 !== peg$FAILED) { + s2 = peg$parseLabeledInstruction(); + if (s2 === peg$FAILED) { + s2 = peg$parseInstruction(); + } + if (s2 !== peg$FAILED) { + s3 = peg$parse_(); + if (s3 === peg$FAILED) { + s3 = null; + } + if (s3 !== peg$FAILED) { + if (peg$c0.test(input.charAt(peg$currPos))) { + s4 = input.charAt(peg$currPos); + peg$currPos++; + } else { + s4 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c1); } + } + if (s4 === peg$FAILED) { + s4 = null; + } + if (s4 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c3(s2); + s0 = s1; + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + + return s0; + } + + function peg$parseLabeledInstruction() { + var s0, s1, s2, s3; + + s0 = peg$currPos; + s1 = peg$parseLabel(); + if (s1 !== peg$FAILED) { + s2 = peg$parse_(); + if (s2 !== peg$FAILED) { + s3 = peg$parseInstruction(); + if (s3 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c4(s1, s3); + s0 = s1; + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + + return s0; + } + + function peg$parseLabel() { + var s0, s1, s2, s3, s4, s5; + + s0 = peg$currPos; + if (input.charCodeAt(peg$currPos) === 91) { + s1 = peg$c5; + peg$currPos++; + } else { + s1 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c6); } + } + if (s1 !== peg$FAILED) { + s2 = peg$parse_(); + if (s2 === peg$FAILED) { + s2 = null; + } + if (s2 !== peg$FAILED) { + s3 = peg$parseLABEL_V(); + if (s3 !== peg$FAILED) { + s4 = peg$parse_(); + if (s4 === peg$FAILED) { + s4 = null; + } + if (s4 !== peg$FAILED) { + if (input.charCodeAt(peg$currPos) === 93) { + s5 = peg$c7; + peg$currPos++; + } else { + s5 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c8); } + } + if (s5 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c9(s3); + s0 = s1; + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + + return s0; + } + + function peg$parseInstruction() { + var s0, s1; + + s0 = peg$currPos; + s1 = peg$parseConditional(); + if (s1 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c10(s1); + } + s0 = s1; + if (s0 === peg$FAILED) { + s0 = peg$currPos; + s1 = peg$parseAssignment(); + if (s1 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c11(s1); + } + s0 = s1; + if (s0 === peg$FAILED) { + s0 = peg$currPos; + s1 = peg$parseGoto(); + if (s1 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c12(s1); + } + s0 = s1; + } + } + + return s0; + } + + function peg$parseGoto() { + var s0, s1, s2, s3; + + s0 = peg$currPos; + s1 = peg$parseGOTO(); + if (s1 !== peg$FAILED) { + s2 = peg$parse_(); + if (s2 !== peg$FAILED) { + s3 = peg$parseLABEL_V(); + if (s3 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c13(s3); + s0 = s1; + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + + return s0; + } + + function peg$parseConditional() { + var s0, s1, s2, s3, s4, s5, s6, s7, s8, s9; + + s0 = peg$currPos; + if (input.substr(peg$currPos, 2) === peg$c14) { + s1 = peg$c14; + peg$currPos += 2; + } else { + s1 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c15); } + } + if (s1 !== peg$FAILED) { + s2 = peg$parse_(); + if (s2 !== peg$FAILED) { + s3 = peg$parseVAR(); + if (s3 !== peg$FAILED) { + s4 = peg$parse_(); + if (s4 === peg$FAILED) { + s4 = null; + } + if (s4 !== peg$FAILED) { + if (input.substr(peg$currPos, 2) === peg$c16) { + s5 = peg$c16; + peg$currPos += 2; + } else { + s5 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c17); } + } + if (s5 !== peg$FAILED) { + s6 = peg$parse_(); + if (s6 === peg$FAILED) { + s6 = null; + } + if (s6 !== peg$FAILED) { + if (input.charCodeAt(peg$currPos) === 48) { + s7 = peg$c18; + peg$currPos++; + } else { + s7 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c19); } + } + if (s7 !== peg$FAILED) { + s8 = peg$parse_(); + if (s8 !== peg$FAILED) { + s9 = peg$parseGoto(); + if (s9 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c20(s3, s9); + s0 = s1; + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + + return s0; + } + + function peg$parseAssignment() { + var s0, s1, s2, s3, s4, s5; + + s0 = peg$currPos; + s1 = peg$parseVAR(); + if (s1 !== peg$FAILED) { + s2 = peg$parse_(); + if (s2 !== peg$FAILED) { + if (input.substr(peg$currPos, 2) === peg$c21) { + s3 = peg$c21; + peg$currPos += 2; + } else { + s3 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c22); } + } + if (s3 !== peg$FAILED) { + s4 = peg$parse_(); + if (s4 !== peg$FAILED) { + s5 = peg$parseExpression(); + if (s5 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c23(s1, s5); + s0 = s1; + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + + return s0; + } + + function peg$parseExpression() { + var s0, s1, s2, s3, s4, s5; + + s0 = peg$currPos; + s1 = peg$parseVAR(); + if (s1 !== peg$FAILED) { + s2 = peg$parse_(); + if (s2 !== peg$FAILED) { + s3 = peg$parseOPERATION(); + if (s3 !== peg$FAILED) { + s4 = peg$parse_(); + if (s4 !== peg$FAILED) { + if (input.charCodeAt(peg$currPos) === 49) { + s5 = peg$c24; + peg$currPos++; + } else { + s5 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c25); } + } + if (s5 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c26(s1, s3); + s0 = s1; + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + if (s0 === peg$FAILED) { + s0 = peg$currPos; + s1 = peg$parseVAR(); + if (s1 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c27(s1); + } + s0 = s1; + } + + return s0; + } + + function peg$parseVAR() { + var s0, s1, s2, s3; + + s0 = peg$currPos; + if (input.charCodeAt(peg$currPos) === 89) { + s1 = peg$c28; + peg$currPos++; + } else { + s1 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c29); } + } + if (s1 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c30(s1); + } + s0 = s1; + if (s0 === peg$FAILED) { + s0 = peg$currPos; + if (input.charCodeAt(peg$currPos) === 88) { + s1 = peg$c31; + peg$currPos++; + } else { + s1 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c32); } + } + if (s1 === peg$FAILED) { + if (input.charCodeAt(peg$currPos) === 90) { + s1 = peg$c33; + peg$currPos++; + } else { + s1 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c34); } + } + } + if (s1 !== peg$FAILED) { + s2 = []; + s3 = peg$parseInteger(); + if (s3 !== peg$FAILED) { + while (s3 !== peg$FAILED) { + s2.push(s3); + s3 = peg$parseInteger(); + } + } else { + s2 = peg$FAILED; + } + if (s2 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c35(s1, s2); + s0 = s1; + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } + + return s0; + } + + function peg$parseGOTO() { + var s0; + + if (input.substr(peg$currPos, 4) === peg$c36) { + s0 = peg$c36; + peg$currPos += 4; + } else { + s0 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c37); } + } + + return s0; + } + + function peg$parseOPERATION() { + var s0; + + if (input.charCodeAt(peg$currPos) === 43) { + s0 = peg$c38; + peg$currPos++; + } else { + s0 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c39); } + } + if (s0 === peg$FAILED) { + if (input.charCodeAt(peg$currPos) === 45) { + s0 = peg$c40; + peg$currPos++; + } else { + s0 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c41); } + } + } + + return s0; + } + + function peg$parseLABEL_V() { + var s0, s1, s2, s3; + + s0 = peg$currPos; + if (peg$c42.test(input.charAt(peg$currPos))) { + s1 = input.charAt(peg$currPos); + peg$currPos++; + } else { + s1 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c43); } + } + if (s1 !== peg$FAILED) { + s2 = []; + s3 = peg$parseInteger(); + if (s3 !== peg$FAILED) { + while (s3 !== peg$FAILED) { + s2.push(s3); + s3 = peg$parseInteger(); + } + } else { + s2 = peg$FAILED; + } + if (s2 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c44(s1, s2); + s0 = s1; + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + } else { + peg$currPos = s0; + s0 = peg$FAILED; + } + + return s0; + } + + function peg$parseInteger() { + var s0, s1, s2; + + peg$silentFails++; + s0 = peg$currPos; + s1 = []; + if (peg$c46.test(input.charAt(peg$currPos))) { + s2 = input.charAt(peg$currPos); + peg$currPos++; + } else { + s2 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c47); } + } + if (s2 !== peg$FAILED) { + while (s2 !== peg$FAILED) { + s1.push(s2); + if (peg$c46.test(input.charAt(peg$currPos))) { + s2 = input.charAt(peg$currPos); + peg$currPos++; + } else { + s2 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c47); } + } + } + } else { + s1 = peg$FAILED; + } + if (s1 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c48(); + } + s0 = s1; + peg$silentFails--; + if (s0 === peg$FAILED) { + s1 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c45); } + } + + return s0; + } + + function peg$parse_() { + var s0, s1, s2; + + peg$silentFails++; + s0 = peg$currPos; + s1 = []; + if (peg$c50.test(input.charAt(peg$currPos))) { + s2 = input.charAt(peg$currPos); + peg$currPos++; + } else { + s2 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c51); } + } + if (s2 !== peg$FAILED) { + while (s2 !== peg$FAILED) { + s1.push(s2); + if (peg$c50.test(input.charAt(peg$currPos))) { + s2 = input.charAt(peg$currPos); + peg$currPos++; + } else { + s2 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c51); } + } + } + } else { + s1 = peg$FAILED; + } + if (s1 !== peg$FAILED) { + peg$savedPos = s0; + s1 = peg$c52(); + } + s0 = s1; + peg$silentFails--; + if (s0 === peg$FAILED) { + s1 = peg$FAILED; + if (peg$silentFails === 0) { peg$fail(peg$c49); } + } + + return s0; + } + + peg$result = peg$startRuleFunction(); + + if (peg$result !== peg$FAILED && peg$currPos === input.length) { + return peg$result; + } else { + if (peg$result !== peg$FAILED && peg$currPos < input.length) { + peg$fail(peg$endExpectation()); + } + + throw peg$buildStructuredError( + peg$maxFailExpected, + peg$maxFailPos < input.length ? input.charAt(peg$maxFailPos) : null, + peg$maxFailPos < input.length + ? peg$computeLocation(peg$maxFailPos, peg$maxFailPos + 1) + : peg$computeLocation(peg$maxFailPos, peg$maxFailPos) + ); + } + } + + return { + SyntaxError: peg$SyntaxError, + parse: peg$parse + }; +})(); + +export default parser; +export const SyntaxError = parser.SyntaxError; diff --git a/src/toys/godel/js/ui.js b/src/toys/godel/js/ui.js new file mode 100644 index 0000000..2952140 --- /dev/null +++ b/src/toys/godel/js/ui.js @@ -0,0 +1,228 @@ +import parser from "./parser.js"; +import { compileProgram } from "./compiler.js"; + +const SAMPLE_PROGRAM = `// THIS PROGRAM COMPUTES X1 + X2 + +// Y <- X1 +[ A1 ] IF X1 != 0 GOTO A2 + GOTO B1 +[ A2 ] X1 <- X1 - 1 + Y <- Y + 1 + GOTO A1 + +// Z1 <- X2 +[ B1 ] IF X2 != 0 GOTO B2 + GOTO C1 +[ B2 ] X2 <- X2 - 1 + Z1 <- Z1 + 1 + GOTO B1 + +// Y <- Y + Z1 +[ C1 ] IF Z1 != 0 GOTO C2 + GOTO E1 +[ C2 ] Z1 <- Z1 - 1 + Y <- Y + 1 + GOTO C1`; + +const STATUS_VARIANTS = { + success: "text-success", + error: "text-error", + info: "muted" +}; + +export class GodelPlayground { + constructor() { + this.elements = { + compileBtn: document.getElementById("compile-btn"), + copyBtn: document.getElementById("copy-btn"), + evalBtn: document.getElementById("eval-btn"), + computeNumberBtn: document.getElementById("compute-godel-btn"), + compileStatus: document.getElementById("compile-status"), + evalStatus: document.getElementById("eval-status"), + godelSequence: document.getElementById("godel-sequence"), + godelNumber: document.getElementById("godel-number") + }; + + this.sourceEditor = null; + this.compiledEditor = null; + this.worker = null; + this.latestSequence = []; + + this.init(); + } + + init() { + this.setupEditors(); + this.bindEvents(); + this.hydrateFromParams(); + if (!this.getSource().trim()) { + this.setSource(SAMPLE_PROGRAM); + } + this.compileSource(); + } + + setupEditors() { + this.sourceEditor = adelieEditor.init("#source-editor", { + language: "javascript" + }); + this.compiledEditor = adelieEditor.init("#compiled-editor", { + language: "javascript" + }); + this.setSource(SAMPLE_PROGRAM); + } + + bindEvents() { + this.elements.compileBtn.addEventListener("click", () => this.compileSource()); + this.elements.evalBtn.addEventListener("click", () => this.evaluateCompiled()); + this.elements.copyBtn.addEventListener("click", () => this.copyShareLink()); + this.elements.computeNumberBtn.addEventListener("click", () => this.computeGodelNumber()); + + document.addEventListener("keydown", (event) => { + if (event.ctrlKey && event.key === "Enter") { + event.preventDefault(); + this.compileSource(); + } + }); + } + + hydrateFromParams() { + const params = new URLSearchParams(window.location.search); + const encoded = params.get("instructions"); + if (encoded) { + try { + const decoded = atob(encoded); + this.setSource(decoded); + } catch (error) { + console.warn("Failed to decode instructions from URL", error); + } + } + } + + getSource() { + return this.sourceEditor.state.doc.toString(); + } + + setSource(content) { + const docLength = this.sourceEditor.state.doc.toString().length; + this.sourceEditor.dispatch({ + changes: { from: 0, to: docLength, insert: content } + }); + } + + getCompiled() { + return this.compiledEditor.state.doc.toString(); + } + + setCompiled(content) { + const docLength = this.compiledEditor.state.doc.toString().length; + this.compiledEditor.dispatch({ + changes: { from: 0, to: docLength, insert: content } + }); + } + + prepareSource(source) { + return source.replace(/\/\/.*$/gm, "").trim(); + } + + compileSource() { + const raw = this.getSource(); + const prepared = this.prepareSource(raw); + + if (!prepared) { + this.setStatus("compile", "Provide some source to compile", "error"); + return; + } + + try { + const ast = parser.parse(prepared); + const { js, godelSequence } = compileProgram(ast); + this.latestSequence = godelSequence; + this.setCompiled(js); + this.renderSequence(godelSequence); + this.setStatus( + "compile", + `Compiled ${godelSequence.length} instruction${godelSequence.length === 1 ? "" : "s"}.`, + "success" + ); + this.elements.computeNumberBtn.disabled = godelSequence.length === 0; + } catch (error) { + this.latestSequence = []; + this.renderSequence([]); + this.elements.computeNumberBtn.disabled = true; + this.setStatus("compile", error.message || "Failed to compile program", "error"); + } + } + + evaluateCompiled() { + const js = this.getCompiled(); + if (!js.trim()) { + this.setStatus("eval", "Compile a program first", "error"); + return; + } + + try { + const result = (0, eval)(js); + this.setStatus( + "eval", + `Result: ${typeof result === "undefined" ? "(no return)" : result}`, + "success" + ); + } catch (error) { + this.setStatus("eval", error.message || "Failed to evaluate program", "error"); + } + } + + renderSequence(sequence) { + if (!sequence.length) { + this.elements.godelSequence.textContent = "Compile to view the Gödel sequence."; + this.elements.godelNumber.textContent = ""; + return; + } + this.elements.godelSequence.textContent = `[${sequence.join(", ")}]`; + this.elements.godelNumber.textContent = ""; + } + + copyShareLink() { + const data = btoa(this.getSource()); + const url = `${window.location.href.split("?")[0]}?instructions=${data}`; + + navigator.clipboard.writeText(url) + .then(() => alert("Shareable link copied to clipboard")) + .catch(() => alert("Failed to copy link")); + } + + computeGodelNumber() { + if (!this.latestSequence.length) { + this.setStatus("compile", "Compile a program to produce its Gödel sequence", "error"); + return; + } + + this.elements.godelNumber.textContent = "Working..."; + this.elements.computeNumberBtn.disabled = true; + + const worker = this.getWorker(); + worker.onmessage = (event) => { + this.elements.godelNumber.textContent = event.data; + this.elements.computeNumberBtn.disabled = false; + }; + worker.onerror = () => { + this.elements.godelNumber.textContent = "Failed to compute Gödel number"; + this.elements.computeNumberBtn.disabled = false; + }; + worker.postMessage(this.latestSequence); + } + + getWorker() { + if (!this.worker) { + const workerUrl = new URL("./godel-worker.js", import.meta.url); + this.worker = new Worker(workerUrl, { type: "module" }); + } + return this.worker; + } + + setStatus(kind, message, variant = "info") { + const element = kind === "compile" ? this.elements.compileStatus : this.elements.evalStatus; + element.textContent = message; + element.className = `status-text ${STATUS_VARIANTS[variant] || ""}`; + } +} |
