内容简介:用 Haskell 实现解释器
这篇文章主要基于王垠早年发过的文章 《怎样写一个解释器》
,我参考了 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 是静态类型,没法把动态类型列表迭代那一套搬过来,因此基本思路和王垠文章中所述类似。为了方便起见,我声明新的类型,并用字符串表示值操作符:
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` 扩展已有的环境。
type Env = [(String, Exp)] extEnv :: String -> Exp -> Env -> Env extEnv x v env = (x, v) : env
-
需要查找变量时,在当前环境中检查有无对应的键。因为
extEnv
将后绑定的变量插入到环境的头部,因此可以屏蔽先插入的同名变量,从而模拟出变量的就近原则。
运算符的计算
- 为了保持解释器主体部分简短,我将运算符的计算提取成单独的函数。其大致结构如下:
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 ...... -- other patterns
-
为了支持
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
,并计算函数的值。
解释器
- 解释器的主体代码如下,完整代码在 h2lang.hs :
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"
- 效果:
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))))) -- Value 6.0 h2 (Let (Param "x") (Value 3.9) (Op "/" (Param "x") (Value 4.32))) -- Value 0.9027778 h2 (Let (Param "x") (Value 8.75) (Op ">=" (Param "x") (Value 7))) -- Boolean True h2 (Op "==" (Boolean True) (Boolean False)) -- Boolean False h2 (Op "++" (String' "test") (String' " case")) -- String' "test case" h2 (If (Op ">=" (Value 2.3) (Value (-2.754))) (String' "Yes") (String' "No")) -- String' "Yes"
参考资料:
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。