如何解读哈斯克尔的callCC？

Question

在Scheme中，从call/cc获得的连续有效地跳回初始调用/cc，并恢复保存的调用堆栈。

我刚开始学习Haskell，我正试图弄清楚如何理解callCC。这是试图从理解方案的callCC call/cc的角度来理解call/cc。callCC的实现是

callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h

据我所知，没有提到与调用堆栈有关的保存或恢复。Haskell中的callCC是如何从熟悉Scheme的call/cc的角度来解释的。

编辑:如果有人能把下面的内容翻译成Haskell，我就能理解了。

(define (f return)
  (return 2)
  3)

(display (f (lambda (x) x))) ; displays 3

(display (call-with-current-continuation f)) ; displays 2

Answer 1

它的工作原理与Scheme的调用/cc非常类似。你需要考虑到它是在Cont monad中。

实际的函数是使用ContT定义的。ContT是一个monad转换器，它允许将连续添加到其他monad中，但让我们先看看身份monad是如何工作的，并将我们限制在Cont上。

Cont r a = Cont {runCont :: (a->r)->r}

在这里，Cont r a表示一个可以计算a类型的值的函数，因为给定一个a->r类型的函数，它可以计算r类型的值。

这显然是一部单曲：

return x = Cont $ \f -> f x

(a类型值的微不足道的“计算”)

ma >>= h = Cont $ \f -> runCont ma $ \a -> runCont (h a) f

(这里是ma :: Cont r a和h :: a -> Cont r b)

( a类型ma的值计算可以转化为b类型值的计算-给定h，给定h类型的值，给定a类型的值，“知道”如何生成b类型值的计算，该值可以提供函数f :: b -> r以计算r类型的值)

在本质上，continuation是ma，>>=绑定ma及其延续来产生函数组合的延续(函数“隐藏”在ma中产生a，而函数“隐藏”在h中产生b)。这就是你要找的“堆栈”。

让我们从简化类型开始(不使用ContT)：

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a

在这里，callCC使用一个函数来构造给定延续的延续。

有一点你似乎也错过了。callCC只有在callCC之后有一个延续的情况下才有意义--也就是说，有一个延续要通过。让我们考虑一下，这是do-block的最后一行，这与说它必须与>>=绑定在一起是一样的。

callCC f >>= return "blah"

就行了。这里最重要的一点是，当您看到这个上下文时，当您看到callCC在>>=的左侧时，可以更容易地理解它的操作。

了解>>=的工作原理，并考虑到>>=的右结合性，您可以看到callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h中的h实际上是使用当前延拓构建的--它是使用出现在>>=右侧的h构建的--从callCC后面到末尾的整个do-block：

(callCC f) >>= h =
Cont $ \g -> runCont
               (cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h) $ 
               \a -> runCont (h a) g =

[reduction step: runCont (Cont x) => x]

Cont $ \g -> (\h -> runCont (f (\a -> Cont $ \_ -> h a)) h) $
               \a -> runCont (h a) g =

[(\h -> f) (\a -> ...) => f [h/(\a -> ...)] -- replace
occurrences of h with (\a -> ...)]

Cont $ \g -> runCont (f (\a -> Cont $ \_ -> (\b -> runCont (h b) g) a)) $
               \a -> runCont (h a) g =

[(\b -> runCont (h b) g) a => runCont (h a) g]

Cont $ \g -> runCont (f (\a -> Cont $ \_ -> runCont (h a) g)) $
               \a -> runCont (h a) g

您可以在这里看到，在调用传递给\_ -> runCont (h a) g的函数之后，f本质上是如何忽略延续的--“切换堆栈”，切换到调用callCC的位置的当前延续h。

(如果callCC是链中的最后一个，也可以应用类似的推理，尽管在这种情况下“当前继续”是传递给runCont的函数的说法不太清楚)

最后一点是，如果runCont (f...) h的实际调用发生在由f计算的延续内部，则实际上并不使用最后一个h，如果发生这种情况。

Answer 2

要理解callCC在Haskell中的含义，您可能希望查看它的类型，而不是它的实现：

callCC :: MonadCont m => ((a -> m b) -> m a) -> m a

这里的第一个也是最重要的是MonadCont m，这意味着callCC只在实现MonadCont的monads中工作--这可能会让您失望，但是IO不是MonadCont的一个实例。在这方面，callCC不像它在方案中那样工作。

无论如何，callCC的参数是((a -> m b) -> m a)：这是一个以(a -> m b)作为参数的计算，它是callCC正在捕获的延续。因此，让我们尝试编写一些利用callCC的东西：

import Control.Monad.Cont
fun _ = return "hi"
main = print $ runCont (callCC fun) id

这很无聊，因为我们不以任何方式使用延拓。让我们尝试不同的乐趣：

fun' escape = do escape "ahoy"
                 return "die die die"

当您运行代码时，您将看到“调用”从不返回--它已经调用了延续，就像在方案中一样。你可能知道“返回”在Haskell中不是这样的:它不是短路操作。您可以将callCC看作是一种提前终止计算的方法。

在实现级别上，cont和runCont是转换为/从延续传递样式的函数.您将希望更详细地研究延续monad，以了解它是如何工作的。试一试。http://www.haskellforall.com/2012/12/the-continuation-monad.html

(在许多方案实现中，调用/cc也不能真正通过“保存调用堆栈”来工作。如果您将一个程序转换为CPS，则调用/cc某种程度上是“免费”的。我想你可能想读eg。这个http://www.pipeline.com/~hbaker1/CheneyMTA.html讨论了CPS的一种实现方式，可以在较低的级别上实现。)