Turing Machine

turing_machine.js

function println(v) {
    console.log(v.toString());
}

class List {
    constructor(array) {
        this.array = array;
    }

    get first() {
        return this.array[0];
    }

    get tail() {
        return new List(this.array.slice(1));
    }

    get init() {
        return new List(this.array.slice(0, -1));
    }

    get last() {
        return this.array[this.array.length - 1]    ;
    }

    prepend(elem) {
        return new List([elem].concat(this.array));
    }

    append(elem) {
        return new List(this.array.concat([elem]));
    }

    toString() {
        return this.array.join(' ');
    }
}

class Head {
    constructor(left, current, right, defaultValue) {
        this.left = left;
        this.current = current;
        this.right = right;
        this.defaultValue = defaultValue;
    }

    moveLeft() {
        return new Head(
            this.left.init,
            this.left.last === undefined ? this.defaultValue : this.left.last,
            this.right.prepend(this.current),
            this.defaultValue
        );
    }

    moveRight() {
        return new Head(
            this.left.append(this.current),
            this.right.first === undefined ? this.defaultValue : this.right.first,
            this.right.tail,
            this.defaultValue
        );
    }

    write(data) {
        return new Head(this.left, data, this.right, this.defaultValue);
    }

    toString() {
        let l = this.left.toString();
        let r = this.right.toString();
        return `[${l}](${this.current})[${r}]`;
    }
}   

class Context {
    constructor(state, head) {
        this.state = state;
        this.head = head; 
    }

    isAcceptable(acceptables) {
        return acceptables.includes(this.state);
    }

    get data() {
        let larr = this.head.left.array;
        let carr = [this.head.current];
        let rarr = this.head.right.array;
        return larr.concat(carr).concat(rarr);
    }     
}

const LEFT = Symbol('move head left');
const RIGHT = Symbol('move head right');

class Rule {
    constructor({state, data, writeData, headDir, nextState}) {
        this.state = state;
        this.data = data;
        this.writeData = writeData;
        this.headDir = headDir;
        this.nextState = nextState;
    }

    isApplicableTo(context) {
        return this.state === context.state && 
               this.data === context.head.current;
    }

    next_context(context) {
        head = context.head.write(this.writeData);
        switch(this.headDir) {
            case LEFT:
                return new Context(this.nextState, head.moveLeft());
            case RIGHT:
                return new Context(this.nextState, head.moveRight());
        }
    }
}

class Manual {
    constructor(rules) {
        this.rules = rules;
    }

    next_context(context) {
        return this.rules
                   .find(rule => rule.isApplicableTo(context))
                   .next_context(context);
    }
}

class Machine {
    constructor(manual, context, acceptables) {
        this.manual = manual;
        this.context = context;
        this.acceptables = acceptables;
    }

    execute() { 
        return this.runUntilHalt(this.context).data;
    }

    runUntilHalt(context) {
        return context.isAcceptable(this.acceptables) ? 
                    context : 
                    this.runUntilHalt(this.manual.next_context(context));
    }
}

let manual = new Manual([
    new Rule({
        state : 1,
        data : 0,
        writeData : 1,
        headDir : RIGHT,
        nextState : 2
    }),
    new Rule({
        state : 1,
        data : 1,
        writeData : 0,
        headDir : LEFT,
        nextState : 1
    }),
    new Rule({
        state : 1,
        data : '\0',
        writeData : 1,
        headDir : RIGHT,
        nextState : 2
    }),
    new Rule({
        state : 2, 
        data : 0,
        writeData : 0,
        headDir : RIGHT,
        nextState : 2
    }),    
    new Rule({
        state : 2,
        data : 1,
        writeData : 1,
        headDir : RIGHT,
        nextState : 2
    }),    
    new Rule({
        state : 2, 
        data : '\0',
        writeData : '\0',
        headDir : LEFT,
        nextState : 3
    })    
]);

let head = new Head(new List([1, 0, 1]), 1, new List([]), '\0');

let context = new Context(1, head);

let machine = new Machine(manual, context, [3]);
let r = machine.execute();
console.log(r);