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

Lispy支持的Scheme子集的語法和語義

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

/* Java */if(x.val() > 0) { z = f(a*x.val() + b);}/* Scheme */(if (> (val x) 0) (set! z (f (+ (* a (val x)) b))))

注意上面的驚嘆號在Scheme中并不是一個特殊字符；它只是”set!“這個名字的一部分。(在Scheme中)只有括號是特殊字符。類似于(set! x y)這樣以特殊關鍵字開頭的列表在Scheme中被稱為一個特殊形式 (special form)；Scheme的優美之處就在于我們只需要六種特殊形式，以及另外的三種語法構造――變量、常量和過程調用。

在該表中，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函數對一個小程序的操作方式：

這里，我們采用了一種盡可能簡單的內部表示，其中Scheme的列表、數字和符號分別使用Python的列表、數字和字符串來表示。

執行: eval
下面是eval函數的定義。對于上面表中列出的九種情況，每一種都有一至三行代碼，eval函數的定義只需要這九種情況：

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[0] == 'quote':   # (quote exp)  (_, exp) = x  return exp elif x[0] == 'if':    # (if test conseq alt)  (_, test, conseq, alt) = x  return eval((conseq if eval(test, env) else alt), env) elif x[0] == 'set!':   # (set! var exp)  (_, var, exp) = x  env.find(var)[var] = eval(exp, env) elif x[0] == 'define':   # (define var exp)  (_, var, exp) = x  env[var] = eval(exp, env) elif x[0] == 'lambda':   # (lambda (var*) exp)  (_, vars, exp) = x  return lambda *args: eval(exp, Env(vars, args, env)) elif x[0] == '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(0)  return proc(*exps) isa = isinstance Symbol = str

eval函數的定義就是這么多…當然，除了environments。Environments (環境) 只是從符號到符號所代表的值的映射而已。一個新的符號/值綁定由一個define語句或者一個過程定義 (lambda表達式) 添加。

讓我們通過一個例子來觀察定義然后調用一個Scheme過程的時候所發生的事情 (lis.py>提示符表示我們正在與Lisp解釋器進行交互，而不是Python):
 

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類的細節了：
 

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) 這個概念。考慮下面這個程序：
 

(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種常用的過程：
 

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[0],'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)。它的工作形式如下：
 

>>> 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，最后嘗試將它解釋為一個符號。根據這些規則，我們得到了如下程序：

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) == 0:  raise SyntaxError('unexpected EOF while reading') token = tokens.pop(0) if '(' == token:  L = []  while tokens[0] != ')':   L.append(read_from(tokens))  tokens.pop(0) # 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解釋器：
 

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)

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

>>> repl()lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))lis.py> (area 3)28.274333877lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))lis.py> (fact 10)3628800lis.py> (fact 100)93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000lis.py> (area (fact 10))4.1369087198e+13lis.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))) 0)))lis.py> (count 0 (list 0 1 2 3 0 0))3lis.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年的斷言：他聲稱我們可以使用“一頁代碼”來定義“世界上最強大的語言”。
 

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下載)：
 

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