（如何（用Python）寫一個（Lisp）解釋器（下））

01-27

上篇：（如何（用Python）寫一個（Lisp）解釋器（上））

2號語言：完整的Lispy

現在我們來加上3個新的語法形式，構造一個更加完整的Scheme子集：

lambda特殊形式會創建一個過程(procedure)。（lambda這個名字來源於Alonzo Church的lambda calculus）

lis.py> (define circle-area (lambda (r) (* pi (* r r)))nlis.py> (circle-area 10)n314.159265359n

過程調用(circle-area 10)使我們對過程的主體部分(* pi (* r r))進行求值。求值所在的環境中pi與*的值同全局環境相同，而r的值為10。事實上，解釋器並不會簡單地在全局環境之中將r的值設為10。如果我們將r用於其他用途會怎麼樣？我們不希望對circle-area的調用改變r的值，因此我們希望將一個局部變數r設為10，這樣就不會影響到其他同名的變數。因此，我們需要構建一種新的環境，允許同時創建局部和全局變數。

想法如下：在我們對(circle-area 10)求值時，首先提取過程主體部分(* pi (* r r))，隨後在僅有一個本地變數r的環境中求值，但該環境同時也能訪問全局環境。下圖演示了這種環境模型，局部環境（藍色）嵌套在全局環境（紅色）之中：

當我們在一個被嵌套的環境中查找變數時，首先在本層查找，如果沒有找到對應值的話就到外一層查找。

顯然，過程和環境相關，所以我們把他們放到一起：

class Procedure(object):n "用戶定義的Scheme過程。"n def __init__(self, parms, body, env):n self.parms, self.body, self.env = parms, body, envn def __call__(self, *args): n return eval(self.body, Env(self.parms, args, self.env))nnclass Env(dict):n "環境是以{var:val}為鍵對的字典，它還帶著一個指向外層環境的引用。"n def __init__(self, parms=(), args=(), outer=None):n self.update(zip(parms, args))n self.outer = outern def find(self, var):n "尋找變數出現的最內層環境。"n return self if (var in self) else self.outer.find(var)nnglobal_env = standard_env()n

我們看到每個過程有3個組成部分：一個包含變數名的列表，一個主體表達式，以及一個外層環境。外層環境使得我們在局部環境中無法找到變數時有下一個地方可以尋找。

環境是dict的子類，因此它含有dict擁有的所有方法。除此之外還有兩個額外的方法：

構造器__init__接受一個變數名列表及對應的變數值列表，構造創造一個新環境，內部形式為{variable: value}鍵對，並擁有一個指向外層環境的引用。
find函數用於找到某個變數所在的正確環境，可能是內層環境也可能是更外層的環境。

要想知道這部分的工作原理，我們首先來看看eval的定義。注意，現在我們需要調用env.find(x)來尋找變數處於哪一層環境之中；隨後我們才能從那一層環境之中提取x。（define分支的定義沒有改變，因為define總是向最內一層的環境添加變數。）同時我們還增加了兩個判定分支：set!分支中，我們尋找變數所處的環境並將其設為新的值。通過lambda，我們可以傳入參數列表、主體以及環境以創建一個新的過程。

def eval(x, env=global_env):n "在某環境中對一個表達式進行求值。"n if isinstance(x, Symbol): # 變數引用n return env.find(x)[x]n elif not isinstance(x, List): # 直面產量n return x n elif x[0] == quote: # 引用n (_, exp) = xn return expn elif x[0] == if: # 條件判斷n (_, test, conseq, alt) = xn exp = (conseq if eval(test, env) else alt)n return eval(exp, env)n elif x[0] == define: # 定義n (_, var, exp) = xn env[var] = eval(exp, env)n elif x[0] == set!: # 賦值n (_, var, exp) = xn env.find(var)[var] = eval(exp, env)n elif x[0] == lambda: # 過程n (_, parms, body) = xn return Procedure(parms, body, env)n else: # 過程調用n proc = eval(x[0], env)n args = [eval(arg, env) for arg in x[1:]]n return proc(*args)n

為了更好地理解過程和環境是怎樣協同運作的，我們來看看下面這段程序。思考一下，在我們對(account1 -20.00)求值的時候，程序會生成一個怎樣的環境呢？

每個矩形框代表一個環境，環境的顏色和程序中新定義變數的顏色相對應。在程序的最後兩行中，我們定義了account1並調用了(account1 -20.00)，這表示我們創建了一個擁有100美金餘額的賬戶，並從中取出20美金。在對(account1 -20.00)進行求值的過程中，我們會對黃色高亮部分進行求值。該表達式中有三個變數：amt可以直接在最內層環境（綠色）中找到。但balance不在那一層環境之中，我們需要查找綠色的外一層環境（藍色）。然而變數『+』依然不能在這兩個環境之中找到，所以我們需要在更外一層環境中尋找（紅色的全局環境）。這一先在內層環境查找，再在外層環境中查找的方式被稱為「詞法作用域」(Lexical Scoping)。Env.find(var)依照詞法作用域規則查找變數所處的正確環境。

現在我們能做的事又多了不少：

>>> repl()nlis.py> (define circle-area (lambda (r) (* pi (* r r))))nlis.py> (circle-area 3)n28.274333877nlis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))nlis.py> (fact 10)n3628800nlis.py> (fact 100)n9332621544394415268169923885626670049071596826438162146859296389521759999322991n5608941463976156518286253697920827223758251185210916864000000000000000000000000nlis.py> (circle-area (fact 10))n4.1369087198e+13nlis.py> (define first car)nlis.py> (define rest cdr)nlis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))nlis.py> (count 0 (list 0 1 2 3 0 0))n3nlis.py> (count (quote the) (quote (the more the merrier the bigger the better)))n4nlis.py> (define twice (lambda (x) (* 2 x)))nlis.py> (twice 5)n10nlis.py> (define repeat (lambda (f) (lambda (x) (f (f x)))))nlis.py> ((repeat twice) 10)n40nlis.py> ((repeat (repeat twice)) 10)n160nlis.py> ((repeat (repeat (repeat twice))) 10)n2560nlis.py> ((repeat (repeat (repeat (repeat twice)))) 10)n655360nlis.py> (pow 2 16)n65536.0nlis.py> (define fib (lambda (n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2))))))nlis.py> (define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b)))))nlis.py> (range 0 10)n(0 1 2 3 4 5 6 7 8 9)nlis.py> (map fib (range 0 10))n(1 1 2 3 5 8 13 21 34 55)nlis.py> (map fib (range 0 20))n(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)n

