特定機器

December 16, 2021

要打造具備特定規則的機器,可以從目前的 Brainfuck 下手,看看上頭有哪些零件可以使用的。

改造磁頭

因為特定機器的操作簡單而單純,也就只需要〈打造 Brainfuck〉中的 ListHead 就可以了,其中 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}]`;
    }
}   

封裝規則

接下來要面對的就是規則本身,在〈Brainfuck 看規則〉中談到了,規則必須是:

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

首先,定義左右移動時使用的符號:

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

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

重構機器

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

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 找出適用的規則,然後透過 Rulenext_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));
    }
}

建立特定機器

現在,如果想建立一台反轉位元的機器,根據〈Brainfuck 看規則〉所述的規則:

  • 目前狀態 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);

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