標籤：

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

01-31

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

> 譯自Peter Norvig的博客，有少量魔改

這篇文章有兩個目的：

  1. 通用地介紹如何實現計算機語言的解釋器。
  2. 介紹如何利用Python實現Lisp方言Scheme的一個子集。

Scheme程序的語法和語義

一門語言的語法（syntax）指的是字母排列成正確表達式或聲明的順序；語義（semantics）則是這些表達式或聲明的意義。例如在數學和許多編程語言之中，一加二的語法是「1 + 2」， 語義則是將加法運算符應用於數字1和2之上，得到結果3。我們將計算表達式的值稱之為求值（evaluating）；「1 + 2」求值得到結果3，我們將之記為「1 + 2」 => 3。

Scheme的語法與你熟悉的大部分語言不同。例如：

// Javanif (x.val() > 0) { n fn(A[i] + 1, n return new String[] {"one", "two"}); n}n

-

;; Schemen(if (> (val x) 0) n (fn (+ (aref A i) 1) n (quote (one two)))n

Java有大量不同的語法約規（關鍵字、中置操作符、三種括弧、操作符優先順序、點、引號、逗號、分號等等），而Scheme的語法則簡單很多：

  • Scheme程序中只有表達式。表達式和聲明之間並無區別。
  • 數字（例如 1）和符號（例如 A）被稱之為原子表達式（atomic expression）；他們無法被拆分成更小的表達式。這部分和Java類似，但在Scheme中，諸如 + 和 > 這種操作符也被認為是符號（symbol），處理方式與A或是fn這種符號別無二致。
  • 除此之外的一切都是列表表達式（list expression）：以「(」為首，「)」為尾，中間包括著零個或更多表達式。列表的第一個元素決定了它的含義：
    • 若第一個元素是關鍵字，例如(if ...)，那這個列表是一個特殊形式（special form）；特殊形式的意義取決於關鍵字。
    • 若第一個元素並非關鍵字，例如(fn ...)，那這個列表則是函數調用。

Scheme之美在於她的簡潔性：整個語言由5個關鍵字和8個語法形式構成。相較之下，Python有33個關鍵字和110個語法形式，Java有50個關鍵字和133個語法形式。Scheme中的大量括弧初看起來可能顯得古怪陌生，但括弧為Scheme提供了簡潔性和一致性。（有些人開玩笑說Lisp的意思是「大量又蠢又煩的括弧（Lots of Irritating Silly Parentheses）」；我覺得應該是「Lisp擁有純凈的語法（Lisp Is Syntactically Pure）。」）

在這篇文章中我們會涉及到Scheme中所有的關鍵點（除了一些瑣碎的細節）。但羅馬城不是一天建成的，我們需要分兩步。首先，我們會定義一個相對簡單的語言，再在它的基礎上定義一個幾近完整的Scheme語言。

1號語言：Lispy計算器

Lispy計算器是Scheme語言的一個子集，它只包含五種語法形式（兩種原子，兩個特殊形式，以及過程調用）。只要你習慣了Lisp前置運算符的古怪語法，你就能利用Lispy計算器干一般計算器的活。你還能幹一般計算器幹不了的活：使用"if"表達式進行條件判斷以及定義新的變數。我們來舉個例子，以下是一個計算圓面積的程序，圓的半徑為10，計算公式為πr^2：

(beginn (define r 10)n (* pi (* r r)))n

下面這張表列舉了所有可用的語法形式：

在表中「語法」一列中，var必須為一個符號，number必須為一個整數或浮點數，其他斜體字可以是任何表達式。其中的「arg...」表示零個或更多個"arg"。在「真正」的Scheme中，begin是一個語法關鍵字，但在這個Scheme實現中，它只是一個普通的函數。

語言解釋器做些什麼？

一個計算機語言的解釋器分為兩部分：

  1. 分析(parse)：解釋器的分析部分將程序以一串字元的形式讀入，依照語法規則(syntactic rules)驗證其正確性並將程序轉換成一種內部表達形式。在一個簡單的解釋器中，內部表達形式是一個樹形結構，人們一般將其稱之為抽象語法樹 (abstract syntax tree)。抽象語法樹的結構和程序中層層嵌套的聲明及表達式非常相近，幾乎可以說是完美對應。在編譯器之中往往存在多個內部表達形式，一開始先轉換成抽象語法樹，隨後再轉換成可以直接被計算器執行的指令序列。Lispy的語法分析器由parse函數實現。
  2. 執行(execution)：內部表達形式被按照語言的語法規則進行處理，以此來進行計算。Lispy的執行函數叫做eval （注意，這會覆蓋Python的同名內置函數）。

以下是對解釋器工作流程的一個簡單的演示：

程序 ---> [parse] ---> 抽象語法樹 ---> [eval] ---> 結果n

下面這個例子則展示了我們希望eval和parse實現的功能：

>> program = "(begin (define r 10) (* pi (* r r)))"nn>>> parse(program)n[begin, [define, r, 10], [*, pi, [*, r, r]]]nn>>> eval(parse(program))n314.1592653589793n

分析：parse, tokenize 以及 read_from_tokens

依照傳統，分析被分為兩個部分:

  1. 詞法分析(lexical analysis)：在這一部分中，輸入的字元串被拆分為一系列的token。
  2. 語法分析(syntactic analysis)：將token彙編為抽象語法樹。

Lispy token們由括弧，符號和數字組成。由許多用來進行詞法分析的工具（例如Mike Lesk和Eric Schmidt寫的lex），但我們只需要用到一個十分簡單的工具：Python的str.split函數。tokenize函數接受一個字元串，並在括弧周圍加上空格；隨後調用str.split來得到一個由token組成的列表：

def tokenize(chars):n "將字元串轉換成由token組成的列表。"n return chars.replace((, ( ).replace(), ) ).split()n>>> program = "(begin (define r 10) (* pi (* r r)))"n>>> tokenize(program)n[(, begin, (, define, r, 10, ), (, *, pi, (, *, r, r, ), ), )]n

我們的parse函數接收一個字元串作為輸入，然後調用tokenize函數獲得一個由token組成的列表，再調用read_from_tokens來將token列表彙編成抽象語法樹。read_from_token函數會查看第一個token，如果是「)」，那就報出一個語法錯誤。如果是「(」，那我們就開始構建一個由子表達式組成的列表，直到匹配到對應的「)」。所有非括弧的token必須是符號或者數字。我們會讓Python來識別它們之間的區別：對任何一個非括弧token，先嘗試將之轉為整數，若失敗則嘗試轉為浮點數，若還是失敗，則轉為符號。下邊是parser的代碼：

