如何使用Python編寫一個Lisp解釋器

原文出處：  Peter Norvig    譯文出處：  jnjc（@jnjcc）

本文有兩個目的: 一是講述實作計算機語言解釋器的通用方法，另外一點，着重展示如何使用Python來實作Lisp方言Scheme的一個子集。我将我的解釋器稱之為Lispy (lis.py)。幾年前，我介紹過如何使用Java編寫一個Scheme解釋器，同時我還使用Common Lisp語言編寫過一個版本。這一次，我的目的是盡可能簡單明了地示範一下Alan Kay所說的“軟體的麥克斯韋方程組” (Maxwell’s Equations of Software)[1]。

Lispy支援的Scheme子集的文法和語義

大多數計算機語言都有許多文法規約 (例如關鍵字、中綴操作符、括号、操作符優先級、點标記、分号等等)，但是，作為Lisp語言家族中的一員，Scheme所有的文法都是基于包含在括号中的、采用字首表示的清單的。這種表示看起來似乎有些陌生，但是它具有簡單一緻的優點。 (一些人戲稱”Lisp”是”Lots of Irritating Silly Parentheses“——“大量惱人、愚蠢的括号“——的縮寫；我認為它是”Lisp Is Syntactically Pure“——“Lisp文法純粹”的縮寫。) 考慮下面這個例子：

1 2 3 4 5 6 7 / * Java * / if (x.val() > ) { z = f(a * x.val() + b); } / * Scheme * / ( if (> (val x) ) ( set ! z (f ( + ( * a (val x)) b))))

注意上面的驚歎号在Scheme中并不是一個特殊字元；它隻是”

set!

“這個名字的一部分。(在Scheme中)隻有括号是特殊字元。類似于

(set! x y)

這樣以特殊關鍵字開頭的清單在Scheme中被稱為一個特殊形式 (special form)；Scheme的優美之處就在于我們隻需要六種特殊形式，以及另外的三種文法構造——變量、常量和過程調用。

形式 (Form)	文法	語義和示例
變量引用	var	一個符号，被解釋為一個變量名；其值就是這個變量的值。 示例:  x
常量字面值	number	數字的求值結果為其本身 示例:  12  或者 -3.45e+6
引用	( quote  exp)	傳回exp的字面值；不對它進行求值。 示例： (quote (a b c)) ⇒ (a b c)
條件測試	( if  test conseq alt)	對test進行求值；如果結果為真，那麼對conseq進行求值并傳回結果；否則對alt求值并傳回結果。 示例： (if (< 10 20) (+ 1 1) (+ 3 3)) ⇒ 2
指派	( set!  varexp)	對exp進行求值并将結果賦給var，var必須已經進行過定義 (使用 define 進行定義或者作為一個封閉過程的參數)。 示例： (set! x2 (* x x))
定義	( define  varexp)	在最内層環境 (environment) 中定義一個新的變量并将對exp表達式求值所得的結果賦給該變量。 示例：( define r 3)  或者  (define square (lambda (x) (* x x)))
過程	( lambda (var…)exp)	建立一個過程，其參數名字為var…，過程體為相應的表達式。 示例： (lambda (r) (* 3.141592653 (* r r)))
(表達式) 序列	( begin exp…)	按從左到右的順序對表達式進行求值，并傳回最終的結果。 示例： (begin (set! x 1) (set! x (+ x 1)) (* x 2)) ⇒ 4
過程調用	(proc exp…)	如果proc是除了 if, set!, define, lambda, begin, 或者 quote 之外的其它符号的話，那麼它會被視作一個過程。它的求值規則如下：所有的表達式exp都将被求值，然後這些求值結果作為過程的實際參數來調用該相應的過程。 示例： (square 12) ⇒ 144

在該表中，var必須是一個符号——一個類似于x或者square這樣的辨別符——number必須是一個整型或者浮點型數字，其餘用斜體辨別的單詞可以是任何表達式。exp…表示exp的0次或者多次重複。

更多關于Scheme的内容，可以參考一些優秀的書籍 (如Friedman和Fellesein, Dybvig,Queinnec, Harvey和Wright或者Sussman和Abelson)、視訊 (Abelson和Sussman)、教程 (Dorai、PLT或者Neller)、或者參考手冊。

語言解釋器的職責

一個語言解釋器包括兩部分：

