跳至內容

Brainfuck

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

Brainfuck,簡稱BF,是一種極小化的程式語言,由Urban Müller在1993年創造。Fuck英語中是髒話,所以這種語言有時稱為Brainf*ckBrainf***,或者只用簡稱。

概述

[編輯]

Müller的目標是建立一種簡單的、可以用最小的編譯器來實現的、符合圖靈完全思想的程式語言。這個語言由八種運算子構成,為Amiga機器編寫的編譯器(第二版)只有240個位元組大小。[1]

Brainfuck的名字已經暗示出來,它的程式代碼很難讀懂。儘管如此,Brainfuck仍然可以像圖靈機一般完成任何計算任務。它雖然計算方式與眾不同,但確實能夠正確執行。

這種語言基於一個簡單的機器模型。這個機器除了指令以外,還包括:一個以位元組為單位、已初始化為零的陣列、一個指向該陣列的指標(開始時指向陣列的第一個位元組)、以及用於輸入輸出的兩個位元組流

下面是這八種狀態的描述,其中每個狀態由一個字元標識:

字元 含義
> 指標加一
< 指標減一
+ 指標所指位元組的值加一
- 指標所指位元組的值減一
. 輸出指標所指位元組內容(ASCII碼
, 向指標所指的位元組輸入內容(ASCII碼)
[ 若指標所指位元組的值為零,則向後跳轉,跳轉到其對應的]的下一個指令處
] 若指標所指位元組的值不為零,則向前跳轉,跳轉到其對應的[的下一個指令處

Brainfuck指令可以逐一替換,翻譯成C語言(假設ptrchar *類型)的陳述式之類:

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條指令。但是,兩個連在一起的修改動作將會破壞「圖靈完全」,因為它們會使可能的主記憶體狀態從無限個變為有限個。更確切地說,從這個角度看,現代的電腦依然達不到完全意義上的「圖靈完全

參考資料

[編輯]
  1. ^ dev/lang/brainfuck-2.lha. Aminet. [2013-10-30]. (原始內容存檔於2005-11-06). 

外部連結

[編輯]