def parse(program):n "從字元串中讀取Scheme表達式"n return read_from_tokens(tokenize(program))nndef read_from_tokens(tokens):n "從一串token之中讀取表達式"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 "數字轉為對應的Python數字，其餘的轉為符號"n try: return int(token)n except ValueError:n try: return float(token)n except ValueError:n return Symbol(token)n

parse函數的工作方式如下：

>>> program = "(begin (define r 10) (* pi (* r r)))"nn>>> parse(program)n[begin, [define, r, 10], [*, pi, [*, r, r]]]n

我們還需要決定一下各種Scheme對象在Python中的表示方法：

Symbol = str # Scheme符號由Python str表示nList = list # Scheme列表由Python list表示nNumber = (int, float) # Scheme數字由Python的整數或浮點數表示n

好了！定義eval的準備工作基本都做好了。但我們需要先了解更多的概念。

環境(Environments)

eval函數接受兩個參數：一個我們想要求值的表達式x，還有一個環境env，x將在這個環境中被求值。環境指的是變數名和他們的值之間的映射。eval默認會使用全局環境(global environment)進行求值，全局環境包含著一系列的標準函數（比如sqrt, max和 * 這類操作符）。這一環境可以用用戶定義的變數拓展，語法為 (define variable value)。我們可以用Python自帶的字典來實現環境，字典中的鍵對為{變數: 值}的形式。

import mathnimport operator as opnnEnv = dict # 環境是{變數: 值}之間的映射nndef standard_env():n "一個包含著一些Scheme標準過程的環境。"n env = Env()n env.update(vars(math)) # sin, cos, sqrt, pi, ...n env.update({n +:op.add, -:op.sub, *:op.mul, /:op.div, 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 envnnglobal_env = standard_env()n

求值：eval

現在，我們已經做好了實現eval函數的準備。來讓我們重新看一遍Lispy計算器的語法形式表以加深一下記憶：

來和eval的代碼對比一下，是不是覺得很像？

def eval(x, env=global_env):n "對在某個環境下的表達式進行求值"n if isinstance(x, Symbol): # 變數引用n return env[x]n elif not isinstance(x, List): # 字面常量n return x n 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 else: # 過程調用n proc = eval(x[0], env)n args = [eval(arg, env) for arg in x[1:]]n return proc(*args)n

搞定！來試試吧：

>>> eval(parse("(define r 10)"))n>>> eval(parse("(* pi (* r r))"))n314.1592653589793n

交互：來做一個REPL

一直打「eval(parse(...))」的話即便是耐心再好的人也會嫌煩。Lisp最偉大的遺產之一就是引入了read-eval-print loop（讀取-求值-輸出 循環，縮寫為REPL，譯者注）。運用REPL，程序員們可以即時地讀取、求值、輸出，而不用麻煩地先編譯再運行。我們先定義一個名為repl的函數以實現這個功能，然後再定義一個schemestr函數來輸出Scheme對象的字元串表示。

def repl(prompt=lis.py> ):n "REPL的懶人實現。"n while True:n val = eval(parse(raw_input(prompt)))n if val is not None: n print(schemestr(val))nndef schemestr(exp):n "將一個Python對象轉換回可以被Scheme讀取的字元串。"n if isinstance(exp, List):n return ( + .join(map(schemestr, exp)) + ) n else:n return str(exp)n

老樣子，做完以後來試試：

>>> repl()nlis.py> (define r 10)nlis.py> (* pi (* r r))n314.159265359nlis.py> (if (> (* 11 11) 120) (* 7 6) oops)n42nlis.py> n

這一章中，我們實現了一個簡單的Lisp計算器，在下半部分中，我們將在此基礎上寫一個更完整的Scheme解釋器。

（破乎什麼時候才能支持Markdown，不能插表格也就算了，圖的質量還壓得那麼差。）


推薦閱讀：

TAG:Scheme | 计算机语言 | Python |