haskell - 如何在Haskell中解释callCC？

在Scheme中，执行从call/cc获得的连续性实际上会跳回到该初始调用/ cc，并恢复保存的调用堆栈。

我刚刚开始学习Haskell，并且试图弄清楚如何理解callCC。试图从理解Scheme的callCC的角度理解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

最佳答案

它的工作原理与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）

（类型为a的值ma的计算可以转换为类型为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块的最后一行，这与说它必须与>>=绑定在一起的含义相同：

callCC f >>= return "blah"

会做。此处重要的一点是，当您看到此上下文位于callCC的左侧时，可以更容易地理解>>=的操作。

了解>>=的工作原理，并考虑到>>=的右相关性，您可以看到h中的callCC 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的函数调用后的继续-并“切换堆栈”，切换到调用h的位置的当前继续callCC 。

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

最后一点是，如果runCont (f...) h的实际调用发生在h计算的延续内部（如果发生的话），则h并不会真正使用最后一个f。

callcc

haskell - 如何在Haskell中解释callCC？