Python写Lisp解释器（五、原文全翻译）

May 16, 2017

这是一篇搬运+翻译。引用国外某大神的Lisp（其实是其中的一种叫做Scheme的方言）的解释器的过程。

正好在学编译原理，准备搞一些事情，这个project纯当一个搞事情的前奏。因为一年多前简略的看过了SICP，所以对LISP语言有一定小小的理解，所以开一个LISP语言的解释器，对编译上的理解可能会非常的有帮助。

另外，国内能够自主写出编译器的人实在是太少，这一行业上可能更多的引用国外大神的博客内容，所以搬运和翻译的这种过程也是极有必要的。

原文地址：http://norvig.com/lispy.html

搬运+翻译人：岐山凤鸣，引用者请加上本站域名。

参考：http://blog.jobbole.com/47659/

插曲：这么久没有更新，很大一部分原因因为数据丢失，有道云笔记略坑。

正文：

这篇文章有两个目的：描述一种写通用编程语言解释器的做法，和如何用Python实现Lisp的一个方言Scheme的解释器。我把我写的这个语言和解释器叫做Lispy(这么蠢的名字，也是醉了。)几年前，我也曾写过用JAVA来实现Scheme的解释器，还有一个用Common LISP语言。现在呢，我们的目标就是能够尽可能的用Python来实现Alan Kay说过的软件中的麦克斯韦方程组。(“Maxwell’s Equations of Software.” )

Scheme程序的语法和语义

一个编程语言的语法就是一连串的字母按照一定的顺序组装组成的一段话，包含一定的意思。语义则是指这段话的具体含义，编程语言中，就对应着这段话所形成的机器指令。举一个栗子，在数学表达式语言中，表示一加二的语法一般使用“1+2”来实现，语法则是“1+2”这几个字母数字，语义则是指“一加二”意思，表达式的值返回3，我们就可以记为“1+2 => 3”

Scheme的语法形式和大多数编程语言不一样，有点反人类：

Java中：

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

而在Scheme中就变成了这个样子：

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

Java有着一套很广泛的语法传统(关键字，三种括号，中缀表达式，操作符优先级，点符号，引用，逗号，分号)，但是Scheme更简单，它的形式是这样的：

  • Scheme的程序只包括表达式，没有变量声明和表达式之间的区别。
  • 数字和符号都被称为原子表达式(atomic expressions)，它们不能被拆开。和Java不一样，+和>在Scheme中都和变量名A和函数名fn一样被对待。
  • 任何东西在Scheme中都是由(操作类型， 操作数1， 操作数2)来进行，其中操作类型包括+，-，×，/这样的，还有关键字define这样的，还有函数名fn这样的，操作数可以输原子表达式，也可以是另外一个括号的嵌套，比如3+5+6,可以表达为(+ 3 (+ 5 6))

Scheme的美观就在于它只用五种关键字和8中语法形式就能够完全的表达一种语言，相比之下，Python有33中关键字和110中语法形式，Java有50中关键字和133种语法形式。用了这么多的括号可能会让Scheme显得非常反人类，所以有人把LISP成为“一大堆sb符号组成的sb玩意”(Lots of irritating silly parentheses)，我觉得它比LISP的本意更好。

在这篇文章中，我们要介绍了Scheme的重点，将通过两个步骤来学习，第一个是定义一门正常的语言，第二个是定义完备的Scheme语言的解释器。

语言1：Lispy计算器

Lispy计算器是一个Scheme的子集，使用了五种语法形式(两种原子表达式，两种特殊的行驶，和一种过程调用)，Lispy计算器让你可以尝试任何的计算并且愉快的去享受前缀表达式的快感（哦，是么）。然后你可以做两件事情，这两件事情在原来的定义中没有实现，比如if表达式，还有一个是定义define关键字，这里有一个简单的程序，表达了计算pirr，计算圆的面积：

(begin
	(define r 10)
	(* pi (* r r))
)

这个表显示了所有允许的表达式：

