这篇文章主要基于王垠早年发过的文章《怎样写一个解释器》，我参考了 Racket 版本的 R2 解释器，并用 Haskell 实现 H2Lang 的简单解释器，较 R2 的功能做了一点改进。
代码的表示
- 王垠的 R2 解释器用 Racket 实现，Racket 可以很容易地用
'(op e1 e1) 的形式表示 S-expr，并且 lambda 表达式也可以复用。Fallenwood 也用 Python 实现了一个类似的 Lisp 解释器，他将操作符和表达式均以列表的形式存储，利用了 Python 的动态类型。知乎上 “如何写 Lisp 解释器” 这个问题下，答主 Belleve 给出了 JS 实现的 Lisp 解释器，并实现了 call/cc。
- Haskell 是静态类型，没法把动态类型列表迭代那一套搬过来，因此基本思路和王垠文章中所述类似。为了方便起见，我声明新的类型，并用字符串表示值操作符：
1
2
3
4
5
6
7
8
9
10
11
| data Exp = Value Float |
Boolean Bool |
String' String |
Param String |
Error String |
Op String Exp Exp |
Lambda Exp Exp |
If Exp Exp Exp |
Let Exp Exp Exp |
Closure Exp Env |
Call Exp Exp deriving (Show)
|
- 在上面的型别声明中，提供了三种类型的数据（
Float、Bool 和 String），以及变量（Param）、错误信息（Error）、运算式（Op）、函数（Lambda）、条件表达式（If）、绑定（Let）、闭包（Closure）和函数调用（Call）。
- 出于方便考虑，只支持了二元运算符，这从
Exp 的声明中也能看出。如果想支持一元运算符，最简单的方式是增加型别的值构造子，并修改解释器的模式匹配；如果想支持多元运算符，可以绑定嵌套。
Closure 值构造子有一个参数为 Env，它用于维护闭包内表达式所处的环境的副本。
变量、值的绑定
- 有了上述型别，简单的值可以通过对应的值构造子产生，如
Value 2.34、Boolean True、String' "test" 等。
- 变量与值的绑定通过类似
Data.Map 的结构，因为值和函数、运算等都可归一为表达式 Exp，因此用一个 [(String, Exp)] 的 list 存放对当前代码区域可见的变量-值绑定，称之为环境。函数 ·extEnv` 扩展已有的环境。
1
2
3
| type Env = [(String, Exp)]
extEnv :: String -> Exp -> Env -> Env
extEnv x v env = (x, v) : env
|
- 需要查找变量时，在当前环境中检查有无对应的键。因为
extEnv 将后绑定的变量插入到环境的头部，因此可以屏蔽先插入的同名变量，从而模拟出变量的就近原则。
运算符的计算
- 为了保持解释器主体部分简短，我将运算符的计算提取成单独的函数。其大致结构如下：
1
2
3
4
5
6
| calc :: String -> Exp -> Exp -> Exp
calc "+" (Value v1') (Value v2') = Value (v1' + v2')
calc "-" (Value v1') (Value v2') = Value (v1' - v2')
calc "*" (Value v1') (Value v2') = Value (v1' * v2')
calc "/" (Value v1') (Value v2') = Value (v1' / v2')
calc ......
|
- 为了支持
String' 和 Boolean 类型的计算，calc 函数必须为每种类型均增加模式匹配。
函数声明和调用
Exp 型别有一个 Lambda 值构造子用来声明函数，解释器遇到 Lambda 表达式时，会将其转化为 Closure 值类型，即将该函数所处的环境保存下来，这么做的目的与 Lexical Scoping 和 Dynamic Scoping 有关。这一点在王垠的文章中讲的很清楚，这里简单提一下。Lexical Scoping，中文为静态域或者词法定界，Dynamic Scoping 为动态作用域，举个例子，let x = 2 in (let f = \y-> x * y in (let x = 4 in (f 3)))，如果结果为 6 就是 Lexical Scoping，结果为 12 就是 Dynamic Scoping。Dynamic Scoping 会带来很多意想不到的后果，因此要想实现静态域，就要在函数定义时保存其所处的环境，并在函数调用时从该环境中提取变量绑定。- 实现的
H2Lang 解释器会在匹配到 Lambda 表达式时将其转化为闭包：interp s@(Lambda _ _) env = Closure s env。
- 为了方便区分普通表达式和函数调用，我在
Exp 的型别中声明了 Call 值构造子，它将两个表达式组合到一起，并认定第一个表达式代表函数，第二个表达式代表某个变量或者值。因为多元函数可以用柯里化不断简化，因此解释器就不做处理了，在调用时可以通过 Call 的嵌套实现。
- 当解释器匹配到
Call e1 e2 时，根据当前环境递归调用解释器计算出 e2 最终的表达式，假设 e1 匹配了 Closure (Lambda (Param x) e) env')，则将计算出 e2 的结果绑定到变量 x，并计算函数的值。
解释器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| interp :: Exp -> Env -> Exp
interp (Param x) env = fromMaybe (Error ("undefined variable" ++ x)) (lookup x env)
interp (Value x) _ = Value x
interp (Boolean x) _ = Boolean x
interp (String' x) _ = String' x
interp s@(Lambda _ _) env = Closure s env
interp (Let (Param x) e1 e2) env = interp e2 (extEnv x (interp e1 env) env)
interp (Op op e1 e2) env = let v1 = interp e1 env
v2 = interp e2 env
in calc op v1 v2
interp (If cond e1 e2) env = let c = interp cond env
in case c of
Error _ -> Error "syntax error"
Boolean False -> interp e2 env
_ -> interp e1 env
interp (Call e1 e2) env = case v2 of
Value _ -> callExp
Boolean _ -> callExp
String' _ -> callExp
_ -> Error "syntax error"
where
v2 = interp e2 env
col = interp e1 env
callExp = case col of
(Closure (Lambda (Param x) e) env') -> interp e (extEnv x v2 env')
_ -> Error "syntax error"
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| h2 (Let (Param "x") (Value 2)
(Let (Param "f") (Lambda (Param "y") (Op "*" (Param "x") (Param "y")))
(Let (Param "x") (Value 4)
(Call (Param "f") (Value 3)))))
h2 (Let (Param "x") (Value 3.9) (Op "/" (Param "x") (Value 4.32)))
h2 (Let (Param "x") (Value 8.75) (Op ">=" (Param "x") (Value 7)))
h2 (Op "==" (Boolean True) (Boolean False))
h2 (Op "++" (String' "test") (String' " case"))
h2 (If (Op ">=" (Value 2.3) (Value (-2.754))) (String' "Yes") (String' "No"))
|
参考资料：
原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2017/02/14/talk-about-interpreter/) 、作者信息（Forec）和本声明。