打造 Brainfuck

現今這個年代，自造正夯，就來動手打造一台 Brainfuck 吧？需要哪些東西呢？磁頭、磁帶…馬達…這…算了！還是拿個鐵盒，找個工讀生塞進去好了！

站在巨人的肩膀上才能看得更遠，自造者也不是樣樣都自己來，尋找適當的零件或現有的機器來加以改造，也算是自造嘛！

按規則執行

用 JavaScript 來寫個程式，讀取、執行 Brainfuck 程式碼如何？這個不錯！畢竟你會寫程式嘛！等一下！在〈空想 Brainfuck〉中不是談到，Brainfuck 這台機器包含了…

+-><[].,
符號對應的規則
可按規則執行動作的硬體

然後現在要用軟體來實現 Brainfuck？那「可按規則執行動作的硬體」這項不就不符合了？還能說是打造了一台 Brainfuck 嗎？

不！就算使用 JavaScript 實現了需求，也沒有違反「可按規則執行動作的硬體」，雖說現代電腦十分強大，可以在上頭安裝作業系統、各式各樣的程式，用以完成各式各樣的需求，然而，當你安裝了可以執行 JavaScript 的環境（例如 Node.js）、用 JavaScript 寫了個可以執行 Brainfuck 程式碼的程式，然後執行 Brainfuck 程式碼，在執行的期間，這強大的電腦就是在裝萌，假裝自己是 Brainfuck 機器了！

也就是說，「可按規則執行動作的硬體」就是你的實體電腦，實際上，無論電腦再強大，在執行某程式時，它都將自己模擬成某機器，如果執行的只是個簡單的加法，在執行時你的電腦就把自己模擬成加法器了。

也許你會說，〈空想 Brainfuck〉中不是說到，Brainfuck 會有無限長的磁帶嗎？現代電腦不用磁帶居多，不過，它有好大好大的記憶體，就當它是磁帶好了，雖然記憶體不是無限的，不過容量超大，就不要在乎無不無限這個細節了…XD

簡單來說，使用 JavaScript 來寫個可以執行 Brainfuck 的程式，也算是打造 Brainfuck 機器！也就是站在巨人的肩膀上，雖然這巨人有點被大材小用。

Brainfuck 零件

首先，需要磁帶的模擬物，雖然可以直接使用 JavaScript 陣列來模擬，不過，這邊打算建立一個不可變（Immutable）的 List，封裝 JavaScript 陣列可變的性質，實際上，其他物件也都打算設計為不可變。

採取不可變，可以避免還原個別物件狀態變化的麻煩，因為每個物件狀態只會被查詢，不會被變動，令程式碼在撰寫上單純許多。

令程式碼撰寫時單純有許多好處，其中之一，就是可以輕易地察覺到程式碼的重複，別忘了打造 Brainfuck 的目的，就是想要 Brainfuck 來代為執行重複性的任務，如果實現過程中，可以輕易察覺程式碼哪邊重複了，就可能理解 Brainfuck 機器中，處理重複性任務的是哪些零件，從而更認識 Brainfuck 這台機器運作時更底層的原理。

在這邊建立的 List 會長得像這樣：

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

    isEmpty() {
        return this.array.length === 0;
    }

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

可以分別透過 first、tail 取得清單首元素與尾清單，透過 init、last 分別取得頭清單與尾元素，prepend 可以在清單前安插元素，append 可以在清單後附加元素，每個操作都會產生新的 List 實例，isEmpty 測試 List 是否為空，toString 是為了方便以字串方式察看清單內容。