表达式 语法 语义和例子  
变量声明 var 一个符号表示一个变量的名字，比如r => 10，定义变量r，让它的值为10  
常数 number 数字，0,1,2,….,100000这样的数字  
条件语句 (if test conseq alt) (if (> 10 20) (+ 1 1) (+ 3 3)) => 6  
定义 define 定义一个新的变量并且赋值 (define r 10)
过程调用 (proc arg …) 比如(sqrt (* 2 8)) => 4.0  

var必须是符号，数字必须是整数或者浮点数，其他的前缀字符可以是任何表达式，符号arg表示0或者是其他的代表参数。在真正的Scheme中，begin是一个语法关键词，但是在我们的Scheme中，它仅仅代表着一个普通的函数。

一个语言的解释器做了什么

一个语言的解释器有下面两个部分组成：

  • Parsing（解析）：解析部分表示输入一串该语言组成的串，然后判断符不符合语法规则，并且将它格式化为一种中间语言。在简单的解释器中，语句通常被解析为树形结构，这种结构能够像一个函数一样被计算机执行

  • Execution（执行）：根据语法规则去翻译一个语句的语义，Lispy是执行函数被称为eval函数（一个很邪恶的函数）

这里有一个图可以很好的表达这种关系：

image

这里是一个简单的栗子表现parse和eval都做了些什么：

>> program = "(begin (define r 10) (* pi (* r r)) )"
>> parse(program)
['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]
>> eval(parse(program))
314.15926

Parsing:parse, tokenize 和 read_from_tokens

解析(parsing)的过程可以传统的分为两部分：词法分析和语义分析。词法分析就是将输入串分离成各种记号。语义分析就是将这些记号弄成一棵抽象语法树。Lispy的记号就是三个，括号，标识符，和数字。有很多的工具能够进行此法分析，但我们用一个很简单的工具，就是Python內建的字符串处理函数split，这个函数能够将字符串根据空格分割，返回一个分割后得到的单词的list，通过这个函数我们可以很方便的得到记号流。

def tokenize(chars):
    return chars.replace('(', ' ( ').replace(')', ' ) ').split()

>>> program = "(begin (define r 10) (* pi (* r r)))"
>>> tokenize(program)
['(', 'begin', '(', 'define', 'r', 10, '(', '*', 'r', 'r', ')', ')', ‘)’]

我们的函数parse需要一个记号流，所以tokenize满足了这个要求，得到了一个列表。那么接下来我们需要一个read_from_tokens这样的一个函数，用来构建抽象语法树，主要是根据记号流中的’(‘和’)’来分析。如果括号不匹配，则弹出错误。任何非括号的记号除了标识符就一定是数字，这一点上面也说过了，否则报错。我们可以用Python去区分它们(标识符还是数字)，首先尝试去解释它是不是int型，然后尝试float，最后尝试是不是标识，下面就是我们的解析器：

def parse(program):
    return read_from_tokens(tokenize(program))
    
def read_from_tokens(tokens):
    if len(tokens) == 0:
        raise SyntaxError('unexpected EOF while reading')
    token = tokens.pop()
    if '(' == token:
        L = []
        while tokens[0] ~= ')':
            L.append(read_from_tokens(tokens))
        tokens.pop(0)
        return L
    elif ')' == token:
        raise SyntaxError('unexpected )')
    else:
        return atom(token)

def atom(token):
    try:
        return int(token)
    except ValueError:
        try: return float(token)
        excepte: ValueError:
            return Symbol(token)

parse像这样工作：

