原文链接:http://blog.sina.com.cn/s/blog_5d90e82f01018ge9.html
卖了好久关子了,说要写一个程序语言理论的入门读物,可是一直没有下笔。终于狠下心来兑现一部分承诺。今天就从解释器讲起吧。
解释器是比较深入的内容。虽然我试图从最基本的原理讲起,尽量让这篇文章不依赖于其它的知识,但是这篇教程并不是针对函数式编程的入门,所以我假设你已经学会了最基本的
Scheme 和函数式编程。如果你完全不了解这些,可以读一下 SICP
解释器其实不是很难的东西,可是好多人都不会写,因为在他们心目中解释器就像一个 Python 解释器那样复杂。如果你想开头就写一个 Python 解释器,那你多半永远也写不出来。你必须从最简单的语言开始,逐步增加语言的复杂度,才能构造出正确的解释器。这篇文章就是告诉你如何写出一个最简单的语言
(lambda calculus) 的解释器,并且带有基本的的算术功能,可以作为一个高级计算器来使用。
一般的编译器课程往往从语法分析(parsing)开始,折腾 lex 和 yacc
等工具。Parsing 的作用其实只是把字符串解码成程序的语法树(AST)结构。麻烦好久得到了 AST 之后,真正的困难才开始!而很多人在写完 parser 之后就已经倒下了。鉴于这个原因,这里我用“S-expression”来表示程序的语法树(AST)结构。S-expression 让我们可以直接跳过 parse 的步骤,进入关键的主题:语义(semantics)。
这里用的 Scheme 实现是 Racket。为了让程序简洁,我使用了 Racket 的模式匹配(pattern
matching)。如果你用其它的 Scheme 实现的话,恐怕要自己做一些调整。
解释器是什么
首先我们来谈一下解释器是什么。说白了解释器跟计算器差不多。它们都接受一个“表达式”,输出一个 “结果”。比如,得到 '(+ 1 2) 之后就输出 3。不过解释器的表达式要比计算器的表达式复杂一些。解释器接受的表达式叫做“程序”,而不只是简单的算术表达式。从本质上讲,每个程序都是一台机器的“描述”,而解释器就是在“模拟”这台机器的运转,也就是在进行“计算”。所以从某种意义上讲,解释器就是计算的本质。当然,不同的解释器就会带来不同的计算。
需要注意的是,我们的解释器接受的参数是一个表达式的“数据结构”,而不是一个字符串。这里我们用一种叫“S-expression”的数据结构来表示表达式。比如表达式 '(+ 1 2) 里面的内容是三个符号:'+, '1 和 '2,而不是字符串“(+
1 2)”。从结构化的数据里面提取信息很方便,而从字符串里提取信息很麻烦,而且容易出错。
递归定义 (recursive definition)
解释器一般都是“递归程序”。之所以是递归的原因,在于它处理的数据结构(程序)本身是“递归定义”的结构。算术表达式就是一个这样的结构,比如:'(* (+ 1 2) (* (- 9 6) 4))。每一个表达式里面可以含有子表达式,子表达式里面还可以有子表达式,如此无穷无尽的嵌套。看似很复杂,其实它的定义不过是:
“算术表达式”有两种形式:
看出来哪里在“递归”了吗?我们本来在定义“算术表达式”这个概念,而它的定义里面用到了“算术表达式”这个概念本身!这就构造了一个“回路”,让我们可以生成任意深度的表达式。
很多其它的数据,包括自然数,都是可以用递归来定义的。比如常见的对自然数的定义是:
“自然数”有两种形式:
看到了吗?“自然数”的定义里面出现了它自己!这就是为什么我们有无穷多个自然数。
所以可以说递归是无所不在的,甚至有人说递归就是自然界的终极原理。递归的数据总是需要递归的程序来处理。虽然递归有时候表现为另外的形式,比如循环(loop),但是“递归”这个概念比“循环”更广泛一些。有很多递归程序不能用循环来表达,比如我们今天要写的解释器就是一个递归程序,它就不能用循环来表达。所以写出正确的递归程序,对于设计任何系统都是至关重要的。其实递归的概念不限于程序设计。在数学证明里面有个概念叫“归纳法”(induction),比如“数学归纳法”(mathematical induction)。其实归纳法跟递归完全是一回事。
我们今天的解释器就是一个递归程序。它接受一个表达式,递归的调用它自己来处理各个子表达式,然后把各个递归的结果组合在一起,形成最后的结果。这有点像二叉树遍历,只不过我们的数据结构(程序)比二叉树复杂一些。
模式匹配和递归:一个简单的计算器
既然计算器是一种最简单的解释器,那么我们为何不从计算器开始写?下面就是一个计算器,它可以计算四则运算的表达式。这些表达式可以任意的嵌套,比如 '(* (+ 1 2) (+ 3 4))。我想从这个简单的例子来讲一下模式匹配(pattern matching) 和递归 (recursion) 的原理。
下面就是这个计算器的代码。它接受一个表达式,输出一个数字作为结果,正如上一节所示。
(define calc