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

PL, Scheme

作者：Peter Norvig 翻译: M. Philis

这篇文章有两个目的：

  1. 通用地介绍如何实现计算机语言的解释器。
  2. 介绍如何利用Python实现Lisp方言Scheme的一个子集。

我将我的这门语言以及解释器称之为Lispy。数年之前，我演示了如何用Java和Common Lisp写Scheme解释器。这次我的目标是以一种尽可能简明的方式演示Alan Kay所谓的“Maxwell’s Equations of Software.”

为什么这很重要？ Steve Yegge说过 ：“若你不知道编译器（或解释器）是怎么工作的，那你就无从得知计算机的运转原理。”

Scheme程序的语法和语义

一门语言的语法（syntax）指的是字母排列成正确表达式或声明的顺序；语义（semantics）则是这些表达式或声明的意义。例如在数学和许多编程语言之中，一加二的语法是“1 + 2”， 语义则是将加法运算符应用于数字1和2之上，得到结果3。我们将计算表达式的值称之为求值（evaluating）；“1 + 2”求值得到结果3，我们将之记为“1 + 2” => 3。

Scheme的语法与你熟悉的大部分语言不同。例如：

1
2
3
4
5
// Java
if (x.val() > 0) { 
  fn(A[i] + 1, 
     return new String[] {"one", "two"}); 
}
1
2
3
4
;; Scheme
(if (> (val x) 0) 
    (fn (+ (aref A i) 1) 
        (quote (one two)))

Java有大量不同的语法约规（关键字、中置操作符、三种括号、操作符优先级、点、引号、逗号、分号等等），而Scheme的语法则简单很多：

  • Scheme程序中只有表达式。表达式和声明之间并无区别。
  • 数字（例如 1）和符号（例如 A）被称之为原子表达式（atomic expression）；他们无法被拆分成更小的表达式。这部分和Java类似，但在Scheme中，诸如 + 和 > 这种操作符也被认为是符号（symbol），处理方式与A或是fn这种符号别无二致。
  • 除此之外的一切都是列表表达式（list expression）：以“(”为首，“)”为尾，中间包括着零个或更多表达式。列表的第一个元素决定了它的含义：
    • 若第一个元素是关键字，例如(if …)，那这个列表是一个特殊形式（special form）；特殊形式的意义取决于关键字。
    • 若第一个元素并非关键字，例如(fn …)，那这个列表则是函数调用。

Scheme之美在于她的简洁性：整个语言由5个关键字和8个语法形式构成。相较之下，Python有33个关键字和110个语法形式，Java有50个关键字和133个语法形式。Scheme中的大量括号初看起来可能显得古怪陌生，但括号为Scheme提供了简洁性和一致性。（有些人开玩笑说Lisp的意思是“大量又蠢又烦的括号（Lots of Irritating Silly Parentheses）”；我觉得应该是“Lisp拥有纯净的语法（Lisp Is Syntactically Pure）。”）

在这篇文章中我们会涉及到Scheme中所有的关键点（除了一些琐碎的细节）。但罗马城不是一天建成的，我们需要分两步。首先，我们会定义一个相对简单的语言，再在它的基础上定义一个几近完整的Scheme语言。

1号语言：Lispy计算器

Lispy计算器是Scheme语言的一个子集，它只包含五种语法形式（两种原子，两个特殊形式，以及过程调用）。只要你习惯了Lisp前置运算符的古怪语法，你就能利用Lispy计算器干一般计算器的活。你还能干一般计算器干不了的活：使用”if”表达式进行条件判断以及定义新的变量。我们来举个例子，以下是一个计算圆面积的程序，圆的半径为10，计算公式为πr^2：

1
2
3
(begin
    (define r 10)
    (* pi (* r r)))

下面这张表列举了所有可用的语法形式：

表达式(expression) 语法(syntax) 语义(sematics)及范例
变量引用(variable reference) var 该符号被认为是变量名；它的值是变量的值。范例：r => 10 （假设我们之前将r定义为10）
字面常量(constant literal) number 一个数字(number)求值得到它自身。范例：12 => 12 或 -3.45e+6 => -3.45e+6
条件(conditional) (if test conseq alt) 对test进行求值；如果结果为真，对conseq进行求值并返回结果；否则对alt求值并返回结果。范例：(if (> 10 20) (+ 1 1) (+ 3 3)) ⇒ 6
定义(definition) (define var exp) 定义一个新的变量，将var的值定义为exp求值得到的结果。范例：(define r 10)
过程调用(procedure call) (proc arg…) 如果proc不是if, define或quote其中之一，那它就被认为是一个过程(procedure)。对proc和所有的args求值，然后将proc过程应用于所有的args之上。范例：(sqrt (* 2 8)) => 4.0

在表中“语法”一列中，var必须为一个符号，number必须为一个整数或浮点数，其他斜体字可以是任何表达式。其中的“arg…”表示零个或更多个”arg“。在“真正”的Scheme中，begin是一个语法关键字，但在这个Scheme实现中，它只是一个普通的函数。

语言解释器做些什么？

一个计算机语言的解释器分为两部分：

  1. 分析(parse)：解释器的分析部分将程序以一串字符的形式读入，依照语法规则(syntactic rules)验证其正确性并将程序转换成一种内部表达形式。在一个简单的解释器中，内部表达形式是一个树形结构，人们一般将其称之为抽象语法树 (abstract syntax tree)。抽象语法树的结构和程序中层层嵌套的声明及表达式非常相近，几乎可以说是完美对应。在编译器之中往往存在多个内部表达形式，一开始先转换成抽象语法树，随后再转换成可以直接被计算器执行的指令序列。Lispy的语法分析器由parse函数实现。
  2. 执行(execution)：内部表达形式被按照语言的语法规则进行处理，以此来进行计算。Lispy的执行函数叫做eval （注意，这会覆盖Python的同名内置函数）。

以下是对解释器工作流程的一个简单的演示：

1
程序 ---> [parse] ---> 抽象语法树 ---> [eval] ---> 结果

下面这个例子则展示了我们希望eval和parse实现的功能：

1
2
3
4
5
6
7
>> program = "(begin (define r 10) (* pi (* r r)))"

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

>>> eval(parse(program))
314.1592653589793

分析：parse, tokenize 以及 read_from_tokens

依照传统，分析被分为两个部分:

  1. 词法分析(lexical analysis)：在这一部分中，输入的字符串被拆分为一系列的token。
  2. 语法分析(syntactic analysis)：将token汇编为抽象语法树。

Lispy token们由括号，符号和数字组成。由许多用来进行词法分析的工具（例如Mike Lesk和Eric Schmidt写的lex），但我们只需要用到一个十分简单的工具：Python的str.split函数。tokenize函数接受一个字符串，并在括号周围加上空格；随后调用str.split来得到一个由token组成的列表：

1
2
3
def tokenize(chars):
    "将字符串转换成由token组成的列表。"
    return chars.replace('(', ' ( ').replace(')', ' ) ').split()
1
2
3
>>> program = "(begin (define r 10) (* pi (* r r)))"
>>> tokenize(program)
['(', 'begin', '(', 'define', 'r', '10', ')', '(', '*', 'pi', '(', '*', 'r', 'r', ')', ')', ')']

我们的parse函数接收一个字符串作为输入，然后调用tokenize函数获得一个由token组成的列表，再调用read_from_tokens来将token列表汇编成抽象语法树。read_from_token函数会查看第一个token，如果是“)”，那就报出一个语法错误。如果是“(”，那我们就开始构建一个由子表达式组成的列表，直到匹配到对应的“)”。所有非括号的token必须是符号或者数字。我们会让Python来识别它们之间的区别：对任何一个非括号token，先尝试将之转为整数，若失败则尝试转为浮点数，若还是失败，则转为符号。下边是parser的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def parse(program):
    "从字符串中读取Scheme表达式"
    return read_from_tokens(tokenize(program))

