内容简介：用 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"
参考资料：
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Chinese Authoritarianism in the Information Age
Routledge / 2018-2-13 / GBP 115.00
This book examines information and public opinion control by the authoritarian state in response to popular access to information and upgraded political communication channels among the citizens in co......一起来看看 《Chinese Authoritarianism in the Information Age》 这本书的介绍吧!