1、解析 (Parsing)：解析部分接受一個使用字元序清單示的輸入程式，根據語言的文法規則對輸入程式進行驗證，然後将程式翻譯成一種中間表示。在一個簡單的解釋器中，中間表示是一種樹結構，緊密地反映了源程式中語句或表達式的嵌套結構。在一種稱為編譯器的語言翻譯器中，内部表示是一系列可以直接由計算機 (作者的原意是想說運作時系統——譯者注) 執行的指令。正如Steve Yegge所說，“如果你不明白編譯器的工作方式，那麼你不會明白計算機的工作方式。”Yegge介紹了編譯器可以解決的8種問題 (或者解釋器，又或者采用Yegge的典型的反諷式的解決方案)。 Lispy的解析器由

parse

函數實作。

2、執行：程式的内部表示 (由解釋器) 根據語言的語義規則進行進一步處理，進而執行源程式的實際運算。(Lispy的)執行部分由

eval

函數實作 (注意，該函數覆寫了Python内建的同名函數)。

下面的圖檔描述了解釋器的解釋流程，(圖檔後的) 互動會話展示了

parse

和

eval

函數對一個小程式的操作方式：

1 2 3 4 5 6 7 >> program = "(begin (define r 3) (* 3.141592653 (* r r)))" >>> parse(program) [ 'begin' , [ 'define' , 'r' , 3 ], [ '*' , 3.141592653 , [ '*' , 'r' , 'r' ]]] >>> eval (parse(program)) 28.274333877

這裡，我們采用了一種盡可能簡單的内部表示，其中Scheme的清單、數字和符号分别使用Python的清單、數字和字元串來表示。

執行: 

eval

下面是

eval

函數的定義。對于上面表中列出的九種情況，每一種都有一至三行代碼，

eval

函數的定義隻需要這九種情況：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 def eval (x, env = global_env): "Evaluate an expression in an environment." if isa(x, Symbol):             # variable reference return env.find(x)[x] elif not isa(x, list ):         # constant literal return x                elif x[ ] = = 'quote' :          # (quote exp) (_, exp) = x return exp elif x[ ] = = 'if' :             # (if test conseq alt) (_, test, conseq, alt) = x return eval ((conseq if eval (test, env) else alt), env) elif x[ ] = = 'set!' :           # (set! var exp) (_, var, exp) = x env.find(var)[var] = eval (exp, env) elif x[ ] = = 'define' :         # (define var exp) (_, var, exp) = x env[var] = eval (exp, env) elif x[ ] = = 'lambda' :         # (lambda (var*) exp) (_, vars , exp) = x return lambda * args: eval (exp, Env( vars , args, env)) elif x[ ] = = 'begin' :          # (begin exp*) for exp in x[ 1 :]: val = eval (exp, env) return val else :                          # (proc exp*) exps = [ eval (exp, env) for exp in x] proc = exps.pop( ) return proc( * exps) isa = isinstance Symbol = str

eval函數的定義就是這麼多…當然，除了environments。Environments (環境) 隻是從符号到符号所代表的值的映射而已。一個新的符号/值綁定由一個

define

語句或者一個過程定義 (

lambda

表達式) 添加。

讓我們通過一個例子來觀察定義然後調用一個Scheme過程的時候所發生的事情 (

lis.py>

提示符表示我們正在與Lisp解釋器進行互動，而不是Python):

1 2 3 lis.py> (define area ( lambda (r) ( * 3.141592653 ( * r r)))) lis.py> (area 3 ) 28.274333877

當我們對

(lambda (r) (* 3.141592653 (* r r)))

進行求值時，我們在

eval

函數中執行

elif x[0] == 'lambda'

分支，将

(_, vars, exp)

三個變量分别指派為清單

x

的對應元素 (如果

x

的長度不是3，就抛出一個錯誤)。然後，我們建立一個新的過程，當該過程被調用的時候，将會對表達式

['*', 3.141592653 ['*', 'r', 'r']]

進行求值，該求值過程的環境 (environment) 是通過将過程的形式參數 (該例中隻有一個參數，

r

) 綁定為過程調用時所提供的實際參數，外加目前環境中所有不在參數清單 (例如，變量

*

) 的變量組成的。新建立的過程被指派給

global_env

中的

area

變量。

那麼，當我們對

(area 3)

求值的時候發生了什麼呢？因為

area

并不是任何表示特殊形式的符号之一，它必定是一個過程調用 (

eval

函數的最後一個

else:

分支)，是以整個表達式清單都将會被求值，每次求值其中的一個。對

