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

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

大多數(shù)計算機語言都有許多語法規(guī)約 (例如關(guān)鍵字、中綴操作符、括號、操作符優(yōu)先級、點標(biāo)記、分號等等)，但是，作為Lisp語言家族中的一員，Scheme所有的語法都是基于包含在括號中的、采用前綴表示的列表的。這種表示看起來似乎有些陌生，但是它具有簡單一致的優(yōu)點。 (一些人戲稱”Lisp”是”Lots of Irritating Silly Parentheses“——“大量惱人、愚蠢的括號“——的縮寫；我認(rèn)為它是”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)這樣以特殊關(guān)鍵字開頭的列表在Scheme中被稱為一個特殊形式 (special form)；Scheme的優(yōu)美之處就在于我們只需要六種特殊形式，以及另外的三種語法構(gòu)造——變量、常量和過程調(diào)用。

在該表中，var必須是一個符號——一個類似于x或者square這樣的標(biāo)識符——number必須是一個整型或者浮點型數(shù)字，其余用斜體標(biāo)識的單詞可以是任何表達(dá)式。exp…表示exp的0次或者多次重復(fù)。

更多關(guān)于Scheme的內(nèi)容，可以參考一些優(yōu)秀的書籍 (如Friedman和Fellesein, Dybvig,Queinnec, Harvey和Wright或者Sussman和Abelson)、視頻 (Abelson和Sussman)、教程 (Dorai、PLT或者Neller)、或者參考手冊。

語言解釋器的職責(zé)
一個語言解釋器包括兩部分：

1、解析 (Parsing)：解析部分接受一個使用字符序列表示的輸入程序，根據(jù)語言的語法規(guī)則對輸入程序進(jìn)行驗證，然后將程序翻譯成一種中間表示。在一個簡單的解釋器中，中間表示是一種樹結(jié)構(gòu)，緊密地反映了源程序中語句或表達(dá)式的嵌套結(jié)構(gòu)。在一種稱為編譯器的語言翻譯器中，內(nèi)部表示是一系列可以直接由計算機 (作者的原意是想說運行時系統(tǒng)——譯者注) 執(zhí)行的指令。正如Steve Yegge所說，“如果你不明白編譯器的工作方式，那么你不會明白計算機的工作方式?！盰egge介紹了編譯器可以解決的8種問題 (或者解釋器，又或者采用Yegge的典型的反諷式的解決方案)。 Lispy的解析器由parse函數(shù)實現(xiàn)。

2、執(zhí)行：程序的內(nèi)部表示 (由解釋器) 根據(jù)語言的語義規(guī)則進(jìn)行進(jìn)一步處理，進(jìn)而執(zhí)行源程序的實際運算。(Lispy的)執(zhí)行部分由eval函數(shù)實現(xiàn) (注意，該函數(shù)覆蓋了Python內(nèi)建的同名函數(shù))。

下面的圖片描述了解釋器的解釋流程，(圖片后的) 交互會話展示了parse和eval函數(shù)對一個小程序的操作方式：

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

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

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函數(shù)的定義就是這么多…當(dāng)然，除了environments。Environments (環(huán)境) 只是從符號到符號所代表的值的映射而已。一個新的符號/值綁定由一個define語句或者一個過程定義 (lambda表達(dá)式) 添加。

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

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

當(dāng)我們對(lambda (r) (* 3.141592653 (* r r)))進(jìn)行求值時，我們在eval函數(shù)中執(zhí)行elif x[0] == 'lambda'分支，將(_, vars, exp)三個變量分別賦值為列表x的對應(yīng)元素 (如果x的長度不是3，就拋出一個錯誤)。然后，我們創(chuàng)建一個新的過程，當(dāng)該過程被調(diào)用的時候，將會對表達(dá)式['*', 3.141592653 ['*', 'r', 'r']]進(jìn)行求值，該求值過程的環(huán)境 (environment) 是通過將過程的形式參數(shù) (該例中只有一個參數(shù)，r) 綁定為過程調(diào)用時所提供的實際參數(shù)，外加當(dāng)前環(huán)境中所有不在參數(shù)列表 (例如，變量*) 的變量組成的。新創(chuàng)建的過程被賦值給global_env中的area變量。

那么，當(dāng)我們對(area 3)求值的時候發(fā)生了什么呢？因為area并不是任何表示特殊形式的符號之一，它必定是一個過程調(diào)用 (eval函數(shù)的最后一個else:分支)，因此整個表達(dá)式列表都將會被求值，每次求值其中的一個。對area進(jìn)行求值將會獲得我們剛剛創(chuàng)建的過程；對3進(jìn)行求值所得的結(jié)果就是3。然后我們 (根據(jù)eval函數(shù)的最后一行) 使用參數(shù)列表[3]來調(diào)用這個新創(chuàng)建的過程。也就是說，對exp(也就是['*', 3.141592653 ['*', 'r', 'r']])進(jìn)行求值，并且求值所在的環(huán)境中r的值是3，并且外部環(huán)境是全局環(huán)境，因此*是乘法過程。