如此一來，我們的語言中就有了過程、變數、條件判斷（if）和順序執行（begin）。如果你熟悉其他語言的話，你可能會覺得我們還需要while或者for循環，但Scheme認為自己不需要這兩種循環結構。Scheme標準中說：「Scheme展示了只需要極少量構造表達式的規則，無需規定表達式的組成方式，就足以構建出一個實用而高效的語言。」在Scheme中，我們通過構建遞歸函數的方式來實現迭代。

Lispy有多小/快/完整/好？

我們以以下的標準來評判Lispy：

小：Lispy十分簡短：不算空行和注釋的話一共只有117行，源碼只有4K大小。（更早的一個版本只有90行，但包含的標準過程更少，也顯得過於簡陋了。）我用Java實現的最小Scheme（Jscheme）包含1664行代碼，源碼有57K大。Jscheme之前叫SILK（Scheme in Fifty Kilobytes，縮寫對不上...anyway），不過實際上只有在編譯成bytecode的情況下才小於50k。在「小」這一方面，Lispy做得要好很多，我想它符合Alan Kay在1972年所說的：「你可以用『一頁代碼』定義出『世界上最強大的語言』」。（其實我覺得Alan Kay本人不會同意，因為Python解釋器的代碼量遠高於一頁。）
快：Lispy可以在0.003秒內計算出(fact 100)的值。對我來說夠快了（儘管比大部分語言慢很多）。
完整：Lispy和Scheme標準比起來算不上完整。一下是主要的一些缺少處：

語法：缺少注釋，quote符和quasiquote符，#常量，延伸的表達式（從if中延伸出的cond，從lambda中延伸出的let），和dotted list標記。
語義：缺少call/cc和尾遞歸。
數據類型：缺少String, character, boolean, ports, vectors, exact/inexact numbers。Python的列表相比於Scheme里的列表實際上更接近於Scheme里的vector。
過程：少了100多種原始過程：包含與所有缺少的數據類型有關的過程，以及set-car!和set-cdr!之類的過程，因為我們沒法用Python列表直接實現這一功能。
錯誤修復：Lispy不會嘗試去偵測，報告以及修復錯誤。想用Lispy編程的話你需要一個從不犯錯的程序員。