area

進行求值将會獲得我們剛剛建立的過程；對3進行求值所得的結果就是3。然後我們 (根據

eval

函數的最後一行) 使用參數清單[3]來調用這個新建立的過程。也就是說，對

exp

(也就是

['*', 3.141592653 ['*', 'r', 'r']]

)進行求值，并且求值所在的環境中

r

的值是3，并且外部環境是全局環境，是以

*

是乘法過程。

現在，我們可以解釋一下Env類的細節了：

1 2 3 4 5 6 7 8 class Env( dict ): "An environment: a dict of {'var':val} pairs, with an outer Env." def __init__( self , parms = (), args = (), outer = None ): self .update( zip (parms,args)) self .outer = outer def find( self , var): "Find the innermost Env where var appears." return self if var in self else self .outer.find(var)

注意

Env

是

dict

的一個子類，也就是說，通常的字典操作也适用于

Env

類。除此之外，該類還有兩個方法，構造函數

__init__

和

find

函數，後者用來為一個變量查找正确的環境。了解這個類的關鍵 (以及我們需要一個類，而不是僅僅使用

dict

的根本原因) 在于外部環境 (outer environment) 這個概念。考慮下面這個程式：

1 2 3 4 5 6

(define make - account ( lambda (balance) ( lambda (amt) (begin ( set ! balance ( + balance amt)) balance)))) (define a1 (make - account 100.00 )) (a1 - 20.00 )

每個矩形框都代表了一個環境，并且矩形框的顔色與環境中最新定義的變量的顔色相對應。在程式的最後兩行我們定義了

a1

并且調用了

(a1 -20.00)

；這表示建立一個開戶金額為100美元的銀行賬戶，然後是取款20美元。在對

(a1 -20.00)

求值的過程中，我們将會對黃色高亮表達式進行求值，該表達式中具有三個變量。

amt

可以在最内層 (綠色) 環境中直接找到。但是

balance

在該環境中沒有定義：我們需要檢視綠色環境的外層環境，也就是藍色環境。最後，

+

代表的變量在這兩個環境中都沒有定義；我們需要進一步檢視外層環境，也就是全局 (紅色) 環境。先查找内層環境，然後依次查找外部的環境，我們把這一過程稱之為詞法定界 (lexical scoping)。

Procedure.find

負責根據詞法定界規則查找正确的環境。

剩下的就是要定義全局環境。該環境需要包含

+

過程以及所有其它Scheme的内置過程。我們并不打算實作所有的内置過程，但是，通過導入Python的math子產品，我們可以獲得一部分這些過程，然後我們可以顯式地添加20種常用的過程：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 def add_globals(env): "Add some Scheme standard procedures to an environment." import math, operator as op env.update( vars (math)) # sin, sqrt, ... env.update( { '+' :op.add, '-' :op.sub, '*' :op.mul, '/' :op.div, 'not' :op.not_, '>' :op.gt, '<' :op.lt, '>=' :op.ge, '<=' :op.le, '=' :op.eq, 'equal?' :op.eq, 'eq?' :op.is_, 'length' : len , 'cons' : lambda x,y:[x] + y, 'car' : lambda x:x[ ], 'cdr' : lambda x:x[ 1 :], 'append' :op.add,  'list' : lambda * x: list (x), 'list?' : lambda x:isa(x, list ), 'null?' : lambda x:x = = [], 'symbol?' : lambda x: isa(x, Symbol)}) return env global_env = add_globals(Env())

PS1: 對麥克斯韋方程組的一種評價是“一般地，宇宙間任何的電磁現象，皆可由此方程組解釋”。Alan Kay所要表達的，大緻就是Lisp語言使用自身定義自身 (Lisp was “defined in terms of Lisp”) 這種自底向上的設計對軟體設計而言具有普遍的參考價值。——譯者注

解析 (Parsing): 

read

和

parse

接下來是

parse

函數。解析通常分成兩個部分：詞法分析和文法分析。前者将輸入字元串分解成一系列的詞法單元 (token)；後者将詞法單元組織成一種中間表示。Lispy支援的詞法單元包括括号、符号 (如

set!

或者

x

) 以及數字 (如2)。它的工作形式如下：

1 2 3 4 5 6 7 >>> program = "(set! x*2 (* x 2))" >>> tokenize(program) [ '(' , 'set!' , 'x*2' , '(' , '*' , 'x' , '2' , ')' , ')' ] >>> parse(program) [ 'set!' , 'x*2' , [ '*' , 'x' , 2 ]]

