Brainfuck
此条目需要补充更多来源。 (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!:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.
目前位置归零
编辑[-]
,.
从键盘读取一个字符并输出到屏幕上。
简单的循环
编辑,[.,]
这是一个循环,连续从键盘读取字符,回显到屏幕上。注意,这里假定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 (页面存档备份,存于互联网档案馆)
注释
编辑参考资料
编辑- ^ 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(页面存档备份,存于互联网档案馆)