現(xiàn)在，我們可以解釋一下Env類的細(xì)節(jié)了：
 

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類。除此之外，該類還有兩個方法，構(gòu)造函數(shù)__init__和find函數(shù)，后者用來為一個變量查找正確的環(huán)境。理解這個類的關(guān)鍵 (以及我們需要一個類，而不是僅僅使用dict的根本原因) 在于外部環(huán)境 (outer environment) 這個概念。考慮下面這個程序：
 

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

每個矩形框都代表了一個環(huán)境，并且矩形框的顏色與環(huán)境中最新定義的變量的顏色相對應(yīng)。在程序的最后兩行我們定義了a1并且調(diào)用了(a1 -20.00)；這表示創(chuàng)建一個開戶金額為100美元的銀行賬戶，然后是取款20美元。在對(a1 -20.00)求值的過程中，我們將會對黃色高亮表達(dá)式進(jìn)行求值，該表達(dá)式中具有三個變量。amt可以在最內(nèi)層 (綠色) 環(huán)境中直接找到。但是balance在該環(huán)境中沒有定義：我們需要查看綠色環(huán)境的外層環(huán)境，也就是藍(lán)色環(huán)境。最后，+代表的變量在這兩個環(huán)境中都沒有定義；我們需要進(jìn)一步查看外層環(huán)境，也就是全局 (紅色) 環(huán)境。先查找內(nèi)層環(huán)境，然后依次查找外部的環(huán)境，我們把這一過程稱之為詞法定界 (lexical scoping)。Procedure.find負(fù)責(zé)根據(jù)詞法定界規(guī)則查找正確的環(huán)境。

剩下的就是要定義全局環(huán)境。該環(huán)境需要包含+過程以及所有其它Scheme的內(nèi)置過程。我們并不打算實現(xiàn)所有的內(nèi)置過程，但是，通過導(dǎo)入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: 對麥克斯韋方程組的一種評價是“一般地，宇宙間任何的電磁現(xiàn)象，皆可由此方程組解釋”。Alan Kay所要表達(dá)的，大致就是Lisp語言使用自身定義自身 (Lisp was “defined in terms of Lisp”) 這種自底向上的設(shè)計對軟件設(shè)計而言具有普遍的參考價值。——譯者注

解析 (Parsing): read和parse

接下來是parse函數(shù)。解析通常分成兩個部分：詞法分析和語法分析。前者將輸入字符串分解成一系列的詞法單元 (token)；后者將詞法單元組織成一種中間表示。Lispy支持的詞法單元包括括號、符號 (如set!或者x) 以及數(shù)字 (如2)。它的工作形式如下：
 

>>> program = "(set! x*2 (* x 2))"
 
>>> tokenize(program)
['(', 'set!', 'x*2', '(', '*', 'x', '2', ')', ')']
 
>>> parse(program)
['set!', 'x*2', ['*', 'x', 2]]

有許多工具可以進(jìn)行詞法分析 (例如Mike Lesk和Eric Schmidt的lex)。但是我們將會使用一個非常簡單的工具：Python的str.split。我們只是在 (源程序中) 括號的兩邊添加空格，然后調(diào)用str.split來獲得一個詞法單元的列表。

接下來是語法分析。我們已經(jīng)看到，Lisp的語法很簡單。但是，一些Lisp解釋器允許接受表示列表的任何字符串作為一個程序，從而使得語法分析的工作更加簡單。換句話說，字符串(set! 1 2)可以被接受為是一個語法上有效的程序，只有當(dāng)執(zhí)行的時候解釋器才會抱怨set!的第一個參數(shù)應(yīng)該是一個符號，而不是數(shù)字。在Java或者Python中，與之等價的語句1 = 2將會在編譯時被認(rèn)定是錯誤。另一方面，Java和Python并不需要在編譯時檢測出表達(dá)式x/0是一個錯誤，因此，如你所見，一個錯誤應(yīng)該何時被識別并沒有嚴(yán)格的規(guī)定。Lispy使用read函數(shù)來實現(xiàn)parse函數(shù)，前者用以讀取任何的表達(dá)式 (數(shù)字、符號或者嵌套列表)。

