Brainfuck

Brainfuck,是一种极小化的程序语言,它是由Urban Müller在1993年创造的。由於fuck英語中是髒話,这种语言有时被称为Brainf*ckBrainf***,或被简称为BF

概述

Müller的目标是建立一种简单的、可以用最小的编译器来实现的、符合图灵完全思想的编程语言。这种语言由八种运算符构成,为Amiga机器编写的编译器(第二版)只有240个字节大小。[1]

就像它的名字所暗示的,Brainfuck程序很难读懂。尽管如此,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)

>>[-]>[-]<<<        // clear cell #2 and #3
[->>+>+<<<]         // transfer cell #0 to #2 and #3
>
    >>[-<<<+>>>]<<  // transfer cell #3 to #0
    [->+>+<<]       // transfer cell #1 to #2 and #3
    >>[-<<+>>]<<    // transfer cell #3 to #1
<

该代码以 cell #3 作为临时变量,将保存在 cell #0 和 cell #1 中的两个整数相加,

结果保存在 cell #2;同时维持原来的两个存储单元数值不变,方便以后使用。

代码运行前,设定指针指向 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 的值;

最后,指针归位(回到初始位置,即指向 cell #0),方便后续运算。

乘法器 multiply(multiplicand, multiplier, *product)

>>[-]>[-]>[-]<<<<       // clear cell #2 and #3 and #4
[->
    [->+>+<<]           // add cell #1 to #2 and #3
    >>
        [-<<+>>]        // move cell #3 back to #1
        >+<             // copy cell #0 to #4
    <<
<]
>>>>[-<<<<+>>>>]<<<<    // move cell #4 back to #0

跟上面的“加法器”类似,这个“乘法器”将保存在 cell #0 和 cell #1 的两个整数相乘,结果保存在 cell #2;同时维持原来的两个存储单元数值不变,方便以后使用。

更多代码解析请参见 https://github.com/moky/BrainFuck页面存档备份,存于

注释

  • 注意,这里数组的每个单元都是一个字节大小;-命令允许溢出,它可以用255个+命令来代替。同样,如果数组单元是有限、循环的<可以用29999个>命令代替。每个修改动作都可以被分解为最多7条指令。可是,两个连在一起的修改动作将会破坏“图灵完全”,因为这会把可能的内存状态限制到有限个数。(更确切的说,从这个角度看,现代的计算机依然不是完全意义上的“图灵完全”)

参考资料

  1. . Aminet. [2013-10-30]. (原始内容存档于2005-11-06).

外部链接

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.