本文有两个目的: 一是讲述实现计算机语言解释器的通用方法，另外一点，着重展示如何使用Python来实现Lisp方言Scheme的一个子集。我将我的解释器称之为Lispy (lis.py)。几年前，我介绍过如何使用Java编写一个Scheme解释器，同时我还使用Common Lisp语言编写过一个版本。这一次，我的目的是尽可能简单明了地演示一下Alan Kay所说的“软件的麦克斯韦方程组” (Maxwell’s Equations of Software)[1]。
Lispy支持的Scheme子集的语法和语义
大多数计算机语言都有许多语法规约 (例如关键字、中缀操作符、括号、操作符优先级、点标记、分号等等)，但是，作为Lisp语言家族中的一员，Scheme所有的语法都是基于包含在括号中的、采用前缀表示的列表的。这种表示看起来似乎有些陌生，但是它具有简单一致的优点。 (一些人戏称”Lisp”是”Lots of Irritating Silly Parentheses“——“大量恼人、愚蠢的括号“——的缩写；我认为它是”Lisp Is Syntactically Pure“——“Lisp语法纯粹”的缩写。) 考虑下面这个例子：
|
|
1234567
|
/* Java */if(x.val() > 0) { z = f(a*x.val() + b);}/* Scheme */(if (> (val x) 0) (set! z (f (+ (* a (val x)) b)))) |
|
注意上面的惊叹号在Scheme中并不是一个特殊字符；它只是”set!“这个名字的一部分。(在Scheme中)只有括号是特殊字符。类似于(set! x y)这样以特殊关键字开头的列表在Scheme中被称为一个特殊形式 (special form)；Scheme的优美之处就在于我们只需要六种特殊形式，以及另外的三种语法构造——变量、常量和过程调用。
| 形式 (Form) |
语法 |
语义和示例 |
| 变量引用 |
var |
一个符号，被解释为一个变量名；其值就是这个变量的值。
示例: x |
| 常量字面值 |
number |
数字的求值结果为其本身
示例: 12 或者-3.45e+6 |
| 引用 |
(quote exp) |
返回exp的字面值；不对它进行求值。
示例：(quote (a b c)) ⇒ (a b c) |
| 条件测试 |
(if test conseq alt) |
对test进行求值；如果结果为真，那么对conseq进行求值并返回结果；否则对alt求值并返回结果。
示例：(if (< 10 20) (+ 1 1) (+ 3 3)) ⇒ 2 |
| 赋值 |
(set! varexp) |
对exp进行求值并将结果赋给var，var必须已经进行过定义 (使用define进行定义或者作为一个封闭过程的参数)。
示例：(set! x2 (* x x)) |
| 定义 |
(define varexp) |
在最内层环境 (environment) 中定义一个新的变量并将对exp表达式求值所得的结果赋给该变量。
示例：(define r 3) 或者 (define square (lambda (x) (* x x))) |
| 过程 |
(lambda(var…)exp) |
创建一个过程，其参数名字为var…，过程体为相应的表达式。
示例：(lambda (r) (* 3.141592653 (* r r))) |
| (表达式) 序列 |
(beginexp…) |
按从左到右的顺序对表达式进行求值，并返回最终的结果。
示例：(begin (set! x 1) (set! x (+ x 1)) (* x 2)) ⇒ 4 |
| 过程调用 |
(proc exp…) |
如果proc是除了if, set!, define, lambda, begin,或者quote之外的其它符号的话，那么它会被视作一个过程。它的求值规则如下：所有的表达式exp都将被求值，然后这些求值结果作为过程的实际参数来调用该相应的过程。
示例：(square 12) ⇒ 144 |
在该表中，var必须是一个符号——一个类似于x或者square这样的标识符——number必须是一个整型或者浮点型数字，其余用斜体标识的单词可以是任何表达式。exp…表示exp的0次或者多次重复。
更多关于Scheme的内容，可以参考一些优秀的书籍 (如Friedman和Fellesein, Dybvig,Queinnec, Harvey和Wright或者Sussman和Abelson)、视频 (Abelson和Sussman)、教程 (Dorai、PLT或者Neller)、或者参考手册。
语言解释器的职责
一个语言解释器包括两部分：
1、解析 (Parsing)：解析部分接受一个使用字符序列表示的输入程序，根据语言的语法规则对输入程序进行验证，然后将程序翻译成一种中间表示。在一个简单的解释器中，中间表示是一种树结构，紧密地反映了源程序中语句或表达式的嵌套结构。在一种称为编译器的语言翻译器中，内部表示是一系列可以直接由计算机 (作者的原意是想说运行时系统——译者注) 执行的指令。正如Steve Yegge所说，“如果你不明白编译器的工作方式，那么你不会明白计算机的工作方式。”Yegge介绍了编译器可以解决的8种问题 (或者解释器，又或者采用Yegge的典型的反讽式的解决方案)。 Lispy的解析器由parse函数实现。
2、执行：程序的内部表示 (由解释器) 根据语言的语义规则进行进一步处理，进而执行源程序的实际运算。(Lispy的)执行部分由eval函数实现 (注意，该函数覆盖了Python内建的同名函数)。
下面的图片描述了解释器的解释流程，(图片后的) 交互会话展示了parse和eval函数对一个小程序的操作方式：
|
|
1234567
|
>> program = \”(begin (define r 3) (* 3.141592653 (* r r)))\” >>> parse(program)[\’begin\’, [\’define\’, \’r\’, 3], [\’*\’, 3.141592653, [\’*\’, \’r\’, \’r\’]]] >>> eval(parse(program))28.274333877 |
|
这里，我们采用了一种尽可能简单的内部表示，其中Scheme的列表、数字和符号分别使用Python的列表、数字和字符串来表示。
执行: eval
下面是eval函数的定义。对于上面表中列出的九种情况，每一种都有一至三行代码，eval函数的定义只需要这九种情况：
|
|
123456789101112131415161718192021222324252627282930313233
|
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.\”>, exp) = x env.me的一个子集。我将我的解释器称之为Lispy (lis.py)。几年前，我介绍过如何使用Java编写一个Scheme解释器，同时我还使用Common Lisp语言编写过一个版本。这一次，我的目的是尽可能简单明了地演示一下Alan Kay所说的“软件的麦克斯韦方程组” (Maxwell’s Equations of Software)[1]。
Lispy支持的Scheme子集的语法和语义
大多数计算机语言都有许多语法规约 (例如关键字、中缀操作符、括号、操作符优先级、点标记、分号等等)，但是，作为Lisp语言家族中的一员，Scheme所有的语法都是基于包含在括号中的、采用前缀表示的列表的。这种表示看起来似乎有些陌生，但是它具有简单一致的优点。 (一些人戏称”Lisp”是”Lots of Irritating Silly Parentheses“——“大量恼人、愚蠢的括号“——的缩写；我认为它是”Lisp Is Syntactically Pure“——“Lisp语法纯粹”的缩写。) 考虑下面这个例子：
|
|
1234567
|
/* Java */if(x.val() > 0) { z = f(a*x.val() + b);}/* Scheme */(if (> (val x) 0) (set! z (f (+ (* a (val x)) b)))) |
|
注意上面的惊叹号在Scheme中并不是一个特殊字符；它只是”set!“这个名字的一部分。(在Scheme中)只有括号是特殊字符。类似于(set! x y)这样以特殊关键字开头的列表在Scheme中被称为一个特殊形式 (special form)；Scheme的优美之处就在于我们只需要六种特殊形式，以及另外的三种语法构造——变量、常量和过程调用。
| 形式 (Form) |
语法 |
语义和示例 |
| 变量引用 |
var |
一个符号，被解释为一个变量名；其值就是这个变量的值。
示例: x |
| 常量字面值 |
number |
数字的求值结果为其本身
示例: 12 或者-3.45e+6 |
| 引用 |
(quote exp) |
返回exp的字面值；不对它进行求值。
示例：(quote (a b c)) ⇒ (a b c) |
| 条件测试 |
(if test conseq alt) |
对test进行求值；如果结果为真，那么对conseq进行求值并返回结果；否则对alt求值并返回结果。
示例：(if (< 10 20) (+ 1 1) (+ 3 3)) ⇒ 2 |
| 赋值 |
(set! varexp) |
对exp进行求值并将结果赋给var，var必须已经进行过定义 (使用define进行定义或者作为一个封闭过程的参数)。
示例：(set! x2 (* x x)) |
| 定义 |
(define varexp) |
在最内层环境 (environment) 中定义一个新的变量并将对exp表达式求值所得的结果赋给该变量。
示例：(define r 3) 或者 (define square (lambda (x) (* x x))) |
| 过程 |
(lambda(var…)exp) |
创建一个过程，其参数名字为var…，过程体为相应的表达式。
示例：(lambda (r) (* 3.141592653 (* r r))) |
| (表达式) 序列 |
(beginexp…) |
按从左到右的顺序对表达式进行求值，并返回最终的结果。
示例：(begin (set! x 1) (set! x (+ x 1)) (* x 2)) ⇒ 4 |
| 过程调用 |
(proc exp…) |
如果proc是除了if, set!, define, lambda, begin,或者quote之外的其它符号的话，那么它会被视作一个过程。它的求值规则如下：所有的表达式exp都将被求值，然后这些求值结果作为过程的实际参数来调用该相应的过程。
示例：(square 12) ⇒ 144 |
在该表中，var必须是一个符号——一个类似于x或者square这样的标识符——number必须是一个整型或者浮点型数字，其余用斜体标识的单词可以是任何表达式。exp…表示exp的0次或者多次重复。
更多关于Scheme的内容，可以参考一些优秀的书籍 (如Friedman和Fellesein, Dybvig,Queinnec, Harvey和Wright或者Sussman和Abelson)、视频 (Abelson和Sussman)、教程 (Dorai、PLT或者Neller)、或者参考手册。
语言解释器的职责
一个语言解释器包括两部分：
1、解析 (Parsing)：解析部分接受一个使用字符序列表示的输入程序，根据语言的语法规则对输入程序进行验证，然后将程序翻译成一种中间表示。在一个简单的解释器中，中间表示是一种树结构，紧密地反映了源程序中语句或表达式的嵌套结构。在一种称为编译器的语言翻译器中，内部表示是一系列可以直接由计算机 (作者的原意是想说运行时系统——译者注) 执行的指令。正如Steve Yegge所说，“如果你不明白编译器的工作方式，那么你不会明白计算机的工作方式。”Yegge介绍了编译器可以解决的8种问题 (或者解释器，又或者采用Yegge的典型的反讽式的解决方案)。 Lispy的解析器由parse函数实现。
2、执行：程序的内部表示 (由解释器) 根据语言的语义规则进行进一步处理，进而执行源程序的实际运算。(Lispy的)执行部分由eval函数实现 (注意，该函数覆盖了Python内建的同名函数)。
下面的图片描述了解释器的解释流程，(图片后的) 交互会话展示了parse和eval函数对一个小程序的操作方式：
|
|
1234567
|
>> program = \”(begin (define r 3) (* 3.141592653 (* r r)))\” >>> parse(program)[\’begin\’, [\’define\’, \’r\’, 3], [\’*\’, 3.141592653, [\’*\’, \’r\’, \’r\’]]] >>> eval(parse(program))28.274333877 |
|
这里，我们采用了一种尽可能简单的内部表示，其中Scheme的列表、数字和符号分别使用Python的列表、数字和字符串来表示。
执行: eval
下面是eval函数的定义。对于上面表中列出的九种情况，每一种都有一至三行代码，eval函数的定义只需要这九种情况：
|
|
123456789101112131415161718192021222324252627282930313233
|
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) |
|
|
|