>>> program = '(begin (define r 10) (* pi (* r r)))'
>>> parse(program)
['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]

关于Scheme语法中的三种对象，我们就用下面的三个东西来代表咯：

Symbol = str
List = list
Number = (int, float)

我们即将准备定义eval, 但是我们还有一个概念要讲解。

环境(Environment)

这个函数eval需要两个参数，一个表达式x, 即我们要解析和执行的代码，另外一个就是环境env。一个环境建立了一个映射，映射了一些标识符到它的实际值。eval的默认第二个参数是标准环境，包含了Scheme名字和标准函数的映射（比如sqrt和max包括*这样的一些东西）。环境还可以让用户自定义标识符，用表达式define, 比如(define variable value)。现在，我们可以看一下怎么用Python中的字典来建立环境。

import math
import operator as op
Env = dict

def standard_env():
    env = Env()
    env.uodate(vars(math)
    env.update({
        '+': op.add, 
        '-': op.sub, 
        '*': op.mul, 
        '/': op.div, 
        '>': op.gt,
        '<': op.lt,
        '>=': op.ge,
        '<=': op.le, 
        '=': op.eq, 
        'abs': abs,
        'append': op.add,  
        'apply': apply,
        'begin': lambda *x: x[-1],
        'car': lambda x: x[0],
        'cdr': lambda x: x[1:], 
        'cons': lambda x,y: [x] + y,
        'eq?': op.is_, 
        '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),   
        'procedure?': callable,
        'round': round,
        'symbol?': lambda x: isinstance(x, Symbol),
    })
    return env
global_env = standard_env()

Evaluation: eval

我们现在准备开始搞我们的eval了，作为一个参考，我先列个表说说Lispy计算器的形式：

表达式 语法 语义和示例
变量声明 var 用一个标识符去声明一个变量的名字，并给它赋值
常数 number 比如12就是12
条件语句 (if test conseq alt) 比如(if (> 20 10) (+ 1 1) (+ 3 3))，得到的结果为6
宏定义 (define var exp) 比如(define r 10)，那么r就是10了
调用语句 (proc arg..) 比如(sqrt (* 2 8), 表示调用sqrt(2*8)，神奇吧

仔细看看我们怎么根据这个表格来写我们的eval:

def eval(x, env = global_env):
    if isinstance(x, Symbol):
        return env[x]
    elif not isinstance(x, List):
        return x
    elif x[0] == 'if':
        (_, test, conseq, alt) = x
        exp = (conseq if eval(test, env) else alt
        return eval(exp, env)
    elif x[0] == 'define':
        (_, var, exp) = x
        env[var] = eval(exp, env)
    else:
        proc = eval(x[0], env)
        args = [eval(arg, env) for arg in x[1:]]
        return proc(*args)

好的，我们已经完成了，看看我们做了些什么吧：

>>> eval(parse("define r 10"))
>>> eval(parse("(* pi (* r r))")
314.15926535

交互式环境

如果每次都eval(parse(代码))的话，有一些反人类，那么我们提供一个交互式的环境就比较好。Lisp的一种很好的方式就是提供了一个eval和显示的循环，这样我们可以迅速得到我们想要的结果。所以就让我们开始我们的交互式环境的搭建。

def repl(prompt = 'lis.py> '):
    while True:
        val = eval(parse(input(prompt)))
        if val is not None:
            print(schemestr(val))

def schemestr(exp):
    if isinstance(exp, List):
        return '(' + ' '.join(map(schemestr, exp)) + ')'
    else:
        return str(exp)

下面是交互式环境工作的样子：

>>> repl()
lis.py> (define r 10)
lis.py> (* pi (* r r))
314.15926535
lis.py> (if (> 11 11) 120) (* 7 6) cops)
42
lis.py>

语言2，完整的Lispy

我们现在可以通过三种形式扩展我们的语言了，这样更加接近Scheme语法的子集。

表达式 语法 语义和示例
引用 (quote exp) 只是引用，并不执行，比如(quote (+ 1 2))解释后直接是(+ 1 2)
赋值 (set! var exp) 给变量名进行直接的赋值，前提是变量名已经定义
lambda表达式 (lambda (var…) exp) 创建一个带参的lambda表达式，比如(lambda (r) (* pi (* r r))

关于lambda表达式不如去看看Python自己的lambda表达式是什么玩意。

做好后，我们就可以这样调用了：

lis.py> (define circle-area (lambda (r) (* pi (* r r)))
lis.py> (circle-area 10)
314.159265359

这个调用(circle-area 10)，能够让我们通过这个名字来调用(* pi (* r r))。在一个环境中pi和*都定义了，但是r并没有，那么r从哪里得到它是什么玩意呢，这就要看我们上一条中定义了传入lambda表达式的r，即circle-area这个操作类型的参数，那么我们再看(circle-area 10)，10即是参数，参数在表达式中充当了r的作用，所以r = 10。然而，我们并不能在标准环境中直接给r赋值为10，那么我们要怎么做才能让r等于10呢，把r变成全局变量也是不太好的。所以我们要创建一个新的环境，一个环境能够满足局部变量和全局变量的需求。

这个思想即是我们调用(circle-area 10), 我们将要展开这个函数体，即(* pi (* r r)), 并且根据一个r叫做10的环境中去执行它，还要保证不会影响到全局变量。换句话说，我们要创建一个看上去是那么一回事的环境，这个环境只在局部发生作用，比如下面这样的一个环境：

pi : 3.1415926535
* : <built-in function mul>
...
r: 10

我们看到那个变量就在这个环境中，我们再往前看一级，就找不到这个变量名了。

很明显，这个环境只在调用这个函数（是不是暴露了什么呢）的时候才会起作用，让我们这样来定义它们好了：

class Procedure(object):
    def __init__(self, parms, body, env):
        self.parms = parms
        self.body = body
        self.env = env
    def __call__(self, *args):
        return eval(self.body, Env(self.parms, args, self.env))
        
class Env(dict):
    def __init__(self, parms = (), args = (), outer = None):
        self.update(zip(parms, args))
        self.outer = outer
    def find(self, var):
        return self if (var in self) else self.outer.find(var)
global_env = standard_env()

我们可以看到每一次调用过程都有三个参量，一系列的参数名，主体表达式，和一个环境，告诉了我们一些主体表达式可以用的一些局部变量。

这个新的环境类继承自字典，它有所有字典有的算法，总的来说就多了两种方法，__init__初始化了这个环境，构建了三个参数并且赋值。然后创建了一个新的环境让它成为一个内部的部分，也有着和原来那个一样的东西。find方法就用在对变量来说，找到一个正确的环境，是内置的那个，还是外部的环境。

为了看它是怎么工作的，这里有一个队eval的定义。我们改变了对变量赋值的写法，我们这样写：env.find(x)，去寻找变量x存在的环境。然后再得到x的真正的值进行运算.(倒是不用修改define里的语句，因为defin里面总是添加了新的变量到全局当中，而find的时候是从最底层开始找，所以不会有冲突)，两个地方需要改，一个是赋值set!, 一个lambda表达式，下面就是改后的eval:

def eval(x, env = global_env):
    if isinstance(x, Symbol):
        return env.find(x)[x]
    elif not isinstance(x, List):
        return x
    elif x[0] == 'quote':
        (_, exp) = x
        return exp
    elif x[0] == 'if':
        (_, test, conseq, alt) = x
        exp = (conseq if eval(test, env) else alt)
        return eval(exp, env)
    elif x[0] == 'define':
        (_, var, exp) = x
        env[var] = eval(exp, env)
    elif x[0] == 'set!':
        env.find(var)[var] = eval(exp, env)
    elif x[0] == 'lambda':
        (_, parms, body) = x
        return Procedure(parms, body, env)
    else:
        proc = eval(x[0], env)
        args = [eval(arg, env) for arg in x[1:]]
        return proc(*args)

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

(define account1 (make-account 100.00))
(account1 -20.00)

 
+: <built-in operator add>
make-account: <a Procedure>
balance: 100.00
amt: -20.00

account1: <a Procedure>

每一个矩形都代表着一个环境，有颜色的变量名就是在新的环境中所定义的东西。在最后两行的代码中可以看到我们定义了account1函数并且调用了(account1 20.0)，这代表着我们创立了一个银行账户，用100刀的活期余额，然后遵循20刀的衰减。在这个调用过程中，我们先执行黄色的语句，这里有三个变量，amt可以迅速在绿色语句中找到，但balance没有定义在这个环节中，我们需要继续往上找，找到了蓝色的语句，终于，找到了balance, 但是+操作并没有找到，我们需要继续往上找，直到进入了红色的环境中，找到了正确的环境得到+所代表的是op.add, 语法全部正确！

好了，让我看看我们现在都可以干些什么东西了：

>>> repl()
lis.py> (define circle-area (lambda (r) (* pi (* r r))))
lis.py> (circle-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> (circle-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? item (first L)) (count item (rest L))) 0)))
lis.py> (count 0 (list 0 1 2 3 0 0))
3
lis.py> (count (quote the) (quote (the more the merrier the bigger the better)))
4
lis.py> (define twice (lambda (x) (* 2 x)))
lis.py> (twice 5)
10
lis.py> (define repeat (lambda (f) (lambda (x) (f (f x)))))
lis.py> ((repeat twice) 10)
40
lis.py> ((repeat (repeat twice)) 10)
160
lis.py> ((repeat (repeat (repeat twice))) 10)
2560
lis.py> ((repeat (repeat (repeat (repeat twice)))) 10)
655360
lis.py> (pow 2 16)
65536.0
lis.py> (define fib (lambda (n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2))))))
lis.py> (define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b)))))
lis.py> (range 0 10)
(0 1 2 3 4 5 6 7 8 9)
lis.py> (map fib (range 0 10))
(1 1 2 3 5 8 13 21 34 55)
lis.py> (map fib (range 0 20))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

