一个计算器计算器也是一种解释器,只不过它只能处理算术表达式。我们的下一个目标,就是写出一个计算器。如果你给它 '(* (+ 1 2) (+ 3 4)),它就输出 21。可不要小看这个计算器,稍后我们把它稍加改造,就可以得到一个更多功能的解释器。
上面的代码里,我们利用递归遍历,对树里的数字求和。那段代码里,其实已经隐藏了一个解释器的框架。你观察一下,一个算术表达式 '(* (+ 1 2) (+ 3 4)),跟二叉树 '((1 2) (3 4)) 有什么不同?发现没有,这个算术表达式比起二叉树,只不过在每个子树结构里多出了一个操作符:一个 * 和两个 + 。它不再是一棵二叉树,而是一种更通用的树结构。
这点区别,也就带来了二叉树求和与解释器算法的区别。对二叉树进行求和的时候,在每个子树节点,我们都做加法。而对表达式进行解释的时候,在每一个子树节点,我们不一定进行加法。根据子树的“操作符”不同,我们可能会选择加,减,乘,除四种操作。
好了,下面就是这个计算器的代码。它接受一个表达式,输出一个数字作为结果。
#lang racket ; 声明用 Racket 语言 (define calc (lambda (exp) (match exp ; 分支匹配:表达式的两种情况 [(? number? x) x] ; 是数字,直接返回 [`(,op ,e1 ,e2) ; 匹配提取操作符op和两个操作数e1,e2 (let ([v1 (calc e1)] ; 递归调用 calc 自己,得到 e1 的值 [v2 (calc e2)]) ; 递归调用 calc 自己,得到 e2 的值 (match op ; 分支匹配:操作符 op 的 4 种情况 ['+ (+ v1 v2)] ; 如果是加号,输出结果为 (+ v1 v2) ['- (- v1 v2)] ; 如果是减号,乘号,除号,相似的处理 ['* (* v1 v2)] ['/ (/ v1 v2)]))]))) 你可以得到如下的结果:
(calc '(+ 1 2)) ;; => 3 (calc '(* 2 3)) ;; => 6 (calc '(* (+ 1 2) (+ 3 4))) ;; => 21 (完整的代码和示例,可以在这里下载。)
跟之前的二叉树求和代码比较一下,你会发现它们惊人的相似,因为解释器本来就是一个树遍历算法。不过你发现它们有什么不同吗?它们的不同点在于:
R2:一个很小的程序语言实现了一个计算器,现在让我们过渡到一种更强大的语言。为了方便称呼,我给它起了一个萌萌哒名字,叫 R2。R2 比起之前的计算器,只多出四个元素,它们分别是:变量,函数,绑定,调用。再加上之前介绍的算术操作,我们就得到一个很简单的程序语言,它只有5种不同的构造。用 Scheme 的语法,这5种构造看起来就像这样:
一般程序语言还有很多其它构造,可是一开头就试图去实现所有那些,只会让人糊涂。最好是把这少数几个东西搞清楚,确保它们正确之后,才慢慢加入其它元素。
这些构造的语义,跟 Scheme 里面的同名构造几乎一模一样。如果你不清楚什么是”绑定“,那你可以把它看成是普通语言里的”变量声明“。
需要注意的是,跟一般语言不同,我们的函数只接受一个参数。这不是一个严重的限制,因为在我们的语言里,函数可以被作为值传递,也就是所谓“first-class function”。所以你可以用嵌套的函数定义来表示有两个以上参数的函数。
举个例子, (lambda (x) (lambda (y) (+ x y))) 是个嵌套的函数定义,它也可以被看成是有两个参数(x 和 y)的函数,这个函数返回 x 和 y 的和。当这样的函数被调用的时候,需要两层调用,就像这样:
(((lambda (x) (lambda (y) (+ x y))) 1) 2) ;; => 3 这种做法在PL术语里面,叫做咖喱(currying)。看起来啰嗦,但这样我们的解释器可以很简单。等我们理解了基本的解释器,再实现真正的多参数函数也不迟。
另外,我们的绑定语法 (let ([x e1]) e2),比起 Scheme 的绑定也有一些局限。我们的 let 只能绑定一个变量,而 Scheme 可以绑定多个,像这样 (let ([x 1] [y 2]) (+ x y))。这也不是一个严重的限制,因为我们可以啰嗦一点,用嵌套的 let 绑定:
上面的代码里,我们利用递归遍历,对树里的数字求和。那段代码里,其实已经隐藏了一个解释器的框架。你观察一下,一个算术表达式 '(* (+ 1 2) (+ 3 4)),跟二叉树 '((1 2) (3 4)) 有什么不同?发现没有,这个算术表达式比起二叉树,只不过在每个子树结构里多出了一个操作符:一个 * 和两个 + 。它不再是一棵二叉树,而是一种更通用的树结构。
这点区别,也就带来了二叉树求和与解释器算法的区别。对二叉树进行求和的时候,在每个子树节点,我们都做加法。而对表达式进行解释的时候,在每一个子树节点,我们不一定进行加法。根据子树的“操作符”不同,我们可能会选择加,减,乘,除四种操作。
好了,下面就是这个计算器的代码。它接受一个表达式,输出一个数字作为结果。
#lang racket ; 声明用 Racket 语言 (define calc (lambda (exp) (match exp ; 分支匹配:表达式的两种情况 [(? number? x) x] ; 是数字,直接返回 [`(,op ,e1 ,e2) ; 匹配提取操作符op和两个操作数e1,e2 (let ([v1 (calc e1)] ; 递归调用 calc 自己,得到 e1 的值 [v2 (calc e2)]) ; 递归调用 calc 自己,得到 e2 的值 (match op ; 分支匹配:操作符 op 的 4 种情况 ['+ (+ v1 v2)] ; 如果是加号,输出结果为 (+ v1 v2) ['- (- v1 v2)] ; 如果是减号,乘号,除号,相似的处理 ['* (* v1 v2)] ['/ (/ v1 v2)]))]))) 你可以得到如下的结果:
(calc '(+ 1 2)) ;; => 3 (calc '(* 2 3)) ;; => 6 (calc '(* (+ 1 2) (+ 3 4))) ;; => 21 (完整的代码和示例,可以在这里下载。)
跟之前的二叉树求和代码比较一下,你会发现它们惊人的相似,因为解释器本来就是一个树遍历算法。不过你发现它们有什么不同吗?它们的不同点在于:
- 算术表达式的模式里面,多出了一个“操作符”(op)叶节点:(,op ,e1 ,e2)
- 对子树 e1 和 e2 分别求值之后,我们不是返回 (+ v1 v2),而是根据 op 的不同,返回不同的结果:
(match op ['+ (+ v1 v2)] ['- (- v1 v2)] ['* (* v1 v2)] ['/ (/ v1 v2)])
R2:一个很小的程序语言实现了一个计算器,现在让我们过渡到一种更强大的语言。为了方便称呼,我给它起了一个萌萌哒名字,叫 R2。R2 比起之前的计算器,只多出四个元素,它们分别是:变量,函数,绑定,调用。再加上之前介绍的算术操作,我们就得到一个很简单的程序语言,它只有5种不同的构造。用 Scheme 的语法,这5种构造看起来就像这样:
- 变量:x
- 函数:(lambda (x) e)
- 绑定:(let ([x e1]) e2)
- 调用:(e1 e2)
- 算术:(• e2 e2)
一般程序语言还有很多其它构造,可是一开头就试图去实现所有那些,只会让人糊涂。最好是把这少数几个东西搞清楚,确保它们正确之后,才慢慢加入其它元素。
这些构造的语义,跟 Scheme 里面的同名构造几乎一模一样。如果你不清楚什么是”绑定“,那你可以把它看成是普通语言里的”变量声明“。
需要注意的是,跟一般语言不同,我们的函数只接受一个参数。这不是一个严重的限制,因为在我们的语言里,函数可以被作为值传递,也就是所谓“first-class function”。所以你可以用嵌套的函数定义来表示有两个以上参数的函数。
举个例子, (lambda (x) (lambda (y) (+ x y))) 是个嵌套的函数定义,它也可以被看成是有两个参数(x 和 y)的函数,这个函数返回 x 和 y 的和。当这样的函数被调用的时候,需要两层调用,就像这样:
(((lambda (x) (lambda (y) (+ x y))) 1) 2) ;; => 3 这种做法在PL术语里面,叫做咖喱(currying)。看起来啰嗦,但这样我们的解释器可以很简单。等我们理解了基本的解释器,再实现真正的多参数函数也不迟。
另外,我们的绑定语法 (let ([x e1]) e2),比起 Scheme 的绑定也有一些局限。我们的 let 只能绑定一个变量,而 Scheme 可以绑定多个,像这样 (let ([x 1] [y 2]) (+ x y))。这也不是一个严重的限制,因为我们可以啰嗦一点,用嵌套的 let 绑定: