凹语言、图灵机和 BF 语言 #

• 时间：2022-11-17
• 撰稿：凹语言 开发组
• 转载请注明原文链接：https://wa-lang.org/smalltalk/st0013.html

凹语言是国内 Gopher 发起的纯社区构建的开源国产编程语言项目（没有公司背景、没有任何赞助）。同时凹语言也是国内第一个实现纯浏览器内编译、执行全链路的自研静态类型的编译型通用编程语言。本文尝试通过凹语言构建一个图灵完备的 BF 语言的虚拟机。

1. 图灵机是什么 #

图灵机是由图灵提出的一种抽象计算模型。机器有一条无限长的纸带，纸带分成了一个一个的小方格，每个方格有不同的颜色，这类似于计算机中的内存。同时机器有一个探头在纸带上移来移去，类似于通过内存地址来读写内存上的数据。机器头有一组内部计算状态，还有一些固定的程序（更像一个哈佛结构）。在每个时刻，机器头都要从当前纸带上读入一个方格信息，然后根据自己的内部状态和当前要执行的程序指令将信息输出到纸带方格上，同时更新自己的内部状态并进行移动。

2. BF 语言是什么 #

图灵机虽然不容易编程，但是非常容易理解。有一种极小化的 BrainFuck 计算机语言，它的工作模式和图灵机非常相似。BrainFuck 由 Urban Müller 在 1993 年创建的，简称为 BF 语言。Müller 最初的设计目标是建立一种简单的、可以用最小的编译器来实现的、符合图灵完备思想的编程语言。这种语言由八种状态构成，早期为 Amiga 机器编写的编译器（第二版）只有 240 个字节大小！

就象它的名字所暗示的，brainfuck 程序很难读懂。尽管如此，brainfuck 图灵机一样可以完成任何计算任务。虽然 brainfuck 的计算方式如此与众不同，但它确实能够正确运行。这种语言基于一个简单的机器模型，除了指令，这个机器还包括：一个以字节为单位、被初始化为零的数组、一个指向该数组的指针（初始时指向数组的第一个字节）、以及用于输入输出的两个字节流。这是一种按照图灵完备的语言，它的主要设计思路是：用最小的概念实现一种 “简单” 的语言。BrainFuck 语言只有八种符号，所有的操作都由这八种符号的组合来完成。

下面是这八种状态的描述，其中每个状态由一个字符标识：

下面是一个 brainfuck 程序，向标准输出打印 "hi" 字符串：

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

理论上我们可以将 BF 语言当作目标机器语言，将其它高级语言编译为 BF 语言后就可以在 BF 机器上运行了。

3. 凹语言构造 BF 虚拟机 #

首先构造一个虚拟机结构体：

type BrainFuck struct {
	mem  :[30000]byte
	code :string
	pos  :int
	pc   :int
}

其中 mem 表示虚拟机的 30000 个字节大小的内存，然后 code 表示输入的 BF 程序，pos 表示当前的输出位置，pc 则是指令的位置。

然后封装对应的构造函数和 Run 方法：

fn NewBrainFuck(code: string) => *BrainFuck {
	return &BrainFuck{code: code}
}

fn BrainFuck.Run() {
	# ...
}

下面是 main 函数构造 BF 虚拟机并执行的方式：

fn main {
	# print hi
	const code = "++++++++++[>++++++++++<-]>++++.+."
	vm := NewBrainFuck(code)
	vm.Run()
}

下面让我们来看看 BrainFuck.Run 函数的实现：

fn BrainFuck.Run() {
	for ; this.pc != len(this.code); this.pc++ {
		switch x := this.code[this.pc]; x {
		case '>':
			this.pos++
		case '<':
			this.pos--
		case '+':
			this.mem[this.pos]++
		case '-':
			this.mem[this.pos]--
		case '[':
			if this.mem[this.pos] == 0 {
				this.loop(1)
			}
		case ']':
			if this.mem[this.pos] != 0 {
				this.loop(-1)
			}
		case '.':
			print(rune(this.mem[this.pos]))
		case ',':
			# TODO: support read byte
		}
	}
	return
}

基本就是按照 BF 语言的指令逐个解释执行。其中输出是通过 print 内置函数打印，输入指令没有处理。

另外 BrainFuck.loop 私有方法则用于处理嵌套指令：

fn BrainFuck.loop(inc: int) {
	for i := inc; i != 0; this.pc += inc {
		switch this.code[this.pc+inc] {
		case '[':
			i++
		case ']':
			i--
		}
	}
}

完整的程序可以参考 brainfuck.wa。

需要克隆最新的凹语言仓库，然后在根目录执行：

$ wa run brainfuck.wa 
hi

4. 未来展望 #

虽然 BF 看似一个非常简单的语言，但是它却是一个图灵完备的编程语言。理论上任何高级语言编写的程序均可以由 BF 语言模拟出等价的程序。既然可以通过凹语言实行一个 BF 虚拟机那么凹语言必然也是图灵完备的，下一次希望通过凹语言构建更为复杂有趣的程序。