[译者前言]：本系列译文译自 PyPy Status Blog
刊登的 Writing an Interpreter with PyPy 系列文章，原文作者为 Andrew
Brown，该系列文章的版权属于原文作者所有，在此向 Andrew Brown 以及 PyPy Status Blog
表示致谢。本文译自该系列的第一篇：Writing an Interpreter with PyPy, Part 1.
当我首次了解到 PyPy 项目的时候，我花了有一段时间才搞清楚它到底是什么。对于那些还不知道的，PyPy 包含了两个东西：
- 一套用来为解释语言 (interpreted languages) 实现解释器 (interpreters) 的工具。
- 使用该工具生成的一个 Python 实现。
上面所说的第二部分也许是大多数人理解的 PyPy ，不过本教程并不讲解该 Python 解释器，而是教你如何使用 PyPy 为自己的语言实现自己的解释器。
本教程也是我为了帮助自己更好的理解 PyPy 是如何工作，以及 PyPy 到底是什么所开始的一个项目。
本教程假定你对于 PyPy 以及它是如何工作的了解甚少，甚至它是什么都不需要很清楚。我会从最最基本的地方开始。
PyPy 是做什么的
这里我将对 PyPy 能做什么给出一个主要的概括。让我们假设你想实现一门解释语言，基本上这包括了编写一个源代码解析器 (parser)，一个用来解释字节码的循环 (a bytecode interpretation loop)，以及大量的标准库。
对于中等复杂程度的语言来说，这可是相当一部分工作量，并且这中间还有不少底层的工作。编写解析器以及编译器通常毫无乐趣可言，这也是为什么会有相应的工具来帮你生成解析器以及编译器。
即使如此，你仍然还得担心如何在解释器里进行内存管理，并且如果你想让你的语言支持一些好用的数据类型的话，比如任意精度的整数，通用的哈希表等等，你还得重新实现相当多的代码。这些东西足以令你放弃你的那些好的想法。
如果能够用一门已有的高级语言来实现自己的语言岂不是很好，比如 Python？这当然是非常理想的，你将获得该高级语言的所有优势，比如内存自动管理以及丰富的任你选择的数据结构。啊！不过使用一门解释语言来解释另一门语言岂不是很慢，对吧？那将是两个层级的解释。
不过你也许已经猜到了，PyPy 解决了这个问题。PyPy 是一个能够帮你分析并翻译你的解释器代码到 C 代码（或 JVM 或
JIT）的工具链 (toolchain)。这个过程通常称作“翻译 (translation)”，PyPy 知道如何去翻译相当一部分的
Python 语法以及标准库，不过不是所有的都能翻译。因此你需要做的是使用 RPython（一个精心定义的使得能够进行该分析及翻译过程的
Python 语言的子集）来编写你的解释器代码，然后 PyPy 将为你生成一个高效的解释器。
因为高效的解释器不应该那么难以实现！
语言
我选择要实现的语言非常简单。语言的运行环境包括了一个用来存储整数的磁带存储器，该磁带上所有的整数都初始化为 0，并且有一个指针指向磁带中的某个存储单元。该语言共有 8 个指令，描述如下：
> 将指针向右移动一个单元
< 将指针向左移动一个单元
+ 将指针指向的单元里的值加 1
- 将指针指向的单元里的值减 1
[ 如果指针指向的单元里的值为 0，则跳过其后的指令直到匹配的 ] 后面一条指令
] 跳回到匹配的 [（测试其条件）
. 打印指针指向的单元里的值到标准输出
, 从标准输入读取值到指针指向的单元里
任何其它字节将被忽略。
你也许已经认出了该语言。这里我将该语言简称为 BF [译注 1]。
需要注意的一点是该语言自身就是它的字节码；并没有一个从源代码到字节码的翻译。这意味着该语言可以直接用来解释，我们的解释器的主 eval 循环将直接读取程序的源代码。这可以大大简化我们的实现。
第一步
让我们先用纯 Python 来实现一个 BF 解释器。第一步是先大体上写出主 eval 循环：
04 | while pc < len(program): |
16 | sys.stdout.write(chr(tape.get())) |
18 | tape.set(ord(sys.stdin.read(1))) |
19 | elif code == "[" and value() == 0: |
21 | elif code == "]" and value() != 0: |
你可以看出一个程序计数器（program counter, pc）保存着当前指令的索引。循环里的第一个语句是取出待执行的指令，然后是一个复合 if-elif 语句来判断如何执行该指令。
[ 与 ] 的实现并未在上述代码中列出，但是它们的操作应该是修改 pc 的值为相匹配的中括号所对应的索引的值（然后 pc 的值再被递增，循环条件在进入循环时会检测一次，在每次遍历后也会检测一次）。
下面是 Tape 类的实现，它保存了磁带上存储的整数值以及磁带指针。
07 | return self.thetape[self.position] |
09 | self.thetape[self.position] = val |
11 | self.thetape[self.position] += 1 |
13 | self.thetape[self.position] -= 1 |
16 | if len(self.thetape) <= self.position: |
17 | self.thetape.append(0) |
你可以看到磁带将按照需要无限的向右扩展。我们其实还应该添加一些错误检测以免得指针指向一个负的地方，不过现在我们先不用担心它。
除了省略掉的 [ 与 ] 的实现，这个代码应该工作的很好。不过，如果一个待解释的程序有大量的注释的话，该代码运行时将不得不一个字节一个字节的跳过。让我们一次性将所有的注释都解析出来。
同时我们还会生成一个使得一对匹配的中括号互相映射的 dict，这样寻找一个中括号匹配的另一个中括号将只是一个简单的 dict 查找操作。这里是代码：
08 | if char in ('[', ']', '<', '>', '+', '-', ',', '.'): |
14 | left = leftstack.pop() |
16 | bracket_map[left] = right |
17 | bracket_map[right] = left |
20 | return "".join(parsed), bracket_map |
这个函数返回一个去除了所有非法指令的字符串，以及一个使得匹配的中括号的索引值互相映射的 dict。
现在我们只需将上述代码整合在一起，就能得到一个可以工作的 BF 解释器了。
2 | program, map = parse(input.read()) |
5 | if __name__ == "__main__": |
7 | run(open(sys.argv[1], 'r')) |
如果你是完全跟随着本文键入代码的话，你还需要修改函数 mainloop() 的定义，并实现 if 语句里的中括号分支。完整的例子可以看这里。
现在你可以在 Python 下运行该解释器，并应该看到它能够工作了。不过，需要警告的是，对于稍微复杂一点的例子，它会运行的很慢：
$ python example1.py 99bottles.b
你可以在我的代码库里找到 mandel.b 以及其它几个 BF 程序例子（不过不是我写的）。
PyPy 的翻译
不过本教程可不是教你去如何实现 BF 解释器的，这里要讲的是 PyPy。那么 PyPy 又是如何将该解释器代码翻译成一个超级快的可执行解释器程序呢？
顺便说一句，在 PyPy 源代码树的 pypy/translator/goal 目录下有许多简单的例子非常有帮助。我学习 PyPy 翻译的起点就是其中的例子 "targetnopstandalone.py"，PyPy 翻译的 hello world。
对我们的例子来说，该 Python 模块必须定义一个名为 "target" 的可调用对象，调用该对象将返回一个入口函数（entry point）。翻译过程首先导入你的模块，寻找该名字，调用它，然后从返回的入口函数开始进行翻译。
04 | read = os.read(fp, 4096) |
07 | program_contents += read |
09 | program, bm = parse(program_contents) |
16 | print "You must supply a filename" |
18 | run(os.open(filename, os.O_RDONLY, 0777)) |
22 | return entry_point, None |
24 | if __name__ == "__main__": |
翻译生成的可执行程序调用时的命令行参数将会传给 entry_point 函数。
其它代码也做了一些改动。请继续...
关于 RPython
现在让我们谈一谈 RPython。PyPy 不可能翻译所有的 Python 代码，因为 Python 有点太动态了。因此 PyPy 对于你能使用的 Python 语法以及标准库都做了限制。我无法在这里列出所有的限制，如果你想了解的话，请看这里。
在上面的例子中，你已经看到我们为此做了一些改动。我现在已不再使用文件对象，而是更底层的文件描述符。"." 与 "," 的实现也相应的做了改动（未在上面列出）。这就是所有需要的改动，剩下的代码 PyPy 可以轻松的消化掉。
这看起来并不难，是吧？我们仍然可以使用 dict，可扩展的 list，甚至 classes 与
objects！如果文件描述符对你来说实在太底层的话，PyPy 的“RPython 标准库”所包含的 rlib.streamio
模块有许多非常有用的抽象可以帮助你。
完整的该例子参见这里。
翻译
如果你还没有 PyPy，那么从 PyPy 的 软件库里克隆一份最新的版本 [译注 2]：
$ hg clone https:///pypy/pypy
（一份较新的版本是必须的，因为上述例子需要其中的一个 bug 修复才能工作）。
需要执行的脚本是 "pypy/translator/goal/translate.py"。运行该脚本，并将我们的模块作为一个参数传递给它。
$ python ./pypy/pypy/translator/goal/translate.py example2.py
（你可以使用 PyPy 的 Python 解释器以获得额外的速度，当然这不是必须的）。
PyPy 会输出一大堆信息，并在你的终端上打印各种形状，直到完成工作。在我的机器上，该过程大约需要 20 秒。
该命令执行的结果将是一个可以解释 BF 程序的可执行二进制程序。在我的软件库里包含了一些 BF 范例程序，其中一个是 mandelbrot 分形生成器，在我的电脑上运行该程序大约需要 45 秒。你可以试一下：
$ example2-c mandel.b
再对比一下在 Python 之上运行未翻译的解释器：
$ python example2.py mandel.b
似乎永远也无法成功返回，是吧？
现在你知道 PyPy 了吧。我们成功的使用 RPython 编写了我们的解释器，并用 PyPy 的工具链进行了翻译。
（更多精彩内容敬请期待下一章）。
译者后注
【1】这里所说的 BF 语言的全称是 brainfuck，Wikipedia 上非常详细的介绍以及一个使用 BF 编写的 hello world 程序。
【2】使用该命令去克隆最新的 PyPy 版本相当慢，没有耐心的观众可以直接从这里下载最新的 tip 版本。
参考
[译文] 使用 PyPy 编写解释器：Part 2
