使用 monad 转换器和 continuations 为早期过程制作一个最小的解释器 return

Question

出于学习的目的，我正在为一种带有子过程调用和 returns 的最小语言做解释器。

data P = Px Int | Ps [P] | Pc P | Pr

意思是：Px x指令x，Ps xs指令序列，Pc x调用子过程x，Pr早return。计算期间的配置只是一个 Int 并且指令 Px 递增它（只是一种可视化这个最小示例的方式，我实际上将这个东西应用到更大的语言）。因此，例如 run 0 $ Ps [Px 1, Px 2] = [1,3] 是从配置 0.

开始的完整执行跟踪

我意识到要处理早期的 return 我需要延续，所以我做了以下

runm :: Int -> P -> ([Int] -> Cont [Int] [Int]) -> Cont [Int] [Int]
runm c p k = case p of
  Px x -> return [c+x]
  Ps [] -> return []
  Ps (x:xs) -> do
    s <- runm c x k
    let c2 = if not (null s) then last s else c
        k' r = k $ s ++ r
    ss <- runm c2 (Ps xs) k'
    return $ s ++ ss
  Pc x -> callCC $ runm c x
  Pr -> k []

看来是正确的，例如：

> evalCont $ runm 0 (Ps [Px 1, Pc $ Ps [Px 2, Pr, Px 100], Px 3]) undefined
[1,3,6]

执行“1”、“2”和“3”，但正确地跳过 return 之后的“100”。

在这种情况下我有点困扰，我必须以某种方式管理 Ps 案例中的逃逸者延续，这与 return 没有太大关系。因此，我认为 writer monad 可能会有所帮助。

想法是 writer monad 将处理 "appending" 连续配置，而 cont 处理 "backward jump" of return。

由于对延续和 monad 转换器不是很熟悉，所以我并没有取得太大的成功。我什至不能真正理解我应该按什么顺序构建 monad 堆栈。

例如：

runwc :: Int -> P -> ([Int] -> ContT [Int] (Writer [Int]) [Int]) -> ContT [Int] (Writer [Int]) [Int]
runwc c p k = case p of
  Px x -> (lift $ tell [c+x]) >> return []
  Ps [] -> return []
  Ps (x:xs) -> do
    (_,s) <- lift $ listen $ evalContT $ runwc c x k
    let c2 = if not (null s) then last s else c
    runwc c2 (Ps xs) k
  Pc x -> callCC $ runwc c x
  Pr -> k []

这不是真的return:

> execWriter $ evalContT $ runwc 0 (Ps [Px 1, Pc $ Ps [Px 2, Pr, Px 100], Px 3]) undefined
[1,3,103,106]

我想我不明白为什么。

相反的顺序在我看来更有希望，但这也不起作用：

runcw :: Int -> P -> (() -> WriterT [Int] (Cont [Int]) ()) -> WriterT [Int] (Cont [Int]) ()
runcw c p k = case p of
  Px x -> tell [c+x]
  Ps [] -> return ()
  Ps (x:xs) -> do
    (_,s) <- listen $ runcw c x k
    let c2 = if not (null s) then last s else c
    runcw c2 (Ps xs) k
  Pc x -> WriterT $ callCC $ \j -> runWriterT $ do
    let k' = \_ -> WriterT $ j ((), [])
    runcw c x k'
  Pr -> k ()

return太多了：

> evalCont $ execWriterT $ runcw 0 (Ps [Px 1, Pc $ Ps [Px 2, Pr, Px 100], Px 3]) undefined
[1,4]

不同之处在于，在这里我认为我理解得更好：转义函数 j 应该使用从后续调用 runwc c x k' 收集的历史记录来调用，但它没有得到它.在 j ((), []) 中，所有内容都被丢弃，callCC return 是 Pc 情况下的空结果。

我的想法是 writer monad 会 "independently" 收集痕迹，这样即使在跳过逃逸者延续时它也会存在，但它似乎不能像这样工作，因为没有似乎是 j 获取 "past" 的一种方式（我尝试了一些来自后续 runcw 调用的递归，但它循环了）。

