打造特定機器

要打造具備特定規則的機器，可以從目前的 Brainfuck 下手，看看上頭有哪些零件可以使用的，因為特定機器的操作簡單而單純，也就只需要〈打造 Brainfuck〉中的 List、Head 就可以了，其中 Head 稍微做些修改，最主要的是修改 Head 的空白可以是自行指定，而不是寫死的 0：

class Head {
    constructor(left, current, right, defaultValue = '\0') {
        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}]`;
    }
}   

接下來要面對的就是規則本身，在〈簡單規則〉中談到了，規則必須是：

• 目前的狀態
• 讀取的字元
• 寫入的字元
• 磁頭移動方向（只能是左或右）
• 進入哪個狀態

首先，定義左右移動時使用的符號：

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

接下來定義 Rule，每個 Rule 實例代表一條規則：

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) {
        let 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());
        }
    }
}

因為建構規則時必須有五個參數，基於可讀性，這邊使用 ES6 物件解構語法，如此在建構 Rule 實例時，可以使用選項物件作為引數。

在不同的狀態，可套用的規則不同，isApplicableTo 可用來判斷規則是否適用，context 會是個 Context 實例，包含了目前環境處於何種狀態，以及目前的 Head 實例，依〈簡單規則〉所述，只要目前狀態、磁頭下的資料符合，就可以套用規則。

next_context 會套用規則，依規則寫入指定的資料，進行磁頭的左移或右移，進入下一個狀態，最後的結果會封裝為一個新的環境物件，也就是傳回 Context 實例。

依 Rule 的需求，Context 定義如下：

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);
    }     
}

isAcceptable 可用來判斷目前是否處於接受狀態，可接受的狀態也許不只一個，因此 acceptables 會是一個陣列，只要環境目前狀態符合 acceptables 之一，機器就可停機，取出磁帶看看結果了。

在〈打造 Brainfuck〉中，你是否想過，Manual 只是個空殼呢？沒有規則傳入的話，它什麼都不是，在當時，規則是一組符號與函式的對應，實際上可以在建構時當成引數傳入，現在就直接這麼做吧！

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

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

現在的 Manual 接受規則組成的陣列實例，每次套用規則時，就是從 rules 找出適用的規則，然後透過 Rule 的 next_context 套用規則，並傳回新的 Context 實例。

操作手冊、環境物件與可接受的狀態，可以全部組裝成一台機器，它跟 Brainfuck 很像：

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));
    }
}

現在，如果想要建立一台反轉位元的機器，根據〈簡單規則〉中所述的規則：

• 目前狀態 1，讀入 0，寫入 1，磁頭右移，進入狀態 1
• 目前狀態 1，讀入 1，寫入 0，磁頭右移，進入狀態 1
• 目前狀態 1，讀入空白，寫入空白，磁頭左移，進入狀態 2
• 目前狀態 2，讀入 0，寫入 0，磁頭左移，進入狀態 2
• 目前狀態 2，讀入 1，寫入 1，磁頭左移，進入狀態 2
• 目前狀態 3，讀入空白，寫入空白，磁頭右移，進入狀態 3（接受狀態）

可以如下建立機器，注意到 Rule 實例完全是對應規則的：

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

let head = new Head(new List([]), '0', new List(Array.from('1010011')));
let context = new Context(1, head);
let machine = new Machine(manual, context, [3]);
let r = machine.execute();

// 顯示 [ '\u0000', '1', '0', '1', '0', '1', '1', '0', '0', '\u0000' ]
console.log(r);

類似地，有九條規則的二進位加一機器：

• 目前狀態 1，讀入 0，寫入 0，磁頭右移，進入狀態 1
• 目前狀態 1，讀入 1，寫入 1，磁頭右移，進入狀態 1
• 目前狀態 1，讀入空白，寫入空白，磁頭左移，進入狀態 2
• 目前狀態 2，讀入 1，寫入 0，磁頭左移，進入狀態 2
• 目前狀態 2，讀入 0，寫入 1，磁頭左移，進入狀態 3
• 目前狀態 2，讀入空白，寫入 1，磁頭左移，進入狀態 3
• 目前狀態 3，讀入 0，寫入 0，磁頭左移，進入狀態 3
• 目前狀態 3，讀入 1，寫入 1，磁頭左移，進入狀態 3
• 目前狀態 3，讀入空白，寫入空白，磁頭右移，進入狀態 4（接受狀態）

可以如下建構：

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

let head = new Head(new List([]), '1', new List(Array.from('1010011')));
let context = new Context(1, head);
let machine = new Machine(manual, context, [4]);
let r = machine.execute();

// 顯示 [ '\u0000', '1', '1', '0', '1', '0', '1', '0', '0', '\u0000' ]
console.log(r);

另一個二進位加一的版本只有六條規則：

• 目前狀態 1，讀入 1，寫入 0，磁頭左移，進入狀態 1
• 目前狀態 1，讀入空白，寫入 1，磁頭右移，進入狀態 2
• 目前狀態 1，讀入 0，寫入 1，磁頭右移，進入狀態 2
• 目前狀態 2，讀入 0，寫入 0，磁頭右移，進入狀態 2
• 目前狀態 2，讀入 1，寫入 1，磁頭右移，進入狀態 2
• 目前狀態 2，讀入空白，寫入空白，磁頭右移，進入狀態 3（接受狀態）

可以如下建構：

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([]));
let context = new Context(1, head);
let machine = new Machine(manual, context, [3]);
let r = machine.execute();

// 顯示 [ '1', '1', '0', '0', '\u0000' ]
console.log(r);

在這邊雖然都用位元或二進位作為範例，然而，只要能達到目的，磁帶上的編碼不見得必須是位元或二進位編碼，試著想想看，要如何設計出一台加法器或特定字串比對呢？