中文試譯：(How to Write a (Lisp) Interpreter (in Python))

作者：Peter Norvig
原文連結：http://norvig.com/lispy.html

這篇文章有兩個目的：描述直譯器通常是如何實作出來，以及展示如何用Python去完成Scheme的子集，Scheme是Lisp的一種方言。我將我的直譯器叫作Lispy(lis.py)。幾年前，我曾展現過如何用Java寫一個Scheme直譯器，類似的Scheme直譯器也曾經以Common Lisp實作過。這次的目的則是為了儘可能地證明Alan Kay曾宣示的"軟體的馬克斯威爾方程式"。

Scheme子集，Lispy的語法及語意
大部份的電腦語言有多樣化的句法規則(關鍵字、中序運算子、大括號、運算子順序、點的表示、分號...等等)。然而，身為Lisp家族的一員，Scheme所有的語法都是根基於括號的list的前置表示法。這或許會不太令人習慣，但這會有簡單與一致性的好處。(有人開玩笑地說，"Lisp"表示"一堆惹人生氣的智障括號(Lots of Irritating Silly Parentheses)"，我認為Lisp是表示"Lisp是純淨的句法(Lisp Is Syntactically Pure)")。考慮一下：

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

注意，驚嘆號並不是Scheme中的特殊字元，它只是"set!"這個名字的一部份。只有小括號才是特別的。一個像(set! x y)這樣有著關鍵字在第一個位置的list，在Scheme中稱呼為special form，這個語言美麗之處就在於只需要6個special form，加上3個可建立句法的組件-variables, constant,以及procedure call。

型式	語法	語意和範例
variable reference	var	一個符號會被解釋為一個變數名稱，其值就是該變數的值。 範例：x
constant literal	number	一個數值會被估算為本身的值 範例：12 或 -3.45e+6
quotation	(quote exp)	將一個exp以字面型式直接回傳，不進行估算。 範例： (quote (a b c)) ⇒ (a b c)
conditional	(if test conseq alt)	估算 test，如果為真，則估算並返回conseq的值，否則就估算並返回 alt的值。 範例：(if (< 10 20) (+ 1 1) (+ 3 3)) ⇒ 2
assignment	(set! var exp)	估算 exp 並將其值給予 var，在此之前，var必須先有定義才行(使用define或被當作一個procedure的參數)。 範例：(set! x2 (* x x))
definition	(define var exp)	在最近的環境中定義一個新的變數，並將exp的估算值設定到該變數上。 範例： (define r 3) or (define square (lambda (x) (* x x)))
procedure	(lambda (var...) exp)	產生一個帶有多個參數var...的程序，其程序主體為exp。 範例： (lambda (r) (* 3.141592653 (* r r)))
sequencing	(begin exp...)	從左至右估算每一個表示式，然後回傳最後的估算值。 範例： (begin (set! x 1) (set! x (+ x 1)) (* x 2)) ⇒ 4
procedure call	(proc exp...)	如果proc不是 if, set!, define, lambda, begin, 或 quote，那就會被當作一個程序。它會以此處所定義的規則來估算。所有的表示式也是用同樣的準則來求值，然後程序會被餵入一串表示式作為參數。 範例： (square 12) ⇒ 144

在此表中，var必須是一個符號--一個像是 x 或 square 的識別符號，而 number 必須是一個整數或浮點數，其他的斜體字則可以是任意的表示法。exp...表示0或多個exp的重複。
如果想深入學習Scheme，可參考一些很棒的書籍(Friedman and Fellesein, Dybvig, Queinnec,Harvey and Wright 或Sussman and Abelson), 影片 (by Abelson and Sussman), 教學 (by Dorai, PLT, orNeller), 或reference manual。

一個語言直譯器作了什麼？

一個語言直譯器有兩件事要處理：

