haskell - 在Haskell中实现语言解释器

Question

我想在Haskell中实现命令式语言解释器(出于教育目的)。但是，我很难为我的解释器创建正确的体系结构:我应该如何存储变量？如何实现嵌套函数调用？我应该如何实现变量作用域？如何添加使用我的语言进行调试的可能性？我应该使用monads / monad变压器/其他技术吗？等等

有人知道关于这个主题的好文章/论文/教程/资源吗？

Answer 1

如果您不熟悉编写这种处理器，我建议您暂时停止使用monad，首先将重点放在获得准系统的实现上，而不必费吹灰之力。

以下内容可以作为指南。

我假设您已经解决了要为之编写解释器的程序的源文本进行解析的问题，并且您已经拥有一些类型来捕获语言的抽象语法。我在这里使用的语言非常简单，仅由整数表达式和一些基本语句组成。

初赛

让我们首先导入一些我们将要使用的模块。

import Data.Function
import Data.List

命令式语言的本质是它具有某种形式的可变变量。在这里，变量仅由字符串表示:

type Var = String

表达方式

接下来，我们定义表达式。表达式由整数常量，变量引用和算术运算构成。

infixl 6 :+:, :-:
infixl 7 :*:, :/:

data Exp
  = C Int        -- constant                                                     
  | V Var        -- variable                                                     
  | Exp :+: Exp  -- addition                                                     
  | Exp :-: Exp  -- subtraction                                                  
  | Exp :*: Exp  -- multiplication                                               
  | Exp :/: Exp  -- division

例如，将常量2加到变量 x的表达式由 V "x" :+: C 2表示。

陈述

语句语言很少。我们有三种形式的语句:变量赋值，while循环和序列。

infix 1 :=

data Stmt
  = Var := Exp      -- assignment                                                
  | While Exp Stmt  -- loop                                                      
  | Seq [Stmt]      -- sequence

例如，用于“交换”变量 x和 y的值的语句序列可以由 Seq ["tmp" := V "x", "x" := V "y", "y" := V "tmp"]表示。

程式

程序只是一个语句。

type Prog = Stmt

专卖店

现在，让我们转到实际的解释器。在运行程序时，我们需要跟踪分配给程序中不同变量的值。这些值只是整数，作为我们“内存”的表示，我们仅使用由变量和值组成的对的列表。

type Val = Int
type Store = [(Var, Val)]

计算表达式

通过将常量映射到常量的值，查找存储中变量的值以及将算术运算映射到其Haskell对应对象来评估表达式。

eval :: Exp -> Store -> Val
eval (C n) r       = n
eval (V x) r       = case lookup x r of
                       Nothing -> error ("unbound variable `" ++ x ++ "'")
                       Just v  -> v
eval (e1 :+: e2) r = eval e1 r + eval e2 r
eval (e1 :-: e2) r = eval e1 r - eval e2 r
eval (e1 :*: e2) r = eval e1 r * eval e2 r
eval (e1 :/: e2) r = eval e1 r `div` eval e2 r

请注意，如果商店包含一个变量的多个绑定(bind)，则 lookup选择在商店中首先出现的绑定(bind)。

执行语句

尽管对表达式的求值不能更改存储的内容，但是执行一条语句实际上可能会导致存储的更新。因此，用于执行语句的函数将存储作为参数，并生成可能更新的存储。

exec :: Stmt -> Store -> Store
exec (x := e) r                    = (x, eval e r) : r
exec (While e s) r | eval e r /= 0 = exec (Seq [s, While e s]) r
                   | otherwise     = r
exec (Seq []) r                    = r
exec (Seq (s : ss)) r              = exec (Seq ss) (exec s r)

请注意，在分配的情况下，我们只需将更新后的变量的新绑定(bind) push 存储，即可有效隐藏该变量的所有先前绑定(bind)。

顶级口译员

运行程序可简化为在初始存储的上下文中执行其顶层语句。

run :: Prog -> Store -> Store
run p r = nubBy ((==) `on` fst) (exec p r)

执行该语句后，我们清除所有阴影绑定(bind)，以便我们可以轻松读取最终存储区的内容。

例

例如，考虑以下程序，该程序计算存储在变量 n中的数字的斐波那契数，并将其结果存储在变量 x中。

fib :: Prog
fib = Seq
  [ "x" := C 0
  , "y" := C 1
  , While (V "n") $ Seq
      [ "z" := V "x" :+: V "y"
      , "x" := V "y"
      , "y" := V "z"
      , "n" := V "n" :-: C 1
      ]
  ]

