内容简介：用 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"
参考资料：
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Java语言程序设计（基础篇 原书第10版）
[美]粱勇（Y.Daniel Liang） / 戴开宇 / 机械工业出版社 / 2015-7 / 85.00元
《Java语言程序设计（基础篇 原书第10版）》是Java语言的经典教材，中文版分为基础篇和进阶篇，主要介绍程序设计基础、面向对象编程、GUI程序设计、数据结构和算法、高级Java程序设计等内容。本书以示例讲解解决问题的技巧，提供大量的程序清单，每章配有大量复习题和编程练习题，帮助读者掌握编程技术，并应用所学技术解决实际应用开发中遇到的问题。您手中的这本是其中的基础篇，主要介绍了基本程序设计、语法......一起来看看 《Java语言程序设计（基础篇 原书第10版）》 这本书的介绍吧!