1. 剖析：parsing元件會被輸入一個以一連串字元所組成的程式，然後藉由句法規則(syntactic rules)來檢視程式，並將程式轉換為一種內部的表達方式。在簡單的直譯器裡，內部表達方式會是一種樹，看起來會很接近程式裡的巢狀結構與表示式的樣子。叫作編譯器的語言轉換器則會將此內部表達方式化為一連串的指令，可以直接被電腦所執行。如同Steve Tegge所說："如果你不知道編譯器如何工作，那麼你就不知道電腦如何工作。"，Yegge描述了八種可以透過編譯器解決問題的情況(直譯器也是一樣，或Yegge's typical heavy dosage of cynicism)。Lispy parser實作在函式 parse 中。

2. 執行：內部表達可以根據語言的語意規則(semantic rules)來處理，然後給出最後計算結果。執行的部份是在函式 eval 中實作(注意，此名稱遮蓋了Python的內建函式)。

這邊有一張直譯過程的示意圖，以及一個把玩 parse, eval 範例：

 

執行：eval

這邊是eval的定義。上表中的9個規則在此處都有幾行實作，eval的定義就只需處理這9個規則：

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

這就是所有要估算的了！...嗯，除了environments以外。environments僅僅是符號與其值的對應而已。一個新的符號/值的關聯會藉由define或一個程序(lambda 表示式)被加入environment中。我們來看看一個例子，當定義了一個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'的分支，將list x指定給3個變數(_, vars, exp)(並且在x的長度不為3的時候發出錯誤)。我們接著造出一個新的程序，該程序若被呼叫時，會在與程序參數關聯的environment中估算['*', 3.141592653, ['*', 'r', 'r']](此例中只有 r 一個參數)，而任何不在參數列裡的變數會在當前的environment中查找(變數 * 就是一個例子)。新建的程序接著就會被當作area的值被放進 global_env中。

當我們估算(area 3)時會發生什麼事呢？既然 area 不是任何的 special form的符號，它必定為程序呼叫(eval中最後的 else:)，然後整串表示式會一個一個被估算。估算 area 會喚起我們剛建立的程序;估算 3 則獲得 3。我們接著(根據eval的最後一行)呼叫剛新建立的程序並給予 list[3] 作為參數。這就是說，要在r為3的environment中估算表示式 ['*', 3.141592653, ['*', 'r', 'r']]，並且外層的environment為global environment，因此 * 就是乘法的程序。

現在我們已經準備好可以解釋 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 的子類別，也就表示了原本對於字典的操作一樣可以正常運作。除此以外，還多了兩個 methods，constructor __init__以及可在正確 environment 找出變數的 find method。理解這個類別的關鍵(以及我們需要一個類別，而不是直接使用 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)

每一個矩型盒子表示一個 environment ，盒子的顏色與定義於該 environment 的變數的顏色會相符。在最後兩行，我們定義了 a1，然後呼叫了 (a1 -20.00)，這表示建立了一個100元的銀行帳戶，然後接著提領出20元。在估算(a1 -20.00)的過程中，我們會估算標示為黃色的那段表示式。該表示式中有3個變數。amt可以立即在最內層的 environment找到(綠色)，但balance並不存在該層：我們必須到綠色的更外一層 env 去查找，也就是藍色的那層 env。最後，變數 + 也無法在那邊找到，所以我們必須到更外層去，於是到了global (紅色) environment。這種先查找最內層envrionment然後逐步往外層的過程稱為 lexical scoping。程序 find 會根據 lexical scoping 規則找到正確的 environment 。

剩下的事情就只有定義global environment了。它需有 + 以及其他 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())

剖析：read以及parse

該來談談 parse 程序了。傳統上，剖析會分為兩個步驟：lexical analysis，會將輸入字串分切為一串 tokens；syntactic analysis，則會將tokens組為內部表達式。Lispy 的 tokens 有 小括號、符號(像是set! 或 x)、數字(像是2)。它會像這樣運作：

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

有許多工具可以幫忙處理 lexical analysis(像是Mike Lesk與 Eric Schmidt的lex)，但我們將會採用的是一個非常簡單的工具：Python的str.split。我們只需在小括號旁邊多加一個空格，然後呼叫 str.split，就可以獲得一串的 tokens 了。

現在輪到syntactic analysis了。我們已經看到 Lisp 的語法非常的簡單，不過有一些 Lisp 直譯器會藉由接受任意的、一個由字串所組成的list作為程式來讓syntactic analysis更簡單。換句話說，像字串(set! 1 2)會被視為是 syntactically 合法的程式，只有當直譯器執行時，才會抱怨 set! 需要它的第一個參數是一個符號才行，而不能是數字。在Java或Python中，像 1=2這樣的述句會在編譯期視為錯誤。另一方面，Java與Python不需要在編譯期偵測像是x/0 這樣的錯誤述句，所以你可以明白了吧？我們不總是會去嚴格要求一個錯誤應該在何時被找出。Lispy實作了 parse 與 read，read 程序是我們將會拿來讀取所有的表示式(數字、符號、巢狀list)。

read 運作時會呼叫 read_from，而read_from的輸入會從tokenize而來。給定一串tokens，我們一開始會先看第一個token；如果它是一個')'，那就是一個語法錯誤。如果是一個'('，那我們就開始建立一個表示式的list直到我們遇到了')'。所有的東西都必須是符號或數字才會完成一個完整的表示式。剩下要處理的就是要知道'2'是一個整數、2.0是一個浮點數、而x是一個符號。我們會讓Python做出這個區別：對每個不是小括號的token，先把它當作整數，然後是浮點數，最後則認為是符號。根據這些準則，我們獲得下列程式：

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.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有多小/快/完整/好？

我們依據下列幾點來審視Lispy：

• 小：Lispy非常地小：去除註解與空行，只有90行。源代碼少於4K(我接受了Eric Cooper的建議，將class定義去除，改用lambda，使得從原本第1版的96行減為90行)。我用Java實作的Scheme，Jscheme，最小的版本也要1664行，57K的大小。Jscheme原本叫作SILK(Scheme in Fifty Kilobytes)，但我是透過計算bytecode而不是代碼大小來維持這個底線。Lispy作的好多了，我認為它有達到Alan Kay在1972的宣示：你可以用一張紙的代碼定義出這個世界上最具威力的語言。(不過我認為Alan會不同意，因為他會將Pyhon compiler也計算進去，那就超過一張紙啦)

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

• 快：Lispy可在0.004秒內算出(fibo 100)。這對我來說夠快了。(當然啦，比其他絕大多數的計算方式要慢的多了)
• 完整：相較於Scheme標準，Lispy並不完整。有幾個主要缺失：
• • 語法：沒有註解，quote/quasiquote 標示符、# 字面、衍生表示式形別(像衍生自 if 的 cond，或衍生自lambda的 let)，以及list。
  • 語意: 沒有call/cc以及tail recursion。
  • 資料型別: 沒有字串、字元、布林、ports、vectors、exact/inexact number。相較於我們實作的Scheme pair與list，Python的list相當接近Scheme的vector。
  • 程序: 沒有至少100個原生的程序：所有沒實作的資料型別以及一些有的沒的(像是set-car!和set-cdr!，因為我們無法透過Python的list去完整實作set-cdr!)
  • 錯誤回復: Lispy不會去偵測並合理地回報或回復錯誤。Lispy期待程式設計師是完美的。
• 好：這要由讀者來決定啦。我覺得它好的足以讓我講解Lisp 直譯器的運作了。

真實的故事

為何知道直譯器是如何運作這件事是有很大幫助的呢？這邊有個小故事。回到1984年，我正在寫博士論文。那是在Latex以及Microsoft Word之前 - 我們用的是troff。不幸的是，troff沒有什麼工具可以向前參考一些符號標籤：我想要能夠寫出"As we will see on page @theoremx"，然後在適當的地方寫下像是"@(set theoremx \n%)"的東西。(troff的暫存器\n%會記住頁數)。我的研究所同學Tony DeRose有有同樣需求，所以我們一起草擬了一個簡單的Lisp程式，它會將處理這件事作為一個前置作業。然而，當時的Lisp程式可以很好地讀取Lisp表示式，但對於不是Lisp的表示式會很慢地一次只讀一個字元，所以我們的程式並不是很好用。

從那時起，Tony和我就採取不同作法。他認為困難的部份在於直譯器如何處理表示式；他需要知道如何寫一個小的C routine將不是Lisp的字元回傳出來，然後再將其連結回Lisp程式。我不知道如何作連結，不過我認為替這個簡單的語言寫一個直譯器是很容易的事(所有要做的事就是設定變數，讀取，然後作字串串接)，所以我就用C寫了個直譯器。所以，諷刺的是，Tony寫了個Lisp程式(還有一個小的C routine)，因為他是一個C 程式設計師，而我寫了個C程式，因為我是一個Lisp程式設計師。到頭來，我們都完成了我們的工作(Tony, Peter)。

全部的東西

為了回顧，這邊是Lispy的完整代碼(也可以從這邊下載：lis.py)

################ Lispy: Scheme Interpreter in Python
## (c) Peter Norvig, 2010; See http://norvig.com/lispy.html
################ Symbol, Env classes
from __future__ import division
Symbol = str
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)
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())

isa = isinstance
################ 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)
################ parse, read, and user interaction
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)
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)