如何使用Python编写一个Lisp解释器
原文: Peter Norvig
译者: johnc

本文有两个目的: 一是讲述实现计算机语言解释器的通用方法，另外一点，着重展示如何使用Python来实现Lisp方言Scheme 的一个子集。我将我的解释器称之为Lispy(lis.py)。几年前，我介绍过如何使用Java编写一个Scheme解释器，同时我还使用Common Lisp语言编写过一个版本。这一次，我的目的是尽可能简单明了地演示一下Alan Kay所说的“软件的麦克斯韦方程组” (Maxwell's Equations of Software)[1]。
Lispy支持的Scheme子集的语法和语义
大多数计算机语言都有许多语法规约 (例如关键字、中缀操作符、括号、操作符优先级、点标记、分号等等)，但是，作为Lisp语言家族中的一员，Scheme所有的语法都是基于包含在括号中的、采用前缀表示的列表的。这种表示看起来似乎有些陌生，但是它具有简单一致的优点。
(一些人戏称"Lisp"是" Lots of Irritating Silly Parentheses"——“大量恼人、愚蠢的括号“——的缩写；我认为它是" Lisp Is Syntactically Pure"——“Lisp语法纯粹”的缩写。考虑下面这个例子:
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!"这个名字的一部分。 (在Scheme中)只有括号是特殊字符。类似于(set! x y)这样以特殊关键字开头的列表在Scheme中被称为一个特殊形式 (special form)；Scheme的优美之处就在于我们只需要六种特殊形式，以及另外的三种语法构造——变量、常量和过程调用:
形式 (Form)
语法
语义和示例
常量引用
var
一个符号，被解释为一个变量名；其值就是这个变量的值。
示例: x
常量字面值
number
数字的求值结果为器本身。 
示例: 12 或者 -3.45e+6
引用
(quote exp)
返回exp的字面值; 不对它进行求值 
示例: (quote (a b c)) ⇒ (a b c)
条件测试
(if test conseq alt)
对test进行求值; 如果结果为真，那么对conseq进行求值并返回结果; 否则对alt进行求值并返回结果。 
示例: (if (< 10 20) (+ 1 1) (+ 3 3)) ⇒ 2
赋值
(set! varexp)
对exp进行求值并将结果赋值给 var, var必须已经进行过定义 (使用define或者作为一个封闭过程的参数)。 
示例: (set! x2 (* x x))
定义
(define var exp)
在最内层环境 (environment) 中定义一个新的变量并将对exp表达式求值所得的结果赋给该变量。 
示例: (define r 3) 或者 (define square (lambda (x) (* x x))).
过程
(lambda () exp)
创建一个过程，其参数名字为，过程体为相应的表达式。 
Example: (lambda (r) (* 3.141592653 (* r r)))
(表达式)序列
(begin )
按从左到右的顺序对表达式进行求值，并返回最终的结果。 
示例: (begin (set! x 1) (set! x (+ x 1)) (* x 2)) ⇒ 4
过程 调用
()
如果proc是除了 if, set!, define, lambda, begin,或者quote之外的其它符号的话，那么它会被视作一个过程。 它的求值规则如下：所有的表达式exp都将被求值，然后这些求值结果作为过程的实际参数来调用该相应的过程。 
示例: (square 12) ⇒ 144
在该表中，var必须是一个符号——一个类似于x或者square这样的标识符——number必须是一个整型或者浮点型数字，其余用斜体标识的单词可以是任何表达式。 表示exp的0次或者多次重复。
更多关于Scheme的内容，可以参考一些优秀的书籍 (如 Friedman 和Fellesein， Dybvig， Queinnec， Harvey和Wright或者 Sussman和Abelson)、视频 (Abelson和Sussman)、教程 (Dorai， PLT，或者 Neller)、或者 参考手册。
语言解释器的职责
一个语言解释器包括两部分：
1. 解析: 解析部分接受一个使用字符序列表示的输入程序，根据语言的语法规则 对输入程序进行验证，然后将程序翻译成一种中间表示。在一个简单的解释器中，中间表示是一种树结构，紧密地反映了源程序中语句或表达式的嵌套结构。在一种称为编译器的语言翻译器中，内部表示是一系列可以直接由计算机 (作者的原意是想说运行时系统——译者注) 执行的指令。正如Steve Yegge所说，“如果你不明白编译器的工作方式，那么你不会明白计算机的工
作方式。“ Yegge介绍了编译器可以解决的8种问题 (或者解释器，又或者采用Yegge的典型的反讽式的解决方案)。Lispy的解析器由parse函数实现。
2. 执行: 程序的内部表示 (由解释器) 根据语言的语义规则进行进一步处理，进而执行源程序的实际运算。(Lispy的)执行部分由eval函数实现 (注意，该函数覆盖了Python内建的同名函数)。
下面的图片描述了解释器的解释流程，(图片后的) 交互会话展示了parse和eval函数对一个小程序的操作方式：

>>program="(begin (define r 3) (* 3.141592653 (* r r)))"
 
>>> parse(program)
['begin',['define','r',3],['*',3.141592653,['*','r','r']]]
 
>>>eval(parse(program))
28.274333877
这里，我们采用了一种尽可能简单的内部表示，其中Scheme的列表、数字和符号分别使用Python的列表、数字和字符串来表示。
执行： eval
下面是eval函数的定义。对于上面表中列出的九种情况，每一种都有一至三行代码，eval函数的定义只需要这九种情况：

defeval(x,env=global_env):
    "Evaluate an expression in an environment."
    ifisa(x,Symbol):            # variable reference
        returnenv.find(x)[x]
    elifnotisa(x, list):        # constant literal
        return x               
    elif x[0]=='quote':          # (quote exp)
        (_,exp)= x
        returnexp
    elif x[0]=='if':            # (if test conseq alt)
        (_, test,conseq, alt)= x
        returneval((conseqifeval(test,env)else alt),env)
    elif x[0]=='set!':          # (set! varexp)
        (_,var,exp)= x
        env.find(var)[var]=eval(exp,env)
    elif x[0]=='define':        # (define varexp)
        (_,var,exp)= x
        env[var]=eval(exp,env)
    elif x[0]=='lambda':        # (lambda (var*) exp)
        (_,vars,exp)= x
        returnlambda*args:eval(exp,Env(vars,args,env))
    elif x[0]=='begin':          # (begin exp*)
        forexpin x[1:]:
            val=eval(exp,env)
        returnval
    else:                          # (procexp*)
        exps=[eval(exp,env)forexpin x]
        proc=exps.pop(0)
        returnproc(*exps)
 
isasyntaxerror是什么错误=isinstance
 
Symbol=str
eval函数的定义就是这么多...当然，除了environments。Environments (环境) 只是从符号到
符号所代表的值的映射而已。一个新的符号/值绑定由一个define语句或者一个过程定义 (lambda表达式) 添加。
让我们通过一个例子来观察定义然后调用一个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'分支，将 (_, vars, exp)三个变量分别赋值为列x的对应元素 (如果 x的长度不是3，就抛出一个错误)。然后，我们创建一个新的过程，当该过程被调用的时候，将会对表达式['*', 3.141592653 ['*', 'r', 'r']] 进行求值，求值过程的环境 (environment) 是通过将过程的形式参数 (该例中只有一个参数， r)绑定为过程调用时所提供的实际参数，外加当前环境中所有不在参数列表 (例如，变量*)的变量组成的。新创建的过程被赋值给global_env中的 area变量。
那么，当我们对(area 3)求值的时候发生了什么呢？因为 area并不是任何表示特殊形式的符号之一，它必定是一个过程调用 (eval函数的最后一个else:分支)，因此整个表达式列表都将会被求值，每次求值其中的一个。对area进行求值将会获得我们刚刚创建的过程；对3进行求值所得的结果就是3。然后我们 (根据eval函数的最后一行) 使用参数列表[3]来调用这个新创建的过程。也就是说，对exp(也就是 ['*', 3.141592653 ['*', 'r', 'r']])进行求值，并且求值所在的环境中r是3，并且外部环境是全局环境，因此* 是乘法过程。