def read_from_tokens(tokens):
    "从一串token之中读取表达式"
    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))
        tokens.pop(0) # pop off ')'
        return L
    elif ')' == token:
        raise SyntaxError('unexpected )')
    else:
        return atom(token)

def atom(token):
    "数字转为对应的Python数字，其余的转为符号"
    try: return int(token)
    except ValueError:
        try: return float(token)
        except ValueError:
            return Symbol(token)

parse函数的工作方式如下：

1
2
3
4
>>> program = "(begin (define r 10) (* pi (* r r)))"

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

我们还需要决定一下各种Scheme对象在Python中的表示方法：

1
2
3
Symbol = str          # Scheme符号由Python str表示
List   = list         # Scheme列表由Python list表示
Number = (int, float) # Scheme数字由Python的整数或浮点数表示

好了！定义eval的准备工作基本都做好了。但我们需要先了解更多的概念。

环境(Environments)

eval函数接受两个参数：一个我们想要求值的表达式x，还有一个环境env，x将在这个环境中被求值。环境指的是变量名和他们的值之间的映射。eval默认会使用全局环境(global environment)进行求值，全局环境包含着一系列的标准函数（比如sqrt, max和 这类操作符）。这一环境可以用用户定义的变量拓展，语法为 (define variable value*)。我们可以用Python自带的字典来实现环境，字典中的键对为{变量: 值}的形式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import math
import operator as op

