在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

请注意,如果存储包含变量的多个绑定,请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)

执行语句后,我们清理所有阴影绑定,以便我们可以轻松读取最终存储的内容.

例

例如,请考虑以下程序,该程序计算存储在变量中的数字的Fibonacci数,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个Fibonacci数:

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

Monadic解释

当然,在这里,我们正在处理一种非常简单和微小的命令式语言.随着您的语言变得越来越复杂,解释器的实现也将变得更加复杂.例如,考虑添加过程时需要添加的内容,并需要区分本地(基于堆栈)存储和全局(基于堆)存储.回到你问题的那一部分,你可能会考虑引入monads来简化你的解释器的实现.

在上面的示例解释器中,有两个"效果"是由monadic结构捕获的候选者:

1. 传递和更新商店.
2. 遇到运行时错误时中止运行程序.(在上面的实现中,解释器只在发生此类错误时崩溃.)

第一个效果通常由状态monad捕获,第二个效果通过错误monad捕获.让我们简要地研究一下如何为我们的翻译做这件事.

我们准备从标准库中再导入一个模块.

import Control.Monad

我们可以使用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:适用的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包装错误消息.

表达式评估器的monadic版本现在读取

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我们执行monadic计算并处理其效果.

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'"

Answer 2

我终于找到了几篇好文章:

• 通过组合Monads构建口译员
• Monad变形金刚一步一步 - 如何使用monad变换器逐步构建微型解释器
• 如何在一天内建立一个monadic解释器
• Monad变形金刚和模块化口译员