(完整的代码和示例,可以在这里下载。)
这个算法很简单,我们可以把它用文字描述如下:
模式匹配现在不得不插入一点 Racket 的技术细节,如果你已经学会使用 Racket 的模式匹配,可以跳过这一节。你也可以通过阅读 Racket 模式匹配的文档来代替这一节。但我建议你不要读太多文档,因为我接下去只用到很少的模式匹配功能,我把它们都解释如下。
模式匹配的形式一般是这样:
(match x [模式 结果] [模式 结果] ... ... ) 它先对 x 求值,然后根据值的结构来进行分支。每个分支由两部分组成,左边是一个模式,右边是一个结果。整个 match 语句的语义是这样:从上到下依次考虑,找到第一个可以匹配 x 的值的模式,返回它右边的结果。左边的模式在匹配之后,可能会绑定一些变量,这些变量可以在右边的表达式里使用。
模式匹配是一种分支语句,它在逻辑上就是 Scheme(Lisp) 的 cond 表达式,或者 Java 的嵌套条件语句 if ... else if ... else ...。然而跟条件语句里的“条件”不同,每条 match 语句左边的模式,可以准确而形象地描述数据结构的形状,而且可以在匹配的同时,对结构里的成员进行“绑定”。这样我们可以在右边方便的访问结构成员,而不需要使用访问函数(accessor)或者 foo.x 这样的属性语法(attribute)。而且模式可以有嵌套的子结构,所以它能够一次性的表示复杂的数据结构。
举个实在点的例子。我的代码里用了这样一个 match 表达式:
(match exp [(? number? x) x] [`(,e1 ,e2) (let ([v1 (tree-sum e1)] [v2 (tree-sum e2)]) (+ v1 v2))]) 第二行里面的 '(,e1 ,e2) 是一个模式(pattern),它被用来匹配 exp 的值。如果 exp 是 '(1 2),那么它与'(,e1 ,e2)匹配的时候,就会把 e1 绑定到 '1,把 e2 绑定到 '2。这是因为它们结构相同:
`(,e1 ,e2) '( 1 2) 说白了,模式就是一个可以含有“名字”(像 e1 和 e2)的结构,像 '(,e1 ,e2)。我们拿这个带有名字的结构,去匹配实际数据,像 '(1 2)。当它们一一对应之后,这些名字就被绑定到数据里对应位置的值。
第一行的“模式”比较特殊,(? number? x) 表示的,其实是一个普通的条件判断,相当于 (number? exp),如果这个条件成立,那么它把 exp 的值绑定到 x,这样右边就可以用 x 来指代 exp。对于无法细分的结构(比如数字,布尔值),你只能用这种方式来“匹配”。看起来有点奇怪,不过习惯了就好了。
模式匹配对解释器和编译器的书写相当有用,因为程序的语法树往往具有嵌套的结构。不用模式匹配的话,往往要写冗长,复杂,不直观的代码,才能描述出期望的结构。而且由于结构的嵌套比较深,很容易漏掉边界情况,造成错误。模式匹配可以直观的描述期望的结构,避免漏掉边界情况,而且可以方便的访问结构成员。
由于这个原因,很多源于 ML 的语言(比如 OCaml,Haskell)都有模式匹配的功能。因为 ML(Meta-Language)原来设计的用途,就是用来实现程序语言的。Racket 的模式匹配也是部分受了 ML 的启发,实际上它们的原理是一模一样的。
好了,树遍历的练习就做到这里。然而这跟解释器有什么关系呢?下面我们只把它改一下,就可以得到一个简单的解释器。
这个算法很简单,我们可以把它用文字描述如下:
- 如果输入 exp 是一个数,那就返回这个数。
- 否则如果 exp 是像 (,e1 ,e2) 这样的子树,那么分别对 e1 和 e2 递归调用 tree-sum,进行求和,得到 v1 和 v2,然后返回 v1 + v2 的和。
模式匹配现在不得不插入一点 Racket 的技术细节,如果你已经学会使用 Racket 的模式匹配,可以跳过这一节。你也可以通过阅读 Racket 模式匹配的文档来代替这一节。但我建议你不要读太多文档,因为我接下去只用到很少的模式匹配功能,我把它们都解释如下。
模式匹配的形式一般是这样:
(match x [模式 结果] [模式 结果] ... ... ) 它先对 x 求值,然后根据值的结构来进行分支。每个分支由两部分组成,左边是一个模式,右边是一个结果。整个 match 语句的语义是这样:从上到下依次考虑,找到第一个可以匹配 x 的值的模式,返回它右边的结果。左边的模式在匹配之后,可能会绑定一些变量,这些变量可以在右边的表达式里使用。
模式匹配是一种分支语句,它在逻辑上就是 Scheme(Lisp) 的 cond 表达式,或者 Java 的嵌套条件语句 if ... else if ... else ...。然而跟条件语句里的“条件”不同,每条 match 语句左边的模式,可以准确而形象地描述数据结构的形状,而且可以在匹配的同时,对结构里的成员进行“绑定”。这样我们可以在右边方便的访问结构成员,而不需要使用访问函数(accessor)或者 foo.x 这样的属性语法(attribute)。而且模式可以有嵌套的子结构,所以它能够一次性的表示复杂的数据结构。
举个实在点的例子。我的代码里用了这样一个 match 表达式:
(match exp [(? number? x) x] [`(,e1 ,e2) (let ([v1 (tree-sum e1)] [v2 (tree-sum e2)]) (+ v1 v2))]) 第二行里面的 '(,e1 ,e2) 是一个模式(pattern),它被用来匹配 exp 的值。如果 exp 是 '(1 2),那么它与'(,e1 ,e2)匹配的时候,就会把 e1 绑定到 '1,把 e2 绑定到 '2。这是因为它们结构相同:
`(,e1 ,e2) '( 1 2) 说白了,模式就是一个可以含有“名字”(像 e1 和 e2)的结构,像 '(,e1 ,e2)。我们拿这个带有名字的结构,去匹配实际数据,像 '(1 2)。当它们一一对应之后,这些名字就被绑定到数据里对应位置的值。
第一行的“模式”比较特殊,(? number? x) 表示的,其实是一个普通的条件判断,相当于 (number? exp),如果这个条件成立,那么它把 exp 的值绑定到 x,这样右边就可以用 x 来指代 exp。对于无法细分的结构(比如数字,布尔值),你只能用这种方式来“匹配”。看起来有点奇怪,不过习惯了就好了。
模式匹配对解释器和编译器的书写相当有用,因为程序的语法树往往具有嵌套的结构。不用模式匹配的话,往往要写冗长,复杂,不直观的代码,才能描述出期望的结构。而且由于结构的嵌套比较深,很容易漏掉边界情况,造成错误。模式匹配可以直观的描述期望的结构,避免漏掉边界情况,而且可以方便的访问结构成员。
由于这个原因,很多源于 ML 的语言(比如 OCaml,Haskell)都有模式匹配的功能。因为 ML(Meta-Language)原来设计的用途,就是用来实现程序语言的。Racket 的模式匹配也是部分受了 ML 的启发,实际上它们的原理是一模一样的。
好了,树遍历的练习就做到这里。然而这跟解释器有什么关系呢?下面我们只把它改一下,就可以得到一个简单的解释器。