有許多工具可以進行詞法分析 (例如Mike Lesk和Eric Schmidt的lex)。但是我們将會使用一個非常簡單的工具：Python的

str.split

。我們隻是在 (源程式中) 括号的兩邊添加空格，然後調用

str.split

來獲得一個詞法單元的清單。

接下來是文法分析。我們已經看到，Lisp的文法很簡單。但是，一些Lisp解釋器允許接受表示清單的任何字元串作為一個程式，進而使得文法分析的工作更加簡單。換句話說，字元串

(set! 1 2)

可以被接受為是一個文法上有效的程式，隻有當執行的時候解釋器才會抱怨

set!

的第一個參數應該是一個符号，而不是數字。在Java或者Python中，與之等價的語句

1 = 2

将會在編譯時被認定是錯誤。另一方面，Java和Python并不需要在編譯時檢測出表達式

x/0

是一個錯誤，是以，如你所見，一個錯誤應該何時被識别并沒有嚴格的規定。Lispy使用

read

函數來實作

parse

函數，前者用以讀取任何的表達式 (數字、符号或者嵌套清單)。

tokenize

函數擷取一系列詞法單元，

read

通過在這些詞法單元上調用

read_from

函數來進行工作。給定一個詞法單元的清單，我們首先檢視第一個詞法單元；如果它是一個’)’，那麼這是一個文法錯誤。如果它是一個’(‘，那麼我們開始建構一個表達式清單，直到我們讀取一個比對的’)’。所有其它的 (詞法單元) 必須是符号或者數字，它們自身構成了一個完整的清單。剩下的需要注意的就是要了解’

2

‘代表一個整數，

2.0

代表一個浮點數，而

x

代表一個符号。我們将區分這些情況的工作交給Python去完成：對于每一個不是括号也不是引用 (quote) 的詞法單元，我們首先嘗試将它解釋為一個int，然後嘗試float，最後嘗試将它解釋為一個符号。根據這些規則，我們得到了如下程式：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 def read(s): "Read a Scheme expression from a string." return read_from(tokenize(s)) parse = read def tokenize(s): "Convert a string into a list of tokens." return s.replace( '(' , ' ( ' ).replace( ')' , ' ) ' ).split() def read_from(tokens): "Read an expression from a sequence of tokens." if len (tokens) = = : raise SyntaxError( 'unexpected EOF while reading' ) token = tokens.pop( ) if '(' = = token: L = [] while tokens[ ] ! = ')' : L.append(read_from(tokens)) tokens.pop( ) # pop off ')' return L elif ')' = = token: raise SyntaxError( 'unexpected )' ) else : return atom(token) def atom(token): "Numbers become numbers; every other token is a symbol." try : return int (token) except ValueError: try : return float (token) except ValueError: return Symbol(token)

最後，我們将要添加一個函數

to_string

，用來将一個表達式重新轉換成Lisp可讀的字元串；以及一個函數

repl

，該函數表示read-eval-print-loop (讀取-求值-列印循環)，用以構成一個互動式的Lisp解釋器：

1 2 3 4 5 6 7 8 9 def to_string(exp): "Convert a Python object back into a Lisp-readable string." return '(' + ' ' .join( map (to_string, exp)) + ')' if isa(exp, list ) else str (exp) def repl(prompt = 'lis.py> ' ): "A prompt-read-eval-print loop." while True : val = eval (parse( raw_input (prompt))) if val is not None : print to_string(val)

下面是函數工作的一個例子：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 >>> repl() lis.py> (define area ( lambda (r) ( * 3.141592653 ( * r r)))) lis.py> (area 3 ) 28.274333877 lis.py> (define fact ( lambda (n) ( if (< = n 1 ) 1 ( * n (fact ( - n 1 )))))) lis.py> (fact 10 ) 3628800 lis.py> (fact 100 ) 9332621544394415268169923885626670049071596826438162146859296389521759999322991 5608941463976156518286253697920827223758251185210916864000000000000000000000000 lis.py> (area (fact 10 )) 4.1369087198e + 13 lis.py> (define first car) lis.py> (define rest cdr) lis.py> (define count ( lambda (item L) ( if L ( + (equal? item (first L)) (count item (rest L))) ))) lis.py> (count ( list 1 2 3 )) 3 lis.py> (count (quote the) (quote (the more the merrier the bigger the better))) 4