好：這項的評判就交由讀者去定了。對我來說，它不錯地完成了預定目標——解釋Lisp解釋器的工作原理。

附錄：完整代碼

################ Lispy: Scheme Interpreter in Pythonnn## (c) Peter Norvig, 2010-16; See http://norvig.com/lispy.htmlnnfrom __future__ import divisionnimport mathnimport operator as opnn################ TypesnnSymbol = str # A Lisp Symbol is implemented as a Python strnList = list # A Lisp List is implemented as a Python listnNumber = (int, float) # A Lisp Number is implemented as a Python int or floatnn################ Parsing: parse, tokenize, and read_from_tokensnndef parse(program):n "Read a Scheme expression from a string."n return read_from_tokens(tokenize(program))nndef tokenize(s):n "Convert a string into a list of tokens."n return s.replace((, ( ).replace(), ) ).split()nndef read_from_tokens(tokens):n "Read an expression from a sequence of tokens."n if len(tokens) == 0:n raise SyntaxError(unexpected EOF while reading)n token = tokens.pop(0)n if ( == token:n L = []n while tokens[0] != ):n L.append(read_from_tokens(tokens))n tokens.pop(0) # pop off )n return Ln elif ) == token:n raise SyntaxError(unexpected ))n else:n return atom(token)nndef atom(token):n "Numbers become numbers; every other token is a symbol."n try: return int(token)n except ValueError:n try: return float(token)n except ValueError:n return Symbol(token)nn################ Environmentsnndef standard_env():n "An environment with some Scheme standard procedures."n env = Env()n env.update(vars(math)) # sin, cos, sqrt, pi, ...n env.update({n +:op.add, -:op.sub, *:op.mul, /:op.truediv, n >:op.gt, <:op.lt, >=:op.ge, <=:op.le, =:op.eq, n abs: abs,n append: op.add, n apply: apply,n begin: lambda *x: x[-1],n car: lambda x: x[0],n cdr: lambda x: x[1:], n cons: lambda x,y: [x] + y,n eq?: op.is_, n equal?: op.eq, n length: len, n list: lambda *x: list(x), n list?: lambda x: isinstance(x,list), n map: map,n max: max,n min: min,n not: op.not_,n null?: lambda x: x == [], n number?: lambda x: isinstance(x, Number), n procedure?: callable,n round: round,n symbol?: lambda x: isinstance(x, Symbol),n })n return envnnclass Env(dict):n "An environment: a dict of {var:val} pairs, with an outer Env."n def __init__(self, parms=(), args=(), outer=None):n self.update(zip(parms, args))n self.outer = outern def find(self, var):n "Find the innermost Env where var appears."n return self if (var in self) else self.outer.find(var)nnglobal_env = standard_env()nn################ Interaction: A REPLnndef repl(prompt=lis.py> ):n "A prompt-read-eval-print loop."n while True:n val = eval(parse(raw_input(prompt)))n if val is not None: n print(lispstr(val))nndef lispstr(exp):n "Convert a Python object back into a Lisp-readable string."n if isinstance(exp, List):n return ( + .join(map(lispstr, exp)) + ) n else:n return str(exp)nn################ Proceduresnnclass Procedure(object):n "A user-defined Scheme procedure."n def __init__(self, parms, body, env):n self.parms, self.body, self.env = parms, body, envn def __call__(self, *args): n return eval(self.body, Env(self.parms, args, self.env))nn################ evalnndef eval(x, env=global_env):n "Evaluate an expression in an environment."n if isinstance(x, Symbol): # variable referencen return env.find(x)[x]n elif not isinstance(x, List): # constant literaln return x n elif x[0] == quote: # (quote exp)n (_, exp) = xn return expn elif x[0] == if: # (if test conseq alt)n (_, test, conseq, alt) = xn exp = (conseq if eval(test, env) else alt)n return eval(exp, env)n elif x[0] == define: # (define var exp)n (_, var, exp) = xn env[var] = eval(exp, env)n elif x[0] == set!: # (set! var exp)n (_, var, exp) = xn env.find(var)[var] = eval(exp, env)n elif x[0] == lambda: # (lambda (var...) body)n (_, parms, body) = xn return Procedure(parms, body, env)n else: # (proc arg...)n proc = eval(x[0], env)n args = [eval(exp, env) for exp in x[1:]]n return proc(*args)n