Env = dict          # 环境是{变量: 值}之间的映射

def standard_env():
    "一个包含着一些Scheme标准过程的环境。"
    env = Env()
    env.update(vars(math)) # sin, cos, sqrt, pi, ...
    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()

求值：eval

现在，我们已经做好了实现eval函数的准备。来让我们重新看一遍Lispy计算器的语法形式表以加深一下记忆：

表达式(expression) 语法(syntax) 语义(sematics)及范例
变量引用(variable reference) var 该符号被认为是变量名；它的值是变量的值。范例：r => 10 （假设我们之前将r定义为10）
字面常量(constant literal) number 一个数字(number)求值得到它自身。范例：12 => 12 或 -3.45e+6 => -3.45e+6
条件(conditional) (if test conseq alt) 对test进行求值；如果结果为真，对conseq进行求值并返回结果；否则对alt求值并返回结果。范例：(if (> 10 20) (+ 1 1) (+ 3 3)) ⇒ 6
定义(definition) (define var exp) 定义一个新的变量，将var的值定义为exp求值得到的结果。范例：(define r 10)
过程调用(procedure call) (proc arg…) 如果proc不是if, define或quote其中之一，那它就被认为是一个过程(procedure)。对proc和所有的args求值，然后将proc过程应用于所有的args之上。范例：(sqrt (* 2 8)) => 4.0

来和eval的代码对比一下，是不是觉得很像？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)

搞定！来试试吧：

1
2
3
>>> eval(parse("(define r 10)"))
>>> eval(parse("(* pi (* r r))"))
314.1592653589793

交互：来做一个REPL

一直打“eval(parse(…))”的话即便是耐心再好的人也会嫌烦。Lisp最伟大的遗产之一就是引入了read-eval-print loop（读取-求值-输出 循环，缩写为REPL，译者注）。运用REPL，程序员们可以即时地读取、求值、输出，而不用麻烦地先编译再运行。我们先定义一个名为repl的函数以实现这个功能，然后再定义一个schemestr函数来输出Scheme对象的字符串表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
def repl(prompt='lis.py> '):
    "REPL的懒人实现。"
    while True:
        val = eval(parse(raw_input(prompt)))
        if val is not None: 
            print(schemestr(val))

def schemestr(exp):
    "将一个Python对象转换回可以被Scheme读取的字符串。"
    if isinstance(exp, List):
        return '(' + ' '.join(map(schemestr, exp)) + ')' 
    else:
        return str(exp)

老样子，做完以后来试试：

1
2
3
4
5
6
7
>>> 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>

2号语言：完整的Lispy

现在我们来加上3个新的语法形式，构造一个更加完整的Scheme子集：

表达式（Expression） 语法（Syntax） 语义（Semantics）和范例
引用（quotation） (quote exp) 直接按字面返回exp，不对其进行求值。范例：(quote (+ 1 2)) ⇒ (+ 1 2)
赋值（assignment） (set! var exp) 对exp进行求值并将结果赋值给var，exp必须在之前定义过（被define定义过或者是包含set!表达式的过程中的一个参数）。范例：(set! r2 (* r r))
过程（procedure） (lambda (var…) exp) 创造一个过程，参数为var…，exp为过程的主体。范例：(lambda (r) ( pi ( r r)))

lambda特殊形式会创建一个过程(procedure)。（lambda这个名字来源于Alonzo Church的lambda calculus）

1
2
3
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的值为10。事实上，解释器并不会简单地在全局环境之中将r的值设为10。如果我们将r用于其他用途会怎么样？我们不希望对circle-area的调用改变r的值，因此我们希望将一个局部变量r设为10，这样就不会影响到其他同名的变量。因此，我们需要构建一种新的环境，允许同时创建局部和全局变量。

想法如下：在我们对(circle-area 10)求值时，首先提取过程主体部分( pi ( r r))，随后在仅有一个本地变量r的环境中求值，但该环境同时也能访问全局环境。下图演示了这种环境模型，局部环境（蓝色）嵌套在全局环境（红色）之中：

[placeholder]

当我们在一个被嵌套的环境中查找变量时，首先在本层查找，如果没有找到对应值的话就到外一层查找。

显然，过程和环境相关，所以我们把他们放到一起：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Procedure(object):
    "用户定义的Scheme过程。"
    def __init__(self, parms, body, env):
        self.parms, self.body, self.env = parms, body, env
    def __call__(self, *args): 
        return eval(self.body, Env(self.parms, args, self.env))

class Env(dict):
    "环境是以{'var':val}为键对的字典，它还带着一个指向外层环境的引用。"
    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()

我们看到每个过程有3个组成部分：一个包含变量名的列表，一个主体表达式，以及一个外层环境。外层环境使得我们在局部环境中无法找到变量时有下一个地方可以寻找。

环境是dict的子类，因此它含有dict拥有的所有方法。除此之外还有两个额外的方法：

  1. 构造器__init__接受一个变量名列表及对应的变量值列表，构造创造一个新环境，内部形式为{variable: value}键对，并拥有一个指向外层环境的引用。
  2. find函数用于找到某个变量所在的正确环境，可能是内层环境也可能是更外层的环境。

要想知道这部分的工作原理，我们首先来看看eval的定义。注意，现在我们需要调用env.find(x)来寻找变量处于哪一层环境之中；随后我们才能从那一层环境之中提取x。（define分支的定义没有改变，因为define总是向最内一层的环境添加变量。）同时我们还增加了两个判定分支：set!分支中，我们寻找变量所处的环境并将其设为新的值。通过lambda，我们可以传入参数列表、主体以及环境以创建一个新的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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!':           # 赋值
        (_, var, exp) = x
        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)

为了更好地理解过程和环境是怎样协同运作的，我们来看看下面这段程序。思考一下，在我们对(account1 -20.00)求值的时候，程序会生成一个怎样的环境呢？

[place holder]

每个矩形框代表一个环境，环境的颜色和程序中新定义变量的颜色相对应。在程序的最后两行中，我们定义了account1并调用了(account1 -20.00)，这表示我们创建了一个拥有100美金余额的账户，并从中取出20美金。在对(account1 -20.00)进行求值的过程中，我们会对黄色高亮部分进行求值。该表达式中有三个变量：amt可以直接在最内层环境（绿色）中找到。但balance不在那一层环境之中，我们需要查找绿色的外一层环境（蓝色）。然而变量‘+’依然不能在这两个环境之中找到，所以我们需要在更外一层环境中寻找（红色的全局环境）。这一先在内层环境查找，再在外层环境中查找的方式被称为“词法作用域”(Lexical Scoping)。Env.find(var)依照词法作用域规则查找变量所处的正确环境。

现在我们能做的事又多了不少：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
>>> 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）和顺序执行（begin）。如果你熟悉其他语言的话，你可能会觉得我们还需要while或者for循环，但Scheme认为自己不需要这两种循环结构。Scheme标准中说：“Scheme展示了只需要极少量构造表达式的规则，无需规定表达式的组成方式，就足以构建出一个实用而高效的语言。”在Scheme中，我们通过构建递归函数的方式来实现迭代。

