Welcome Guest ( Log In | Register )

欢迎访问本站。游客仅能浏览首页新闻、版块主题、维基条目与资源信息,需登录后方可获得内容发布、话题讨论、维基编辑与资源下载等权限。若无账号请先完成注册流程。
 
Reply to this topicStart new topic
> (如何(用Python)写一个(Lisp)解释器)【施工中】
TheFool
2017-08-08, 13:58
Post #1


Jack of all trades, master of none.
Group Icon
 295
   15

Group: Avatar
Posts: 180
Joined: 2015-12-19
Member No.: 65240



# (如何(用Python)写一个(Lisp)解释器)

- 作者:Peter Norvig
- 翻译及少量魔改:TheFool

这篇文章有两个目的:

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

我将我的这门语言以及解释器称之为Lispy。数年之前,我演示了如何用Java和Common Lisp写Scheme解释器。这次我的目标是以一种尽可能简明的方式演示Alan Kay所谓的“[*Maxwell's Equations of Software*](http://www.righto.com/2008/07/maxwells-equations-of-software-examined.html).”

为什么这很重要? [Steve Yegge说过](http://steve-yegge.blogspot.com/2007/06/rich-programmer-food.html) :“若你不知道编译器(或解释器)是怎么工作的,那你就无从得知计算机的运转原理。”

## Scheme程序的语法和语义

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

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

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

```lisp
;; 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:

```lisp
(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的同名内置函数)。

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

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

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

```
>> 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组成的列表:

```python
def tokenize(chars):
"将字符串转换成由token组成的列表。"
return chars.replace('(', ' ( ').replace(')', ' ) ').split()
```

```
>>> 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的代码:

```python
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函数的工作方式如下:

```
>>> program = "(begin (define r 10) (* pi (* r r)))"

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

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

```python
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自带的字典来实现环境,字典中的键对为{变量: 值}的形式。

```python
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的代码对比一下,是不是觉得很像?

```python
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.1592653589793
```

## 交互:来做一个REPL

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

```python
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)
```

老样子,做完以后来试试:

```
>>> 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>
```


This post has been edited by TheFool: 2017-08-08, 14:10
TOP
butten
2017-09-23, 11:41
Post #2


主物质者
Group Icon
 9
   0

Group: Primer
Posts: 1
Joined: 2014-10-23
Member No.: 61495


这里也能看到py大佬啊
TOP
Mithsul
2018-02-10, 13:17
Post #3


主物质者
Group Icon
 8
   0

Group: Primer
Posts: 2
Joined: 2013-03-02
Member No.: 53232


这里还能看到lisp大佬啊=-=
TOP
Fast ReplyReply to this topicStart new topic
 


Time is now: 2018-09-21, 02:35