空想 Brainfuck

December 15, 2021

你有一台機器,這機器有無限長的磁帶,往左、往右都是無限(為了便於描述,之後有時會將磁帶上資料最左方稱為磁帶開頭),有個磁頭可以在磁帶各位置讀出或寫入資料,你有八個指令可以控制這台機器,例如,要令機器在磁頭右邊的磁帶寫入 Hello,World 這些字元,可以輸入指令:

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

規則

這哪裡是指令?指令就是規則,每個規則對應於一個符號,上頭用到的符號不超過八個(其實只有用到七個),每個符號對應的規則是:

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

這邊的 Brainfuck 與 Urban Müller 在 1993 年建立的 Brainfuck 稍有不同,差別在於 ., 都是在磁帶上運作,而非將資料送至標準輸出或從標準輸入取得資料。

機器磁帶上每個位置的預設值都是 0,磁頭一開始位於磁帶上第一個位置,因此,餵給機器 ++++++++,會在磁帶上第一個位置進行八次的加一,最後在磁帶第一個位置就會是 8,餵給機器 ++++++++>++++++++,磁帶第一個位置是 8,右移磁頭在磁帶第二個位置進行八次的加一,最後在磁帶第一與第二位置都會是 8。

如果想在磁帶第二個位置寫下 64 呢?>之後寫 64 次 + 雖然可以,不過,可以使用 ++++++++[>+++++++++<-],這時指令的執行順序會是…

  1. 因為 +++++++++,磁帶第一個位置會寫下 8
  2. 執行指令 [,磁頭下方的數字不為 0,因此前進至下個指令
  3. 執行指令 >,右移磁頭
  4. 接下來有 8 個 + 指令,表示在磁帶第二個位置寫下 8
  5. 執行 <,磁頭左移
  6. 執行 -,磁頭下方數字減一成為 7
  7. 執行 ],因為磁頭下方數字不為 0,返回 [ 指令
  8. 執行 [ 指令,磁頭下方的數字不為 0,因此前進至下個指令

顯然地,步驟 2 到 8 會重複執行至磁帶第一個位置的數字被減至 0 為止,步驟 2 到 8 總共會執行 8 次,也就是在磁帶第二個位置寫下 64 的數字了,如果指令最後加上一個 .,將 64 轉換為 ASCII 字元,就會是 H字元了。

發現了嗎?這機器有加減法,[] 具有重複執行的效果,結合起來就可以有乘法效果,[] 也可以組合出程式語言中 if 的功能,簡直就可以當成一門程式語言了!沒錯,這機器確實是一門程式語言,稱為 Brainfuck

語言?

沒搞錯吧!+-><[]., 可以作為一門程式語言?當然不行,沒有規則以及可以按指令規則執行的硬體,這八個字元只是符號而已。

也就是說,Brainfuck 這門程式語言(或者這台機器),包含了…

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

通常有了前兩項,就會假設這樣的硬體是存在的,至少還有你可以躲在一個鐵盒裏,按照指令與規則來動作,最後把磁帶塞到外頭,給鐵盒外輸入指令的人看,對吧!

也就是說,看到現今任何一門程式語言的書時,其實都假設了,可以按照程式碼執行的機器是確實存在的,不然的話,怎麼會快快樂樂地捧著書、看著文件裏的程式碼呢?

在還不能在任何電腦上執行程式碼之前,你就是那台機器了!來吧!執行看看:

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

拿著紙筆慢慢來,最後應該會寫出 Hello,World,不過這對人類太苦了,充滿許多重複性的動作,就不能打造出一台真正的 Brainfuck 機器嗎?