22

我想在 Haskell 中实现一个命令式语言解释器（用于教育目的）。但是我很难为我的解释器创建正确的架构：我应该如何存储变量？如何实现嵌套函数调用？我应该如何实现变量范围？如何在我的语言中添加调试可能性？我应该使用单子/单子转换器/其他技术吗？等等

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

4

2 回答 2

76

如果您是编写这种处理器的新手，我建议您暂时推迟使用 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

请注意，如果存储包含一个变量的多个绑定，则lookup选择存储中最先出现的绑定。

执行语句

虽然表达式的评估不能改变存储的内容，但执行语句实际上可能会导致存储的更新。因此，用于执行语句的函数将存储作为参数并生成可能更新的存储。

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)

请注意，在赋值的情况下，我们只需将更新变量的新绑定推送到存储区，有效地隐藏该变量的任何先前绑定。

顶级口译员

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

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

执行语句后，我们清除所有隐藏的绑定，以便我们可以轻松读取最终存储的内容。

例子

例如，考虑以下程序，该程序计算存储在变量中的数字的斐波那契数，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 来稍微简化解释器的实现。

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

  1. 店铺的流通和更新。
  2. 遇到运行时错误时中止运行程序。（在上面的实现中，当发生此类错误时，解释器会简单地崩溃。）

第一个效果通常由状态单子捕获，第二个效果由错误单子捕获。让我们简要研究一下如何为我们的解释器执行此操作。

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

import Control.Monad

我们可以使用 monad 转换器通过组合基本状态 monad 和基本错误 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 年编辑：Applicative Monad 提案

由于 Applicative Monad Proposal (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年底

对于 store 的读取和写入，我们引入了有效的函数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-wrapped 错误消息。

表达式求值器的一元版本现在为

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)

在 for 的情况下:/:，除以零会导致通过Monad-method生成错误消息fail，对于 for 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我们执行一元计算并处理其效果。

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'"
于 2013-06-06T20:28:03.843 回答
10

我终于找到了几篇好论文：

于 2013-06-07T16:56:07.077 回答