打造 Brainfuck

December 16, 2021

現今這個年代,自造正夯,就來動手打造一台 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(' ');
    }
}

可以分別透過 firsttail 取得清單首元素與尾清單,透過 initlast 分別取得頭清單與尾元素,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}]`;
    }
}    

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

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

為什麼不定義一個 Tape,封裝 leftcurrentright,然後令 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 是前進至下個指令,rightBracketleftBracket 將指令前進至 ][ 的位置,為了簡化以便進行後續討論,這邊不考慮 [] 形成巢狀的情況,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