Brainfuck 看輸入

December 16, 2021

現在已經打造了一台 Brainfuck 機器,可以寫點程式讓它來跑一下了,不過,Brainfuck 會不會太陽春了點?不會!其實 Brainfuck 還蠻複雜的,只不過因為 JavaScript 的一些魔法,才令它打造起來簡單一些。

只有一條磁帶

例如,目前的打造的 Brainfuck 真的使用單磁帶嗎?不,並沒有,其實使用了兩個磁頭、兩條磁帶,資料是寫在其中一個磁帶,另一條磁帶寫了 Brainfuck 程式碼,需要知道下個指令時,必須讀取程式碼磁帶,然後在資料磁帶上進行對應的操作。

如果沒了程式碼磁帶,Brainfuck 還會是 Brainfuck 嗎?畢竟,Brainfuck 有 [] 指令可以用來撰寫迴圈之類的程式碼,這表示 Brainfuck 並單純逐一消耗指令到沒有指令為止,至少是必須記得 [] 之間的指令,才有可能重複運行,沒了另一條程式碼磁帶,似乎會令 Brainfuck 不再能完成 Brainfuck 原本可以達到的任務。

不!就算真的沒了程式碼磁帶,還是能打造出 Brainfuck 的,因為可以將程式碼與資料寫在同一磁帶,這會令實作變得麻煩,然而並非做不到,拿掉程式碼磁帶,並不會令 Brainfuck 變笨。

實作的方式在於,可以在同一磁帶上規畫出程式碼專用區段及資料專用區段,為了方便,可以將程式碼專用區段放在磁帶開頭:

Brainfuck 看輸入

每次需要執行指令時,磁頭會回到程式碼專用區段的開頭,當中記錄了指令索引位置,索引 0 是從它的右邊開始起算,若指令需要讀寫資料或者在資料間移動,就移動至資料專用區段的開頭,看看接下來要讀寫哪個索引位置,索引 0 是從記錄資料索引的位置右方開始起算。

依機器存取磁帶之目的,概略上可以分為兩個狀態,一個是磁頭在程式碼專用區段移動時讀寫指令的狀態,一個是碰頭在資料專用區段讀寫資料的狀態,為了便於實作,稍後可以將這兩個狀態設計為獨立互不相干的兩個物件。

改造 Brainfuck 機器

