用 Haskell 实现解释器

内容简介：用 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"

参考资料：

• 王垠 - 怎样写一个解释器
• Fallenwood - 怎样写一个解释器
• (How to Write a (Lisp) Interpreter (in Python))
• 知乎 - 如何写 Lisp 解释器

以上所述就是小编给大家介绍的《用 Haskell 实现解释器》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

关注我们，获取更多IT资讯^_^

查看所有标签

• 用 Haskell 实现解释器
• 怎样写一个解释器(雾)
• 怎样写一个解释器(雾)
• 设计模式-解释器模式
• Lisp解释器终于写完了
• Go 实现一个 JS 解释器

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。