那麼來建立磁頭的模擬物吧！磁頭用來讀寫磁帶，然而依 List 現在的定義，要在中間讀寫資料是不可能的，那麼就把磁帶分成三個部份吧！磁帶左方（一個 List）、磁頭下目前的元素（一個數字）、磁帶右方（一個 List）：

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

    moveLeft() {
        return new Head(
            this.left.init,
            this.left.last || 0,
            this.right.prepend(this.current)
        );
    }

    moveRight() {
        return new Head(
            this.left.append(this.current),
            this.right.first || 0,
            this.right.tail
        );
    }
    
    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}]`;
    }
}

moveLeft 與 moveRight 用來移動磁頭，write 會在磁頭下方的磁帶位置寫入指定資料，每次都產生新的 Head 物件，由於磁帶被分成三個部份，因此僅運用 List 定義的方法，就可以讀寫磁帶上的值了，Brainfuck 磁帶上預設值會是 0，因此在移動至磁帶上新位置時，若 List 底層陣列對應位置是 undefined，就使用 0 當成是讀取值。

Head 的 toString 設計成方便觀察磁頭位置、磁帶左方、磁帶右方，例如，[1 2 3 4 5](6)[7 8 9 10] 表示磁頭正下方的值是 6，[](1)[2 3 4 5 6 7 8 9 10] 表示磁頭正下方的值是 1，左邊的清單是空的，所以磁頭位於磁帶開頭。

為什麼不定義一個 Tape，封裝 left、current 與 right，然後令 Head 接受 Tape 實例進行建構呢？這樣就可以清楚地看出哪個是磁頭、哪個是磁帶物件。這樣做也可以，然而最後會是對 Head 的操作，大多委託給 Tape，為了令程式碼單純一些，因此這邊決定不這麼做，也就是令磁頭與磁帶是一體的，若想取得磁帶資料，就透過 Head 來取得。

Brainfuck 指令環境

Brainfuck 的程式碼會以字串方式餵給 Brainfuck 機器，根據〈空想 Brainfuck〉中的說明，必須要能在字串中找尋 [、] 的位置，為了方便，還是將字串轉換成陣列，這樣可以方便運用陣列方的搜尋相關方法：

class Commands {
    constructor(commands, idx = 0) {
        this.commands = commands;
        this.idx = idx;
    }

    get current() {
        return this.commands[this.idx];
    }

    step() {
        return new Commands(this.commands, this.idx + 1);
    }

    rightBracket() {
        let idx = this.commands.slice(this.idx).indexOf(']') + this.idx;
        return new Commands(this.commands, idx);
    }

    leftBracket() {
        let idx = this.commands.slice(0, this.idx).lastIndexOf('[');
        return new Commands(this.commands, idx);
    }

    isRunnable() {
        return this.idx < this.commands.length;
    }
}

commands 接受陣列，idx 表示目前指令執行到哪個位置，current 可以取得目前的指令，step 是前進至下個指令，rightBracket、leftBracket 將指令前進至 ]、[ 的位置，為了簡化以便進行後續討論，這邊不考慮 [、] 形成巢狀的情況，isRunnable 用來測試是否執行完全部的指令。如果指令位置有變動，都是傳回新的 Commands 實例。

在執行過程中，每執行一次指令，Brainfuck 機器環境的狀態就會變化，為了便於掌握環境的狀態變化，設計一個 Context 好了：

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

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

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

Context 封裝了環境變化，可以掌握環境是否可繼續執行，也可以透過它取得磁帶資料，為了方便檢視與處理，磁帶資料轉成陣列傳回。

Brainfuck 規則

接著來處理 Brainfuck 的符號規則，也就是底下這些…

+：將磁頭下方的數字加一，前進至下個指令。
-：將磁頭下方的數字減一，前進至下個指令。
>：右移磁頭，前進至下個指令。
<：左移磁頭，前進至下個指令。
[：磁頭下方的數字若不為 0，前進至下個指令，若為 0，前進至第一個遇上的 ] 指令。
]：磁頭下方的數字若不為 0 時，返回第一個遇上 [ 指令，若為 0，前進至下個指令。
.：將磁頭下方的數字轉成 ASCII 字元，前進至下個指令。
,：將磁頭下方的 ASCII 字元轉成數字，前進至下個指令。

把它們寫進一個操作手冊好了：

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

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

        function writeCurrent(context, x) {
            return new Context(
                context.commands.step(), 
                context.head.write(x)
            );
        }
        
        // +
        function addOne(context) {
            return writeCurrent(context, head(context) + 1);
        }

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

        // <
        function moveHeadLeft(context) {
            return new Context(
                context.commands.step(),
                context.head.moveLeft()
            );   
        }

        // >
        function moveHeadRight(context) {
            return new Context(
                context.commands.step(),
                context.head.moveRight()
            );         
        }

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

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

        // [
        function leftBracket(context) {
            return new Context(
                head(context) === 0 ? context.commands.rightBracket() : context.commands.step(),
                context.head
            );
        }

        // ]
        function rightBracket(context) {
            return new Context(
                    head(context) === 0 ? context.commands.step() : context.commands.leftBracket(),
                    context.head
                );   
        }
    }

    next_context(context) {
        return this.rules.get(context.commands.current)(context);
    }
}

每條規則中，符號都對應一個函式，重要的是 next_context，它透過傳入的 Context 實例取得目前的指令，以便查詢指令符號對應的函式，執行函式之後必須反映出 Brainfuck 機器的環境變化，因此建立新的 Context 物件傳回。

組裝 Brainfuck

接下來就是把這些零件都裝進 Brainfuck 裏了：

class Brainfuck {
    constructor(code) {
        this.context = new Context(
            new Commands(Array.from(code)),
            new Head(new List([]), 0, new List([]))
        );
        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 一開機，磁頭位於磁帶第一個位置，因此左右磁帶都以空 List 代表，因為磁帶每個位置預設值都是 0，磁頭目前位置下的值就設定為 0。若要執行程式碼，呼叫 execute，Brainfuck 從目前的環境物件開始運行，直到執行完畢為止（如果你寫的程式能執行完畢的話）。

現在可以來寫個程式了：

++++++++[>+++++++++<-]>.<+++++++[>>++++++++++<<-]>>-.<<+++++++[>>>++++++++++<<<-]>>>++++++.<<<+++++++[>>>>++++++++++<<<<-]>>>>++++++.<<<<++++++++[>>>>>++++++++++<<<<<-]>>>>>-.<<<<<++++[>>>>>>+++++++++++<<<<<<-]>>>>>>.<<<<<<+++++++++[>>>>>>>++++++++++<<<<<<<-]>>>>>>>---.<<<<<<<++++++++[>>>>>>>>++++++++++<<<<<<<<-]>>>>>>>>-.<<<<<<<<++++++++[>>>>>>>>>++++++++++<<<<<<<<<-]>>>>>>>>>++.<<<<<<<<<++++++++[>>>>>>>>>>++++++++++<<<<<<<<<<-]>>>>>>>>>>----.<<<<<<<<<<+++++++[>>>>>>>>>>>++++++++++<<<<<<<<<<<-]>>>>>>>>>>>--.<<<<<<<<<<<

真的行得通？試試看不就知道了：

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

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

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

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

進階修改

為了簡化以方便聚焦想要討論的對象，之後的文件不會採取考慮接下來討論的程式修改，底下的修改純綷只是作為一個記錄。

如果想要 Brainfuck 可以考慮 [、] 形成巢狀的情況，可以改寫一下 Commands：

class Commands {
    constructor(commands, idx = 0) {
        this.commands = commands;
        this.idx = idx;
    }

    get current() {
        return this.commands[this.idx];
    }

    step() {
        return new Commands(this.commands, this.idx + 1);
    }

    rightBracket() {
        function rightB(n, i) {
            if(n === 0) {
                return i - 1;
            }
            if(cmds[i] === '[') {
                return rightB(n + 1, i + 1);
            }
            if(cmds[i] === ']') {
                return rightB(n - 1, i + 1);
            } 
            return rightB(n, i + 1);
        }
        return new Commands(this.commands, rightB(1, this.idx + 1));
    }

    leftBracket() {
        let cmds = this.commands;

        function leftB(n, i) {
            if(n === 0) {
                return i + 1;
            }
            if(cmds[i] === ']') {
                return leftB(n + 1, i - 1);
            }
            if(cmds[i] === '[') {
                return leftB(n - 1, i - 1);
            } 
            return leftB(n, i - 1);
        }

        return new Commands(this.commands, leftB(1, this.idx - 1));
    }

    isRunnable() {
        return this.idx < this.commands.length;
    }
}

進一步地，想要跟維基百科上〈Brainfuck〉條目中功能描述一致，可以修改 Manual：

const fs = require('fs');

function getCharSync(tips = '>') {
    process.stdout.write(tips);
    process.stdin.pause();
    const buf = Buffer.allocUnsafe(10000);
    let response = fs.readSync(process.stdin.fd, buf, 0, 10000, 0);
    process.stdin.end();
    return buf.toString('utf8', 0, response)[0];
}

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

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

        function writeCurrent(context, x) {
            return new Context(
                context.commands.step(), 
                context.head.write(x)
            );
        }
        
        // +
        function addOne(context) {
            return writeCurrent(context, head(context) + 1);
        }

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

        // <
        function moveHeadLeft(context) {
            return new Context(
                context.commands.step(),
                context.head.moveLeft()
            );   
        }

        // >
        function moveHeadRight(context) {
            return new Context(
                context.commands.step(),
                context.head.moveRight()
            );         
        }

        // .
        function putChar(context) {
            process.stdout.write(String.fromCharCode(head(context)));
            return new Context(
                context.commands.step(),
                context.head
            );
        }

        // ,
        function getChar(context) {
            let char = getCharSync();
            return writeCurrent(context, char.charCodeAt(0));
        }

        // [
        function leftBracket(context) {
            return new Context(
                head(context) === 0 ? context.commands.rightBracket() : context.commands.step(),
                context.head
            );
        }

        // ]
        function rightBracket(context) {
            return new Context(
                    head(context) === 0 ? context.commands.step() : context.commands.leftBracket(),
                    context.head
                );   
        }
    }

    next_context(context) {
        return this.rules.get(context.commands.current)(context);
    }
}

如此一來，底下程式就會顯示 Hello World!：

let code = '++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.';
new Brainfuck(code).execute();

底下的程式可以執行加法：

let code = ',>++++++[<-------->-],,[<+>-],<.>.';
new Brainfuck(code).execute();

由於 getCharSync 是基於換行，與 C 語言版本的 getchar 不同，因此輸入的方式會是如下：

> 3
> +
> 4
> 
7

類似地，底下的程式可以執行乘法：

let code = ',>,,>++++++++[<------<------>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>>>++++++[<++++++++>-],<.>.';
new Brainfuck(code).execute();

輸入的方式會是如下：

> 2
> *
> 4
>
8