我们现在可以调用语句，声明变量，做if操作。如果你对其他的编程语言熟练的话，可以尝试while和for循环怎么做，但是Scheme中没有这些东西，Scheme的文档中说”Scheme demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language.” ,在Scheme中，你重复的定义了递归的函数。

Lispy性能如何？小？快？完备？棒棒？

这里我们通过这几个方面去判断Lispy 的好坏：

  • 小：Scheme小到令人发指，117行无注释和空行代码，4k的源代码，早期版本仅仅90行，但没有标准调用。最小的版本我曾实现过的是Java写的，1664行和57k的代码。Jscheme初始的时候被SILK调用，但我一直处于被动因为一直在数二进制而不是源代码。我觉得在1972年遇到Alan Kay表示你可以定义出世界上最强大的编程语言用一张纸的量，我觉得差不多做到了，哪怕他自己都不相信。
  • bash$ grep "^s*[^#\s]" lis.py | wc
117    497    4276

  • 快：对我来说已经很快了，调用(fact 100)用了0.003秒

  • 完备：Lispy并不完备，还没有满足标准Scheme的内容，大概下面几个方面有短缺：
    • 语法：缺少注释，引用和引用符
    • 语义：缺少调用和尾递归
    • 数据类型：缺少字符串，字符，布尔，容器等等数据类型。python 的列表倒是和Scheme中的向量很像。
    • 调用：缺少至少一百种原生调用，对每一个数据类型都应配上，要加上像set-car! 和set-cdr!这样的东西，因为我们不能够直接调用set-cdr!仅仅只是用Python的列表来实现的话。
    • 错误抓取：Lispy并不能做出错误检测，所以还需要增加很多内容
    • 好坏：要看使用者去说了，实践是检验真理的唯一标准嘛。

