本文有两个目的: 一是讲述实现计算机语言解释器的通用方法,另外一点,着重展示如何使用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语法纯粹”的缩写。) 考虑下面这个例子:
|
|
/* 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))) |
(表达式) 序列 |
(begin exp…) |
按从左到右的顺序对表达式进行求值,并返回最终的结果。
示例:(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
函数对一个小程序的操作方式:
|
|
>> 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
函数的定义只需要这九种情况:
|
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
|
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语法纯粹”的缩写。) 考虑下面这个例子:
|
|
/* 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))) |
(表达式) 序列 |
(begin exp…) |
按从左到右的顺序对表达式进行求值,并返回最终的结果。
示例:(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 函数对一个小程序的操作方式:
|
|
>> 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 函数的定义只需要这九种情况:
|
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
|
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) | | | |