《Python Cookbook(第2版)中文版》

本书适合具有一定Python基础的读者阅读参考。 ...

↑我也要推荐

[译文] 使用 PyPy 编写解释器:Part 1

发布时间:2011-06-19 11:02:23, 关注:+9539, 赞美:+7, 不爽:+5

本文标签: pypy 解释器

原始出处: 开源小厨

 [译者前言]:本系列译文译自 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 循环:

def mainloop(program):
    tape = Tape()
    pc = 0
    while pc < len(program):
        code = program[pc]

        if code == ">":
            tape.advance()
        elif code == "<":
            tape.devance()
        elif code == "+":
            tape.inc()
        elif code == "-":
            tape.dec()
        elif code == ".":
            sys.stdout.write(chr(tape.get()))
        elif code == ",":
            tape.set(ord(sys.stdin.read(1)))
        elif code == "[" and value() == 0:
            # Skip forward to the matching ]
        elif code == "]" and value() != 0:
            # Skip back to the matching [

        pc += 1 

 你可以看出一个程序计数器(program counter, pc)保存着当前指令的索引。循环里的第一个语句是取出待执行的指令,然后是一个复合 if-elif 语句来判断如何执行该指令。

[ 与 ] 的实现并未在上述代码中列出,但是它们的操作应该是修改 pc 的值为相匹配的中括号所对应的索引的值(然后 pc 的值再被递增,循环条件在进入循环时会检测一次,在每次遍历后也会检测一次)。

下面是 Tape 类的实现,它保存了磁带上存储的整数值以及磁带指针。

class Tape(object):
    def __init__(self):
        self.thetape = [0]
        self.position = 0

    def get(self):
        return self.thetape[self.position]
    def set(self, val):
        self.thetape[self.position] = val
    def inc(self):
        self.thetape[self.position] += 1
    def dec(self):
        self.thetape[self.position] -= 1
    def advance(self):
        self.position += 1
        if len(self.thetape) <= self.position:
            self.thetape.append(0)
    def devance(self):
        self.position -= 1

你可以看到磁带将按照需要无限的向右扩展。我们其实还应该添加一些错误检测以免得指针指向一个负的地方,不过现在我们先不用担心它。

除了省略掉的 [ 与 ] 的实现,这个代码应该工作的很好。不过,如果一个待解释的程序有大量的注释的话,该代码运行时将不得不一个字节一个字节的跳过。让我们一次性将所有的注释都解析出来。

同时我们还会生成一个使得一对匹配的中括号互相映射的 dict,这样寻找一个中括号匹配的另一个中括号将只是一个简单的 dict 查找操作。这里是代码:

def parse(program):
    parsed = []
    bracket_map = {}
    leftstack = []

    pc = 0
    for char in program:
        if char in ('[', ']', '<', '>', '+', '-', ',', '.'):
            parsed.append(char)

            if char == '[':
                leftstack.append(pc)
            elif char == ']':
                left = leftstack.pop()
                right = pc
                bracket_map[left] = right
                bracket_map[right] = left
            pc += 1

    return "".join(parsed), bracket_map

这个函数返回一个去除了所有非法指令的字符串,以及一个使得匹配的中括号的索引值互相映射的 dict。

现在我们只需将上述代码整合在一起,就能得到一个可以工作的 BF 解释器了。

def run(input):
    program, map = parse(input.read())
    mainloop(program, map)

if __name__ == "__main__":
    import sys
    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)。翻译过程首先导入你的模块,寻找该名字,调用它,然后从返回的入口函数开始进行翻译。

def run(fp):
    program_contents = ""
    while True:
        read = os.read(fp, 4096)
        if len(read) == 0:
            break
        program_contents += read
    os.close(fp)
    program, bm = parse(program_contents)
    mainloop(program, bm)

def entry_point(argv):
    try:
        filename = argv[1]
    except IndexError:
        print "You must supply a filename"
        return 1
    run(os.open(filename, os.O_RDONLY, 0777))
    return 0

def target(*args):
    return entry_point, None

if __name__ == "__main__":
    entry_point(sys.argv)

翻译生成的可执行程序调用时的命令行参数将会传给 entry_point 函数。

其它代码也做了一些改动。请继续...

关于 RPython

现在让我们谈一谈 RPython。PyPy 不可能翻译所有的 Python 代码,因为 Python 有点太动态了。因此 PyPy 对于你能使用的 Python 语法以及标准库都做了限制。我无法在这里列出所有的限制,如果你想了解的话,请看这里

在上面的例子中,你已经看到我们为此做了一些改动。我现在已不再使用文件对象,而是更底层的文件描述符。"." 与 "," 的实现也相应的做了改动(未在上面列出)。这就是所有需要的改动,剩下的代码 PyPy 可以轻松的消化掉。

这看起来并不难,是吧?我们仍然可以使用 dict,可扩展的 list,甚至 classes 与 objects!如果文件描述符对你来说实在太底层的话,PyPy 的“RPython 标准库”所包含的 rlib.streamio 模块有许多非常有用的抽象可以帮助你。

完整的该例子参见这里

翻译

如果你还没有 PyPy,那么从 PyPy 的 bitbucket.org 软件库里克隆一份最新的版本 [译注 2]:

$ hg clone https://bitbucket.org/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 版本。

如果你觉得本站对你有帮助,欢迎向本站赞助 :P

使用支付宝捐赠

Copyright© Python4cn(news, jobs) simple-is-better.com, 技术驱动:powered by web.py 空间主机:Webfaction

版权申明:文章转载已注明出处,如有疑问请来信咨询。本站为 python 语言推广公益网站,与 python 官方没有任何关系。

联系/投搞/留言: en.simple.is.better@gmail.com 向本站捐赠