Turing Machine implementation with example machines and parser

turing.ts

const EMPTY = " " as const;
const START = "<" as const;

type Cell = typeof EMPTY | typeof START | string;
type Direction = "L" | "R";

class Tape {
    private symbols: Map<number, Cell>;
    private position: number;

    constructor(startState: string | undefined = undefined) {
        this.symbols = new Map();
        this.position = 0;
        this.symbols.set(-1, START);

        if (startState !== undefined) {
            for (let c of startState) {
                this.write(c);
                this.move("R");
            }
            this.position = 0;
        }
    }

    move(direction: Direction) {
        switch (direction) {
            case "L":
                if (this.position === -1)
                    throw "attempt to move tape leftwards from beginning";
                this.position -= 1;
                break;
            case "R":
                this.position += 1;
                break;
            default:
                break;
        }
    }

    read(): Cell {
        return this.symbols.get(this.position) ?? EMPTY;
    }

    write(cell: Cell) {
        if (this.position === -1 && cell !== START)
            throw "attempt to write to beginning of tape";

        if (this.position !== -1 && cell === START)
            throw "attempt to write start cell elsewhere";

        if (cell === EMPTY) {
            this.symbols.delete(this.position);
            return;
        }

        this.symbols.set(this.position, cell);
    }

    print() {
        const sz = Math.max(...this.symbols.keys()) + 2;
        const tape = Array.from({ length: sz }, (_, i) => this.symbols.get(-1 + i) ?? EMPTY).join("");
        const cursor = " ".repeat(1 + this.position) + "^";
        console.log(`${tape}\n${cursor}`);
    }
}

/** a null return means the state is final */
type State = (cell: Cell) => { state: State, cell: Cell, direction: Direction } | null;

function compile(source: Map<string, Map<Cell, { cell: Cell, state: string, direction: Direction }> | null>): State {
    if (!source.has("S0")) {
        throw "every turing machine must have a start state";
    }

    const stateMap: Map<string, State> = new Map();
    const errorState = (stateName) => (cell: Cell) => { throw `error state: no transition at state ${stateName} from ${cell}`; };

    for (let [stateName, mappings] of source.entries()) {
        if (mappings == null) {
            stateMap.set(stateName, (_) => null);
        } else {
            stateMap.set(stateName, (cell) => {
                const target = mappings.get(cell);

                // if the binding doesn't exist in the mapping it should return the errorState
                if (target === undefined) {
                    return errorState(stateName)(cell);
                }

                return {
                    cell: target.cell,
                    direction: target.direction,
                    state: stateMap.get(target.state) ?? errorState(stateName)
                };
            });
        }
    }

    return stateMap.get("S0")!;
}

function run(start: string, initialState: State) {
    let tape = new Tape(start);
    let currentState: State = initialState;
    console.log("START:");
    tape.print();

    while (true) {
        let result = currentState(tape.read());
        if (result === null) {
            break;
        }

        let { state, direction, cell } = result;
        tape.write(cell);
        tape.move(direction);
        currentState = state;
    }
    console.log("END:");
    tape.print();
}

function splat(o: Object) {
    return new Map(Object.entries(o));
}

function mt(o: { [from: string]: Map<string, Transition> | null }) {
    return compile(splat(o));
}

function s(o: { [cellFrom: string]: Transition }): Map<string, Transition> {
    return splat(o);
}

type Transition = { cell: Cell, direction: Direction, state: string };

function t(cell: Cell, direction: Direction, state: string): Transition {
    return { cell, direction, state };
}

declare interface String {
    splitOnce(delim: string): [string, string] | null;
}

String.prototype.splitOnce = function (delim: string) {
    var i = this.indexOf(delim);
    if (i === -1) return null;
    return [this.slice(0, i), this.slice(i + delim.length)];
}

function parse(src: string) {
    const lines = src.split("\n").map(s => s.trim()).filter(s => s);
    const rules = lines.map(l => {
        let [tok, rest] = l.splitOnce("->")!;
        let from = tok.trim();
        if (rest.trim() === "*") {
            return { from, to: "*" as const };
        }
        [tok, rest] = rest.trim().splitOnce(":")!;
        let to = tok.trim();
        rest = rest.trim();
        let triplet = rest.substring(1, rest.length - 1);
        let [cellFrom, cellTo, direction] = triplet.split(",").map(s => s.trim());
        let map = (c: string) => c === "_" ? EMPTY : c === "<" ? START : c;
        cellFrom = map(cellFrom);
        cellTo = map(cellTo);
        return { from, to, cellFrom, cellTo, direction: direction as Direction };
    });
    const grouped = Object.fromEntries(Object.entries(Object.groupBy(
        rules,
        ({ from }) => from
    )).map(
        ([state, rules]) => {
            if (rules!.find(x => x.to === "*")) {
                // this is a final state
                return [state, null];
            }

            const pivoted = Object.fromEntries(Object.entries(Object.groupBy(rules!, ({ cellFrom }) => cellFrom!)).map(
                ([cellFrom, rules]) => {
                    return [cellFrom, rules!.map(rule => t(rule.cellTo as string, rule.direction as Direction, rule.to)).at(0)!];
                }
            ));

            return [state, s(pivoted)];
        }
    ));
    return mt(grouped);
}

run("1010", parse(`
    S0 -> S0 : (0, 1, R)
    S0 -> S0 : (1, 0, R)
    S0 -> S1 : (_, _, L)
    S1 -> S1 : (1, 1, L)
    S1 -> S1 : (0, 0, L)
    S1 -> Sf : (<, <, R)
    Sf -> *
`));


const adder = parse(`
    S0 -> S0 : (0, 0, R)
    S0 -> S0 : (1, 1, R)
    S0 -> soma : (_, _, L)
    soma -> retorno : (0, 1, L)
    soma -> vai um : (1, 0, L)
    retorno -> retorno : (0, 0, L)
    retorno -> retorno : (1, 1, L)
    retorno -> saida : (<, <, R)
    vai um -> vai um : (1, 0, L)
    vai um -> retorno : (0, 1, L)
    vai um -> estouro : (<, <, R)
    estouro -> avanca : (0, 1, R)
    avanca -> avanca : (0, 0, R)
    avanca -> retorno : (_, 0, L)
    saida -> *
`);

console.log("inc 1")
run("1", adder);
console.log("inc 101")
run("101", adder);
console.log("inc 11111")
run("1111", adder);