如何使用Python编写一个Lisp解释器

1如何使用Python编写一个Lisp解释器原文:PeterNorvig译者:johnc本文有两个目的:一是讲述实现计算机语言解释器的通用方法，另外一点，着重展示如何使用Python来实现Lisp方言Scheme的一个子集。我将我的解释器称之为Lispy(lis.py)。几年前，我介绍过如何使用Java编写一个Scheme解释器，同时我还使用CommonLisp语言编写过一个版本。这一次，我的目的是尽可能简单明了地演示一下AlanKay所说的“软件的麦克斯韦方程组”(Maxwell'sEquationsofSoftware)[1]。Lispy支持的Scheme子集的语法和语义大多数计算机语言都有许多语法规约(例如关键字、中缀操作符、括号、操作符优先级、点标记、分号等等)，但是，作为Lisp语言家族中的一员，Scheme所有的语法都是基于包含在括号中的、采用前缀表示的列表的。这种表示看起来似乎有些陌生，但是它具有简单一致的优点。(一些人戏称Lisp是LotsofIrritatingSillyParentheses——“大量恼人、愚蠢的括号“——的缩写；我认为它是LispIsSyntacticallyPure——“Lisp语法纯粹”的缩写。考虑下面这个例子:JavaSchemeif(x.val()0){z=f(a*x.val()+b);}(if((valx)0)(set!z(f(+(*a(valx))b))))2注意上面的惊叹号在Scheme中并不是一个特殊字符；它只是set!这个名字的一部分。(在Scheme中)只有括号是特殊字符。类似于(set!xy)这样以特殊关键字开头的列表在Scheme中被称为一个特殊形式(specialform)；Scheme的优美之处就在于我们只需要六种特殊形式，以及另外的三种语法构造——变量、常量和过程调用:形式(Form)语法语义和示例常量引用var一个符号，被解释为一个变量名；其值就是这个变量的值。示例:x常量字面值number数字的求值结果为器本身。示例:12或者-3.45e+6引用(quoteexp)返回exp的字面值;不对它进行求值示例:(quote(abc))⇒(abc)条件测试(iftestconseqalt)对test进行求值;如果结果为真，那么对conseq进行求值并返回结果;否则对alt进行求值并返回结果。示例:(if(1020)(+11)(+33))⇒2赋值(set!varexp)对exp进行求值并将结果赋值给var,var必须已经进行过定义(使用define或者作为一个封闭过程的参数)。示例:(set!x2(*xx))定义(definevarexp)在最内层环境(environment)中定义一个新的变量并将对exp表达式求值所得的结果赋给该变量。示例:(definer3)或者(definesquare(lambda(x)(*xx))).过程(lambda(var...)exp)创建一个过程，其参数名字为var...，过程体为相应的表达式。Example:(lambda(r)(*3.141592653(*rr)))(表达式)序列(beginexp...)按从左到右的顺序对表达式进行求值，并返回最终的结果。示例:(begin(set!x1)(set!x(+x1))(*x2))⇒43过程调用(procexp...)如果proc是除了if,set!,define,lambda,begin,或者quote之外的其它符号的话，那么它会被视作一个过程。它的求值规则如下：所有的表达式exp都将被求值，然后这些求值结果作为过程的实际参数来调用该相应的过程。示例:(square12)⇒144在该表中，var必须是一个符号——一个类似于x或者square这样的标识符——number必须是一个整型或者浮点型数字，其余用斜体标识的单词可以是任何表达式。exp...表示exp的0次或者多次重复。更多关于Scheme的内容，可以参考一些优秀的书籍(如Friedman和Fellesein，Dybvig，Queinnec，Harvey和Wright或者Sussman和Abelson)、视频(Abelson和Sussman)、教程(Dorai，PLT，或者Neller)、或者参考手册。语言解释器的职责一个语言解释器包括两部分：1.解析:解析部分接受一个使用字符序列表示的输入程序，根据语言的语法规则对输入程序进行验证，然后将程序翻译成一种中间表示。在一个简单的解释器中，中间表示是一种树结构，紧密地反映了源程序中语句或表达式的嵌套结构。在一种称为编译器的语言翻译器中，内部表示是一系列可以直接由计算机(作者的原意是想说运行时系统——译者注)执行的指令。正如SteveYegge所说，“如果你不明白编译器的工作方式，那么你不会明白计算机的工作方式。“Yegge介绍了编译器可以解决的8种问题(或者解释4器，又或者采用Yegge的典型的反讽式的解决方案)。Lispy的解析器由parse函数实现。2.执行:程序的内部表示(由解释器)根据语言的语义规则进行进一步处理，进而执行源程序的实际运算。(Lispy的)执行部分由eval函数实现(注意，该函数覆盖了Python内建的同名函数)。下面的图片描述了解释器的解释流程，(图片后的)交互会话展示了parse和eval函数对一个小程序的操作方式：program=(begin(definer3)(*3.141592653(*rr)))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):Evaluateanexpressioninanenvironment.ifisa(x,Symbol):#variablereferencereturnenv.find(x)[x]elifnotisa(x,list):#constantliteral5returnxelifx[0]=='quote':#(quoteexp)(_,exp)=xreturnexpelifx[0]=='if':#(iftestconseqalt)(_,test,conseq,alt)=xreturneval((conseqifeval(test,env)elsealt),env)elifx[0]=='set!':#(set!varexp)(_,var,exp)=xenv.find(var)[var]=eval(exp,env)elifx[0]=='define':#(definevarexp)(_,var,exp)=xenv[var]=eval(exp,env)elifx[0]=='lambda':#(lambda(var*)exp)(_,vars,exp)=xreturnlambda*args:eval(exp,Env(vars,args,env))elifx[0]=='begin':#(beginexp*)forexpinx[1:]:val=eval(exp,env)returnvalelse:#(procexp*)exps=[eval(exp,env)forexpinx]proc=exps.pop(0)returnproc(*exps)isa=isinstanceSymbol=streval函数的定义就是这么多...当然，除了environments。Environments(环境)只是从符号到符号所代表的值的映射而已。一个新的符号/值绑定由一个define语句或者一个过程定义(lambda表达式)添加。让我们通过一个例子来观察定义然后调用一个Scheme过程的时候所发生的事情(lis.py提示符表示我们正在与Lisp解释器进行交互，而不是Python)：6lis.py(definearea(lambda(r)(*3.141592653(*rr))))lis.py(area3)28.274333877当我们对(lambda(r)(*3.141592653(*rr)))进行求值时,我们在eval函数中执行elifx[0]=='lambda'分支，将(_,vars,exp)三个变量分别赋值为列x的对应元素(如果x的长度不是3，就抛出一个错误)。然后，我们创建一个新的过程，当该过程被调用的时候，将会对表达式['*',3.141592653['*','r','r']]进行求值，求值过程的环境(environment)是通过将过程的形式参数(该例中只有一个参数，r)绑定为过程调用时所提供的实际参数，外加当前环境中所有不在参数列表(例如，变量*)的变量组成的。新创建的过程被赋值给global_env中的area变量。那么，当我们对(area3)求值的时候发生了什么呢？因为area并不是任何表示特殊形式的符号之一，它必定是一个过程调用(eval函数的最后一个else:分支)，因此整个表达式列表都将会被求值，每次求值其中的一个。对area进行求值将会获得我们刚刚创建的过程；对3进行求值所得的结果就是3。然后我们(根据eval函数的最后一行)使用参数列表[3]来调用这个新创建的过程。也就是说，对exp(也就是['*',3.141592653['*','r','r']])进行求值，并且求值所在的环境中r是3，并且外部环境是全局环境，因此*是乘法过程。现在，我们可以解释一下Env类的细节了：classEnv(dict):Anenvironment:adictof{'var':val}pairs,withanouterEnv.7def__init__(self,parms=(),args=(),outer=None):self.update(zip(parms,args))self.outer=outerdeffind(self,var):FindtheinnermostEnvwherevarappears.returnselfifvarinselfelseself.outer.find(var)注意Env是dict的一个子类，也就是说，通常的字典操作也适用于Env类。除此之外，该类还有两个方法，构造函数__init__和find函数，后者用来为一个变量查找正确的环境。理解这个类的关键(以及我们需要一个类，而不是仅仅使用dict)的根本原因)在于外部环境(outerenvironment)这个概念。考虑下面这个程序：(definemake-account(lambda(balance)(lambda(amt)(begin(set!balance(+balanceamt))balance))))(definea1(make-account100.00))(a1-20.00)每个矩形框都代表了一个环境，并且矩形框的颜色与环境中最新定义的变量的颜色相对应。在程序的最后两行我们定义了a1并且调用了(a1-20.00)；这表示创建一个开户金额为100美元的银行账户，然后是取款20美元。在对(a1-20.00)求值的过程中，我们将会对黄色高亮表达式进行求值，该表达式中具有三个变量。amt可以在最内层(绿色)环境中直接找到。但是balance在该环境中没有定义：我们需要查看绿色环境的外层环境，也就是蓝色环境。最后，+代表的变量在这两个环境中都没有定义；我们需要进一步查看外层环境，也就是全局(红色)环境。先查找内层环境，然后依次查找外部的环境，我们把这一过程称之为8词法定界(lexicalscoping)。Procedure.find负责根据词法定界规则查找正确的环