diff options
Diffstat (limited to 'src/toys/turing')
| -rw-r--r-- | src/toys/turing/css/styles.css | 66 | ||||
| -rw-r--r-- | src/toys/turing/index.html | 42 | ||||
| -rw-r--r-- | src/toys/turing/js/machine.js | 75 | ||||
| -rw-r--r-- | src/toys/turing/js/main.js | 4 | ||||
| -rw-r--r-- | src/toys/turing/js/parser.js | 141 | ||||
| -rw-r--r-- | src/toys/turing/js/samples.js | 88 | ||||
| -rw-r--r-- | src/toys/turing/js/tape.js | 103 | ||||
| -rw-r--r-- | src/toys/turing/js/ui.js | 386 |
8 files changed, 0 insertions, 905 deletions
diff --git a/src/toys/turing/css/styles.css b/src/toys/turing/css/styles.css deleted file mode 100644 index 2407cb4..0000000 --- a/src/toys/turing/css/styles.css +++ /dev/null @@ -1,66 +0,0 @@ -.tape { - display: flex; - gap: 0.25rem; - padding: var(--space-md); - overflow-x: auto; - background: var(--surface-alt); - border: var(--border-width) solid var(--border); - box-shadow: inset 1px 1px 0 var(--border-light), - inset -1px -1px 0 var(--border-dark); - min-height: 5rem; -} - -.cell { - position: relative; - width: 3.25rem; - padding: var(--space-xs); - background: var(--surface); - border: 2px solid var(--border-dark); - box-shadow: inset 1px 1px 0 var(--border-light), - inset -1px -1px 0 var(--border-dark); - flex-shrink: 0; -} - -.cell input { - width: 100%; - text-align: center; - border: none; - background: transparent; - font-family: var(--font-mono); - color: var(--fg); - font-size: 0.875rem; - padding: 0.25rem; -} - -.cell input:focus { - outline: 1px dotted var(--fg); - outline-offset: 2px; -} - -.cell.active { - border-color: var(--primary); - background: color-mix(in srgb, var(--primary) 15%, var(--surface)); -} - -.cell.active::after { - content: '▲'; - position: absolute; - bottom: -1.5rem; - left: 50%; - transform: translateX(-50%); - color: var(--primary); - font-size: 1rem; - line-height: 1; -} - -#state-text { - font-family: var(--font-mono); - font-weight: 700; - margin-top: var(--space-md); -} - -.controls { - display: flex; - gap: var(--space-sm); - flex-wrap: wrap; -} diff --git a/src/toys/turing/index.html b/src/toys/turing/index.html deleted file mode 100644 index 838c5bf..0000000 --- a/src/toys/turing/index.html +++ /dev/null @@ -1,42 +0,0 @@ -<!DOCTYPE html> -<html lang="en"> -<head> - <meta charset="UTF-8"> - <meta name="viewport" content="width=device-width, initial-scale=1.0"> - <link rel="stylesheet" href="https://adelie.liz.coffee/bundle.css"> - <link rel="stylesheet" href="./css/styles.css"> - <title>Turing Machine</title> -</head> -<body> - <main> - <article> - <h3>Turing Machine</h3> - - <p id="state-text">State: _, Step: 0</p> - - <div id="tape" class="tape mt-md"></div> - - <div class="controls mt-sm"> - <button id="run-btn" class="primary">Run (Ctrl + Enter)</button> - <button id="step-btn">Step</button> - <button id="reset-btn">Reset</button> - <button id="copy-btn">Copy State</button> - </div> - - <section class="mt-lg"> - <div class="mt-sm"> - <label for="program-select">Example:</label> - <select id="program-select"></select> - </div> - - <div id="code-editor" class="code-editor-container mt-sm"></div> - </section> - </article> - </main> - - <script src="https://adelie.liz.coffee/bundle.js"></script> - <script src="https://adelie.liz.coffee/adelie-editor.js"></script> - <script type="module" src="./js/main.js"> - </script> -</body> -</html> diff --git a/src/toys/turing/js/machine.js b/src/toys/turing/js/machine.js deleted file mode 100644 index 6af4be6..0000000 --- a/src/toys/turing/js/machine.js +++ /dev/null @@ -1,75 +0,0 @@ -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 deleted file mode 100644 index c9f37fc..0000000 --- a/src/toys/turing/js/main.js +++ /dev/null @@ -1,4 +0,0 @@ -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 deleted file mode 100644 index dd65613..0000000 --- a/src/toys/turing/js/parser.js +++ /dev/null @@ -1,141 +0,0 @@ -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 deleted file mode 100644 index 0998ee4..0000000 --- a/src/toys/turing/js/samples.js +++ /dev/null @@ -1,88 +0,0 @@ -// 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 = = L 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 deleted file mode 100644 index fd05366..0000000 --- a/src/toys/turing/js/tape.js +++ /dev/null @@ -1,103 +0,0 @@ -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 deleted file mode 100644 index ae01a4b..0000000 --- a/src/toys/turing/js/ui.js +++ /dev/null @@ -1,386 +0,0 @@ -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 = `<span class="text-error">Error: ${error.message}</span>`; - } - } - - 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 = `<span class="text-error">Error: ${error.message}</span>`; - } - } - - this.loadProgram(this.currentProgramIndex); - } - - step() { - if (!this.machine) { - try { - this.compile(); - } catch (error) { - this.elements.stateText.innerHTML = `<span class="text-error">Error: ${error.message}</span>`; - 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 = `<span class="text-error">Error: ${error.message}</span>`; - 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 = `<span class="text-success">Accept(${status})</span>`; - } else if (this.machine.isRejecting()) { - this.elements.stateText.innerHTML = `<span class="text-error">Reject(${status})</span>`; - } else { - this.elements.stateText.innerHTML = `<span class="text-error">Halt(${status})</span>`; - } - 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")); - } -} |
