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