More ergonomic way of defining state transition ruleset

turing.ts

// Defines a function, compile, that can convert a textual
// representation of a state transition ruleset into a function
// that we can invoke to transition from one state to another.
//
// Also defines a simple function, decode, that converts a
// textual representation of a program into the "tape" that we
// feed our Turing Machine.

////////////////////////////////////////////////////////////////
// Types
////////////////////////////////////////////////////////////////

enum State {
    Init = "INIT",
    ReadInstruction = "READ",
    MoveToEnd = "M2E",
    MoveToBeg = "M2B",
    Discard = "DSC",
    Accept = "ACPT",
    Reject = "RJCT",
}
type Head = { i: number; state: State; };

enum Alphabet {
    Zero = "0",
    Hash = "#",
    Discarded = "X",
    SectorSep = "|",
    EOL = "$",
};

enum Direction {
    Right = "R",
    Left = "L",
    Stay = "_",
};

type Tape = Alphabet[];
type Program = {
    head: Head;
    tape: Tape;
};

type Transition = (program: Program) => [Alphabet | null, Direction, State];

////////////////////////////////////////////////////////////////
// Library
////////////////////////////////////////////////////////////////

function matches(state: State, v: Alphabet | null, program: Program): boolean {
    return program.head.state === state && (v === null ? true : program.tape[program.head.i] === v);
}

function compile(table: string): Transition {
    const states: {[x: string]: State} = {
        "INIT": State.Init,
        "READ": State.ReadInstruction,
        "M2E": State.MoveToEnd,
        "M2B": State.MoveToBeg,
        "DSC": State.Discard,
        "ACPT": State.Accept,
        "RJCT": State.Reject,
    };
    const alphabet: {[x: string]: Alphabet} = {
        "$": Alphabet.EOL,
        "X": Alphabet.Discarded,
        "#": Alphabet.Hash,
        "|": Alphabet.SectorSep,
        "_": null,
    };
    const directions: {[x: string]: Direction} = {
        "R": Direction.Right,
        "L": Direction.Left,
        "_": Direction.Stay,
    };
    const rules: string[] = table.trim().split("\n");
    const result: [State, Alphabet | null, Alphabet | null, Direction, State][] = [];
    for (const rule of rules) {
        const [s0, read, write, dir, s1] = rule.trim().split(/\s+/);
        const [a, b, c, d, e] = [states[s0], alphabet[read], alphabet[write], directions[dir], states[s1]];
        if (typeof a === "undefined") throw new Error(`Failed to decode s0: ${s1}`);
        if (typeof b === "undefined") throw new Error(`Failed to decode read: ${read}`);
        if (typeof c === "undefined") throw new Error(`Failed to decode write: ${write}`);
        if (typeof d === "undefined") throw new Error(`Failed to decode direction: ${dir}`);
        if (typeof e === "undefined") throw new Error(`Failed to decode s1: ${s1}`);
        result.push([a, b, c, d, e]);
    }
    return (program) => {
        for (const rule of result) {
            const [s0, read, write, move, s1] = rule;
            if (matches(s0, read, program)) {
                return [write, move, s1];
            }
        }
        throw new Error(`Unsupported pattern: ${program.head.state} ${program.tape[program.head.i]}`);
    };
}

const transition = compile(`
    INIT _ _ R READ
    READ $ _ R M2E
    M2E  # _ L M2B
    M2E  _ _ R M2E
    M2B  $ _ L M2B
    M2B  # _ R DSC
    M2B  _ _ L M2B
    DSC  _ X R READ
    READ | _ _ ACPT
`);

////////////////////////////////////////////////////////////////
// Main
////////////////////////////////////////////////////////////////

function decode(tape: string): Tape {
    return tape.split(" ").map((x) => ({
        "#": Alphabet.Hash,
        "0": Alphabet.Zero,
        "$": Alphabet.EOL,
        "|": Alphabet.SectorSep,
    })[x]);
}

let program: Program = {
    head: { i: 0, state: State.Init },
    // Schema:# PROGRAM # RAM #
    // Read instruction from PROGRAM (including immediate values - no pointers)
    tape: decode("# $ | 0 0 0 0 #"),
};

let s: number = 0;
while (![State.Accept, State.Reject].includes(program.head.state)) {
    console.log(`[ ${program.tape.join(" | ")} ] ${program.head.state}`);
    console.log(" ".repeat(program.head.i * 4) + "  ^ ");
    if (s > 40) {
        console.log("Exhausted");
        break;
    }
    const [w, direction, state] = transition(program);
    if (w !== null) {
        program.tape[program.head.i] = w;
    }
    program.head.state = state;
    switch (direction) {
        case Direction.Left: {
            program.head.i -= 1;
            break;
        }
        case Direction.Right: {
            program.head.i += 1;
            break;
        }
    }
    s += 1;
}
if (program.head.state === State.Accept) {
    console.log("Success!");
} else {
    console.log("Failure.");
}