Brainfuck

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

## 概述

Müller的目標是創建一種簡單的、可以用最小的編譯器來實現的、符合圖靈完全思想的程式語言。這個語言由八種運算符構成，為Amiga機器編寫的編譯器（第二版）只有240個字節大小。

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

這種語言基於一個簡單的機器模型。這個機器除了指令以外，還包括：一個以字節為單位、已初始化為零的陣列、一個指向該陣列的指針（開始時指向陣列的第一個字節）、以及用於輸入輸出的兩個字節流。

下面是這八種狀態的描述，其中每個狀態由一個字符標識：

字符｜含義

`>`｜指針加一

`<`｜指針減一

`+`｜指針所指字節的值加一

`-`｜指針所指字節的值減一

`.`｜輸出指針所指字節內容（ASCII碼）

`,`｜向指針所指的字節輸入內容（ASCII碼）

`[`｜若指針所指字節的值為零，則向後跳轉，跳轉到其對應的`]`的下一個指令處

`]`｜若指針所指字節的值不為零，則向前跳轉，跳轉到其對應的`[`的下一個指令處

Brainfuck指令可以逐一替換，翻譯成C語言（假設`ptr`是`char *`類型）的語句之類：

Brainfuck｜C

`>`｜`++ptr;`

`<`｜`--ptr;`

`+`｜`++*ptr;`

`-`｜`--*ptr;`

`.`｜`putchar(*ptr);`

`,`｜`*ptr = getchar();`

## 例子

### Hello World!

在螢幕上列印Hello World!：

```bf
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.
```

### 目前位置歸零

```bf
[-]
```

### 字符I/O

```bf
,.
```

從鍵盤讀取一個字符並輸出到螢幕上。

### 簡單的循環

```bf
,[.,]
```

這是一個循環，連續從鍵盤讀取字符，回顯到螢幕上。注意，這裡假定0表示輸入結束，但有些系統並非如此。如果是-1表示輸入結束，代碼就應是

```bf
,+[-.,+]
```

如果是輸入未改變表示輸入結束，代碼則是

```bf
,[->+>-<<]>[-<+>]>[[-]<<.[->>+<<],[->+>-<<]>[-<+>]>]
```

### 指針維護

```bf
>,[.>,]
```

移動指針，保存所有的輸入，供後面的程序使用。

### 加法

```bf
[->+<]
```

把當前位置的值加到後面的單元中（會讓左邊的單元歸零）。

### 條件指令

```bf
,----------[----------------------.,----------]
```

從鍵盤讀來小寫字符，轉成大寫。按回車鍵退出程序。

首先，通過`,`讀入第一個字符並把它減10（10 在大多數情況下為換行符 LF 的值）。如果使用者按的是回車鍵，循環命令（`[`）就會直接跳轉到程序的結尾：因為這時第一個字節已經減到了零。如果輸入的字符不是換行符（比如是一個小寫字符），程序就進入循環。在這裡再減去剩下的22，這樣總共減掉32。這是ASCII碼中小寫字符和大寫字符的差值。

下面輸出到螢幕。然後接收下一個輸入字符，並減去10。如果它是換行符，退出循環；否則，再回到循環的開始，減去22並輸出……退出了循環，後面沒有了其他指令，程序便隨之終止。

### 加法器 add(summand, addend, *sum)

```brainfuck
>>[-]>[-]<<<        // 清空 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)

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

## 外部連結

- 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