标签归档:冯诺伊曼

Brainfuck 语言与图灵机

Brainfuck 语言是在 1992 年由瑞士一名学生 Urban Müller 设计的[1]。Brainfuck 是一种语言要素极精简的计算机语言,它没有一般高级语言拥有的关键字、运算符、标识符、语句等概念,甚至连汇编语言的操作数概念都没有。因此,Brainfuck 语言的编译器和解释器都十分容易实现,并且它们的代码可以非常短小,已经有人实现了可执行文件只有 100 字节的 Brainfuck 编译器。

Brainfuck 语言一共只有 8 个指令,颇有些简陋的语言设计使其代码其实很难编写,写成的代码看上去也是一片混乱,可读性很差。正如它名字所说的,这不是一门实用的程序设计语言,仅是一种程序员自娱自乐的工具。尽管如此,它仍然是一门图灵完备的语言,理论上可以用它实现任何其他计算机程序设计语言能实现的程序。另外,学习 Brainfuck 语言也对理解计算机组成原理和计算机程序原理有一些帮助。

Brainfuck 的全部 8 个指令都由一个单字符表示,分别是 +、-、<、>、.、,、[ 和 ]。Brainfuck 定义了一块内存空间和一个指针,指针指向内存空间的某个地址,指令可以移动指针和操作指针指向的内存单元。Brainfuck 每个指令的作用如下所述。

  • + 指针指向内存单元的值加 1;
  • – 指针指向内存单元的值减 1;
  • < 指针向左移动 1 个单元;
  • > 指针向右移动 1 个单元;
  • . 以字符形式输出指针指向的内存单元的值;
  • , 以字符形式输入到指针指向的内存单元;
  • [ 测试指针指向的内存单元值是否为 0,如果是,跳到对应的 ] 指令的下一个指令处继续执行;
  • ] 测试指针指向的内存单元值是否非 0,如果是,跳到对应的 [ 指令的下一个指令处继续执行。

相比于一门编程语言,Brainfuck 更像是一个简易计算机系统的指令集。语言本身定义了一种包含运算器、内存、寄存器和输入输出设备的计算机,而编程实现 Brainfuck 解释器实质上就是实现了这样一个虚拟机的实例。前面讲到,Brainfuck 是一种很容易实现解释器和编译器的语言,下面是我用 Python 实现的一个 Brainfuck 解释器

Brainfuck 语言缺少基本运算指令,甚至缺少数据传送指令,名副其实,用 Brainfuck 编写程序是一件并不那么愉快的事情。下面是一段用 Brainfuck 编写的可以输出一个指定字符串的 Brainfuck 代码的程序,实际上只是按每个字符的 ASCII 码数值输出了相应数目的自加指令,得到的输出会非常长。为了使输出的代码变得短一些,还有很多发挥技巧的空间,但我不太想这样做了。

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

尽管 Brainfuck 不适合用于编写实用的计算机程序,但它存在的另外一个意义是很直观地描述了一个图灵机的原型。图灵机并不是一台具体的计算机,而是英国数学家阿兰·图灵于 1936 年提出的一种抽象计算模型[2]。图灵机是现代电子计算机的理论基础。

通俗描述的图灵机包含以下四个部分:

  • 一条(无限长)的纸带,纸带分成无穷多个格子,每个格子中可以记录一个数字或符号;
  • 一个读写头,可以在纸带上左右移动,可以读取或修改当前所在格子中的符号;
  • 一个状态寄存器,可以保存机器当前的全部状态;
  • 一套规则表,可以根据当前的状态以及当前读写头指向的纸带中的字符查表决定下一步应该做什么操作。

图灵机有一个特殊的状态,称作停机状态。图灵机必须在有限次的执行步骤后进入停机状态,此时计算完成。图灵认为,图灵机模拟了人类解决数学问题的过程,理论上可以解决任何人类需要手工完成的数学计算。

Brainfuck 语言的描述与图灵机高度契合。在 Brainfuck 解释器中,Brainfuck 的内存数组是图灵机中的那条纸带,指针是图灵机的读写头,额外的几个变量是图灵机的状态寄存器,而 Brainfuck 程序源代码则是图灵机的规则表。Brainfuck 语言解释器实际上成了一个运行在计算机上的虚拟图灵机原型。

图灵机与现代计算机关系密切,是现代电子计算机的理论基础;但如上所述,图灵机并没有描述计算机在硬件上具体如何实现。真正设计了现代电子计算机体系结构的是被称为电子计算机之父的美国科学家约翰·冯·诺伊曼。冯·诺伊曼指出了一个实际可行的电子图灵机的结构:一部由运算器、控制器、存储器和输入输出设备组成的,由程序控制运行的机器,被称为冯·诺伊曼系统结构。

冯·诺伊曼提出的电子计算机系统结构一直被沿用至今,今天我们使用的所有计算机均是建立在这个体系结构之上的。

向图灵、冯·诺伊曼及其他所有参与设计建造电子计算机的先驱们致敬。

(允许转载本文,转载请注明出处:http://luodichen.com/blog/?p=391 )

参考文献
[1] Wikipedia. Brainfuck[EB/OL]. https://en.wikipedia.org/wiki/Brainfuck
[2] Wikipedia. 图灵机[EB/OL].https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA
[3] 吴军. 文明之光(第三册)[M]. 人民邮电出版社, 2015.