程序构成-第三章

第三章: 解析计算机程序

3.1 介绍

章节1以及2描述了两个程序的基本要素之间的紧密联系: 函数以及数据. 我们已经见识过函数是如何在高阶函数中被当做数据来操作. 我们也见识过数据是如何通过消息传递以及一个对象系统而被赋予行为的. 我们也学习了用来组织大型程序的技术, 例如函数抽象, 数据抽象, 类继承, 以及一般函数. 这些关键概念构成了建立模块化, 可维护, 可扩展的程序的坚实基础.

本章节专注于编程的第三个基本要素: 程序本身. 一个Python程序只是一个文本的集合. 只有经过解析的过程我们才能基于该文本执行任何有意义的计算. 像Python这样的语言很有用, 因为我们可以定义一个_解析器_, 这是一个可以处理Python的运算以及执行过程的程序. 把这认为是编程的基本思想是毫不夸张的, 一个解析器它能确定表达式在编程语言中的含义, 它本身也就仅仅是另一个程序而已.

要体会到这一点需要转变我们自己作为程序员的印象. 我们要将自己看做是语言的设计者, 而不仅仅是经由其他人设计的语言的使用者.

3.1.1

编程语言在它们的句法结构，特征和应用领域都变化很大. 在通用的编程语言之中, 函数定义以及函数应用的结构是普遍存在的. 另一方面, 存在强大的语言, 它并不包括对象系统, 高阶函数, 赋值, 甚至是控制结构如while以及for语句. 以具有这些特性的最小子集的强大的语言作为例子, 我们将会介绍Scheme编程语言, 在本文中介绍的Scheme的子集不允许可变值.

在这个章节中, 我们学习设计一个解析器以及当它们执行程序时创建的计算过程. 为一个通用编程语言设计一个解析器的景愿可能看起来是令人畏惧的. 然而, 许多解析器具有优雅的共同结构: 两个相互递归函数. 第一个在环境中执行表达式; 第二个则是将函数作为参数来进行应用.

这些函数都是递归的, 因为它们是相互定义的: 应用一个函数需要执行它内部的表达式, 而执行一个表达式可能涉及到调用一个或者更多个函数.

3.2 函数式编程

在任何现代计算机上运行的软件都是由各种各样的编程语言编写的. 有物理语言, 如针对特定的计算机的机器语言. 这些语言关注数据的表示以及根据各个位来控制存储以及原始计算机指令. 而机器语言编程员关心的是用给定的硬件来构建系统以及在资源有限的计算机上使得实用程序能高效实施. 高阶语言, 架设在机器语言的基础上, 隐藏对数据表示为位的集合以及程序作为一系列原始计算机指令的表示的关注. 这些语言具有组合以及抽象的手段, 比如函数定义, 这适用于大规模组织的软件系统.

在这一章节中, 我们要介绍一种鼓励函数式风格的高阶编程语言, 我们学习的对象是Scheme语言的子集, 它使用的计算模型根Python的很相似, 但只使用表达式(没有声明), 专注于符号运算, 同时只使用不可变数据.

Scheme是Lisp的一种方言, 是第二古老的编程语言(在Fortran之后), 它直到今天仍然被广泛地使用. Lisp程序员社区已经持续存在成长了几十年了, 同时新的Lisp的方言比如Clojure具有一些跟现代编程语言一样增长最快的编程员社区. 为了跟上本文的例子, 你可以下载一个Scheme编辑器.

3.2.1 表达式

Scheme程序由表达式组成, 也叫做表达式或者特殊形式. 一个可调用的表达式由一个操作符表达式伴随着零或多个操作数子表达式组成, 就像Python那样. 操作数以及操作符都是包含在括号中:

1
2


(quotient 10 2)
5

Scheme只使用前缀符号. 操作符通常是一个符号, 例如+以及*. 调用表达式可以是嵌套的, 同时它们可能会跨越超过一行.

1
2
3
4
5
6
7
8


(+ (* 3 5) (- 10 6))
19
(+ (* 3
      (+ (* 2 4)
         (+ 3 5)))
   (+ (- 10 7)
      6))
57

跟在Python中那样, Scheme表达式可以是原语或者是组合. 数字文字是原语, 而调用表达式是组合形式其内包含任意子表达式. 调用表达式执行程序跟吻合Python的这些地方: 首先操作符以及操作数表达式被执行, 然后将作为运算符的值的函数应用于作为操作数的值的自变量.

在Scheme中的if表达式是一种特殊形式, 意味着虽然它看起来在句法上像是一个调用表达式, 但是它具有不同的执行过程. if表达式的一般形式是:

1

(if <predicate> <consequent> <alternative>)

为了执行一个if表达式, 解析器会开始于执行表达式的<predicate>的部分. 如果<predicate>运行后得到真值, 解析器之后就会执行<consequent>部分然后返回它的值. 否则它会执行<alternative>并返回它的值.

数值可以用熟悉的比较操作符来进行比较, 但是前缀符号也一样被用在这个例子中:

1
2


(>= 2 1)
true

布尔值#t(或者真)以及#f(或者假)在Scheme中可以以特殊的布尔形式来进行组合, 也具有跟Python类似的运行过程.

(and <e1>...<en>) 解析器一次执行一个表达式<e>, 以从左到右的顺序, 如果任何一个<e>执行的结果为假, 那么and表达式的结果就为假, 而剩下的<e>表达式都不会执行, 如果所有的<e>执行的值都为真, 那么and表达式的值就为最后一个(表达式)的值.

