用Python编写一个简单的Lisp解释器的教程

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

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

lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))
lis.py> (area 3)
28.274333877

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)

(define make-account
 (lambda (balance)
 (lambda (amt)
  (begin (set! balance (+ balance amt)) balance))))
(define a1 (make-account 100.00))
(a1 -20.00)

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"htmlcode">

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



有许多工具可以进行词法分析 (例如Mike Lesk和Eric Schmidt的lex)。但是我们将会使用一个非常简单的工具：Python的str.split。我们只是在 (源程序中) 括号的两边添加空格，然后调用str.split来获得一个词法单元的列表。
接下来是语法分析。我们已经看到，Lisp的语法很简单。但是，一些Lisp解释器允许接受表示列表的任何字符串作为一个程序，从而使得语法分析的工作更加简单。换句话说，字符串(set! 1 2)可以被接受为是一个语法上有效的程序，只有当执行的时候解释器才会抱怨set!的第一个参数应该是一个符号，而不是数字。在Java或者Python中，与之等价的语句1 = 2将会在编译时被认定是错误。另一方面，Java和Python并不需要在编译时检测出表达式x/0是一个错误，因此，如你所见，一个错误应该何时被识别并没有严格的规定。Lispy使用read函数来实现parse函数，前者用以读取任何的表达式 (数字、符号或者嵌套列表)。
tokenize函数获取一系列词法单元，read通过在这些词法单元上调用read_from函数来进行工作。给定一个词法单元的列表，我们首先查看第一个词法单元；如果它是一个')'，那么这是一个语法错误。如果它是一个'(‘，那么我们开始构建一个表达式列表，直到我们读取一个匹配的')'。所有其它的 (词法单元) 必须是符号或者数字，它们自身构成了一个完整的列表。剩下的需要注意的就是要了解'2‘代表一个整数，2.0代表一个浮点数，而x代表一个符号。我们将区分这些情况的工作交给Python去完成：对于每一个不是括号也不是引用 (quote) 的词法单元，我们首先尝试将它解释为一个int，然后尝试float，最后尝试将它解释为一个符号。根据这些规则，我们得到了如下程序：


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"_blank" href="http://norvig.com/jscheme.html">Jscheme最初被称为SILK (Scheme in Fifty Kilobytes——50KB的Scheme解释器)，但是只有计算字节码而不是源代码的时候，我才能保证 (其体积) 小于该最小值。Lispy做的要好得多；我认为它满足了Alan Kay在1972年的断言：他声称我们可以使用“一页代码”来定义“世界上最强大的语言”。

 




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



*高效：Lispy计算(fact 100)只需要0.004秒。对我来说，这已经足够快了 (虽然相比起其它的计算方式来说要慢很多)。
*完备：相比起Scheme标准来说，Lispy不是非常完备。主要的缺陷有：

(1) 语法：缺少注释、引用 (quote) / 反引用 (quasiquote) 标记 (即'和`——译者注)、#字面值 (例如#\a——译者注)、衍生表达式类型 (例如从if衍生而来的cond，或者从lambda衍生而来的let)，以及点列表 (dotted list)。

(2) 语义：缺少call/cc以及尾递归。

(3) 数据类型：缺少字符串、字符、布尔值、端口 (ports)、向量、精确/非精确数字。事实上，相比起Scheme的pairs和列表，Python的列表更加类似于Scheme的向量。

(4) 过程：缺少100多个基本过程：与缺失数据类型相关的所有过程，以及一些其它的过程 (如set-car!和set-cdr!，因为使用Python的列表，我们无法完整实现set-cdr!)。

(5) 错误恢复：Lispy没有尝试检测错误、合理地报告错误以及从错误中恢复。Lispy希望程序员是完美的。
*优秀：这一点需要读者自己确定。我觉得，相对于我解释Lisp解释器这一目标而言，它已经足够优秀。
真实的故事
了解解释器的工作方式会很有帮助，有一个故事可以支持这一观点。1984年的时候，我在撰写我的博士论文。当时还没有LaTeX和Microsoft Word——我们使用的是troff。遗憾的是，troff中没有针对符号标签的前向引用机制：我想要能够撰写“正如我们将要在@theoremx页面看到的”，随后在合适的位置撰写”@(set theoremx \n%)” (troff寄存器\n%保存了页号)。我的同伴，研究生Tony DeRose也有着同样的需求，我们一起实现了一个简单的Lisp程序，使用这个程序作为一个预处理器来解决我们的问题。然而，事实证明，当时我们用的Lisp善于读取Lisp表达式，但在采用一次一个字符的方式读取非Lisp表达式时效率过低，以至于我们的这个程序很难使用。
在这个问题上，Tony和我持有不同的观点。他认为 (实现) 表达式的解释器是困难的部分；他需要Lisp为他解决这一问题，但是他知道如何编写一个短小的C过程来处理非Lisp字符，并知道如何将其链接进Lisp程序。我不知道如何进行这种链接，但是我认为为这种简单的语言编写一个解释器 (其所具有的只是设置变量、获取变量值和字符串连接) 很容易，于是我使用C语言编写了一个解释器。因此，戏剧性的是，Tony编写了一个Lisp程序，因为他是一个C程序员；我编写了一个C程序，因为我是一个Lisp程序员。
最终，我们都完成了我们的论文。
整个解释器
重新总结一下，下面就是Lispy的所有代码 (也可以从lis.py下载)：

 




# -*- coding: UTF-8 -*-
# 源代码略。以下纯属娱乐。。。
# 你想看完整源代码？真的想看？
# 真的想看你就说嘛，又不是我编写的代码，你想看我总不能不让你看，对吧？
# 真的想看的话就参考上述下载地址喽。。。LOL