出于学习的目的，我正在使用最少的语言进行解释程序，并带有子过程调用和返回。
data P = Px Int | Ps [P] | Pc P | Pr
含义是：Px x指令x，Ps xs指令序列，Pc x调用子过程x，Pr提前返回。计算过程中的配置只是一个Int，而指令Px将其递增（这只是可视化此最小示例的一种方式，我实际上是将此事物应用于更大的语言）。因此，例如run 0 $ Ps [Px 1, Px 2] = [1,3]是从配置0开始的完整执行跟踪。
我意识到要处理早期回报，我需要继续工作，所以我做了以下工作
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”，但在返回后正确跳过“ 100”。
在这种情况下，我不得不以某种方式管理Ps情况下的转义符连续性，这让我有些烦恼，这与返回没有太大关系。因此，我认为作家monad可能会有所帮助。
[想法是，编写程序monad将在连续处理返回的“向后跳转”时负责“追加”连续配置。
对延续和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 []
这不会真正返回：
> 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 ()
返回太多：
> 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情况，Pc返回空结果。
[我的想法是作家monad将“独立”收集踪迹，因此即使在跳过转义符延续时也将存在，但似乎无法如此工作，因为似乎没有办法使j获得“过去”（我尝试了随后的runcw调用的一些递归，但它循环了）。
为了阐明我的预期能力，我可以使用功能更强大的state 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直到返回之前发生了什么，然后将其扔到j。
问题是，这显然太强大了：在任何时候都可以通过“全局”状态来访问和操纵完整的执行跟踪。
是否可以通过仅使用State来获得Writer解决方案的优点，以便解释器的每个步骤仅可以执行其结果的一小部分？
我的印象是，即使我在使用ContT r (Writer w) a方面取得了更大的进步，正确的签名实际上还是WriterT w (ContT r) a。第一个对应于(a -> (r,w)) -> (r,w)，而第二个对应于((a,w) -> r) -> r，在我看来，这最后一个在a和w之间具有太多的对称性，但是大约在这里，我的头开始了爆炸程序，所以我问，因为这实际上是我第一次进行除琐碎测试以外的有意义的事情。
我最终完成了这一工作，我发现它比原始代码更简单，并且将所有详细信息移到了monadic堆栈下。 （好吧，如果我们至少接受“隐藏复杂性”作为“简化”。:-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]
按预期。
主要单子类型T需要说明：
type T = ContT () (RWS () [Int] Int) ()
-- 1 2 3 4 5
这里：
()是最终结果的类型，一旦应用了延续则。我选择()，因为该迹线在“ writer” monad中，但可能是其他。()是只读状态的类型（RWS的“阅读器”部分）。这是微不足道的，因为我们不需要它。[Int]跟踪的类型（RWS的“ writer”部分）。Int计数器的类型（RWS的“状态”部分）。()单项操作结果的类型，将传递给延续的结果（可能是其他）。其余代码应该或多或少清楚。 Px获取状态，将其递增并记录。 Ps很简单：我们为块中的每个runwc p k调用p。 Pc设置当前延续。 Pr调用设置的延续。