From 91b7598b22f89319f64054daf42c950de3eb6451 Mon Sep 17 00:00:00 2001 From: Elizabeth Hunt Date: Wed, 7 Jan 2026 19:29:30 -0800 Subject: Adding some of my favorite toys --- src/toys/turing/js/machine.js | 75 ++++++++ src/toys/turing/js/main.js | 4 + src/toys/turing/js/parser.js | 141 +++++++++++++++ src/toys/turing/js/samples.js | 88 ++++++++++ src/toys/turing/js/tape.js | 103 +++++++++++ src/toys/turing/js/ui.js | 386 ++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 797 insertions(+) create mode 100644 src/toys/turing/js/machine.js create mode 100644 src/toys/turing/js/main.js create mode 100644 src/toys/turing/js/parser.js create mode 100644 src/toys/turing/js/samples.js create mode 100644 src/toys/turing/js/tape.js create mode 100644 src/toys/turing/js/ui.js (limited to 'src/toys/turing/js') diff --git a/src/toys/turing/js/machine.js b/src/toys/turing/js/machine.js new file mode 100644 index 0000000..6af4be6 --- /dev/null +++ b/src/toys/turing/js/machine.js @@ -0,0 +1,75 @@ +export class TuringMachine { + constructor({ + tape, + rules, + startState, + acceptStates = [], + rejectStates = [] + }) { + this.tape = tape; + this.rules = rules; + this.state = startState; + this.acceptStates = new Set(acceptStates); + this.rejectStates = new Set(rejectStates); + this.iteration = 0; + } + + step() { + if (this.isHalted()) { + return false; + } + + const currentSymbol = this.tape.readHead(); + const ruleKey = this.getRuleKey(this.state, currentSymbol); + if (!this.rules.has(ruleKey)) { + return false; + } + + const { nextState, writeSymbol, direction } = this.rules.get(ruleKey); + this.tape.writeHead(writeSymbol); + + if (direction === "R") { + this.tape.moveRight(); + } else if (direction === "L") { + this.tape.moveLeft(); + } + + this.state = nextState; + this.iteration += 1; + return !this.isHalted(); + } + + canStep() { + if (this.isHalted()) { + return false; + } + + const currentSymbol = this.tape.readHead(); + const ruleKey = this.getRuleKey(this.state, currentSymbol); + return this.rules.has(ruleKey); + } + + getRuleKey(state, symbol) { + return `${state}:${symbol}`; + } + + isAccepting() { + return this.acceptStates.has(this.state); + } + + isRejecting() { + return this.rejectStates.has(this.state); + } + + isHalted() { + return this.isAccepting() || this.isRejecting(); + } + + getStateStatus() { + return `State: ${this.state}, Step: ${this.iteration}`; + } + + getState() { + return this.state; + } +} diff --git a/src/toys/turing/js/main.js b/src/toys/turing/js/main.js new file mode 100644 index 0000000..c9f37fc --- /dev/null +++ b/src/toys/turing/js/main.js @@ -0,0 +1,4 @@ +import { TuringMachineUI } from "./ui.js"; +document.addEventListener("DOMContentLoaded", (event) => { + new TuringMachineUI(); +}); diff --git a/src/toys/turing/js/parser.js b/src/toys/turing/js/parser.js new file mode 100644 index 0000000..dd65613 --- /dev/null +++ b/src/toys/turing/js/parser.js @@ -0,0 +1,141 @@ +export function parseInstructionSet(code) { + const lines = code.split("\n"); + const instructions = []; + const config = { + startState: null, + acceptStates: new Set(), + rejectStates: new Set() + }; + + lines.forEach((line, lineIndex) => { + const withoutComments = line.replace(/\/\/.*$/, "").trim(); + if (!withoutComments) { + return; + } + + if (withoutComments.startsWith("#")) { + applyDirective(withoutComments.slice(1).trim(), config, lineIndex + 1); + return; + } + + const parts = withoutComments.split(/\s+/).filter(Boolean); + if (parts.length !== 5) { + throw new Error(`Invalid instruction on line ${lineIndex + 1}: expected 5 parts, received ${parts.length}`); + } + + const [fromState, readSymbol, writeSymbol, direction, toState] = parts; + if (!config.startState) { + config.startState = fromState; + } + + instructions.push({ fromState, readSymbol, writeSymbol, direction, toState, line: lineIndex + 1 }); + }); + + if (!instructions.length) { + throw new Error("No instructions provided"); + } + + const { acceptStates, rejectStates } = deriveHaltingStates(instructions, config); + const rules = buildRuleMap(instructions); + + return { + rules, + startState: config.startState ?? instructions[0].fromState, + acceptStates, + rejectStates + }; +} + +function applyDirective(directiveLine, config, lineNumber) { + if (!directiveLine) { + return; + } + + const [keyword, ...values] = directiveLine.split(/\s+/).filter(Boolean); + if (!keyword) { + return; + } + + switch (keyword.toLowerCase()) { + case "start": { + if (values.length !== 1) { + throw new Error(`#start on line ${lineNumber} must provide exactly one state`); + } + config.startState = values[0]; + break; + } + case "accept": + case "accepts": + case "accepting": { + if (!values.length) { + throw new Error(`#${keyword} on line ${lineNumber} must include at least one state`); + } + values.forEach((value) => config.acceptStates.add(value)); + break; + } + case "reject": + case "rejects": + case "rejecting": { + if (!values.length) { + throw new Error(`#${keyword} on line ${lineNumber} must include at least one state`); + } + values.forEach((value) => config.rejectStates.add(value)); + break; + } + default: + throw new Error(`Unknown directive '#${keyword}' on line ${lineNumber}`); + } +} + +function deriveHaltingStates(instructions, config) { + const fromStates = new Set(); + const toStates = new Set(); + const allStates = new Set(); + + instructions.forEach(({ fromState, toState }) => { + fromStates.add(fromState); + toStates.add(toState); + allStates.add(fromState); + allStates.add(toState); + }); + + // Remove any overlap so rejects always win + config.rejectStates.forEach((state) => config.acceptStates.delete(state)); + + if (!config.acceptStates.size) { + for (const state of allStates) { + if (!fromStates.has(state) && toStates.has(state) && !config.rejectStates.has(state)) { + config.acceptStates.add(state); + } + } + } + + return { + acceptStates: Array.from(config.acceptStates), + rejectStates: Array.from(config.rejectStates) + }; +} + +function buildRuleMap(instructions) { + const rules = new Map(); + + instructions.forEach(({ fromState, readSymbol, writeSymbol, direction, toState, line }) => { + const dir = direction.toUpperCase(); + if (!["L", "R", "S"].includes(dir)) { + throw new Error(`Invalid direction '${direction}' on line ${line}. Use L, R, or S.`); + } + + const key = `${fromState}:${readSymbol}`; + if (rules.has(key)) { + throw new Error(`Duplicate rule for state '${fromState}' reading '${readSymbol}' (line ${line})`); + } + + rules.set(key, { + nextState: toState, + writeSymbol, + direction: dir + }); + }); + + return rules; +} diff --git a/src/toys/turing/js/samples.js b/src/toys/turing/js/samples.js new file mode 100644 index 0000000..4d76b49 --- /dev/null +++ b/src/toys/turing/js/samples.js @@ -0,0 +1,88 @@ +// Example programs with initial tape states +export const EXAMPLE_PROGRAMS = [ + { + name: "Replace two B's", + code: `#start q0 +#accept acc +#reject rej + +q0 B 1 R q1 +q1 1 1 R q1 +q1 B 1 R acc`, + initialTape: "" + }, + { + name: "Binary equality checker", + code: `// https://stackoverflow.com/questions/59045832 + +#start q0 +#accept acc +#reject rej + +q0 0 X R q1 +q0 1 X R q2 +q0 = = R q7 +q1 0 0 R q1 +q1 1 1 R q1 +q1 = = R q3 +q2 0 0 R q2 +q2 1 1 R q2 +q2 = = R q4 +q3 X X R q3 +q3 0 X L q5 +q3 1 1 L rej +q3 B B L rej +q4 X X R q4 +q4 0 0 L rej +q4 B B L rej +q4 1 X L q5 +q5 X X L q5 +q5 = = L q6 +q6 0 0 L q6 +q6 1 1 L q6 +q6 X X R q0 +q7 X X R q7 +q7 B B L q8 +q7 0 0 L rej +q7 1 1 L rej +q8 X X L q8 +q8 0 0 L q8 +q8 1 1 L q8 +q8 = = acc`, + initialTape: "1011=1011" + }, + { + name: "Binary addition", + code: `// https://stackoverflow.com/questions/59045832 + +#start q0 +#accept acc +#reject rej + +q0 B B R q0 +q0 0 0 R q0 +q0 1 1 R q0 +q0 + + R q1 +q1 0 0 R q1 +q1 1 1 R q1 +q1 B B L q2 +q2 0 1 L q2 +q2 1 0 L q3 +q2 + + R q5 +q3 0 0 L q3 +q3 1 1 L q3 +q3 + + L q4 +q4 0 1 R q0 +q4 1 0 L q4 +q4 B 1 R q0 +q5 1 B R q5 +q5 B B R q6 +q6 B B L q6 +q6 + B L q7 +q7 0 0 L q7 +q7 1 1 L q7 +q7 B B R acc +`, + initialTape: "101+110" + } +]; diff --git a/src/toys/turing/js/tape.js b/src/toys/turing/js/tape.js new file mode 100644 index 0000000..fd05366 --- /dev/null +++ b/src/toys/turing/js/tape.js @@ -0,0 +1,103 @@ +const ESCAPE_REGEX = /[.*+?^${}()|[\]\\]/g; + +function escapeForRegex(value) { + return value.replace(ESCAPE_REGEX, "\\$&"); +} + +export class Tape { + constructor({ + initialContent = "", + blankSymbol = "B", + minLength = 50, + padding = 40 + } = {}) { + this.blankSymbol = blankSymbol; + this.minLength = minLength; + this.padding = padding; + this.reset(initialContent); + } + + reset(initialContent = "") { + const targetLength = Math.max(this.minLength, initialContent.length + this.padding); + this.cells = Array(targetLength).fill(this.blankSymbol); + const startOffset = Math.floor((targetLength - initialContent.length) / 2); + for (let i = 0; i < initialContent.length; i++) { + this.cells[startOffset + i] = initialContent[i]; + } + this.headIndex = startOffset; + } + + get length() { + return this.cells.length; + } + + getHeadIndex() { + return this.headIndex; + } + + readHead() { + return this.getCell(this.headIndex); + } + + writeHead(symbol) { + this.cells[this.headIndex] = symbol || this.blankSymbol; + } + + readAt(index) { + return this.getCell(index); + } + + writeAt(index, symbol) { + if (index < 0) { + throw new Error("Cannot write to a negative tape index"); + } + this.ensureRightCapacity(index); + this.cells[index] = symbol || this.blankSymbol; + } + + setHead(index) { + if (index < 0) { + throw new Error("Head index cannot be negative"); + } + this.ensureRightCapacity(index); + this.headIndex = index; + } + + moveLeft() { + if (this.headIndex === 0) { + this.cells.unshift(this.blankSymbol); + } else { + this.headIndex -= 1; + return; + } + } + + moveRight() { + this.headIndex += 1; + if (this.headIndex >= this.cells.length) { + this.cells.push(this.blankSymbol); + } + } + + getCell(index) { + if (index < 0 || index >= this.cells.length) { + return this.blankSymbol; + } + return this.cells[index]; + } + + ensureRightCapacity(index) { + while (index >= this.cells.length) { + this.cells.push(this.blankSymbol); + } + } + + getContents({ trimTrailing = true } = {}) { + let snapshot = this.cells.join(""); + if (trimTrailing) { + const regex = new RegExp(`${escapeForRegex(this.blankSymbol)}+$`, "g"); + snapshot = snapshot.replace(regex, ""); + } + return snapshot; + } +} diff --git a/src/toys/turing/js/ui.js b/src/toys/turing/js/ui.js new file mode 100644 index 0000000..ae01a4b --- /dev/null +++ b/src/toys/turing/js/ui.js @@ -0,0 +1,386 @@ +import { Tape } from "./tape.js"; +import { TuringMachine } from "./machine.js"; +import { parseInstructionSet } from "./parser.js"; +import { EXAMPLE_PROGRAMS } from "./samples.js"; + +const SCROLL_THRESHOLD = 3; + +export class TuringMachineUI { + constructor() { + this.machine = null; + this.editor = null; + this.intervalId = null; + this.isRunning = false; + this.initialTapeSize = 50; + this.blankSymbol = "B"; + this.currentProgramIndex = 0; + this.loadedFromURL = false; + this.urlTapeState = ""; + this.lastScrollPosition = 0; + this.renderedTapeLength = 0; + this.simulationInterval = 200; + + this.elements = { + tape: document.getElementById("tape"), + stateText: document.getElementById("state-text"), + runBtn: document.getElementById("run-btn"), + stepBtn: document.getElementById("step-btn"), + resetBtn: document.getElementById("reset-btn"), + copyBtn: document.getElementById("copy-btn"), + programSelect: document.getElementById("program-select") + }; + + this.init(); + } + + init() { + this.setupEditor(); + this.populateProgramSelect(); + this.setupEventListeners(); + this.loadFromURL(); + } + + setupEditor() { + this.editor = adelieEditor.init("#code-editor", { + language: "javascript" + }); + + this.editor.dom.addEventListener("input", () => { + this.machine = null; + }); + } + + populateProgramSelect() { + if (!this.elements.programSelect) { + return; + } + + this.elements.programSelect.innerHTML = ""; + EXAMPLE_PROGRAMS.forEach((program, index) => { + const option = document.createElement("option"); + option.value = index.toString(); + option.textContent = program.name; + this.elements.programSelect.appendChild(option); + }); + } + + setupEventListeners() { + this.elements.runBtn.addEventListener("click", () => this.toggleRun()); + this.elements.stepBtn.addEventListener("click", () => this.step()); + this.elements.resetBtn.addEventListener("click", () => this.reset()); + this.elements.copyBtn.addEventListener("click", () => this.copyState()); + + this.elements.programSelect.addEventListener("change", (event) => { + this.loadProgram(parseInt(event.target.value, 10)); + }); + + document.addEventListener("keydown", (event) => { + if (event.ctrlKey && event.key === "Enter") { + event.preventDefault(); + this.reset(); + setTimeout(() => this.run(), 0); + } + }); + + this.elements.tape.addEventListener("input", (event) => this.handleTapeInput(event)); + this.elements.tape.addEventListener("focusin", () => { + if (this.isRunning) { + this.pause(); + } + }); + } + + handleTapeInput(event) { + if (!this.machine) { + return; + } + const target = event.target; + if (!(target instanceof HTMLInputElement)) { + return; + } + + const parentCell = target.closest(".cell"); + if (!parentCell) { + return; + } + + const index = Number(parentCell.dataset.index); + if (Number.isNaN(index)) { + return; + } + + const sanitized = (target.value || this.blankSymbol).slice(0, 1); + target.value = sanitized; + this.machine.tape.writeAt(index, sanitized || this.blankSymbol); + } + + loadFromURL() { + const urlParams = new URLSearchParams(window.location.search); + const startState = urlParams.get("start") ?? ""; + const instructions = urlParams.get("instructions"); + + if (!instructions) { + this.loadProgram(0); + return; + } + + try { + const code = atob(instructions); + this.setEditorContent(code); + this.loadedFromURL = true; + this.urlTapeState = startState; + this.compile(this.urlTapeState); + } catch (error) { + console.error("Failed to load from URL", error); + this.loadedFromURL = false; + this.loadProgram(0); + } + } + + setEditorContent(content) { + const length = this.editor.state.doc.toString().length; + this.editor.dispatch({ + changes: { from: 0, to: length, insert: content } + }); + } + + getEditorContent() { + return this.editor.state.doc.toString(); + } + + loadProgram(index = 0) { + const program = EXAMPLE_PROGRAMS[index]; + if (!program) { + return; + } + + this.loadedFromURL = false; + this.currentProgramIndex = index; + this.elements.programSelect.value = index.toString(); + this.setEditorContent(program.code); + + try { + this.compile(program.initialTape); + } catch (error) { + this.elements.stateText.innerHTML = `Error: ${error.message}`; + } + } + + compile(initialTape = "") { + this.pause(); + + const code = this.getEditorContent(); + const instructionSet = parseInstructionSet(code); + const tapeSeed = initialTape || EXAMPLE_PROGRAMS[this.currentProgramIndex]?.initialTape || ""; + + const tape = new Tape({ + initialContent: tapeSeed, + blankSymbol: this.blankSymbol, + minLength: Math.max(this.initialTapeSize, tapeSeed.length + 40) + }); + + this.machine = new TuringMachine({ + tape, + rules: instructionSet.rules, + startState: instructionSet.startState, + acceptStates: instructionSet.acceptStates, + rejectStates: instructionSet.rejectStates + }); + + this.renderedTapeLength = 0; + this.lastScrollPosition = tape.getHeadIndex(); + this.updateStateDisplay(); + this.updateTape(true); + } + + reset() { + this.pause(); + + if (this.loadedFromURL) { + try { + this.compile(this.urlTapeState); + return; + } catch (error) { + this.elements.stateText.innerHTML = `Error: ${error.message}`; + } + } + + this.loadProgram(this.currentProgramIndex); + } + + step() { + if (!this.machine) { + try { + this.compile(); + } catch (error) { + this.elements.stateText.innerHTML = `Error: ${error.message}`; + return; + } + } + + const canContinue = this.machine.step(); + this.updateStateDisplay(); + this.updateTape(); + + if (!canContinue) { + this.pause(); + } + } + + toggleRun() { + if (this.isRunning) { + this.pause(); + } else { + this.run(); + } + } + + run() { + if (this.isRunning) { + return; + } + + if (!this.machine) { + try { + this.compile(); + } catch (error) { + this.elements.stateText.innerHTML = `Error: ${error.message}`; + return; + } + } + + this.isRunning = true; + this.elements.runBtn.textContent = "⏸ Pause"; + this.elements.runBtn.classList.remove("primary"); + + this.intervalId = setInterval(() => { + const canContinue = this.machine.step(); + this.updateStateDisplay(); + this.updateTape(); + if (!canContinue) { + this.pause(); + } + }, this.simulationInterval); + } + + pause() { + if (!this.isRunning) { + return; + } + + this.isRunning = false; + clearInterval(this.intervalId); + this.intervalId = null; + + this.elements.runBtn.textContent = "▶ Run (Ctrl + Enter)"; + this.elements.runBtn.classList.add("primary"); + } + + updateStateDisplay() { + if (!this.machine) { + this.elements.stateText.textContent = "State: _, Step: 0"; + return; + } + + const status = this.machine.getStateStatus(); + + if (!this.machine.canStep()) { + if (this.machine.isAccepting()) { + this.elements.stateText.innerHTML = `Accept(${status})`; + } else if (this.machine.isRejecting()) { + this.elements.stateText.innerHTML = `Reject(${status})`; + } else { + this.elements.stateText.innerHTML = `Halt(${status})`; + } + return; + } + + this.elements.stateText.textContent = status; + } + + updateTape(forceRender = false) { + if (!this.machine) { + return; + } + + const tape = this.machine.tape; + if (forceRender || this.renderedTapeLength !== tape.length) { + this.renderTape(); + } + + const cells = this.elements.tape.querySelectorAll(".cell"); + const headIndex = tape.getHeadIndex(); + + cells.forEach((cell, index) => { + cell.dataset.index = index.toString(); + const input = cell.querySelector("input"); + const value = tape.getCell(index); + if (input.value !== value) { + input.value = value; + } + + if (index === headIndex) { + cell.classList.add("active"); + this.maybeScrollIntoView(cell, headIndex, forceRender); + } else { + cell.classList.remove("active"); + } + }); + } + + renderTape() { + const fragment = document.createDocumentFragment(); + const tape = this.machine.tape; + + for (let i = 0; i < tape.length; i++) { + fragment.appendChild(this.createCell(i, tape.getCell(i))); + } + + this.elements.tape.innerHTML = ""; + this.elements.tape.appendChild(fragment); + this.renderedTapeLength = tape.length; + } + + createCell(index, value) { + const cell = document.createElement("div"); + cell.classList.add("cell"); + cell.dataset.index = index.toString(); + + const input = document.createElement("input"); + input.type = "text"; + input.maxLength = 1; + input.value = value; + + cell.appendChild(input); + return cell; + } + + maybeScrollIntoView(cell, headIndex, forceImmediate = false) { + if (forceImmediate) { + cell.scrollIntoView({ behavior: "auto", block: "nearest", inline: "center" }); + this.lastScrollPosition = headIndex; + return; + } + + if (Math.abs(headIndex - this.lastScrollPosition) < SCROLL_THRESHOLD) { + return; + } + + cell.scrollIntoView({ behavior: "smooth", block: "nearest", inline: "center" }); + this.lastScrollPosition = headIndex; + } + + copyState() { + if (!this.machine) { + return; + } + + const tapeState = this.machine.tape.getContents(); + const instructions = btoa(this.getEditorContent()); + const url = `${window.location.href.split("?")[0]}?start=${tapeState}&instructions=${instructions}`; + + navigator.clipboard.writeText(url) + .then(() => alert("State copied to clipboard!")) + .catch(() => alert("Failed to copy to clipboard")); + } +} -- cgit v1.2.3-70-g09d2