tokenize函數(shù)獲取一系列詞法單元，read通過在這些詞法單元上調(diào)用read_from函數(shù)來進(jìn)行工作。給定一個詞法單元的列表，我們首先查看第一個詞法單元；如果它是一個')'，那么這是一個語法錯誤。如果它是一個'(‘，那么我們開始構(gòu)建一個表達(dá)式列表，直到我們讀取一個匹配的')'。所有其它的 (詞法單元) 必須是符號或者數(shù)字，它們自身構(gòu)成了一個完整的列表。剩下的需要注意的就是要了解'2‘代表一個整數(shù)，2.0代表一個浮點數(shù)，而x代表一個符號。我們將區(qū)分這些情況的工作交給Python去完成：對于每一個不是括號也不是引用 (quote) 的詞法單元，我們首先嘗試將它解釋為一個int，然后嘗試float，最后嘗試將它解釋為一個符號。根據(jù)這些規(guī)則，我們得到了如下程序：

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)

最后，我們將要添加一個函數(shù)to_string，用來將一個表達(dá)式重新轉(zhuǎn)換成Lisp可讀的字符串；以及一個函數(shù)repl，該函數(shù)表示read-eval-print-loop (讀取-求值-打印循環(huán))，用以構(gòu)成一個交互式的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)

下面是函數(shù)工作的一個例子：
 

>>> 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))) 0)))
lis.py> (count 0 (list 0 1 2 3 0 0))
3
lis.py> (count (quote the) (quote (the more the merrier the bigger the better)))
4

Lispy有多小、多快、多完備、多優(yōu)秀？

我們使用如下幾個標(biāo)準(zhǔn)來評價Lispy：

*小巧：Lispy非常小巧：不包括注釋和空白行，其源代碼只有90行，并且體積小于4K。(比第一個版本的體積要小，第一個版本有96行——根據(jù)Eric Cooper的建議，我刪除了Procedure的類定義，轉(zhuǎn)而使用Python的lambda。) 我用Java編寫的Scheme解釋器Jscheme最小的版本，其源代碼也有1664行、57K。Jscheme最初被稱為SILK (Scheme in Fifty Kilobytes——50KB的Scheme解釋器)，但是只有計算字節(jié)碼而不是源代碼的時候，我才能保證 (其體積) 小于該最小值。Lispy做的要好得多；我認(rèn)為它滿足了Alan Kay在1972年的斷言：他聲稱我們可以使用“一頁代碼”來定義“世界上最強大的語言”。
 

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

*高效：Lispy計算(fact 100)只需要0.004秒。對我來說，這已經(jīng)足夠快了 (雖然相比起其它的計算方式來說要慢很多)。

*完備：相比起Scheme標(biāo)準(zhǔn)來說，Lispy不是非常完備。主要的缺陷有：
(1) 語法：缺少注釋、引用 (quote) / 反引用 (quasiquote) 標(biāo)記 (即'和`——譯者注)、#字面值 (例如#\a——譯者注)、衍生表達(dá)式類型 (例如從if衍生而來的cond，或者從lambda衍生而來的let)，以及點列表 (dotted list)。
(2) 語義：缺少call/cc以及尾遞歸。
(3) 數(shù)據(jù)類型：缺少字符串、字符、布爾值、端口 (ports)、向量、精確/非精確數(shù)字。事實上，相比起Scheme的pairs和列表，Python的列表更加類似于Scheme的向量。
(4) 過程：缺少100多個基本過程：與缺失數(shù)據(jù)類型相關(guān)的所有過程，以及一些其它的過程 (如set-car!和set-cdr!，因為使用Python的列表，我們無法完整實現(xiàn)set-cdr!)。
(5) 錯誤恢復(fù)：Lispy沒有嘗試檢測錯誤、合理地報告錯誤以及從錯誤中恢復(fù)。Lispy希望程序員是完美的。

*優(yōu)秀：這一點需要讀者自己確定。我覺得，相對于我解釋Lisp解釋器這一目標(biāo)而言，它已經(jīng)足夠優(yōu)秀。

真實的故事

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

在這個問題上，Tony和我持有不同的觀點。他認(rèn)為 (實現(xiàn)) 表達(dá)式的解釋器是困難的部分；他需要Lisp為他解決這一問題，但是他知道如何編寫一個短小的C過程來處理非Lisp字符，并知道如何將其鏈接進(jìn)Lisp程序。我不知道如何進(jìn)行這種鏈接，但是我認(rèn)為為這種簡單的語言編寫一個解釋器 (其所具有的只是設(shè)置變量、獲取變量值和字符串連接) 很容易，于是我使用C語言編寫了一個解釋器。因此，戲劇性的是，Tony編寫了一個Lisp程序，因為他是一個C程序員；我編寫了一個C程序，因為我是一個Lisp程序員。

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

整個解釋器

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

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

最新評論