为了阐明我希望能够做什么，我可以使用更强大的状态 monad 来代替：

runcs :: Int -> P -> (() -> StateT [Int] (Cont [Int]) ()) -> StateT [Int] (Cont [Int]) ()
runcs c p k = case p of
  Px x -> modify (++ [c+x])
  Ps [] -> return ()
  Ps (x:xs) -> do
    s <- runcs c x k >> get
    let c2 = if not (null s) then last s else c
    runcs c2 (Ps xs) k
  Pc x -> StateT $ \s -> callCC $ \j -> flip runStateT s $ do
    let k' = \_ -> StateT $ \s' -> j ((), s')
    runcs c x k'
  Pr -> k ()

这可以正常工作

> evalCont $ execStateT (runcs 0 (Ps [Px 1, Pc $ Ps [Px 2, Pr, Px 100], Px 3]) undefined) []
[1,3,6]

最后一个解决方案使我无需处理 Ps 序列案例中的逃逸者延续，它能够陈述-get return 之前发生的事情并将其扔给 j.

问题是这显然太强大了：在任何时候都可以通过 "global" 状态访问和操作完整的执行跟踪。

是否可以通过仅使用一个Writer来获得State解决方案的优点，以便解释器的每一步都可以只附加其结果的一小部分？

我的印象是正确的签名实际上是 ContT r (Writer w) a，即使我在 WriterT w (ContT r) a 上取得了更多进步。第一个对应于 (a -> (r,w)) -> (r,w)，而第二个对应于 ((a,w) -> r) -> r，在我看来，最后一个在 a 和 w 之间具有太多的对称性，但关于这里我的头开始了爆炸程序，所以我问，因为这实际上是我第一次在琐碎的测试之外对延续做一些有意义的事情。

Answer 1

我最终得到了这个，我发现它比原始代码简单得多，将所有细节都移到了 monadic 堆栈下。（好吧，如果我们接受 "hiding the complexity" 作为 "simplifying"，至少。:-P ）

import Control.Monad.Cont
import Control.Monad.Trans.RWS

data P = Px Int | Ps [P] | Pc P | Pr

-- A shorthand
type T = ContT () (RWS () [Int] Int) ()

runwc :: P -> (() -> T) -> T
runwc p k = case p of
  Px x -> lift $ do
     c <- get
     tell [c+x]
     put (c+x)
  Ps xs -> mapM_ (flip runwc k) xs
  -- Equivalent to:
  -- Ps [] -> return ()
  -- Ps (x:xs) -> do
  --   runwc x k
  --   runwc (Ps xs) k
  Pc x -> callCC $ runwc x
  Pr -> k ()

test :: [Int]
test = trace
   where
   (_result, _counter, trace) = runRWS action () 0
   action = runContT (runwc (Ps [Px 1, Pc $ Ps [Px 2, Pr, Px 100], Px 3]) return)
            (const $ return ())

输出为

> test
[1,3,6]

符合预期。

主要的 monadic 类型 T 需要一些评论：

type T = ContT () (RWS () [Int] Int) ()
            -- 1       2  3     4    5

这里：

() 是应用延续后最终结果的类型。我选择 () 因为跟踪在 "writer" monad 中，但也可能是其他东西。
() 是只读状态的类型（RWS 的 "reader" 部分）。这很简单，因为我们不需要它。
[Int] 跟踪类型（RWS 的 "writer" 部分）。
Int 计数器的类型（RWS 的 "state" 部分）。
() monadic 操作的结果类型，将传递给延续的结果类型（可以是其他类型）。

剩下的代码应该差不多清楚了。 Px 获取状态，增加它，并记录它。 Ps 很简单：我们为块中的每个 p 调用 runwc p k。 Pc 设置当前延续。 Pr 调用集合延续。

使用 monad 转换器和 continuations 为早期过程制作一个最小的解释器 return

Using monad transformers and continuations to make a minimal interpreter for procedure early return

continuations

haskell

monad-transformers