來改寫〈打造 Brainfuck〉中的實作,首先,List 不用變更,因為它單純只是封裝 JavaScript 陣列的行為,接著,由於稍後會需要連續移動磁頭,因此將 HeadmoveLeftmoveRight 加強為可連續移動的版本。

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

    moveLeft(n = 1, head = this) {
        if(n === 0) {
            return head;
        } 
        else {
            let h = new Head(
                head.left.init,
                head.left.last || 0,
                head.right.prepend(head.current)
            );
            return this.moveLeft(n - 1, h);
        }
    }    

    moveRight(n = 1, head = this) {
        if(n === 0) {
            return head;
        } 
        else {
            let h = new Head(
                head.left.append(head.current),
                head.right.first || 0,
                head.right.tail
            )
            return this.moveRight(n - 1, h);
        }
    }    

    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}]`;
    }
}

moveLeftmoveRight 可以指定移動的位置數,預設值 1,表示僅在磁帶上移動一個位置。

在〈打造 Brainfuck〉中的 Commands,實際上就隱含著機器存取指令的一個狀態,然而由於是在另一個陣列中操作,狀態的概念不明顯,既然 Commands 隱含的就是機器存取指令的狀態,上頭的方法操作介面,就會是存取單一磁帶時需要的,只不過內部實作必須重新改寫:

class CommandState {
    constructor(head) {
        this.head = head;
    }

    // idx 是指令索引,不是指陣列索引
    get idx() {
        return this.head.current;
    }

    // 取得目前的指令
    get current() {
        return this.head.moveRight(this.idx + 1).current;
    }

    // 磁頭在指令區前進 n 個位置
    step(n = 1) {
        return new CommandState(
            this.head.write(this.idx + n)
        );
    }

    // 移動至最近的 ] 指令
    rightBracket() {
        function bracket(commandState) {
            if(commandState.current === ']') {
                return commandState.idx;
            } else {
                return bracket(commandState.step());
            }
        }

        return new CommandState(
            this.head.write(bracket(this))
        );
    } 

    // 移動至最近的 [ 指令
    leftBracket() {
        function bracket(commandState) {
            if(commandState.current === '[') {
                return commandState.idx;
            } else {
                return bracket(commandState.step(-1));
            }
        }

        return new CommandState(
            this.head.write(bracket(this))
        );
    }

    // 將磁頭停靠在「指令索引」位置   
    park(head = this.head) {
        return head.left.isEmpty() ? 
                    new CommandState(head) : this.park(head.moveLeft());
    }

    isRunnable() {
        return this.current !== '\0';
    }         
}

操作 CommandState 實例時必須注意的是,若是從資料存取狀態轉移至指令存取狀態,必須先將磁頭停靠在「指令索引」位置,以便後續可以讀取索引值、移動磁頭來取得指令,磁頭的停靠可以透過呼叫 park 來達到目的。

class DataState {
    constructor(head) {
        this.head = head;
    }

    // idx 是資料索引,不是指陣列索引
    get idx() {
        return this.head.current;
    }

    // 取得目前磁頭下的資料   
    get current() {
        return this.head.moveRight(this.idx + 1).current;
    }    

    // 磁頭在資料區前進 n 個位置
    step(n = 1) {
        return new DataState(
            this.head.write(this.idx + n)
        );
    }

    // 在目前位置寫入指定的資料
    writeCurrent(x) {
        let head = this.head.moveRight(this.idx + 1);
        return new DataState(
            head.write(x).moveLeft(this.idx + 1)
        );
    }

    // 將磁頭停靠在「資料索引」位置   
    park(head = this.head) {
        return head.current === '\0' ? new DataState(head.moveRight()) : this.park(head.moveRight());
    }    
}

同樣地,若是從指令存取狀態轉移至資料存取狀態,必須先將磁頭停靠在「資料索引」位置,以便後續可以讀取索引值、移動磁頭來取得資料,磁頭的停靠可以透過呼叫 park 來達到目的,為了便於區隔程式碼區段與資料區段,使用了一個空字元 \0,磁頭停靠的「資料索引」位置,就是在空字元的右方。

從狀態轉移的觀點來看,CommandStateDataStatepark 方法,就像是在明確地畫出界限,park 之後才會是轉移至另一狀態,無論是從 CommandStateDataState,或者是從 DataStateCommandState

原先封裝 Brainfuck 機器環境狀態的 Context,也要做出對應的修改:

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

    isRunnable() {
        return this.state.isRunnable();
    }

    get data() {
        let head = this.state.head;
        // 呼叫 park 轉移狀態
        let dataState = new DataState(head).park();

        return dataState.head.right.array;
    }
}

Context 封裝了狀態,在內部,Context 總是從 CommandState,也就是指令存取的狀態開始,指令在操作過程中,會有轉移至 DataState 的過程,然後最後總是回到 CommandState,並封裝在 Context 之中,這是因為每執行完一個指令,總是會回到準備執行下個指令的狀態。

在上頭可以看到,為了要取得資料區的資料,可以呼叫 data,這時建立 DataState 並呼叫 park 將磁頭停靠在「資料索引」,相當於轉移狀態至資料區,這是目前看到明確進行狀態轉移的第一個實際例子。

接下來就是修改操作手冊了:

class Manual {
    constructor() {
        this.rules = new Map([
            ['+', addOne],
            ['-', minusOne],
            ['>', moveHeadRight],
            ['<', moveHeadLeft],
            ['[', leftBracket],
            [']', rightBracket],
            ['.', convertToChar],
            [',', convertToNumber]            
        ]);

        function head(dataState) {
            return dataState.current;
        }

        function writeCurrent(dataState, x) {
            // 轉移至指令狀態
            let commandState = new CommandState(dataState.writeCurrent(x).head)
                                        .park().step();
            return new Context(commandState.head);
        }

        // +
        function addOne(dataState) {
            return writeCurrent(dataState, head(dataState) + 1);
        }

        // -
        function minusOne(dataState) {
            return writeCurrent(dataState, head(dataState) - 1);
        }

        // <
        function moveHeadLeft(dataState) {
            // 轉移至指令狀態
            let commandState = new CommandState(dataState.step(-1).head).park().step();
            return new Context(commandState.head);  
        }

        // >
        function moveHeadRight(dataState) {
            // 轉移至指令狀態
            let commandState = new CommandState(dataState.step().head).park().step();
            return new Context(commandState.head);         
        }

        // .
        function convertToChar(dataState) {
            return writeCurrent(dataState, String.fromCharCode(head(dataState)));
        }

        // ,
        function convertToNumber(dataState) {
            return writeCurrent(dataState, head(dataState).charCodeAt(0));
        }

        // [
        function leftBracket(dataState) {
            // 轉移至指令狀態
            let commandState = new CommandState(dataState.head).park();
            if(head(dataState) === 0) {
                return new Context(commandState.rightBracket().head);
            }
            else {
                return new Context(commandState.step().head);
            }
        }

        // ]
        function rightBracket(dataState) {
            // 轉移至指令狀態
            let commandState = new CommandState(dataState.head).park();
            if(head(dataState) === 0) {
                return new Context(commandState.step().head);
            }
            else {
                return new Context(commandState.leftBracket().head);
            }
        }
    }

    next_context(context) {
        let commandState = context.state;
        let cmd = commandState.current;
        // 轉移至資料狀態
        let dataState = new DataState(commandState.head).park();
        return this.rules.get(cmd)(dataState);
    }
}

可以看到 next_context 中,每次要執行指令之前會轉移至 DataState,取得手冊中的規則並執行完指令之後,又會轉移至 CommandState,然後封裝在 Context 之中傳回。

同樣地,將上頭實作出來的零件塞進 Brainfuck 之中:

class Brainfuck {
    constructor(code) {
        this.context = new Context(
            new Head(new List([]), 0, new List(Array.from(code + '\0')))
        );
        this.manual = new Manual();
    }

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

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

最主要的差別在於,建立 Brainfuck 實例時,磁帶開頭會是程式碼區段,接著是個空字元 \0,磁頭一開始是停靠在磁帶最前頭。

要執行程式的話,撰寫方式是相同的:

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

let code = '++++++++[>+++++++++<-]>.<+++++++[>>++++++++++<<-]>>-.<<+++++++[>>>++++++++++<<<-]>>>++++++.<<<+++++++[>>>>++++++++++<<<<-]>>>>++++++.<<<<++++++++[>>>>>++++++++++<<<<<-]>>>>>-.<<<<<++++[>>>>>>+++++++++++<<<<<<-]>>>>>>.<<<<<<+++++++++[>>>>>>>++++++++++<<<<<<<-]>>>>>>>---.<<<<<<<++++++++[>>>>>>>>++++++++++<<<<<<<<-]>>>>>>>>-.<<<<<<<<++++++++[>>>>>>>>>++++++++++<<<<<<<<<-]>>>>>>>>>++.<<<<<<<<<++++++++[>>>>>>>>>>++++++++++<<<<<<<<<<-]>>>>>>>>>>----.<<<<<<<<<<+++++++[>>>>>>>>>>>++++++++++<<<<<<<<<<<-]>>>>>>>>>>>--.<<<<<<<<<<<';

let result = new Brainfuck(code).execute();

// HELLO,WORLD
println(result.slice(1).join(''));  

之前使用雙磁帶,在撰寫上確實是帶了來許多方便(當然也借助了 JavaScript 的一些魔法),然而改為單磁帶,並沒有令 Brainfuck 變笨,它還是做了該做的事情,而且突顯了運行時不斷轉移狀態的這個現象…這代表著什麼呢?