Lispy有多小、多快、多完備、多優秀？

我們使用如下幾個标準來評價Lispy：

*小巧：Lispy非常小巧：不包括注釋和空白行，其源代碼隻有90行，并且體積小于4K。(比第一個版本的體積要小，第一個版本有96行——根據Eric Cooper的建議，我删除了

Procedure

的類定義，轉而使用Python的

lambda

。) 我用Java編寫的Scheme解釋器Jscheme最小的版本，其源代碼也有1664行、57K。Jscheme最初被稱為SILK (Scheme in Fifty Kilobytes——50KB的Scheme解釋器)，但是隻有計算位元組碼而不是源代碼的時候，我才能保證 (其體積) 小于該最小值。Lispy做的要好得多；我認為它滿足了Alan Kay在1972年的斷言：他聲稱我們可以使用“一頁代碼”來定義“世界上最強大的語言”。

1 2 bash$ grep "^\s*[^#\s]" lis.py | wc 90 398 3423

*高效：Lispy計算

(fact 100)

隻需要0.004秒。對我來說，這已經足夠快了 (雖然相比起其它的計算方式來說要慢很多)。

*完備：相比起Scheme标準來說，Lispy不是非常完備。主要的缺陷有：

(1) 文法：缺少注釋、引用 (quote) / 反引用 (quasiquote) 标記 (即

'

和

`

——譯者注)、#字面值 (例如#\a——譯者注)、衍生表達式類型 (例如從

if

衍生而來的

cond

，或者從

lambda

衍生而來的

let

)，以及點清單 (dotted list)。

(2) 語義：缺少call/cc以及尾遞歸。

(3) 資料類型：缺少字元串、字元、布爾值、端口 (ports)、向量、精确/非精确數字。事實上，相比起Scheme的pairs和清單，Python的清單更加類似于Scheme的向量。

(4) 過程：缺少100多個基本過程：與缺失資料類型相關的所有過程，以及一些其它的過程 (如

set-car!

和

set-cdr!

，因為使用Python的清單，我們無法完整實作

set-cdr!

)。

(5) 錯誤恢複：Lispy沒有嘗試檢測錯誤、合理地報告錯誤以及從錯誤中恢複。Lispy希望程式員是完美的。

*優秀：這一點需要讀者自己确定。我覺得，相對于我解釋Lisp解釋器這一目标而言，它已經足夠優秀。

真實的故事

了解解釋器的工作方式會很有幫助，有一個故事可以支援這一觀點。1984年的時候，我在撰寫我的博士論文。當時還沒有LaTeX和Microsoft Word——我們使用的是troff。遺憾的是，troff中沒有針對符号标簽的前向引用機制：我想要能夠撰寫“正如我們将要在@theoremx頁面看到的”，随後在合适的位置撰寫”@(set theoremx \n%)” (troff寄存器\n%儲存了頁号)。我的同伴，研究所學生Tony DeRose也有着同樣的需求，我們一起實作了一個簡單的Lisp程式，使用這個程式作為一個預處理器來解決我們的問題。然而，事實證明，當時我們用的Lisp善于讀取Lisp表達式，但在采用一次一個字元的方式讀取非Lisp表達式時效率過低，以至于我們的這個程式很難使用。

在這個問題上，Tony和我持有不同的觀點。他認為 (實作) 表達式的解釋器是困難的部分；他需要Lisp為他解決這一問題，但是他知道如何編寫一個短小的C過程來處理非Lisp字元，并知道如何将其連結進Lisp程式。我不知道如何進行這種連結，但是我認為為這種簡單的語言編寫一個解釋器 (其所具有的隻是設定變量、擷取變量值和字元串連接配接) 很容易，于是我使用C語言編寫了一個解釋器。是以，戲劇性的是，Tony編寫了一個Lisp程式，因為他是一個C程式員；我編寫了一個C程式，因為我是一個Lisp程式員。

最終，我們都完成了我們的論文。

整個解釋器

重新總結一下，下面就是Lispy的所有代碼 (也可以從lis.py下載下傳)：

1 2 3 4 5 # -*- coding: UTF-8 -*- # 源代碼略。以下純屬娛樂。。。 # 你想看完整源代碼？真的想看？ # 真的想看你就說嘛，又不是我編寫的代碼，你想看我總不能不讓你看，對吧？ # 真的想看的話就參考上述下載下傳位址喽。。。LOL