Haskell

Question

我正在学习 Monad Transformers 并决定使用 Monad Transformers 为类似于 Brainfuck 的简单语言（具有循环结构）编写解释器。我想在一定数量的语句后终止解释器。

这种简单的语言由能够容纳 Int 和 5 条指令输入、输出、递增、递减和循环的单个存储单元组成。当内存中的值为零时，循环终止。从列表中读取输入，类似地，输出写入另一个列表。 Increment 和 Decrement 对应地对内存做 +1 和 -1。

我正在使用 World 类型来跟踪输入、输出（流）和内存，Sum Int 来计算评估的指令数。 Except World 在某些语句后终止计算。

module Transformers where

import qualified Data.Map                      as Map
import           Data.Maybe
import           Control.Monad.State.Lazy
import           Control.Monad.Writer.Lazy
import           Control.Monad.Except


data Term = Input
  | Output
  | Increment
  | Decrement
  | Loop [Term]
  deriving (Show)

data World = World {
  inp :: [Int],
  out :: [Int],
  mem :: Int
} deriving Show

op_limit = 5

loop
  :: [Term]
  -> StateT World (WriterT (Sum Int) (Except World)) ()
  -> StateT World (WriterT (Sum Int) (Except World)) ()
loop terms sp = sp >> do
  s <- get
  if mem s == 0 then put s else loop terms (foldM (\_ t -> eval t) () terms)

limit :: StateT World (WriterT (Sum Int) (Except World)) ()
limit = do
  (s, count) <- listen get
  when (count >= op_limit) $ throwError s

tick :: StateT World (WriterT (Sum Int) (Except World)) ()
tick = tell 1

eval :: Term -> StateT World (WriterT (Sum Int) (Except World)) ()
eval Input =
  limit >> tick >> modify (\s -> s { inp = tail (inp s), mem = head (inp s) })
eval Output       = limit >> tick >> modify (\s -> s { out = mem s : out s })
eval Increment    = limit >> tick >> modify (\s -> s { mem = mem s + 1 })
eval Decrement    = limit >> tick >> modify (\s -> s { mem = mem s - 1 })
eval (Loop terms) = loop terms (void get)

type Instructions = [Term]

interp :: Instructions -> World -> Either World (World, Sum Int)
interp insts w =
  let sp = foldM (\_ inst -> eval inst) () insts
  in  runExcept (runWriterT (execStateT sp w))

ghci 中的示例运行:

*Transformers> interp [Loop [Output, Decrement]]  $ World [] [] 5
Right (World {inp = [], out = [1,2,3,4,5], mem = 0},Sum {getSum = 10})

基于计数的 monad limit 应该决定要么以当前状态失败，要么什么都不做。但我注意到 (s, count) <- listen get 中的 count 始终为零。我不明白为什么会这样。请帮助我了解哪里出了问题。

我在堆栈中对变压器的排序是否正确？是否有任何规则（非正式）来决定分层？

Answer 1

Writer monad 内的计算无法访问它们自己的累加器。更重要的是：累加器是 never 在计算运行时被强制，甚至不是 WHNF。这适用于 Writer 的严格和惰性变体——严格变体在某种意义上是严格的，与累加器无关。如果计算运行时间过长，累加器中不可避免的惰性可能是 space 泄漏的来源。

您的 limit 函数未根据 "mainline" WriterT 累加器的值进行分支。 get 操作（您正在使用 mtl）只是从 StateT 层读取状态，并且在其他层中不执行任何操作：它将 mempty 添加到其 WriterT 累加器没有抛出错误。

然后，listen 提取 get 动作的 Writer 累加器（仅 get，而不是整个计算）并将其添加到"mainline" 累加器。但是这个提取的值（元组中返回的值）将始终是 mempty，即 Sum 0!

而不是 WriterT，您可以将计数器置于 StateT 状态，正如@chi 提到的那样。您还可以使用 AccumT，它与 WriterT 非常相似，但允许您检查累加器（它还允许您使用 bang 模式将其强制为 WHNF）。

AccumT 似乎没有相应的 mtl 类型类，因此您需要进行一些提升才能使用它。

Haskell - Monad Transformers - 限制解释器中的评估次数

Haskell - Monad Transformers - Limit number of evaluations in an interpreter

monad-transformers

state-monad