(or <e1>...<en>) 解析器一次执行一个表达式<e>, 以从左到右的顺序, 如果任何<e>执行得到的值为真值, 那么这个值就会作为or表达式的值被返回, 而剩下的<e>表达式不会执行. 如果所有的<e>执行都得到假值, 那么or表达式的值就为false.

(not <e>) 当<e>执行为假时not表达式的值为真, 否则的话就为假.

3.2.2 定义

值可以用define这种特殊形式来进行命名:

1
2
3


(define pi 3.14)
(* pi 2)
6.28

新的函数(在Scheme中称为过程)可以使用define的第二个特殊形式的版本来定义. 例如, 定义一个平方, 我们编写:

1

(define (square e) ( * x x))

过程定义的一般形式是:

1

(define (<name> <formal parameters>) <body>)

<name>是一个跟在环境中定义的过程相关联的符号. <formal parameters>是用在过程内部的各个名称, 这些名称与过程中的参数相对应. <body>是一个表达式, 当形式参数被实际参数替换来进行调用时它会返回过程调用后的值. <name>以及<formal parameters>以括号为分组, 就像对被定义的过程进行实际调用一样.

有了平方的定义之后, 我们现在可以在调用表达式中使用它.

1
2
3
4
5
6
7
8


(square 21)
441

(square (+ 2 5))
49

(square (square 3))
81

用户定义的函数可以接受多个参数以及包含特殊形式:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


(define (average x y)
  (/ (+ x y) 2))

(average 1 3)
2

(define (abs x)
    (if (< x 0)
        (- x)
        x))

(abs -3)
3

Scheme支持具有与Python相同的词法作用域规则的本地定义. 下面, 我们使用嵌套定义以及递归来定义一个迭代过程去计算平方根:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))
(sqrt 9)
3.00009155413138

匿名函数是使用lambda特殊形式来创建的, lambda是用来创建过程的方式跟define一样, 除了不需要为过程指定名称:

1

(lambda (<formal-parameters>) <body>)

这种结果过程跟用define创建过程用得一样多. 唯一的不同是它没有跟环境中的任何一个名称相关联. 实际上, 下面的表达式是一样的:

1
2


(define (plus4 x) (+ x 4))
(define plus4 (lambda (x) (+ x 4)))

就像任何具有过程作为它的值的表达式一样, 一个lambda表达式可以在调用表达式内用作一个操作符:

1
2


((lambda (x y z) (+ x y (square z))) 1 2 3)
12

3.2.3 复合值

数据对在Scheme中是内建的. 由于一些历史原因, 数据对是由cons这个内建函数来创建的, 同时通过car以及cdr来访问数据对中的元素:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


(define x (cons 1 2))

x
(1 . 2)

(car x)
1

(cdr x)
2

递归列表同时也使用数据对来内建到了语言当中. 一个特殊的值, 其表示为nil或者'()表示一个空的列表. 一个递归列表的值是通过放置它的元素到括号内, 并以空格分隔渲染得到的:

 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


(cons 1
      (cons 2
            (cons 3
                  (cons 4 nil))))
(1 2 3 4)

(list 1 2 3 4)
(1 2 3 4)

(define one-through-four (list 1 2 3 4))

(car one-through-four)
1

(cdr one-through-four)
(2 3 4)

(car (cdr one-through-four))
2

(cons 10 one-through-four)
(10 1 2 3 4)

(cons 5 one-through-four)
(5 1 2 3 4)

一个列表是否是空的可以使用原语null?来判断. 使用它, 我们可以为计算length以及选择元素来定义标准的序列操作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


(define (length items)
  (if (null? items)
      0
      (+ 1 (length (cdr items)))))
(define (getitem items n)
  (if (= n 0)
      (car items)
      (getitem (cdr items) (- n 1))))
(define squares (list 1 4 9 16 25))

(length squares)
5

(getitem squares 3)
16

3.2.4 符号数据

到目前为止我们使用的所有的组合数据对象最终都是由数字来组成的. Scheme的一个强项是与作为抽象符号的数据进行工作.

为了去操作符号我们的语言需要一个新的元素: 能对数据对象进行引用. 假设我们想要构造一个列表(a, b). 我们不可以通过(list a b)这样来进行构造, 因为这个表达式会构造一个具有值为a跟b的列表而不是符号a跟b本身. 在Scheme中, 我们通过在符号a以及b的前面加上一个单引号来引用符号a以及b而不是它们的值.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


(define a 1)
(define b 2)

(list a b)
(1 2)

(list 'a 'b)
(a b)