例如，在交互式环境中，我们现在可以使用解释器来计算第25个斐波那契数:

> lookup "x" $ run fib [("n", 25)]
Just 75025

单子(monad)释义

当然，在这里，我们正在处理一种非常简单且很小的命令式语言。随着您的语言变得越来越复杂，解释器的实现也会越来越复杂。例如，考虑添加过程时需要哪些附加功能，以及需要区分本地(基于堆栈的)存储和全局(基于堆的)存储。回到问题的那一部分，您可能确实会考虑引入monad来稍微简化解释器的实现。

在上面的示例解释器中，有两个“效果”可以被单子(monad)结构捕获:

商店的传递和更新。

在遇到运行时错误时中止运行程序。 (在上述实现中，解释器仅在发生此类错误时崩溃。)

第一个效果通常是由状态monad捕获的，第二个则是由错误monad捕获的。让我们简要地研究如何为我们的口译员做到这一点。

我们通过从标准库中仅导入一个模块来进行准备。

import Control.Monad

通过结合基本状态monad和基本误差monad，我们可以使用monad更改器(mutator)为两种效果构造一个复合monad。但是，在这里，我们只需要一次性构建复合monad。

newtype Interp a = Interp { runInterp :: Store -> Either String (a, Store) }

instance Monad Interp where
  return x = Interp $ \r -> Right (x, r)
  i >>= k  = Interp $ \r -> case runInterp i r of
               Left msg      -> Left msg
               Right (x, r') -> runInterp (k x) r'
  fail msg = Interp $ \_ -> Left msg

编辑2018年:适用的Monad建议

由于适用单子(monad)提案(AMP)，每个单子(monad)也必须是Functor和Applicative的实例。为此，我们可以添加

import Control.Applicative -- Otherwise you can't do the Applicative instance.

导入，并使Interp这样成为Functor和Applicative的实例

instance Functor Interp where
  fmap = liftM -- imported from Control.Monad

instance Applicative Interp where
  pure  = return
  (<*>) = ap -- imported from Control.Monad

编辑2018年末

为了读取和写入商店，我们引入了有效的函数 rd和 wr:

rd :: Var -> Interp Val
rd x = Interp $ \r -> case lookup x r of
         Nothing -> Left ("unbound variable `" ++ x ++ "'")
         Just v  -> Right (v, r)

wr :: Var -> Val -> Interp ()
wr x v = Interp $ \r -> Right ((), (x, v) : r)

请注意，如果变量查找失败，则 rd会生成包裹 Left的错误消息。

现在，表达式评估器的单声道版本读取为

eval :: Exp -> Interp Val
eval (C n)       = do return n
eval (V x)       = do rd x
eval (e1 :+: e2) = do v1 <- eval e1
                      v2 <- eval e2
                      return (v1 + v2)
eval (e1 :-: e2) = do v1 <- eval e1
                      v2 <- eval e2
                      return (v1 - v2)
eval (e1 :*: e2) = do v1 <- eval e1
                      v2 <- eval e2
                      return (v1 * v2)
eval (e1 :/: e2) = do v1 <- eval e1
                      v2 <- eval e2
                      if v2 == 0
                        then fail "division by zero"
                        else return (v1 `div` v2)

在 :/:的情况下，被零除会导致通过 Monad -method fail生成错误消息，对于 Interp，该错误消息减少为将消息包装在 Left -value中。

为了执行语句，我们有

exec :: Stmt -> Interp ()
exec (x := e)       = do v <- eval e
                         wr x v
exec (While e s)    = do v <- eval e
                         when (v /= 0) (exec (Seq [s, While e s]))
exec (Seq [])       = do return ()
exec (Seq (s : ss)) = do exec s
                         exec (Seq ss)

exec的类型表明，语句不会产生值，而是仅由于它们对存储的影响或它们可能触发的运行时错误而执行。

最后，在函数 run中，我们执行单子(monad)计算并处理其效果。

run :: Prog -> Store -> Either String Store
run p r = case runInterp (exec p) r of
            Left msg      -> Left msg
            Right (_, r') -> Right (nubBy ((==) `on` fst) r')

在交互式环境中，我们现在可以重新查看示例程序的解释:

> lookup "x" `fmap` run fib [("n", 25)]
Right (Just 75025)

> lookup "x" `fmap` run fib []
Left "unbound variable `n'"