如何解释Haskell中的callCC？

Question

在Scheme中执行从call/cc有效跳转到初始调用/ cc 获得的延续并恢复保存的调用堆栈.

我刚刚开始学习Haskell,我正在试图弄清楚如何理解callCC.这是试图callCC理解Scheme的理解call/cc.执行callCC是

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

据我所知,没有提到有关保存或恢复调用堆栈的内容.callCCHaskell的解释是如何熟悉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

要了解callCC在Haskell中的含义,您可能希望更多地查看其类型,而不是它的实现:

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,那么调用/ cc类似于"免费"的东西.我想你可能会想要阅读例如http://www.pipeline.com/~hbaker1/CheneyMTA.html,其中讨论了CPS可以在低级别实施的一种方式.)

Answer 2

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

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

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

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

它显然是一个 monad：

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 ma是给定的h，给定类型的值a，它“知道”如何产生类型值的计算b- 可以提供具有f :: b -> r计算类型值的函数r）

从本质上说，h是延续的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当您看到此上下文时，当您看到它位于 的左侧时，可以更容易地理解的操作>>=。

怎么知道>>=的作品，并要考虑到以下右键关联>>=，你可以看到，h在callCC f = cont $ \h -> runCont (f (\a -> cont $ \_ -> h a)) h实际上是在利用当前的延续建成-它是建立使用h上的右侧出现>>=-整个do从以下callCC到底行-块：

(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-的函数调用之后的延续，并“切换堆栈”，切换到调用h位置的当前延续callCC。

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

最后一点是runCont (f...) h不真正使用 this last h，如果 的实际调用h发生在由 计算的延续内部f，如果发生的话。