真实的故事

回到我当时的想法，解释一个解释的工作是一个非常有用的过程，这是一个真实的故事，让我们回到1984年，我正在进行phd项目。那还是在LaTeX出现之前，甚至Word和Windows都没有，我们用troff。很不幸的是，troff没有设备也没有前缀标识符。我想要有这个功能，我的同事的研究生Tony DeRose也有同样的想法，然后我们合伙搞了一点事情，弄出来了一个简单的Lisp程序，这样我们就能把它当成我们的预处理程序了。然而，我们当时的那个Lisp非常棒棒的能够读取Lisp表达式，但是在读取字符上太慢了，所以我们的程序就很难用。

从那时起Tony和我走向了不同的道路。他认为困难的地方就是对表达式进行解释这个地方，他需要Lisp但是他也知道写一个tiny C路线链接到那个Lisp程序中去读取字符可能更好。我不知道怎么链接，但我认为写一个解释器，尤其是这么平凡的语言，应该很简单，所以我写了一个C语言的解释器，然后，Tony写了Lisp 的程序并且链接了一个C语言写的东西去读字符，因为他也是一个C语言编程者。我写C语言倒是因为我是一个Lisp编程者。

最后，我们都完成了我们的论文。

更多阅读：

作者原话：

To learn more about Scheme consult some of the fine books (by Friedman and Fellesein, Dybvig, Queinnec, Harvey and Wright or Sussman and Abelson), videos (by Abelson and Sussman), tutorials (by Dorai, PLT, or Neller), or the reference manual.