[譯者前言]：本系列譯文譯自 PyPy Status Blog
刊登的 Writing an Interpreter with PyPy 系列文章，原文作者為 Andrew
Brown，該系列文章的版權(quán)屬于原文作者所有，在此向 Andrew Brown 以及 PyPy Status Blog
表示致謝。本文譯自該系列的第一篇：Writing an Interpreter with PyPy, Part 1.
當(dāng)我首次了解到 PyPy 項(xiàng)目的時候，我花了有一段時間才搞清楚它到底是什么。對于那些還不知道的，PyPy 包含了兩個東西：
- 一套用來為解釋語言 (interpreted languages) 實(shí)現(xiàn)解釋器 (interpreters) 的工具。
- 使用該工具生成的一個 Python 實(shí)現(xiàn)。
上面所說的第二部分也許是大多數(shù)人理解的 PyPy ，不過本教程并不講解該 Python 解釋器，而是教你如何使用 PyPy 為自己的語言實(shí)現(xiàn)自己的解釋器。
本教程也是我為了幫助自己更好的理解 PyPy 是如何工作，以及 PyPy 到底是什么所開始的一個項(xiàng)目。
本教程假定你對于 PyPy 以及它是如何工作的了解甚少，甚至它是什么都不需要很清楚。我會從最最基本的地方開始。
PyPy 是做什么的
這里我將對 PyPy 能做什么給出一個主要的概括。讓我們假設(shè)你想實(shí)現(xiàn)一門解釋語言，基本上這包括了編寫一個源代碼解析器 (parser)，一個用來解釋字節(jié)碼的循環(huán) (a bytecode interpretation loop)，以及大量的標(biāo)準(zhǔn)庫。
對于中等復(fù)雜程度的語言來說，這可是相當(dāng)一部分工作量，并且這中間還有不少底層的工作。編寫解析器以及編譯器通常毫無樂趣可言，這也是為什么會有相應(yīng)的工具來幫你生成解析器以及編譯器。
即使如此，你仍然還得擔(dān)心如何在解釋器里進(jìn)行內(nèi)存管理，并且如果你想讓你的語言支持一些好用的數(shù)據(jù)類型的話，比如任意精度的整數(shù)，通用的哈希表等等，你還得重新實(shí)現(xiàn)相當(dāng)多的代碼。這些東西足以令你放棄你的那些好的想法。
如果能夠用一門已有的高級語言來實(shí)現(xiàn)自己的語言豈不是很好，比如 Python？這當(dāng)然是非常理想的，你將獲得該高級語言的所有優(yōu)勢，比如內(nèi)存自動管理以及豐富的任你選擇的數(shù)據(jù)結(jié)構(gòu)。??！不過使用一門解釋語言來解釋另一門語言豈不是很慢，對吧？那將是兩個層級的解釋。
不過你也許已經(jīng)猜到了，PyPy 解決了這個問題。PyPy 是一個能夠幫你分析并翻譯你的解釋器代碼到 C 代碼（或 JVM 或
JIT）的工具鏈 (toolchain)。這個過程通常稱作“翻譯 (translation)”，PyPy 知道如何去翻譯相當(dāng)一部分的
Python 語法以及標(biāo)準(zhǔn)庫，不過不是所有的都能翻譯。因此你需要做的是使用 RPython（一個精心定義的使得能夠進(jìn)行該分析及翻譯過程的
Python 語言的子集）來編寫你的解釋器代碼，然后 PyPy 將為你生成一個高效的解釋器。
因?yàn)楦咝У慕忉屍鞑粦?yīng)該那么難以實(shí)現(xiàn)！
語言
我選擇要實(shí)現(xiàn)的語言非常簡單。語言的運(yùn)行環(huán)境包括了一個用來存儲整數(shù)的磁帶存儲器，該磁帶上所有的整數(shù)都初始化為 0，并且有一個指針指向磁帶中的某個存儲單元。該語言共有 8 個指令，描述如下：
> 將指針向右移動一個單元
< 將指針向左移動一個單元
+ 將指針指向的單元里的值加 1
- 將指針指向的單元里的值減 1
[ 如果指針指向的單元里的值為 0，則跳過其后的指令直到匹配的 ] 后面一條指令
] 跳回到匹配的 [（測試其條件）
. 打印指針指向的單元里的值到標(biāo)準(zhǔn)輸出
, 從標(biāo)準(zhǔn)輸入讀取值到指針指向的單元里
任何其它字節(jié)將被忽略。
你也許已經(jīng)認(rèn)出了該語言。這里我將該語言簡稱為 BF [譯注 1]。
需要注意的一點(diǎn)是該語言自身就是它的字節(jié)碼；并沒有一個從源代碼到字節(jié)碼的翻譯。這意味著該語言可以直接用來解釋，我們的解釋器的主 eval 循環(huán)將直接讀取程序的源代碼。這可以大大簡化我們的實(shí)現(xiàn)。
第一步
讓我們先用純 Python 來實(shí)現(xiàn)一個 BF 解釋器。第一步是先大體上寫出主 eval 循環(huán)：
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: |
你可以看出一個程序計數(shù)器（program counter, pc）保存著當(dāng)前指令的索引。循環(huán)里的第一個語句是取出待執(zhí)行的指令，然后是一個復(fù)合 if-elif 語句來判斷如何執(zhí)行該指令。
[ 與 ] 的實(shí)現(xiàn)并未在上述代碼中列出，但是它們的操作應(yīng)該是修改 pc 的值為相匹配的中括號所對應(yīng)的索引的值（然后 pc 的值再被遞增，循環(huán)條件在進(jìn)入循環(huán)時會檢測一次，在每次遍歷后也會檢測一次）。
下面是 Tape 類的實(shí)現(xiàn)，它保存了磁帶上存儲的整數(shù)值以及磁帶指針。
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) |
你可以看到磁帶將按照需要無限的向右擴(kuò)展。我們其實(shí)還應(yīng)該添加一些錯誤檢測以免得指針指向一個負(fù)的地方，不過現(xiàn)在我們先不用擔(dān)心它。
除了省略掉的 [ 與 ] 的實(shí)現(xiàn)，這個代碼應(yīng)該工作的很好。不過，如果一個待解釋的程序有大量的注釋的話，該代碼運(yùn)行時將不得不一個字節(jié)一個字節(jié)的跳過。讓我們一次性將所有的注釋都解析出來。
同時我們還會生成一個使得一對匹配的中括號互相映射的 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 |
這個函數(shù)返回一個去除了所有非法指令的字符串，以及一個使得匹配的中括號的索引值互相映射的 dict。
現(xiàn)在我們只需將上述代碼整合在一起，就能得到一個可以工作的 BF 解釋器了。
2 | program, map = parse(input.read()) |
5 | if __name__ == "__main__": |
7 | run(open(sys.argv[1], 'r')) |
如果你是完全跟隨著本文鍵入代碼的話，你還需要修改函數(shù) mainloop() 的定義，并實(shí)現(xiàn) if 語句里的中括號分支。完整的例子可以看這里。
現(xiàn)在你可以在 Python 下運(yùn)行該解釋器，并應(yīng)該看到它能夠工作了。不過，需要警告的是，對于稍微復(fù)雜一點(diǎn)的例子，它會運(yùn)行的很慢：
$ python example1.py 99bottles.b
你可以在我的代碼庫里找到 mandel.b 以及其它幾個 BF 程序例子（不過不是我寫的）。
PyPy 的翻譯
不過本教程可不是教你去如何實(shí)現(xiàn) BF 解釋器的，這里要講的是 PyPy。那么 PyPy 又是如何將該解釋器代碼翻譯成一個超級快的可執(zhí)行解釋器程序呢？
順便說一句，在 PyPy 源代碼樹的 pypy/translator/goal 目錄下有許多簡單的例子非常有幫助。我學(xué)習(xí) PyPy 翻譯的起點(diǎn)就是其中的例子 "targetnopstandalone.py"，PyPy 翻譯的 hello world。
對我們的例子來說，該 Python 模塊必須定義一個名為 "target" 的可調(diào)用對象，調(diào)用該對象將返回一個入口函數(shù)（entry point）。翻譯過程首先導(dǎo)入你的模塊，尋找該名字，調(diào)用它，然后從返回的入口函數(shù)開始進(jìn)行翻譯。
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__": |
翻譯生成的可執(zhí)行程序調(diào)用時的命令行參數(shù)將會傳給 entry_point 函數(shù)。
其它代碼也做了一些改動。請繼續(xù)...
關(guān)于 RPython
現(xiàn)在讓我們談一談 RPython。PyPy 不可能翻譯所有的 Python 代碼，因?yàn)?Python 有點(diǎn)太動態(tài)了。因此 PyPy 對于你能使用的 Python 語法以及標(biāo)準(zhǔn)庫都做了限制。我無法在這里列出所有的限制，如果你想了解的話，請看這里。
在上面的例子中，你已經(jīng)看到我們?yōu)榇俗隽艘恍└膭?。我現(xiàn)在已不再使用文件對象，而是更底層的文件描述符。"." 與 "," 的實(shí)現(xiàn)也相應(yīng)的做了改動（未在上面列出）。這就是所有需要的改動，剩下的代碼 PyPy 可以輕松的消化掉。
這看起來并不難，是吧？我們?nèi)匀豢梢允褂?dict，可擴(kuò)展的 list，甚至 classes 與
objects！如果文件描述符對你來說實(shí)在太底層的話，PyPy 的“RPython 標(biāo)準(zhǔn)庫”所包含的 rlib.streamio
模塊有許多非常有用的抽象可以幫助你。
完整的該例子參見這里。
翻譯
如果你還沒有 PyPy，那么從 PyPy 的 軟件庫里克隆一份最新的版本 [譯注 2]：
$ hg clone https:///pypy/pypy
（一份較新的版本是必須的，因?yàn)樯鲜隼有枰渲械囊粋€ bug 修復(fù)才能工作）。
需要執(zhí)行的腳本是 "pypy/translator/goal/translate.py"。運(yùn)行該腳本，并將我們的模塊作為一個參數(shù)傳遞給它。
$ python ./pypy/pypy/translator/goal/translate.py example2.py
（你可以使用 PyPy 的 Python 解釋器以獲得額外的速度，當(dāng)然這不是必須的）。
PyPy 會輸出一大堆信息，并在你的終端上打印各種形狀，直到完成工作。在我的機(jī)器上，該過程大約需要 20 秒。
該命令執(zhí)行的結(jié)果將是一個可以解釋 BF 程序的可執(zhí)行二進(jìn)制程序。在我的軟件庫里包含了一些 BF 范例程序，其中一個是 mandelbrot 分形生成器，在我的電腦上運(yùn)行該程序大約需要 45 秒。你可以試一下：
$ example2-c mandel.b
再對比一下在 Python 之上運(yùn)行未翻譯的解釋器：
$ python example2.py mandel.b
似乎永遠(yuǎn)也無法成功返回，是吧？
現(xiàn)在你知道 PyPy 了吧。我們成功的使用 RPython 編寫了我們的解釋器，并用 PyPy 的工具鏈進(jìn)行了翻譯。
（更多精彩內(nèi)容敬請期待下一章）。
譯者后注
【1】這里所說的 BF 語言的全稱是 brainfuck，Wikipedia 上非常詳細(xì)的介紹以及一個使用 BF 編寫的 hello world 程序。
【2】使用該命令去克隆最新的 PyPy 版本相當(dāng)慢，沒有耐心的觀眾可以直接從這里下載最新的 tip 版本。
參考
[譯文] 使用 PyPy 編寫解釋器：Part 2