(list 'a b)
(a 2)

在Scheme中, 任何为运行的表达式都被称为引用. 这种引用概念派生自经典哲学中事物之间的区分, 例如一个狗, 它在跑动并吠叫, 同时"狗"这个名称是一个用来指定这样的事物的语言结构. 当我们用引号来使用"狗"这个名称时, 我们不是在引用某个特定的狗而是这个字本身. 在语言层面上, 引号允许我们谈及语言本身, 因此它在Scheme中是这样的:

1
2


(list 'define 'list)
(define list)

引号同样允许我们去输入一个复合对象, 使用列表的常规打印表示:

1
2
3
4
5


(car '(a b c))
a

(cdr '(a b c))
(b c)

完整的Scheme语言包含其他的特性, 例如可变操作, 向量以及映射等. 然而, 到目前为止我们介绍了的子集已经提供给我们丰富的函数式编程语言的能力来实现许多到目前为止在本文中讨论的想法.

3.2.5 龟图

本章节中, 龟形图作为Scheme的伴随实现, 来说明作为图标开发语言(另一种Lisp方言)的一部分开发环境. 这个龟开始于画布的中间, 根据程序来进行移动以及转动, 同时随着它的移动来进行画线. 虽然发明这个龟图只是用来让儿童参与编程行为, 但是它对于高级程序员来说依然是一个引人入胜的图形工具.

在课程当中的任何时候执行的Scheme程序, 这个龟都在画布中具有一个位置以及标题. 单一参数程序例如, forward以及right会修改龟的位置以及标题. 通用的程序具有缩写: forward也可以被叫做fd, 等等. 在Scheme中的特殊形式的begin允许单一表达式来包含多个子表达式. 这种形式对于多个命令的发出是有用的:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


> (define (repeat k fn) (if (> k 0)
                  (begin (fn) (repeat (- k 1) fn))
                  nil))

> (repeat 5
      (lambda () (fd 100)
            (repeat 5
                (lambda () (fd 20) (rt 144)))
            (rt 144)))
nil

龟程序的完整曲目同样也作为龟型库模块内建在了Python中.

作为最后的一个例子. Scheme可以通过以一种异常紧凑的形式来使用它的龟图表现出递归绘图. 谢尔宾斯基三角形是一种分形, 通过将每个三角形绘制为三个相邻的三角形同时在包含它们的三角形的底部的中点处具有顶点. 这可以通过Scheme程序来绘画一个有限的递归深度的图形:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


> (define (repeat k fn)
    (if (> k 0)
      (begin (fn) (repeat (- k 1) fn))
      nil))

> (define (tri fn)
    (repeat 3 (lambda () (fn) (lt 120))))

> (define (sier d k)
    (tri (lambda ()
      (if (= k 1) (fd d) (leg d k)))))

> (define (leg d k)
    (sier (/ d 2) (- k 1))
    (penup)
    (fd d)
    (pendown))

trangle过程是一个一般方法来重复绘画某个过程三次并在每次重复中进行左转. sier过程需要一个长度d以及一个递归深度k. 如果深度是1它会绘画一个空的三角形, 否则会绘画一个通过调用leg组成的三角形. leg过程会通过调用sier方法填充前一半的腿部的长度来为谢尔宾斯基三角形绘画一个单一的腿部, 然后通过移动龟图到下一个顶点. 程序penup以及pendown通过举起笔来进行移动并放下来实现停止绘画的过程. sier以及leg的相互递归调用的过程返回了它的结果:

1

> (sier 400 6)

Sierpinski’s triangle

3.3 异常

程序必须总是要注意那些可能会出现在里面的错误. 其中的例子比比皆是: 一个函数可能没有接收到参数, 但是它的设计是需要接收的, 一个必要的资源可能缺失了, 或者一个跨网络的连接可能丢失了. 当设计一个程序, 我们必须要去预见例外的情况, 这些情况可能会出现并需要适当的措施来处理它们.

这里没有唯一一个正确的方法来处理程序中出现的错误. 程序设计来提供一些持久服务比如网络服务器对于错误处理应该是强健的, 能够记录他们以作后续考虑, 同时尽可能长地继续服务新的请求. 另一方面, Python解析器通过立即终止并打印一个错误信息来处理错误, 因此程序员能够在问题出现时立即解决问题. 在任何情况下, 程序员必须对他们的程序应该如何对错误情况作出反应而作出合理的选择.

异常, 是本章的主题, 提供一个一般机制来添加错误处理逻辑到程序里面. 引发异常是一个用来打断程序正常执行流程的技术, 用来表明有异常情况, 并直接返回到程序的被指定对这种情况作出反应的封闭部分. Python解析器每次在一个表达式或者声明中检测到一个错误时都会抛出一个异常. 用户也可以用raise以及assert声明来抛出异常.

抛出异常. 每个异常都是一个继承自BaseException类的对象实例, 可能是直接继承或者间接继承. 在第一章介绍的assert声明抛出一个类型为AssertionError的异常. 一般情况下, 任何异常实例都可以用raise声明来抛出. 抛出异常的一般形式在Python文档中有描述. 最常见的是使用raise构造出一个异常实例并抛出它.

1
2
3
4


>>>　raise Exception('An error occurred');
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
Exception: an error occurred

当一个异常被抛出, 在当前代码块中将不再执行其他语句. 除非这个异常能够被处理(在下面会描述), 解析器会直接返回到解析器的交互式读写循环中, 或者如果Python是以文件参数启动的将会直接终止. 此外, 解析器会打印一个堆栈回溯, 就是一个描述异常抛出时正在执行的函数调用分支的嵌套集的文本结构块, 在上面的例子中, 文件名<stdin>表示异常通过在交互式会话中的用户被抛出而不是从文件的代码中被抛出.

处理异常. 一个异常可以通过封闭在一个try声明中被处理. 一个try声明由多个条款组成; 首先以try开始然后其他的以except开始:

1
2
3
4
5


try:
  <try suite>
except <exception class> as <name>:
  <except suite>
  ...

<try suite>在执行到try声明时总是马上执行. except条目部分则只在执行<try suite>过程当中有错误被抛出时才会执行. 没一个except语句条目指定了对特殊的异常类型来进行处理. 比如, 如果<exception class>是AssertionError, 那么任何继承自AssertionError的类在执行<try suite>项的过程当中被抛出都会被接下来的<except suite>处理. 在<except suite>内部, 识别器<name>是绑定到被抛出的异常处理对象上的, 但是这个绑定范围并不会超出<except suite>.

例如, 我们可以通过使用try声明来处理ZeroDivisionError异常, 当有异常被抛出时在异常处理里面把名称x绑定为0.

1
2
3
4
5
6
7
8


>>> try:
        x = 1/0
    except ZeroDivisionError as e:
        print('handling a', type(e))
        x = 0
handling a <class 'ZeroDivisionError'>
>>> x
0

一个try声明会处理发生在它的<try suite>里面应用的函数的函数体内的异常(不管是直接的还是间接的). 当一个异常被抛出, 控制流直接跳到距离try最近的能处理这种类型异常的<except suite>内部来.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


>>> def invert(x):
        result = 1/x  # Raises a ZeroDivisionError if x is 0
        print('Never printed if x is 0')
        return result
>>> def invert_safe(x):
        try:
            return invert(x)
        except ZeroDivisionError as e:
            return str(e)
>>> invert_safe(2)
Never printed if x is 0
0.5
>>> invert_safe(0)
'division by zero'

这个例子说明在invert里面发生异常时的print表达式未被执行, 相反控制流被转移到except项的invert_safe里面去. 并迫使ZeroDivisionError e异常通过invert_safe函数的返回变成一个人类可读的字符串: `'division by zero’.

3.3.1 异常对象

异常对象本身可以具有属性, 例如在一个assert中的错误消息状态以及关于异常被抛出时函数执行到哪里的信息. 用户定义的异常可以有额外的属性.

在第一章, 我们实现了牛顿方法来为任意函数找到零点. 接下来的例子定义了一个异常类型, 这个类型会在任何ValueError发生的时候返回在迭代改进过程当中的最佳猜测值. 当sqrt被应用到一个负数上时会抛出数学领域的错误(类型为ValueError). 这个异常会通过抛出一个IterImproveError来保存得自于牛顿法的最近的值为一个属性.

首先, 我们定义一个新的继承自Exception的类.

1
2
3


>>> class IterImproveError(Exception):
        def __init__(self, last_guess):
            self.last_guess = last_guess

接下来, 我们定义一个improve通用迭代改进算法的改进版. 这个版本能处理任意的ValueError通过抛出一个IterImproveError来保存最近的猜测值. 像之前, improve以两个函数作为参数, 没个函数取单个数字作为参数. update函数返回新的猜测值, 而done函数返回一个布尔值表明改进已经覆盖为正确的值.

1
2
3
4
5
6
7
8
9


>>> def improve(update, done, guess=1, max_updates=1000):
        k = 0
        try:
            while not done(guess) and k < max_updates:
                guess = update(guess)
                k = k + 1
            return guess
        except ValueError:
            raise IterImproveError(guess)

最后, 我们定义find_zero函数, 它会返回improve函数应用的结果到在第一章定义的在这个例子中无需修改的牛顿更新函数newton_update上. find_zero版本的函数通过返回它的最新的猜测值来处理IterImproveError.

1
2
3
4
5
6
7


>>> def find_zero(f, guess=1):
        def done(x):
            return f(x) == 0
        try:
            return improve(newton_update(f), done, guess)
        except IterImproveError as e:
            return e.last_guess

考虑一下应用find_zero来查找函数$2x^2 + \sqrt{x}$的零点. 这个函数在0处具有零点, 但是执行它在任意负数上会抛出一个ValueError. 我们第一章实现的牛顿法会抛出这个错误并不会返回任何关于零点的猜测值. 我们修订之前的实现来返回出现错误之前的猜测值.

1
2
3


>>> from math import sqrt
>>> find_zero(lambda x: 2 * x * x + sqrt(x))
-0.030211203830201594

虽然这个近似值距离正确的答案0依然很远, 但是一些应用会更喜欢这个粗略的近似值而不是ValueError.

异常是另一种用来帮助我们将程序的关注点分解为模块化部件组成的程序的技术. 在本例中, Python的异常机制允许我们分离迭代改进的逻辑, 原有的在try子句中的语句看起来并没有变化, 而处理错误的逻辑将出现在except语句中. 我们也会发现异常在用Python实现解析器的时候会是一个有用的特性.

3.4 组合语言的解析器

现在我们正在展开用一门语言来构建另一门语言的技术之旅上. 元语言抽象-建立新语言-在工程设计的所有分支上扮演着一个重要的角色. 而它对计算机编程尤为重要, 因为在程序设计中我们不仅能够定制新的语言, 还可以构建这些语言所需要的编译器. 一个语言的编译器是一个函数, 当应用这个函数到这个语言的表达式时, 执行的操作需要通过执行这些表达式来确定.

我们首先会为Scheme语言的一个有限子集定义一个解析器, 称它为计算器. 然后, 我们会为Scheme整体开发一个素描的编译器. 我们创建的编译器在某种意义上是完备的, 它允许我们编写能充分在Scheme上执行的程序. 为此, 它会为执行我们在第一章介绍的Python程序而实现相同的环境模型.

在本节中的许多模型都包含在同版的Scheme语法计算器例子中, 但是它们太复杂, 无法适应本文的格式.

3.4.1 一个Scheme语法的计算器

Scheme语法的计算器(或者简单计算器)是一种算术操作的表达语言, 用来表达加法, 减法, 乘法, 以及除法. 计算器共享Scheme的调用表达式语法以及操作行为. 加法(+)以及乘法(*)操作两者都接收任意数量的参数:

1
2
3
4
5
6
7
8


> (+ 1 2 3 4)
10
> (+)
0
> (* 1 2 3 4)
24
> (*)
1

减法(-)具有两种行为. 当只有一个参数的时候, 它将参数变成对应的相反数. 最少具有两个参数时, 它以第一个开始减去后续所有的数. 除法(/)具有相似的两个行为: 计算单个参数的乘法逆运算或者以第一个参数开始除以后续的所有参数:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


> (- 10 1 2 3)
4
> (- 3)
-3
> (/ 15 12)
1.25
> (/ 30 5 2)
3
> (/ 10)
0.1

调用一个表达式就是通过执行它的操作数的子表达式然后应用操作符到得到的结果上来执行的:

1
2


> (- 100 (* 7 (+ 8 (/ -12 -3))))
16.0

我们会在Python中实现一个计算器语言的解析器. 也就是我们会编写一个Python程序, 它会接受多行字符串然后返回把这些行当作计算器表达式来执行的结果. 如果计算器表达式不具有恰当的形式我们的解析器会抛出一个适当的异常.

3.4.2 表达式树

直到这一点之前的课程里, 表达式树一直都是概念上的实体也就是我们之前提到的对计算过程的描述; 我们此前从来没有在我们的程序中将表达式树作为数据来进行表示. 为了去编写一个解析器, 我们必须要将表达式作为数据来进行操作.

一个原始的表达式就仅仅是一个在计算器中的数字或者字符串: 要们是一个int或者float或者是一个操作符号. 所有的组合的表达式都叫做表达式. 一个调用表达式是一个Scheme列表, 这个列表的第一个元素(也就是操作符)后面会接有零个或更多的操作数表达式

Scheme对. 在Scheme中, 列表就是嵌套的数据对, 但是并不是所有的对都是列表. 为了要在Python中表示Scheme中的数据对以及列表, 我们会定义一个Pair类, 这个类跟前面章节中的Rlist类十分相似. 这个实现出现在scheme_reader.

空的列表通过用一个叫做nil的对象来表示, 这个对象是nil类的实例. 我们假设有且只有一个nil实例会被创建.

Pair类以及nil对象都是Scheme值在Python中的表示. 它们具有repr这种以Python表达式形式表示的字符串以及str这种以Scheme表达式形式表示的字符串.

1
2
3
4
5


>>> s = Pair(1, Pair(2, nil))
>>> s
Pair(1, Pair(2, nil))
>>> print(s)
(1 2)

它们实现了基础的Python序列接口包括长度和元素选择以及一个返回Scheme列表的map方法.

1
2
3
4
5
6


>>> len(s)
2
>>> s[1]
2
>>> print(s.map(lambda x: x+4))
(5 6)

嵌套列表. 嵌套对可以表示一个列表, 但是列表中的元素也可以是列表本身. 因此, 对已经足够用来表示Scheme中的表达式, 它实际上就是嵌套列表.

1
2
3
4
5
6
7


>>> expr = Pair('+', Pair(Pair('*', Pair(3, Pair(4, nil))), Pair(5, nil)))
>>> print(expr)
(+ (* 3 4) 5)
>>> print(expr.second.first)
(* 3 4)
>>> expr.second.first.second.first
3

这个例子表明所有的计算器表达式都是嵌套的Scheme列表. 我们的计算器解析器会读入一个嵌套的Scheme列表, 转换它们为表达式树表示为嵌套对实例(在下面的解析表达式一节中), 然后计算表达式树产出值(下面的执行计算器一节).

3.4.3 解析表达式

解析是从原有输入文本生成表达式树的一个过程. 一个解析器是由两个部分组成的: 一个词法分析器以及一个句法分析器. 首先, 词法分析器将输入的字符串划分成标记, 这标记是这个语言的最小句法单元如名称以及符号. 其次, 句法分析器从这一标记组成的序列中构造一个表达式树. 这个由词法分析器产生的标记序列由句法序列来消耗.

词法分析. 解析字符串的为标记序列的部分称之为标记器或者词法分析器. 在我们的实现中, 标记器是一个在scheme_tokens中被称为tokenize_line的函数. Scheme标记由空格, 括号, 点或者单引号来进行划分. 分隔符本身也是标记, 符号也数字也是如此. 标记器一个字符接着一个字符地分析一行文本, 验证符号和数字的格式.

符号化一个形式良好的计算器表达式直接划分所有的符号和分隔符, 但是需要识别多字符数字(如: 2.3)以及转换它们为数字类型.

1
2


>>> tokenize_line('(+ 1 (* 2.3 45))')
['(', '+', 1, '(', '*', 2.3, 45, ')', ')']

词法分析是一个迭代过程, 它可以应用到没一行处于隔离状态的程序输入上.

句法分析. 翻译标记序列为一个表达式树被称为_句法分析_. 句法分析是一个树递归过程. 同时它必须考虑整个表达式有可能会跨越多行.

句法分析是通过scheme_reader中的scheme_read函数来实现的. 它是树递归形式的因为分析一个标记序列通常涉及到将这些标记的子序列分析为子表达式, 它本身也一个更大的表达式树的一个分支(比如: 操作数). 递归生成的层次结构最终由运算器来消耗.

scheme_read函数预期它的输入项src是一个Buffer类型的实例, 提供权限来访问标记序列. Buffer是定义在buffer模块里面, 收集跨越多行的标记到单个的可以被语法分析的对象里面去.

1
2
3
4
5
6


>>> lines = ['(+ 1', '   (* 2.3 45))']
>>> expression = scheme_read(Buffer(tokenize_lines(lines)))
>>> expression
Pair('+', Pair(1, Pair(Pair('*', Pair(2.3, Pair(45, nil))), nil)))
>>> print(expression)
(+ 1 (* 2.3 45))

scheme_read函数首先检查各种基础的例子, 包括空输入(会抛出一个文档结束异常, 在Python中叫做EOFError)以及原始表达式. 在任何时候遇到(标记指示一个列表的开端的时候read_tail函数就会被递归调用.

read_tail函数不断地从相同的输入src中读入, 而且预期列表开始后被调用. 它的基础情况是一个空的输入(一个错误)或者一个终止列表的右括号. 它的递归调用用scheme_list函数读入列表的第一个元素, 用read_tail读入其余的项, 然后返回用Pair表示的列表.

scheme_read的这一实现可以读入形式良好的Scheme列表, 也就是我们的计算器语言所需要的所有东西. 解析点列表以及引号形式就留作一个练习.

语法错误信息实际上能够提升一个解析器的可用性. SyntaxError异常会包含描述以及遇到的问题来被抛出.

3.4.4 计算器运算

scalc模块为计算器语言实现了一个运算器. calc_eval函数接收一个表达式作为参数然后返回它的计算结果. 帮助函数simplify, reduce以及as_scheme_list的定义出现在模块里面并在下面会使用到.

对于计算器而言, 表达式只有两个合法的句法形式, 那就是数字以及调用表达式, 也就是表示良好形式的Scheme列表的Pair实例. 数字是自运算的; 他们可以从calc_eval函数中被直接返回. 调用表达式需要函数应用程序.

1
2
3
4
5
6
7
8
9


>>> def calc_eval(exp):
        """Evaluate a Calculator expression"""
        if type(exp) in (int, float):
            return simplify(exp)
        elif isinstance(exp, Pair):
            arguments = exp.second.map(calc_eval)
            return simplify(calc_apply(exp.first, arguments))
        else:
            raise TypeError(exp + ' is not a number or call expression')

调用表达式首先通过递归映射calc_eval函数到操作数的列表中来执行运算, 也就是计算arguments列表的值. 然后, 操作符在第二个函数calc_apply中被应用到这些参数上.

计算器语言简单到足够我们可以轻易地表达应用每一个操作符到单一一个函数体中的逻辑. 在calc_apply函数中, 每一个条件语句对应使用一个操作符.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


>>> def calc_apply(operator, args):
        """Apply the named operator to a list of args."""
        if not isinstance(operator, str):
            raise TypeError(str(operator) + ' is not a symbol')
        if operator == '+':
            return reduce(add, args, 0)
        elif operator == '-':
            if len(args) == 0:
                raise TypeError(operator + ' requires at least 1 argument')
            elif len(args) == 1:
                return -args.first
            else:
                return reduce(sub, args.second, args.first)
        elif operator == '*':
            return reduce(mul, args, 1)
        elif operator == '/':
            if len(args) == 0:
                raise TypeError(operator + ' requires at least 1 argument')
            elif len(args) == 1:
                return 1/args.first
            else:
                return reduce(truediv, args.second, args.first)
        else:
            raise TypeError(operator + ' is an unknown operator')

上面, 每一个判断套件都计算不同的操作符的结果或者在遇到错误的数字或者给定一个错误的参数时抛出一个恰当的TypeError. calc_apply函数可以直接使用, 但它必须被传输一系列的值来作为参数而不是一系列的操作数表达式.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


>>> calc_apply('+', as_scheme_list(1, 2, 3))
6
>>> calc_apply('-', as_scheme_list(10, 1, 2, 3))
4
>>> calc_apply('*', nil)
1
>>> calc_apply('*', as_scheme_list(1, 2, 3, 4, 5))
120
>>> calc_apply('/', as_scheme_list(40, 5))
8.0

calc_eval的作用是在将操作数子表达式作为参数传输给calc_apply之前先正确地调用calc_apply函数计算操作数子表达式的值. 因此, calc_eval可以接受嵌套表达式.

1
2
3
4


>>> print(exp)
(+ (* 3 4) 5)
>>> calc_eval(exp)
17

calc_eval的结构就是一个按类型派发的例子: 按表达式的形式. 第一个表达式的形式是一个数字, 它不需要额外的执行步骤. 通常情况下, 原始表达式不需要额外的称为自运算的运算步骤. 在我们的计算器语言中唯一的自运算表达式是数字, 但是一个一般的编程语言也可能包含字符串, 布尔值等等.

读取-求值-输出循环. 最常见的与解析器交互的方法就是通过一个读取-求值-输出循环, 或者称为REPL, 也就是一种互动模式会读取表达式, 执行它同时为用户输出结果. Python的互动会话模式就是这样的循环的一个例子.

实现一个REPL在很大程度上可以独立于它所使用的解析器. 下面的函数read_eval_print_loop缓冲来自用户的输入, 构造表达式需要使用特定的语言函数scheme_read, 然后输出应用calc_eval到这个表达式上的结果.

1
2
3
4
5
6
7


>>> def read_eval_print_loop():
        """Run a read-eval-print loop for calculator."""
        while True:
            src = buffer_input()
            while src.more_on_line:
                expression = scheme_read(src)
                print(calc_eval(expression))

这一版本的read_eval_print_loop包含所有交互式界面的必要的组件. 一个会话例子如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


> (* 1 2 3)
6
> (+)
0
> (+ 2 (/ 4 8))
2.5
> (+ 2 2) (* 3 3)
4
9
> (+ 1
     (- 23)
     (* 4 2.5))
-12

这个循环的实现并没有提供终端或者错误处理机制. 我们可以通过为用户报告错误来改进界面. 我们也可以允许用户通过发出键盘中断信号来退出循环(在UNIX上是Control-C)或者文件末尾异常(在UNIX上是Control-D). 要使这些实现可行, 我们将while声明语句套件部分放到try声明语句部分中, 第一个except条款通过抛出scheme_read来处理SyntaxError以及ValueError错误异常以及通过抛出calc_eval异常来处理TypeError以及ZeroDivisionError错误异常.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


>>> def read_eval_print_loop():
        """Run a read-eval-print loop for calculator."""
        while True:
            try:
                src = buffer_input()
                while src.more_on_line:
                    expression = scheme_read(src)
                    print(calc_eval(expression))
            except (SyntaxError, TypeError, ValueError, ZeroDivisionError) as err:
                print(type(err).__name__ + ':', err)
            except (KeyboardInterrupt, EOFError):  # <Control>-D, etc.
                print('Calculation completed.')
                return

这个循环的实现了报告错误而不用退出循环. 而不是在遇到错误的时候退出程序, 并在报告错误信息让用户修正他们的表达式后重启循环. 导入readline模块之后, 用户甚至可以使用上箭头或者 Comtrol-P 来再次调用他们之前的输入. 最后的结果是提供了一个内容丰富的错误报告界面:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


> )
SyntaxError: unexpected token: )
> 2.3.4
ValueError: invalid numeral: 2.3.4
> +
TypeError: + is not a number or call expression
> (/ 5)
TypeError: / requires exactly 2 arguments
> (/ 1 0)
ZeroDivisionError: division by zero

当我们将解析器推广到计算器以外的新语言时, 我们会看到read_eval_print_loop是一个通过一个解析函数, 一个执行函数, 以及通过try声明进行异常类型处理的参数化了的函数. 在这些更改之外, 所有的REPL都可以用相同的结构来实现.

3.5 具有抽象语言的翻译器

计算器语言提供了一种通过嵌套调用表达式来进行组合的手段. 然而, 这样没有办法去定义新的操作符, 给定数值一个名称, 或者表达一般的计算方法. 计算器并不支持任何方式的抽象. 因此, 它并不是一个特别强大或一般的编程语言. 我们现在的任务转为定义一个一般的编程语言以支持抽象用来为值绑定名称以及定义新的操作.

不像之前的章节那样会以Python源程序来呈现完整的翻译器, 这节会采用描述性的方法. 这个伴生性项目要求你来实现一个功能完善的Scheme翻译器以呈现在这里的这些想法

3.5.1 构造

这一节描述Scheme解析器的一般构造. 完成这一个项目将会在这里生产出一个在这里描述的解析器的可用实现.

一个Scheme解析器可以共享大部分的计算器解析器的结构. 一个解析器产出一个给执行器解读的表达式. 执行函数检查表达式的形式, 以及对于调用表达式它调用一个函数来将过程应用于某些参数. 执行器的区别是跟特殊形式, 用户定义函数, 以及实现的环境计算模型有关.

解析. 来自于计算器解析器的scheme_reader以及scheme_tokens模块几乎已经足够解析任何Scheme表达式. 然而, 它还没有支持引用或者点列表. 一个完整的Scheme解析器应该能够解析以下的输入表达式.

1
2


>>> read_line("(car '(1 . 2))")
Pair('car', Pair(Pair('quote', Pair(Pair(1, 2), nil)), nil))

你在实现Scheme解析器的首要任务将会是拓展scheme_reader去正确地解析点列表以及引用.

运算. Scheme每一次对一条表达式执行运算. 实现一个运算器的骨架被定义在伴生项目的scheme.py文件中. 每一个表达式从scheme_read中返回后被传递到scheme_eval函数中, 这个函数会在当前的环境env中执行一个表达式expr.

scheme_eval函数执行在Scheme中不同形式的表达式: 原语, 特殊形式, 以及调用表达式. Scheme中的组合形式可以通过检查它的首个参数来决定. 每一个特殊形式都具有它自己的运算规则. 一个简化的scheme_eval实现出现在下面. 一些错误检查以及特殊形式处理已经被移除以便让我们专注于我们的讨论. 完整的实现在伴生项目中.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


>>> def scheme_eval(expr, env):
        """Evaluate Scheme expression expr in environment env."""
        if scheme_symbolp(expr):
            return env[expr]
        elif scheme_atomp(expr):
            return expr
        first, rest = expr.first, expr.second
        if first == "lambda":
            return do_lambda_form(rest, env)
        elif first == "define":
            do_define_form(rest, env)
            return None
        else:
            procedure = scheme_eval(first, env)
            args = rest.map(lambda operand: scheme_eval(operand, env))
            return scheme_apply(procedure, args, env)

应用程序. 上面的最后一个例子调用了第二个过程, 应用程序, 它是通过函数scheme_apply来实施的. 在Scheme中的应用程序过程比在计算器中的calc_apply函数更为一般. 它应用两个类型的参数: 一个PrimtiveProcedure或者一个LambdaProcedure. 一个PrimtiveProcedure是在Python中执行的; 它具有一个被绑定到Python函数的实例属性fn. 此外, 它可能会也可能不会需要访问当前环境. 每当程序应用时这个Python函数会被调用.

一个LambdaProcedure是在Scheme中执行的. 它具有一个body属性, 这个属性是一个Scheme表达式, 每当程序应用时都会被执行. 为了将过程应用于参数列表, 表达式体会在一个新的环境中执行. 为了构建这个环境, 一个新的帧被添加到了这个环境中, 其中过程的正式参数会被绑定到实参上. 表达式体会用scheme_eval来执行.

执行/应用递归. 运行执行过程的函数, scheme_eval以及scheme_apply, 是相互递归的. 当遇到调用表达式时, 需要应用程序来执行. 应用程序使用执行过程来将操作数表达式计算为参数, 以及去执行用户定义的过程体. 这种相互递归过程的一般构造相当普遍地出现在编译器上: 执行过程是根据应用程序来定义同时应用程序又是是由执行过程来定义的.

这个递归循环结束于语言的原语. 执行过程具有最基础的情况, 那就是执行一个原始表达式. 有一些特殊的形式也是在没有递归调用的情况下由基础形式构成. 函数应用具有的基础形式就是应用一个原语过程. 这个相互递归结构由一个处理表达式形式的执行函数以及一个处理函数过程的应用函数以及它们的参数之间构成执行过程的本质.

3.5.2 环境

现在我们已经描述了Scheme解析器的结构, 我们现在要转而实现Frame类用它来形成环境. 没一个Frame实例代表一个环境, 这个环境就是一个绑定到值的符号. 一个帧具有一个绑定字典, 同时全局帧的父级帧是None.

绑定是不能够直接访问的, 而是通过两个帧方法: lookup以及define来访问. 第一个实现了第一章中对环境模型的计算描述的查找过程. 一个符号与当前帧的绑定相匹配. 如果它被找到, 那么它绑定的值会被返回. 如果找不到, 查看过程最终将进行到父级. 另一方面, define方法总是将符号绑定到当前帧中的值.

实现lookup以及使用define的就留作练习, 作为使用说明, 思考下下面的Schem程序例子:

1
2
3
4
5


(define (factorial n)
  (if (= n 0) 1 (* n (factorial (- n 1)))))

(factorial 5)
120

第一个输入表达式是一个define的特殊形式, 通过Python函数do_define_form来运行. 定义一个函数具有下面几个步骤:

检查表达式的形式来确保这是一个良好形式的Scheme列表且具有至少两个元素紧跟在define关键词后面.
分析第一个元素, 在这个例子中是Pair, 去寻找函数名称factorial以及形式参数列表(n).
创建一个具有形式参数, 函数体以及父级环境的LambdaProcedure.
在当前环境的第一个帧中绑定符号factorial到这个函数. 在这个例子中, 这个环境只由全局帧组成.

第二个输入是一个调用表达式. 传入到scheme_apply的procedure是那个刚刚创建并绑定到factorial符号的LambdaProcedure. 传入的args是只有一个元素的Scheme列表(5). 为了调用这个过程, 一个新的拓展自全局帧(factorial过程的父级环境帧)的帧会被创建, 在这个帧中, 符号n被绑定到值5. 然后, factorial的函数体会在这个环境中执行, 生成的值会被返回.

3.5.3 作为程序的数据

在思考执行Scheme表达式的程序时, 比喻类比会是更有用的. 有个关于程序意义的操作视图就是程序其实是一个抽象机器. 例如, 再次考虑计算阶乘的程序:

1
2


(define (factorial n)
    (if (= n 0) 1 (* n (factorial (- n 1)))))

我们会用一个等价的Python程序来表示, 使用一个条件表达式.

1
2


>>> def factorial(n):
        return 1 if n == 0 else factorial(n - 1)

我们可以将这个程序视为一个包含了减法, 乘法, 和相等测试的部件以及具有两位开关以及其他阶乘机器的机器的描述. (阶乘机器是无穷的, 因为它包含另一个阶乘机器在内部) 下面的图就是阶乘机器的流程图, 展示各个部分是如何连接在一起的.

factorial mechine

以类似的方式, 我们可以将Scheme解析器看作是一个非常特殊的机器, 以输入作为机器的描述. 给定这个输入, 解析器配置它自己模拟机器的描述. 例如, 如果我们为我们的执行器喂入阶乘的定义, 那这个执行器就能够计算阶乘.

从这个角度看, 我们的Scheme解析器被认为是通用机器. 当这些程序被描述成Scheme程序时, 它会模仿其他的机器(的行为). 它作为被我们的程序语言操作的数据对象跟程序语言本身的桥梁. 想象一下, 一个用户写下一个Scheme表达式输入到正在运行的Scheme解析器中. 从用户的这个角度看, 输入的一个表达式如(+ 2 2)是一个程序语言中能够进行解析的表达式. 然而, 从Scheme解析器的角度看, 表达式只是一句话, 这句话根据已经定义好的一系列规则来进行操作.

用户的程序是解析器需要的数据并不会是混乱的源头. 实际上, 某些时候能够方便地忽略掉这些区别, 并使用户有能力去明确地将数据对象作为一个表达式来执行. 在Scheme, 每当采用run程序时我们会用到这个设备. 在Python中存在的类似程序: eval函数会执行一个Python表达式而exec函数会执行一个Python声明, 因此,

1
2


>>> eval('2+2')
4

和

1
2


>>> 2+2
4

都返回相同的结果. 作为构造好的执行过程的一部分来执行表达式在动态编程语言中是一个常见且强有力的特性. 在某几种语言中, 也具有跟Scheme相同的做法, 但是在程序执行过程中构建和执行表达式的能力被证明是任何程序员的宝贵工具.