3

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

我刚开始学习 Haskell，我正试图弄清楚如何理解callCC. 那就是尝试callCC从对Scheme的理解方面来理解call/cc。的实现callCC是

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

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

编辑：也许如果有人可以将以下内容翻译成 Haskell，这将有助于我理解。

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

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

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

2 回答 2

7

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

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

这里首先也是最重要的是 MonadCont m。这意味着 callCC 只能在实现 MonadCont 的 monad 中工作——这可能会让您失望，但 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 是转换为/从 continuation-passing-style 的函数。您将需要更详细地研究 continuation monad 以了解它实际上是如何工作的。尝试例如。http://www.haskellforall.com/2012/12/the-continuation-monad.html

（在许多方案实现中， call/cc 也不能通过“保存调用堆栈”来真正起作用。如果将程序转换为 CPS，那么 call/cc 有点“免费”。我想你可能想阅读例如这个http://www.pipeline.com/~hbaker1/CheneyMTA.html，它讨论了一种可以在低级别实现 CPS 的方法。）

于 2013-12-08T09:44:59.917 回答
5

它的工作方式与 Scheme 的 call/cc 非常相似。您需要考虑到它在 Cont monad 中。

实际函数是使用 ContT 定义的。ContT 是一个 monad 转换器，它允许将延续添加到其他 monad 中，但让我们先看看它是如何与 Identity 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）

（类型值的计算ama，可以变成类型值的计算b- runCont mais given h，给定类型的值，它a“知道”如何产生类型值的计算b- 可以提供具有f :: b -> r计算类型值的函数r）

本质上，h是 的延续，ma并且>>=bindsma和它的延续产生函数组合的延续（函数“隐藏”在里面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当你看到这个上下文时，可以更容易理解 的操作，当你看到它在 的左侧时>>=。

知道如何>>=工作，并考虑到 的右关联性>>=，您可以看到hincallCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h实际上是使用当前延续构建的 - 它是使用h出现在右侧的-从 callCC 之后的行到末尾>>=的整个- 块构建的：do

(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的当前延续。hcallCC

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

最后一点是，如果实际调用发生在由 计算的延续内部，那么它runCont (f...) h并没有真正使用这个 last ，如果这种情况发生的话。hhf

于 2013-12-08T09:56:28.827 回答