（如何用Python编写一个（Lisp）解释器）（2010）

# (如何用Python编写一个(Lisp)解释器) 来源：https://norvig.com/lispy.html 本页面有两个目的：一方面描述如何实现计算机语言解释器的一般方法，另一方面具体使用Python 3 (http://python.org/)作为实现语言，为Lisp的*Scheme* (http://en.wikipedia.org/wiki/Scheme_(programming_language))方言的大部分特性构建一个解释器。我将我的语言和解释器称为*Lispy* (**lis.py** (https://norvig.com/lis.py))。 多年前，我曾展示过如何用Java (https://norvig.com/jscheme.html)和Common Lisp (http://books.google.com/books?id=QzGuHnDhvZIC&lpg=PA756&vq=scheme%20interpreter&dq=Paradigms%20of%20Artificial%20Intelligence%20Programming&pg=PA753#v=onepage&q&f=false))编写一个半实用的Scheme解释器。而这次的目标是尽可能简洁和简单地展示Alan Kay (http://queue.acm.org/detail.cfm?id=1039523)所称的“*软件的麦克斯韦方程组* (http://www.righto.com/2008/07/maxwells-equations-of-software-examined.html)”。 为什么这很重要？正如Steve Yegge (http://steve-yegge.blogspot.com/2007/06/rich-programmer-food.html)所说：“*如果你不了解编译器如何工作，那么你就不了解计算机如何工作。*”Yegge描述了8个可以用编译器（或者同样可以用解释器，以及Yegge典型的浓厚讽刺风格）解决的问题。 ## Scheme程序的语法与语义 语言的*语法*是字符排列以形成正确语句或表达式的规则；*语义*是这些语句或表达式的含义。例如，在数学表达式语言（以及许多编程语言）中，计算一加二的语法是“1 + 2”，其语义是将加法操作应用于两个数字，得到值3。当我们确定一个表达式的值时，我们说在*求值*该表达式；我们会说“1 + 2”求值为3，并写成“1 + 2” ⇒ 3。 Scheme语法与大多数其他编程语言不同。考虑： > Java|Scheme > ---|--- > **if**(x.val() > 0) { **return** fn(A[i] + 3 * i, **new** String[] {"one", "two"}); } | (**if**(> (val x) 0) (fn (+ (aref A i) (* 3 i)) (**quote**(one two))) Java有各种各样的语法约定（关键字、中缀操作符、三种括号、运算符优先级、点符号、引号、逗号、分号），而Scheme语法则简单得多： - Scheme程序仅由*表达式*组成。没有语句/表达式的区分。 - 数字（如1）和符号（如A）称为*原子表达式*；它们不能被分解。这与Java中对应的概念类似，不同之处在于Scheme中诸如`+`和`>`这样的操作符也是符号，并且与`A`和`fn`一样对待。 - 其他一切都是*列表表达式*：一个“`(`”，后跟零个或多个表达式，再跟一个“`)`”。列表的第一个元素决定了其含义： - 以关键字开头的列表，例如`(if ...)`，是*特殊形式*；其含义取决于关键字。 - 以非关键字开头的列表，例如`(fn ...)`，是函数调用。 Scheme之美在于，完整语言只需要5个关键字和8种语法形式。相比之下，Python有33个关键字和110 (https://docs.python.org/3/reference/grammar.html)种语法形式，Java有50个关键字和133 (https://docs.oracle.com/javase/specs/jls/se7/html/jls-18.html)种语法形式。所有这些括号可能看起来令人生畏，但Scheme语法具有简单和一致的优点。（有些人开玩笑说“Lisp”代表“***L**ots of**I**rritating**S**illy**P**arentheses* (http://www.google.com/search?q=Lots+of+Irritating+Silly+Parentheses)”；而我认为它代表“***L**isp**I**s**S**yntactically**P**ure* (http://www.google.com/search?hl=en&as_q=&as_epq=Lisp+Is+Syntactically+Pure)”。） 在本页面中，我们将涵盖Scheme语言及其解释的所有重要点（省略一些细节），但我们将分两步实现：首先定义一个简化版语言，然后定义接近完整的Scheme语言。 ## 语言1：Lispy计算器 *Lispy计算器*是Scheme的一个子集，仅使用五种语法形式（两种原子形式、两种特殊形式和过程调用）。Lispy计算器允许您进行任何典型计算器能做的计算——只要您习惯前缀表示法。而且您还可以做两件典型计算器语言不提供的事情："if"表达式和定义新变量。 以下是一个示例程序，使用公式π*r²计算半径为10的圆的面积： ``(define r 10) (* pi (* r r))`` 以下是所有允许表达式的表格： | 表达式 | 语法 | 语义与示例 | |-------|------|----------| | 变量引用 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.1) | *symbol* | 符号被解释为变量名；其值为该变量的值。示例：`r` ⇒ 10（假设`r`先前被定义为10） | | 常量字面量 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.2) | *number* | 数字求值为自身。示例：`12` ⇒ 12 *或* `-3.45e+6` ⇒ -3.45e+6 | | 条件表达式 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.5) | `(if *test conseq alt*)` | 求值*test*；如果为真，则求值并返回*conseq*；否则返回*alt*。示例：`(if (> 10 20) (+ 1 1) (+ 3 3))` ⇒ 6 | | 定义 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-8.html#%_sec_5.2) | `(define *symbol* *exp*)` | 定义一个新变量，并赋予它求值表达式*exp*得到的值。示例：`(define r 10)` | | 过程调用 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.3) | `(*proc* *arg...*)` | 如果*proc*不是`if`、`define`或`quote`之一，则视为过程。求值*proc*和所有*args*，然后将过程应用于*arg*值列表。示例：`(sqrt (* 2 8))` ⇒ 4.0 | 在该表格的语法列中，*symbol*必须是一个符号，*number*必须是一个整数或浮点数，其他斜体字可以是任何表达式。符号*arg...*表示零个或多个*arg*的重复。 ## 语言解释器做什么 语言解释器有两个部分： 1. **解析：**解析组件接受输入程序（字符序列），根据语言的*语法规则*进行验证，并将程序转换为内部表示。在简单的解释器中，内部表示是一个树结构（通常称为*抽象语法树*），它紧密地反映了程序中语句或表达式的嵌套结构。在称为*编译器*的语言翻译器中，通常有一系列内部表示，从抽象语法树开始，逐渐转化为可以直接由计算机执行的指令序列。Lispy的解析器通过函数`parse`实现。 2. **执行：**然后根据语言的*语义规则*处理内部表示，从而执行计算。Lispy的执行函数称为`eval`（注意这会遮蔽Python内置的同名函数）。 以下是解释过程的图示： > 程序 ➡ 解析 ➡ 抽象语法树 ➡ 求值 ➡ 结果 以下是一个简短的示例，展示我们希望`parse`和`eval`能够做到的事情（`begin`依次求值每个表达式并返回最后一个）： ``>> program = "(begin (define r 10) (* pi (* r r)))" >>> parse(program) ['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]] >>> eval(parse(program)) 314.1592653589793`` ## 类型定义 让我们明确对Scheme对象的表示： ``Symbol = str # Scheme符号实现为Python的str Number = (int, float) # Scheme数字实现为Python的int或float Atom = (Symbol, Number) # Scheme原子是Symbol或Number List = list # Scheme列表实现为Python的list Exp = (Atom, List) # Scheme表达式是Atom或List Env = dict # Scheme环境（定义如下） # 是{variable: value}的映射`` ## 解析：`parse`、`tokenize`和`read_from_tokens` 解析传统上分为两部分：*词法分析*，将输入字符字符串分解为一系列*记号*；以及*语法分析*，将记号组装成抽象语法树。Lispy的记号包括括号、符号和数字。有许多词法分析工具（例如Mike Lesk和Eric Schmidt的lex (http://dinosaur.compilertools.net/#lex)），但目前我们将使用一个非常简单的工具：Python的`str.split`。函数`tokenize`接受一个字符字符串作为输入；它在每个括号周围添加空格，然后调用`str.split`获取记号列表： ``def tokenize(chars: str) -> list: "Convert a string of characters into a list of tokens." return chars.replace('(', ' ( ').replace(')', ' ) ').split()`` 这里我们将`tokenize`应用于我们的示例程序： ``>>> program = "(begin (define r 10) (* pi (* r r)))" >>> tokenize(program) ['(', 'begin', '(', 'define', 'r', '10', ')', '(', '*', 'pi', '(', '*', 'r', 'r', ')', ')', ')']`` 我们的函数`parse`将接收程序字符串作为输入，调用`tokenize`获取记号列表，然后调用`read_from_tokens`组装抽象语法树。`read_from_tokens`查看第一个记号；如果是`')'`，则是语法错误。如果是`'('`，则开始构建子表达式列表，直到遇到匹配的`')'`。任何非括号记号必须是符号或数字。我们将让Python来区分它们：对于每个非括号记号，首先尝试将其解释为int，然后为float，如果都不是，则必须是符号。以下是解析器： ``def parse(program: str) -> Exp: "Read a Scheme expression from a string." return read_from_tokens(tokenize(program)) def read_from_tokens(tokens: list) -> Exp: "Read an expression from a sequence of tokens." if len(tokens) == 0: raise SyntaxError('unexpected EOF') token = tokens.pop(0) if token == '(': L = [] while tokens[0] != ')': L.append(read_from_tokens(tokens)) tokens.pop(0) # pop off ')' return L elif token == ')': raise SyntaxError('unexpected )') else: return atom(token) def atom(token: str) -> Atom: "Numbers become numbers; every other token is a symbol." try: return int(token) except ValueError: try: return float(token) except ValueError: return Symbol(token)`` `parse`工作如下： ``>>> program = "(begin (define r 10) (* pi (* r r)))" >>> parse(program) ['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]`` 我们几乎准备好定义`eval`了。但还需要一个概念。 ## 环境 环境是变量名到其值的映射。默认情况下，`eval`会使用一个全局环境，其中包含一系列标准函数（如`sqrt`和`max`，以及`*`等运算符）的名称。这个环境可以通过用户定义的变量来扩充，使用表达式`(define *symbol* *value*)`。 ``import math import operator as op def standard_env() -> Env: "An environment with some Scheme standard procedures." env = Env() env.update(vars(math)) # sin, cos, sqrt, pi, ... env.update({ '+':op.add, '-':op.sub, '*':op.mul, '/':op.truediv, '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, 'abs': abs, 'append': op.add, 'apply': lambda proc, args: proc(*args), 'begin': lambda *x: x[-1], 'car': lambda x: x[0], 'cdr': lambda x: x[1:], 'cons': lambda x,y: [x] + y, 'eq?': op.is_, 'expt': pow, 'equal?': op.eq, 'length': len, 'list': lambda *x: List(x), 'list?': lambda x: isinstance(x, List), 'map': map, 'max': max, 'min': min, 'not': op.not_, 'null?': lambda x: x == [], 'number?': lambda x: isinstance(x, Number), 'print': print, 'procedure?': callable, 'round': round, 'symbol?': lambda x: isinstance(x, Symbol), }) return env global_env = standard_env()`` ## 求值：`eval` 我们现在准备实现`eval`。作为复习，我们重复一下Lispy计算器形式的表格： | 表达式 | 语法 | 语义与示例 | |-------|------|----------| | 变量引用 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.1) | *symbol* | 符号被解释为变量名；其值为该变量的值。示例：`r` ⇒ 10（假设`r`先前被定义为10） | | 常量字面量 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.2) | *number* | 数字求值为自身。示例：`12` ⇒ 12 *或* `-3.45e+6` ⇒ -3.45e+6 | | 条件表达式 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.5) | `(if *test conseq alt*)` | 求值*test*；如果为真，则求值并返回*conseq*；否则返回*alt*。示例：`(if (> 10 20) (+ 1 1) (+ 3 3))` ⇒ 6 | | 定义 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-8.html#%_sec_5.2) | `(define *symbol* *exp*)` | 定义一个新变量，并赋予它求值表达式*exp*得到的值。示例：`(define r 10)` | | 过程调用 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.3) | `(*proc* *arg...*)` | 如果*proc*不是`if`、`define`或`quote`之一，则视为过程。求值*proc*和所有*args*，然后将过程应用于*arg*值列表。示例：`(sqrt (* 2 8))` ⇒ 4.0 | 以下是`eval`的代码，它严格遵循上面的表格： ``def eval(x: Exp, env=global_env) -> Exp: "Evaluate an expression in an environment." if isinstance(x, Symbol): # variable reference return env[x] elif isinstance(x, Number): # constant number return x elif x[0] == 'if': # conditional (_, test, conseq, alt) = x exp = (conseq if eval(test, env) else alt) return eval(exp, env) elif x[0] == 'define': # definition (_, symbol, exp) = x env[symbol] = eval(exp, env) else: # procedure call proc = eval(x[0], env) args = [eval(arg, env) for arg in x[1:]] return proc(*args)`` *我们完成了！* 您可以看看它的实际效果： ``>>> eval(parse("(begin (define r 10) (* pi (* r r)))")) 314.1592653589793`` ## 交互：REPL 每次都输入`eval(parse("..."))`很繁琐。Lisp的一大遗产是交互式读取-求值-打印循环的概念：程序员可以输入一个表达式，立即看到它被读取、求值和打印，而无需经过冗长的构建/编译/运行周期。所以让我们定义函数`repl`（代表读取-求值-打印循环），以及函数`schemestr`，它返回表示Scheme对象的字符串。 ``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(schemestr(val)) def schemestr(exp): "Convert a Python object back into a Scheme-readable string." if isinstance(exp, List): return '(' + ' '.join(map(schemestr, exp)) + ')' else: return str(exp)`` 以下是`repl`的运作： ``>>> repl() lis.py> (define r 10) lis.py> (* pi (* r r)) 314.159265359 lis.py> (if (> (* 11 11) 120) (* 7 6) oops) 42 lis.py> (list (+ 1 1) (+ 2 2) (* 2 3) (expt 2 3)) lis.py>`` ## 语言2：完整Lispy 现在我们将用三种新的特殊形式扩展我们的语言，从而得到一个更接近完整的Scheme子集： | 表达式 | 语法 | 语义与示例 | |-------|------|----------| | 引用 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.2) | `(quote *exp*)` | 原样返回*exp*；不进行求值。示例：`(quote (+ 1 2))` ⇒ `(+ 1 2)` | | 赋值 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.6) | `(set! *symbol* *exp*)` | 求值*exp*并将该值赋给*symbol*，该符号必须先前已定义（通过`define`或作为外层过程的参数）。示例：`(set! r2 (* r r))` | | 过程 (http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.h