The Interpreter
Table of Contents
之前写了一篇关于 The Sllgen Parser 的文章,那是我了解 parser 的笔记,主要是关于语言实现的前端部分,现在以后端部分为主.
之所以要写这两篇文章是因为之前读 EOPL 的时候太匆忙了,书本提供的代码只是过了一遍,没有形成一个写 interpreter 该有的思路.
这里我会继续以 LET 语言做为例子来 理清楚编写 interpreter 思路,不会涉及语言特性的实现问题和基础知识,不过我之后会单独写笔记进行总结.
这篇的文章的结构就是根据 EOPL 第三版的第三章中 实现LET 的内容结构进行重排(说是重排,实际是个人总结),之所以选这一个实践做为参考,那是因为整本书的实践都是基于这一套模式进行的.
重排是因为 EOPL 第三版的内容个人觉得零散和啰嗦,不形成自己的想法是不会有实质的收获,所以我就想,作者这么做是不是想让读者多花点时间思考呢?
除了总结,我这一次还会抽空把书上的例子按照这个思路重新实践一遍,这次绝对不含糊.并且总结语言特性实现方面的笔记,最后完成练习补全笔记.
当定义好语言语法和词法规范之后,并且定义好 parser 后,对于直译型语言来说剩下的工作就是直译(interpreting)了.
个人根据 EOPL 中第三章的内容分成两大步: 定义规范 和 实现规范.其实讲 The Sllgen 的那篇笔记也是这样的.
注意,这篇笔记里面的代码引用到了 The Sllgen Parser 的代码,所以如果代码部分有什么地方不明确的请翻一翻那篇文章的 完整的例子 部分.
值的规范 (Specification of Values)
编程语言中最重要的语言规范之一就是语言可以操作哪些类型的值,也就是语言的数据类型.根据使用场合,每一个编程语言有至少两类值.
Expressed values 和 denoted values,前者用来表示表达式值,后者表示变量绑定的值,某些语言中两者还可以是一样的.
LET 语言有两种值, Int 和 Bool,并且 expressed values 和 denoted values 是一样.
ExpVal = Int + Bool DenVal = Int + Bool
因为是一样的,所以只需要定义一个 ExpVal, 然后为这些数据定义好接口,用于之后实现这些接口,
num-val : Int → ExpVal bool-val : Bool → ExpVal expval->num : ExpVal → Int expval->bool : ExpVal → Bool
并且认为,
expval->num : non-expVal-for-num -> undefined expval->bool : non-expval-for-bool -> undefined
直译本质是计算,而计算结果是 Expressed Value,并非 Denoted Value.
环境 (Environments)
为了运算包含变量的表达式,需要知道每个变量关联的值.可以把这些值储存到一个环境里面.
环境就像是数学意义上的函数,定义域(domain)是一个无限的变量集合,值域(range)就是 denoted values,就像这样
Environment : Variable → DenVal
EOPL 采用了一套缩写来表示环境,
ρ覆盖整个环境.[]表示空的环境.[var = val]ρ表示(extend-env var val ρ),也就是给环境在存入一个值为val的变量var.[var1 = val1, var2 = val2]ρ可以缩写为[var1 = val1]([var 2 = val2]ρ),等等[var1 = val1, var2 = val2, ...]表示环境里面的值,var1的值是val1,var2的值是val2,等等.
为了提高可读性,还会采用缩进,比如
[x=3] [y=7] [u=5]ρ
等同于
(extend-env 'x 3
(extend-env 'y 7
(extend-env 'u 5 ρ)))
在使用一门语言的时候一般都不能直接操作环境的,所以下面这些接口是 interpreter 内部使用的,
init-env : () → Env env? : Env → bool empty-env : () → '() empty-env? : Env → bool extend-env : Var x DenVal x Env → Env apply-env : Env x Var → DenVal
行为规范 (Specifying the Behavior)
行为规范是根据语言的句法结构来定义的接口,定义接口就是说 定义接口的输入和输出.
(句法结构在 parser 中就定义过了, the-grammar 变量, 为了节省边幅这里就不写了.)
接口分两类, constructor 和 observer,分别用于构建对象和观察对象.
Constructor
根据语言的句法结构,可以看出 Expression 有六类,每一类需要一个 constructor.
如果看的是 BNF 语法,就是每一个 production 就需要一个 constructor.
因此,
Expression 的 Constructors 如下,
const-exp : Int → Exp zero?-exp : Exp → Exp if-exp : Exp × Exp × Exp → Exp diff-exp : Exp × Exp → Exp var-exp : Var → Exp let-exp : Var × Exp × Exp → Exp
Program 只有一个 constructor,
a-program : Exp -> Program
Observer
Observer 观察对象实际上就是计算出对象的值,如果还记得 Interpreter 的本质是运算的话就能理解 observer 是重头戏.
据我观察, observer 貌似是一类 production 需要一个 observer.
所以,
Expression 需要一个 可以判断表达式类型并且计算出表达式的值(是Expressed Value,不是 Denoted Value) 的 observer,
value-of : Exp x Env → ExpVal
value-of 的行为比较复杂,所以需要写下详细的规范:
其中 => 表示变换, := 表示结果的一个子集.
(value-of (const-exp n) ρ) => (num-val n)
(value-of (var-exp var) ρ) => (apply-env ρ var)
(value-of (diff-exp exp1 exp2) ρ)
=> (num-val
(-
(expval->num (value-of exp 1 ρ))
(expval->num (value-of exp 2 ρ))))
(value-of (zero?-exp exp1) ρ)
:= (bool-val #t) if (expval->num val1) = 0
:= (bool-val #f) if (expval->num val1) ≠ 0
(value-of (if-exp exp1 exp2 exp3) ρ)
:= (value-of exp2 ρ) if (expval->bool val1) = #t
:= (value-of exp3 ρ) if (expval->bool val1) = #f
=> (if (expval->bool (value-of exp 1 ρ ))
(value-of exp 2 ρ )
(value-of exp 3 ρ ))
(value-of (let-exp var exp1 body) ρ)
=> (value-of body [var = val1] ρ)
=> (value-of body [var=(value-of exp1 ρ)] ρ)
Program 需要一个可以计算出它的值 observer,
value-of-program : Program → ExpVal
具体规范为,
(value-of-program pgm) => (value-of-program (a-program exp)) => (value-of exp ρ)
实现规范 (Implementing)
一旦定义好规范,就可以开始实现了.同样,也是分 constructor 和 observer 来做.
对于实现 constructor, parser 那篇文章就已经完成了,就不说了.
(还记得这个表达式吗: (sllgen:make-define-datatypes the-lexical-spec the-grammar) ?)
所有接口的实现就如下,
#lang racket
(require eopl
"lang.rkt")
;;;;;;;;;;;;;;;;;; Values ;;;;;;;;;;;;;;;;;;
;;; denoted values and expressed values are identical.
(define-datatype expval expval?
(num-val
(value number?))
(bool-val
(boolean boolean?)))
;; extractors:
;; expval->num : ExpVal -> Int
(define expval->num
(lambda (v)
(cases expval v
(num-val (num) num)
(else (expval-extractor-error 'num v)))))
;; expval->bool : ExpVal -> Bool
(define expval->bool
(lambda (v)
(cases expval v
(bool-val (bool) bool)
(else (expval-extractor-error 'bool v)))))
(define expval-extractor-error
(lambda (variant value)
(eopl:error 'expval-extractors "Looking for a ~s, found ~s"
variant value)))
;;;;;;;;;;;;;;;;;; Environment ;;;;;;;;;;;;;;;;;;
(define init-env
(lambda ()
(extend-env
'i (num-val 1)
(extend-env
'v (num-val 5)
(extend-env
'x (num-val 10)
(empty-env))))))
(define env?
(lambda (x)
(or (empty-env? x)
(and [pair? x]
[symbol? (car (car x))]
[expval? (cadr (car x))]
[env? (cdr x)]))))
(define empty-env (lambda () '()))
(define empty-env? null?)
(define extend-env
(lambda (sym val old-env)
(cons (list sym val) old-env)))
(define apply-env
(lambda (env search-sym)
(if (empty-env? env)
(eopl:error 'apply-env "No binding for ~s" search-sym)
(let ([sym (car (car env))]
[val (cadr (car env))]
[old-env (cdr env)])
(if (eqv? search-sym sym)
val
(apply-env old-env search-sym))))))
;;;;;;;;;;;;;;;;;; the interpreter, observers ;;;;;;;;;;;;;;;;;;
;; value-of-program : Program -> ExpVal
(define value-of-program
(lambda (pgm)
(cases program pgm
(a-program (exp1)
(value-of exp1 (init-env))))))
;; value-of : Exp * Env -> ExpVal
(define value-of
(lambda (exp env)
(cases expression exp
[const-exp (num) (num-val num)]
[var-exp (var) (apply-env env var)]
[diff-exp (exp1 exp2)
(let ((val1 (value-of exp1 env))
(val2 (value-of exp2 env)))
(let ((num1 (expval->num val1))
(num2 (expval->num val2)))
(num-val
(- num1 num2))))]
[zero?-exp (exp1)
(let ((val1 (value-of exp1 env)))
(let ((num1 (expval->num val1)))
(if (zero? num1)
(bool-val #t)
(bool-val #f))))]
[if-exp (exp1 exp2 exp3)
(let ((val1 (value-of exp1 env)))
(if (expval->bool val1)
(value-of exp2 env)
(value-of exp3 env)))]
[let-exp (var exp1 body)
(let ((val1 (value-of exp1 env)))
(value-of body
(extend-env var val1 env)))])))
;;;;;;;;;;;;;;;;;; Example ;;;;;;;;;;;;;;;;;;
(define run
(lambda (src)
(cases expval (value-of-program (scan&parse src))
[num-val (num) num]
[bool-val (bool) bool]
[else (eopl:error 'expval-extractors "Undefined")])))
(run "if zero?(0) then 2 else 0") ; => 2
(run "-(1,2)") ; => -1
(run "let a = 1 in -(10, a)") ; => 9
(run "i")