Brainfuck
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目需要補充更多來源。 (2022年9月27日) |
Brainfuck,簡稱BF,是一種極小化的程序語言,由Urban Müller在1993年創造。Fuck在英語中是髒話,所以這種語言有時稱為Brainf*ck或Brainf***,或者只用簡稱。
概述
Müller的目標是創建一種簡單的、可以用最小的編譯器來實現的、符合圖靈完全思想的編程語言。這個語言由八種運算符構成,為Amiga機器編寫的編譯器(第二版)只有240個字節大小。[1]
Brainfuck 的名字已經暗示出來,它的程序代碼很難讀懂。儘管如此,Brainfuck仍然可以像圖靈機一般完成任何計算任務。它雖然計算方式與眾不同,但確實能夠正確運行。
這種語言基於一個簡單的機器模型。這個機器除了指令以外,還包括:一個以字節為單位、已初始化為零的數組、一個指向該數組的指針(開始時指向數組的第一個字節)、以及用於輸入輸出的兩個字節流。
下面是這八種狀態的描述,其中每個狀態由一個字符標識:
字符 | 含義 |
---|---|
> |
指針加一 |
< |
指針減一 |
+ |
指針所指字節的值加一 |
- |
指針所指字節的值減一 |
. |
輸出指針所指字節內容(ASCII碼) |
, |
向指針所指的字節輸入內容(ASCII碼) |
[
|
若指針所指字節的值為零,則向後跳轉,跳轉到其對應的] 的下一個指令處
|
]
|
若指針所指字節的值不為零,則向前跳轉,跳轉到其對應的[ 的下一個指令處
|
Brainfuck指令可以逐一替換,翻譯成C語言(假設ptr
是char *
類型)的語句之類:
Brainfuck | C |
---|---|
> |
++ptr;
|
< |
--ptr;
|
+
|
++*ptr;
|
-
|
--*ptr;
|
.
|
putchar(*ptr);
|
,
|
*ptr = getchar();
|
[
|
while (*ptr) {
|
]
|
}
|
例子
Hello World!
在屏幕上打印Hello World!:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.
目前位置歸零
[-]
字符I/O
,.
從鍵盤讀取一個字符並輸出到屏幕上。
簡單的循環
,[.,]
這是一個循環,連續從鍵盤讀取字符,回顯到屏幕上。注意,這裡假定0表示輸入結束,但有些系統並非如此。如果是-1表示輸入結束,代碼就應是,+[-.,+]
。如果是輸入未改變表示輸入結束,代碼則是,[->+>-<<]>[-<+>]>[[-]<<.[->>+<<],[->+>-<<]>[-<+>]>]
。
指針維護
>,[.>,]
移動指針,保存所有的輸入,供後面的程序使用。
加法
[->+<]
把當前位置的值加到後面的單元中(會讓左邊的單元歸零)。
條件指令
,----------[----------------------.,----------]
從鍵盤讀來小寫字符,轉成大寫。按回車鍵退出程序。
首先,通過,
讀入第一個字符並把它減10(10 在大多數情況下為換行符 LF 的值)。如果用戶按的是回車鍵,循環命令([
)就會直接跳轉到程序的結尾:因為這時第一個字節已經減到了零。如果輸入的字符不是換行符(比如是一個小寫字符),程序就進入循環。在這裡再減去剩下的22,這樣總共減掉32。這是ASCII碼中小寫字符和大寫字符的差值。
下面輸出到屏幕。然後接收下一個輸入字符,並減去10。如果它是換行符,退出循環;否則,再回到循環的開始,減去22並輸出……退出了循環,後面沒有了其他指令,程序便隨之終止。
加法器 add(summand, addend, *sum)
>>[-]>[-]<<< // 清空 cell #2 和 #3
[->>+>+<<<] // cell #0 的值移到 cell #2 和 #3
>
>>[-<<<+>>>]<< // cell #3 的值移到 cell #0
[->+>+<<] // cell #1 的值移到 cell #2 和 #3
>>[-<<+>>]<< // cell #3 的值移到 cell #1
<
將保存在 cell #0 和 #1 中的兩個整數相加,結果保存在 cell #2。 以 cell #3 為臨時變量,保證了原來的兩個存儲單元數值不變,方便以後使用。
代碼運行前,指針指向 cell #0,
第一步,先將 cell #2 和 cell #3 清空,確保不會有多餘的數據影響運算結果;
第二步,將 cell #0 的值同時轉移到 cell #2 和 cell #3,再用 cell #3 來恢復 cell #0 的值;
第三步,將 cell #1 的值同時轉移到 cell #2 和 cell #3,再用 cell #3 來恢復 cell #1 的值;
最後,指針歸位(回到初始位置),方便後續運算。
乘法器 multiply(multiplicand, multiplier, *product)
>>[-]>[-]>[-]<<<< // 清空 cell #2、 #3 和 #4
[-> // cell #0 的值减 1
[->+>+<<] // cell #1 的值加进 cell #2 和 #3
>>
[-<<+>>] // cell #3 的值移回 cell #1
>+< // cell #4 的值加 1,这样外循环结束时 cell #4 的值和 cell #0 原来的值就相等
<<
<]
>>>>[-<<<<+>>>>]<<<< // cell #4 的值移回 cell #0
跟上面的「加法器」類似,這個「乘法器」將保存在 cell #0 和 cell #1 的兩個整數相乘,結果保存在 cell #2。 同樣使用了臨時變量,保證了原來的兩個存儲單元數值不變,方便以後使用。
更多代碼解析請參見 https://github.com/moky/BrainFuck (頁面存檔備份,存於網際網路檔案館)
注釋
- 注意,這裡數組的每個單元大小都是一個字節;
-
命令允許溢出,1個-
等於是255個+
。同樣,如果數組單元是有限、循環的,1個<
就等於是29999個>
。每個修改動作都可以分解為最多7條指令。但是,兩個連在一起的修改動作將會破壞「圖靈完全」,因為它們會使可能的內存狀態從無限個變為有限個。更確切地說,從這個角度看,現代的計算機依然達不到完全意義上的「圖靈完全」
參考資料
- ^ dev/lang/brainfuck-2.lha. Aminet. [2013-10-30]. (原始內容存檔於2005-11-06).
外部連結
- Brian Raiter, Muppetlabs. Brainfuck:八條指令的圖靈完全編程語言(頁面存檔備份,存於網際網路檔案館)。這個網站包括一個Brainfuck程序quine。
- Panu Kalliokoski. Brainfuck檔案有許多Brainfuck實現、程序和quine。
- Cat's Eye Technologies. Brainfuck
- Frans Faase. BF is Turing Complete(頁面存檔備份,存於網際網路檔案館)
- Brainfucked - Brainfuck Compiler
- BrainFuck Codes - moky(頁面存檔備份,存於網際網路檔案館)
- Brainfuck - Esolang(頁面存檔備份,存於網際網路檔案館)
|