什么是解释器

在我国的大学里,学生们学会的第一门编程语言一般是C语言。因此,不少同学都习惯性地将编程语言的执行过程等价为【编译-链接-执行】的过程。但实际上,编程语言还可以进行所谓的【解释执行】。

什么叫【解释执行】呢?就是计算机直接对抽象语法树(或者进一步变换的结构)进行求值,而非把抽象语法树编译成目标代码再让机器对目标代码进行求值。可以【解释执行】代码的程序就是【解释器】了。

这个时候,聪明的同学也许会想到,整个计算机系统恰恰就是目标代码的解释器

解释器的基本模型

【解释器的模型】这个词的意思是,解释器将会被实现为【什么东西】。最简单的模型是【表达式-环境】模型。这个模型指整个解释器被实现为一个eval函数,这个函数的参数为expressionenvironment,返回值为一个value.

expression自然不用多说,environment是什么东西呢?几乎所有的编程语言都有“定义变量”的功能。比如在C中,我们可以这样写:

int a = 10;
printf("%d", a);

在第二行的printf("%d", a);中,a是一个【变量】,应该被解释为10. 但expression中是没有这个信息的,我们需要一个参数来保存a->10这个信息,这就是environment.

特别地,我们这里实现的解释器不支持【有副作用的操作】,也就是说,一个【变量】不能被赋值两次。这样一来,所谓的【变量】,就可以看作一个【绑定】,即将一个符号绑定到一个值上。

我们这里使用了Essentials of Programming Languages里的LET语言作为例子,它支持以下语法:

1

可以看到,这是一个很简单的语言,一个例子程序如下:

let i = 0 in
  if zero?(i) then -(i, 1) else i

解释器的实现

Parser部分,我们采用Essentials of Programming Languages送给我们的一套系统,下面不再讨论。

解释器部分是这样实现的:

(define value-of
  (lambda(exp env)
    (cases expression exp
      [const-exp (num)
                 (num-val num)]
      [var-exp (var)
               (apply-environment env var)]
      [sub-exp (exp0 exp1)
               (num-val
                (-
                 (exp-val->num (value-of exp0 env))
                 (exp-val->num (value-of exp1 env))))]
      [zero-exp (exp0)
                (if (= (exp-val->num (value-of exp0 env)) 0)
                    (bool-val #t)
                    (bool-val #f))]
      [if-exp (exp0 exp1 exp2)
              (if (exp-val->bool (value-of exp0 env))
                  (value-of exp1 env)
                  (value-of exp2 env))]
      [let-exp (var val body)
               (let ([value (value-of val env)])
                 (value-of body
                           (extend-environment
                            env var value)))]

由于我们这里使用了Essentials of Programming Languages送的一套类型系统define-datatype,所以这里各种类型转换有点麻烦,但是总体如何求值却是很清晰的。比如说上面的的代码

let i = 0 in
  if zero?(i) then -(i, 1) else i

会被Parser变成:

(a-program
 (let-exp
  'i
  (const-exp 0)
  (if-exp
   (zero-exp (var-exp 'i))
   (sub-exp (var-exp 'i) (const-exp 1))
   (var-exp 'i))))

首先,对let-exp求值,会首先求其第二个元素,也就是这里的(const-exp 0)的值,而它的值为(num-val 0),之后,我们进行一个尾递归,对第三个元素,也即是这里的(if-exp ...)进行求值,此时的env会是:

(extend-environment empty-environment 'i (num-val 0))

在后面的求值中,i就会被解释为(num-val 0),这是通过对于val-exp的求值实现的:

[var-exp (var)
               (apply-environment env var)]

这里的(apply-environment env var)就会返回envvar所绑定的值。

头等函数的实现

scheme系语言中,头等函数一直是整个语言的核心,这也是【函数式编程】得名的原因。函数可以被随意的定义、传入、传出,是一个值。它来源于lambda表达式。

在lambda表达式中,有所谓的【自由变量】和【绑定变量】的概念,比如说:

λx.λy.xyz\lambda x.\lambda y.xyz

在这个lambda表达式中,xy都是【绑定变量】,而z是【自由变量】。具体的形式定义这里就不涉及了。我们要知道的是,在进行【函数调用】也就是所谓的$$\beta -reduction$$时,【绑定变量】最终会被【替换】为一个【实际参数】,而【自由变量】则不会如此。

这样就出现了一个问题 – 如何【处理】自由变量。

scheme将函数实现为一个【闭包】,也就是说,

(define func
  (let ((a 10))
    (lambda () a))
  )
(func) ;永远都是10

这里的func实际上是(lambda () a),而a是一个【自由变量】,scheme的设计是,【自由变量】永远会被解释为lambda表达式创建时的环境中的同名绑定。在这里,(lambda () a)创建时的环境是(a 10)a被绑定到10,所以无论func何时被调用,a的值永远为10.

要实现这个模型,我们的【函数对象】必须【保存】了三个内容:

  1. 函数体,也即一个表达式
  2. 绑定变量,或者说形式参数
  3. 被创建时的环境,这个环境中保存了所有的【自由变量】。

为了实现简单,我们这里直接把【被创建时的环境】整个拿到【函数对象】中:

(define procedure
  (λ(var body env)
    (λ(val)
      (value-of body
                (extend-environment env var val)))))
(define apply-procedure
  (λ(proc val)
    (proc val)))
[proc-exp (var body)
                (proc-val (procedure var body env))]
[apply-exp (func para)
                 (apply-procedure (exp-val->proc
                                   (value-of func env))
                                  (value-of para env))]

这样一来,我们就实现了头等函数。现在,这门语言可以说是【图灵完全】的了。