Lispy有多小/快/完整/好？

我们以以下的标准来评判Lispy：

  • 小：Lispy十分简短：不算空行和注释的话一共只有117行，源码只有4K大小。（更早的一个版本只有90行，但包含的标准过程更少，也显得过于简陋了。）我用Java实现的最小Scheme（Jscheme）包含1664行代码，源码有57K大。Jscheme之前叫SILK（Scheme in Fifty Kilobytes，缩写对不上…anyway），不过实际上只有在编译成bytecode的情况下才小于50k。在“小”这一方面，Lispy做得要好很多，我想它符合Alan Kay在1972年所说的：“你可以用‘一页代码’定义出‘世界上最强大的语言’”。（其实我觉得Alan Kay本人不会同意，因为Python解释器的代码量远高于一页。）

    1
    2
    bash$ grep "^\s*[^#\s]" lis.py | wc
         117     497    4276

  • 快：Lispy可以在0.003秒内计算出(fact 100)的值。对我来说够快了（尽管比大部分语言慢很多）。

  • 完整：Lispy和Scheme标准比起来算不上完整。一下是主要的一些缺少处：

    • 语法：缺少注释，quote符和quasiquote符，#常量，延伸的表达式（从if中延伸出的cond，从lambda中延伸出的let），和dotted list标记。
    • 语义：缺少call/cc和尾递归。
    • 数据类型：缺少String, character, boolean, ports, vectors, exact/inexact numbers。Python的列表相比于Scheme里的列表实际上更接近于Scheme里的vector。
    • 过程：少了100多种原始过程：包含与所有缺少的数据类型有关的过程，以及set-car!和set-cdr!之类的过程，因为我们没法用Python列表直接实现这一功能。
    • 错误修复：Lispy不会尝试去侦测，报告以及修复错误。想用Lispy编程的话你需要一个从不犯错的程序员。

  • 好：这项的评判就交由读者去定了。对我来说，它不错地完成了预定目标——解释Lisp解释器的工作原理。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
################ Lispy: Scheme Interpreter in Python

## (c) Peter Norvig, 2010-16; See http://norvig.com/lispy.html

from __future__ import division
import math
import operator as op

################ Types

Symbol = str          # A Lisp Symbol is implemented as a Python str
List   = list         # A Lisp List is implemented as a Python list
Number = (int, float) # A Lisp Number is implemented as a Python int or float

################ Parsing: parse, tokenize, and read_from_tokens

def parse(program):
    "Read a Scheme expression from a string."
    return read_from_tokens(tokenize(program))

def tokenize(s):
    "Convert a string into a list of tokens."
    return s.replace('(',' ( ').replace(')',' ) ').split()

def read_from_tokens(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))
        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)

################ Environments

def standard_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':   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

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)

global_env = standard_env()

################ Interaction: A REPL

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(lispstr(val))

def lispstr(exp):
    "Convert a Python object back into a Lisp-readable string."
    if isinstance(exp, List):
        return '(' + ' '.join(map(lispstr, exp)) + ')' 
    else:
        return str(exp)

################ Procedures

class Procedure(object):
    "A user-defined Scheme procedure."
    def __init__(self, parms, body, env):
        self.parms, self.body, self.env = parms, body, env
    def __call__(self, *args): 
        return eval(self.body, Env(self.parms, args, self.env))

################ eval

def eval(x, env=global_env):
    "Evaluate an expression in an environment."
    if isinstance(x, Symbol):      # variable reference
        return env.find(x)[x]
    elif not isinstance(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
        exp = (conseq if eval(test, env) else alt)
        return eval(exp, env)
    elif x[0] == 'define':         # (define var exp)
        (_, var, exp) = x
        env[var] = eval(exp, env)
    elif x[0] == 'set!':           # (set! var exp)
        (_, var, exp) = x
        env.find(var)[var] = eval(exp, env)
    elif x[0] == 'lambda':         # (lambda (var...) body)
        (_, parms, body) = x
        return Procedure(parms, body, env)
    else:                          # (proc arg...)
        proc = eval(x[0], env)
        args = [eval(exp, env) for exp in x[1:]]
        return proc(*args)