(How to Write a (Lisp) Interpreter (in Python))中文版(包括上下篇)

Python 实现 Lisp 解释器

内容目录

译者序............................................................................................................................1

第一篇：(How to Write a (Lisp) Interpreter (in Python)) ............................................................2

1 Syntax and Semantics of the Lispy Scheme Subset .......................................................2

2 What A Language Interpreter Does ................................................................................3

3 Execution：eval ..............................................................................................................4

4 Parsing：read and parse .................................................................................................6

5 How Small/Fast/Complete/Good is Lispy? ......................................................................9

(4) Better eval with tail recursion optimization................................................................19

(5) Call-with-current-continuation (call/cc).......................................................................21

(6) Procedures with arbitrary number of arguments........................................................22

(7) Earlier error detection and extended syntax...............................................................23

8) More primitive procedures............................................................................................26

(9) Testing..........................................................................................................................27

(Appendix) Brought to you by............................................................................................31

译后记..........................................................................................................................32

译者序

因为在看《PY 源码剖析》，看到函数实现那部分，最近函数式编程话题很多，加上本人想学一门函数式编程语言完善

由于我糟糕的英文水平和对函数式语言相关方面的不了解，文章有很多翻译不恰当的地方；而且，许多专业术语到翻译

也不准确，如：将 Interpreter（解释器）翻译成来解析器（Parser），Symbol（标识符）翻译成了符号，还有些句

子不太通顺，等等；后来进行了修改，但仍有很多错误没改过来。第二篇的翻译则相对好一些，一些单词干脆用原文表示以

免阅读者理解错误。如果你发现翻译不准确的地方，欢迎来信指出。

2010-10-18 九月十一日朝

德哥（shuxiang29@gmail.com)

第一篇：(How to Write a (Lisp) Interpreter (in Python))

这玩意有两个目的，描述通常如何实现一个计算机语言解释器，又特别地展示如何使用 Python

实现 Lisp 的一个方言

组”( "Maxwell's Equations of Software" )。

大多数计算机语言有大量的语法约定(关键字，中缀操作符，括号，运算符优先级，点符号，分号等)，但如同许多 Lisp

族的语言，所有的 Scheme 语法都是基于在括号的前缀符号列表。这看起来似乎陌生，但它具有简单性和一致性。(一些人

调戏 Lisp，说它是"Lots of Irritating Silly Parentheses"--大量搞疯你的傻逼括号；我认为 Lisp 代表"Lisp Is

Syntactically Pure" --语法上的纯粹) ，请看：

Java Scheme

y )，它的开始位置有一个特殊关键字，称为 Scheme 的一个 Special Form。这门语言的美是：我们仅仅需要 6 个

specil form，外加 3 个句法结构：变量，常量和过程调用：

variable

reference

一个被解析成变量名的标识符 ，它的值是变量的值

constant

alt ，例如： (if (< 10 20) (+ 1 1) (+ 3 3)) =>2

assignment (set! var exp)

执行 exp 并把值赋给 var，var 必须已经被定义( 使用 define 或作为一

个封闭过程的参数如： (set ！ (* x x))

给最深环境定义一个变量，并把它的值给 exp 表达式以计算 如：(define

r 3) 或 (define square (lambda (x) (* x x)))

call

如果表达式不是这些标识符(if,set!,define,lambda,begin, quote)

都执行好，则过程被调用； 而表达式列表 当作过程的参数, 如 (square

12) => 144

在这个表中，var 必须是一个符号，一个标识符，如 x 或 square；并且 number 必须是一个数字或浮点数， 其它

的则可以是任何表达式，exp..则是零个或多个 exp 的重复。

你可以参考这些书来学习更多 Sheme 的知识，(by Friedman and Fellesein, Dybvig, Queinnec,

Harvey and Wright or Sussman and Abelson), videos (by Abelson and Sussman), tutorials (by

如 Steve Yegger

说的 ，"If you don't know how compilers work, then you don't

know how computers work." Yegger 描述 8 种编译器能解决的情况(or equally with

interpreters, or alternatively with Yegge's typical heavy dosage of cynicism.)

Lispy parser 实现了功能 parse 。

2.Execution ： 程序的内部表示形式是依据语言的语义规则来处理的，从而能进行计算处理。Execution

实现的功能是 eval()，注意这就像 Python 的内建函数 eval 。

这有一张解析过程的图片，和在一个短程序中一个交换式的会话显示了 parse 和 eval 的操作。

>> program = "(begin (define r 3) (* 3.141592653 (* r r)))"

这里定义了 eval，上面表中的九种情况在这里都有一两行代码，eval 不需要其它的，仅仅需要解决这九种情况。

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 常量 ，如果不是一个 list

return x

elif x[0] == 'quote': # (quote 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) lambda 演算

(_, vars, exp) = x

return lambda *args: eval(exp, Env(vars, args, env))

elif x[0] == 'begin': # (begin exp*)# 执行一系列语句

for exp in x[1:]: