连续位移

Question

在尝试为 ContT monad 转换器建立一些直觉时，我（也许不足为奇）发现自己很困惑。问题出在 shiftT 操作上，它似乎没有做任何有用的事情。

首先是一个简单的示例，说明如何使用它

shiftT $ \famr -> lift $ do
  a <- calculateAFromEnvironment
  famr a

famr a 可以是一些更复杂的表达式，只要它 returns 一些 m r。现在尝试解释我的直觉，即 shiftT 没有添加任何内容：

-- inline shiftT
ContT (\f2 -> evalContT ((\f1 -> lift (do
  a <- calculateAFromEnvironment
  f1 a)) f2))

-- beta reduction
ContT (\f2 -> evalContT (lift (do
  a <- calculateAFromEnvironment
  f2 a)))

-- inline evalConT
ContT (\f2 -> runContT (lift (do
  a <- calculateAFromEnvironment
  f2 a)) return)

-- inline lift
ContT (\f2 -> runContT (ContT (\f3 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= f3)) return)

-- apply runConT
ContT (\f2 -> (\f3 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= f3) return)

-- beta reduce
ContT (\f2 -> (do
  a <- calculateAFromEnvironment
  f2 a) >>= return)

-- (>>= return) is identity
ContT $ \f2 -> do
  a <- calculateAFromEnvironment
  f2 a

原来我们可以直接构建 ContT。

提问时间：有没有shift/shiftT加东西超过cont/ContT的情况？或者它们只是用来提高代码的可读性？

Answer 1

在 shiftT 和 resetT 的 searching github by Gurkenglas's advice I've discovered this very nice explanation 之后，有用法、动机和语义的例子！

这些功能非常简单。它们在 transformers 库中的定义很简单：

resetT :: (Monad m) => ContT r m r -> ContT r' m r
resetT = lift . evalContT

shiftT :: (Monad m) => ((a -> m r) -> ContT r m r) -> ContT r m a
shiftT f = ContT (evalContT . f)

但哲学和意义远远落后于一些直观的理解。所以我建议你阅读上面 link 的解释。有时很容易定义的东西实际上可以做一些复杂的事情。

根据 pugs link 上面的解释改编的文档：

shiftT

shiftT is like callCC, except that when you activate the continuation provided by shiftT, it will run to the end of the nearest enclosing resetT, then jump back to just after the point at which you activated the continuation. Note that because control eventually returns to the point after the subcontinuation is activated, you can activate it multiple times in the same block. This is unlike callCC's continuations, which discard the current execution path when activated.

See resetT for an example of how these delimited subcontinuations actually work.

resetT

Create a scope that shiftT's subcontinuations are guaranteed to eventually exit out the end of. Consider this example:
resetT $ do
    alfa
    bravo
    x <- shiftT $ \esc -> do   -- note: esc :: m Int, not a ContT
       charlie
       lift $ esc 1
       delta
       lift $ esc 2
       return 0
    zulu x
This will:

Perform alfa

Perform bravo

Perform charlie

Bind x to 1, and thus perform zulu 1

Fall off the end of resetT, and jump back to just after esc 1

Perform delta

Bind x to 2, and thus perform zulu 2

Fall off the end of resetT, and jump back to just after esc 2

Escape from the resetT, causing it to yield 0

Thus, unlike callCC's continuations, these subcontinuations will eventually return to the point after they are activated, after falling off the end of the nearest resetT.

Answer 2

你是对的 delimited continuations 可以使用无分隔符的延续来表达。所以 shiftT 和 resetT 的定义总是可以只用 ContT 来描述。但是：

定界延续来自 Oleg Kiselyov less powerful. This makes them easier to implement and also reason about for humans. (See also a lot of other interesting posts about continuations。
使用大家熟悉的shift/reset表示法，更容易理解，尤其是对于熟悉这个概念的人。

本质上，continuations 允许将程序从里到外翻转：当 shift 调用传递的函数时，由 reset 分隔的块被挤压到程序的内部。（在无限延续的情况下，整个执行上下文都被压缩在里面，这就是它们如此奇怪的原因。）

举几个例子：

import Data.List
import Control.Monad
import Control.Monad.Trans
import Control.Monad.Trans.Cont

test0 :: Integer
test0 = evalCont . reset $ do
    return 0

如果我们有 reset 而没有 shift，那只是一个纯粹的计算，没什么特别的。上面的函数只是returns0.

现在让我们同时使用它们：

test1 :: Integer
test1 = evalCont . reset $ do
    r <- shift $ \esc -> do
        let x = esc 2
            y = esc 3
        return $ x * y
    return $ 1 + r

这变得更有趣了。 shift和reset之间的代码实际上被挤进了esc的调用中，在这个简单的例子中就是return $ 1 + r。当我们调用 esc 时，将执行整个计算，其结果成为 esc 调用的结果。我们这样做了两次，所以基本上我们调用了 shift 和 reset 之间的所有内容两次。整个计算的结果是 result $ x * y，shift 调用的结果。

所以在某种意义上，shift块成为计算的外部部分，reset和shift之间的块成为计算的内部部分。

到目前为止一切顺利。但是，如果我们调用 shift 两次，就会变得更加令人生畏，就像在这个代码示例中一样：

list2 :: [(Int, String)]
list2 = evalCont . reset $ do
    x <- shift $ \yieldx ->
        return $ concatMap yieldx [1, 2, 3]
    y <- shift $ \yieldy ->
        return $ concatMap yieldy ["a", "b", "c"]
    return [(x, y)]

这是它产生的结果（对于那些想把它当作练习来理解的人来说是隐藏的）：

[(1,"a"),(1,"b"),(1,"c"),(2,"a"),(2,"b"),(2,"c"),(3,"a"),(3,"b"),(3,"c")]

现在发生的事情是程序被翻转两次:

首先，x <- shift ... 块之外的所有内容都绑定到 yieldx 调用，包括下一个 shift。而计算的结果就是x <- shift ...块的结果。
其次，当调用 yieldx 中的第二个 y <- shift ... 时，其余计算再次绑定到 yieldy 调用。这个内部计算的结果是 y <- shift ... 块的结果。

所以在 x <- shift 中，我们运行对三个参数中的每一个进行剩余的计算，并且在每个参数中，我们对其他三个参数中的每一个进行类似的操作。结果是两个列表的笛卡尔积，因为我们实际上执行了两个嵌套循环。

同样的事情适用于 shiftT 和 resetT，只是增加了副作用。例如，如果我们想调试实际发生的事情，我们可以在 IO monad 中运行上面的代码并打印调试语句：

list2' :: IO [(Int, String)]
list2' = evalContT . resetT $ do
    x <- shiftT $ \yield ->
        lift . liftM concat . mapM (\n -> print n >> yield n) $ [1, 2, 3]
    y <- shiftT $ \yield ->
        lift . liftM concat . mapM (\n -> print n >> yield n) $ ["a", "b", "c"]
    return [(x, y)]

连续位移

Cont monad shift

continuations

haskell

delimited-continuations

`shiftT`

`resetT`