haskell - 呼叫/抄送实施？

Question

我试图找出 call/cc 是如何实现的。我发现的最好的是这个 Haskell 片段：

callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

Cont尽管由于and ，这并不像我想要的那么简单runCont。我还找到了关于它的功能的描述，尽管从来没有实际代码那么清晰。

那么它是如何以最简单的形式实现的呢？我用 Scheme 和 Haskell 标记它，因为这是我更喜欢的两种语言。

score 88 · Accepted Answer

“实施call/cc”在您正在工作的层上并没有真正意义；如果您可以call/cc用一种语言实现，那仅意味着它具有至少与call/cc. 在语言本身的层面上，call/cc基本上是一个原始的控制流操作符，就像某种形式的分支必须是一样的。

当然，你可以用call/cc没有它的语言来实现一种语言；这是因为它处于较低的水平。您正在以特定方式翻译语言的结构，并安排此翻译以便您可以实施call/cc；即，一般来说，延续传递样式（尽管对于 C 中的非可移植实现，您也可以直接复制堆栈；稍后我将更深入地介绍延续传递样式）。这并没有真正对call/cc 自身提供任何深刻的洞察力——洞察力在于你使之成为可能的模型。最重要的是，call/cc它只是一个包装器。

现在，Haskell 没有公开延续的概念。它会破坏参考透明度，并限制可能的实施策略。Cont就像所有其他 monad 一样，在 Haskell 中实现，您可以将其视为一种语言模型，该语言具有使用延续传递样式的延续，就像 list monad 模型非确定性一样。

callCC从技术上讲，如果您只是删除和的应用程序Cont，该定义确实类型runCont。但这不会帮助你理解它在Contmonad 的上下文中是如何工作的，所以让我们看看它的定义。（这个定义不是当前 Monad Transformer Library 中使用的定义，因为其中的所有 monad 都是在它们的转换器版本之上构建的，但它与片段的使用相匹配Cont（仅适用于旧版本），并且大大简化了事情。）

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

好的，Cont r ajust 也是如此(a -> r) -> r，runCont让我们从一个Cont r a值中获取这个函数。很简单。但是这是什么意思？

Cont r a是具有最终结果r和结果的连续传递计算a。最终结果是什么意思？好吧，让我们runCont更明确地写出 out 的类型：

runCont :: Cont r a -> (a -> r) -> r

所以，正如我们所见，“最终结果”是我们最终得到的价值runCont。现在，我们如何建立计算Cont？monad 实例很有启发性：

instance Monad (Cont r) where
  return a = Cont (\k -> k a)
  m >>= f = Cont (\k -> runCont m (\result -> runCont (f result) k))

好吧，如果您已经知道它的含义，那将很有启发性。关键是当你写的时候Cont (\k -> ...)，剩下的k就是计算——它期望你给它一个值a，然后会给你计算的最终结果（类型r，记住），然后你可以将其用作你自己的返回值，因为你的返回类型r也是。哇！当我们使用运行Cont计算时runCont，我们只是指定了最终k结果——产生最终结果的计算的“顶层”。

这个“其余的计算”叫什么？延续，因为它是计算的延续！

(>>=)实际上很简单：我们在左边运行计算，给它我们自己的剩余计算。剩下的计算只是将值输入f，它会产生自己的计算。我们运行该计算，将其输入到我们已经给出的组合操作的其余计算中。通过这种方式，我们可以将计算线程化Cont：

computeFirst >>= \a ->
computeSecond >>= \b ->
return (a + b)

或者，用更熟悉的do表示法：

do a <- computeFirst
   b <- computeSecond
   return (a + b)

然后我们可以运行这些计算runCont——大多数时候，类似的东西runCont foo id会很好地工作，将foo具有相同结果和最终结果类型的 a 转换为它的结果。

到现在为止还挺好。现在让我们让事情变得混乱。

wtf :: Cont String Int
wtf = Cont (\k -> "eek!")

aargh :: Cont String Int
aargh = do
  a <- return 1
  b <- wtf
  c <- return 2
  return (a + b + c)

这里发生了什么？！wtf是Cont具有最终结果String和结果的计算Int，但Int看不到。

当我们运行时会发生什么aargh，比如说 with runCont aargh show— 即运行计算，并将show其Int结果作为 aString来产生最终结果？

我们"eek!"回来。

还记得k“计算的其余部分”如何吗？我们所做的wtf是巧妙地不调用它，而是提供我们自己的最终结果——然后就变成了，嗯，最终的！

这只是延续可以做的第一件事。类似的东西Cont (\k -> k 1 + k 2)运行其余的计算，就好像它返回 1，然后又好像它返回 2，然后将两个最终结果加在一起！延续基本上允许表达任意复杂的非本地控制流，使它们既强大又令人困惑。事实上，延续是如此普遍，以至于在某种意义上，每个单子都是Cont. 实际上，您(>>=)通常可以将其视为使用一种延续传递风格：

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

第二个参数是一个延续，获取第一个计算的结果并返回要运行的其余计算。

但我仍然没有回答这个问题：这是怎么回事callCC？好吧，它使用当前的延续调用您提供的函数。但是等一下，这不是我们已经在做的Cont吗？是的，但比较类型：

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

嗯。你看，问题Cont是我们不能从我们传递的函数内部对动作进行排序——我们只是r以纯粹的方式产生结果。callCC让延续被访问、传递，并且通常只是从内部 Cont计算中被弄乱。当我们有

do a <- callCC (\cc -> ...)
   foo ...

你可以想象cc一个函数，我们可以在函数内部使用任何值调用它，以使其成为callCC (\cc -> ...)计算本身的返回值。或者，当然，我们可以正常返回一个值，但首先调用callCC会有点毫无意义:)

至于b那里的神秘，那只是因为你可以用它cc foo来代替你想要的任何类型的计算，因为它逃脱了正常的控制流，就像我说的那样，立即将它用作整个callCC (\cc -> ...). 因此，由于它永远不必实际产生一个值，它可以返回一个它想要的任何类型的值。偷偷摸摸！

这将我们带到了实际的实现中：

callCC f = Cont (\k -> runCont (f (\a -> Cont (\_ -> k a))) k)

首先，我们得到整个其余的计算，并调用它k。但这f (\a -> Cont (\_ -> k a))部分是关于什么的？好吧，我们知道lambdaf接受一个类型的值(a -> Cont r b)，这就是 lambda ——一个接受一个值作为 ` 的结果的函数callCC f，并返回一个Cont忽略其延续并仅通过返回该值的计算k——“rest的计算”的角度callCC f。好的，所以该f调用的结果是另一个Cont计算，我们需要提供一个延续才能运行。我们只是再次传递相同的延续，因为如果一切正常，我们希望计算返回的任何内容都是我们的返回值并正常继续。（确实，传递另一个值不会使感觉——它是“当前延续的调用”，而不是“与你实际运行我的调用不同的延续调用”。）

总而言之，我希望你觉得这篇文章很长很有启发性。延续非常强大，但要了解它们的工作原理可能需要很多时间。我建议玩弄Cont（您必须调用cont它才能使当前的 mtl 工作）并弄清楚如何获得结果以了解控制流。

推荐继续阅读：

所有单子之母（以前链接过）
Haskell Wikibook的延续传递风格章节
快速而肮脏的控制重新反转（显示“真实世界”的延续使用）
Oleg Kiselyov 网站的延续和定界控制部分

score 13 · Accepted Answer

call/cc实现起来很简单。困难的部分是建立可以实施的环境。

我们必须首先定义一个持续传递风格 (CPS) 的执行环境。在这种环境下，您的函数（或类似函数的东西）不会直接返回值；相反，它们被传递了一个函数，该函数代表计算中的“下一步”——“延续”——然后它们将结果传递到那里。在 Haskell 中，这看起来像这样：

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

正如你所看到的，一个Contmonad 动作实际上是一个函数，它接受一个 continuation (a -> r)，将结果传递a给 continuation，然后返回的最终结果r，它只是将其传递给它的调用者（即，一个monadCont动作应该尾部调用延续）。runCont只需将其从 newtype 包装器中取出 - 您也可以将其视为调用具有某些特定延续的操作，如runCont someAction someContinuation.

然后我们可以把它变成一个 monad：

instance Monad (Cont r) where
    return x = Cont $ \cc -> cc x
    (Cont f) (>>=) g = Cont $ \cc -> f (\r -> runCont (g r) cc)

如您所见，return只需获取一个 continuationcc并将其值传递给 continuation。(>>=)有点棘手，它必须f使用一个延续调用，然后调用g，取回动作，然后将外部延续传递给这个新动作。

因此，鉴于此框架，继续进行很简单。我们只想调用一个带有其延续的函数两次。棘手的部分是我们需要在一个新的单子动作中重新包装这个延续，从而抛出现有的延续。所以让我们分解一下：

-- Invoke a raw continuation with a given argument, throwing away our normal 
-- continuation
gotoContinuation :: (a -> r) -> a -> Cont r x
gotoContinuation continuation argument = Cont $ \_ -> continuation argument

-- Duplicate the current continuation; wrap one up in an easy-to-use action, and
-- the other stays the normal continuation for f
callCC f = Cont $ \cc -> runCont (f (gotoContinuation cc)) cc

很简单，不是吗？

在其他语言如 Scheme 中，原理是相同的，尽管它可能被实现为编译器原语；我们可以在 Haskell 中执行此操作的原因是因为延续传递是我们在 Haskell 中定义的，而不是在运行时的较低级别。但原理是一样的——你需要先有CPS，然后call/cc是这个执行模型的一个微不足道的应用。

score 7 · Accepted Answer

您已经听说过等式的 Haskell 方面；我会给你一个 Racket/Scheme，无论哪一个对你最有帮助，你都可以使用它。

我的回答会短很多，因为我认为我可以为您提供的在简单球拍评估器中实施 call/cc 的最佳资源来自 Shriram Krishnamurthi 的PLAI，特别是第 20 节。我考虑过包括相关部分解释器——它在第 205 页上——但在尝试重新格式化它几次之后，我认为它在页面上的适当位置会更有意义。

再说一次，我不想在这里解释 call/cc 背后的想法，只是指出一个可行的实现。如果您还有其他问题，请告诉我。

score 3 · Accepted Answer

冒着偏离语言的风险我认为在 Smalltalk 中可以最容易地实现和理解延续。原因是在 Smalltalk 中，执行堆栈是由可以像任何其他对象一样访问和操作的普通对象组成的。

要实现一个简单的延续对象，需要以下两种方法。在第一种方法中，我们通过迭代父（发送者）帧（上下文）并复制它们的状态（程序计数器、临时变量、参数）来初始化延续：

Continuation>>initializeFromContext: aContext
    context := aContext.
    stream := WriteStream on: (Array new: 200).
    [ context notNil ] whileTrue: [
        stream nextPut: context.
        1 to: context class instSize do: [ :index |
            stream nextPut: (context instVarAt: index) ].
        1 to: context size do: [ :index |
            stream nextPut: (context at: index) ].
        context := context sender ].
    values := stream contents

第二种方法是恢复执行：首先我们展开当前堆栈（同样这只是执行堆栈上的一个简单循环），然后我们恢复捕获的堆栈帧，将它们重新附加到当前堆栈帧thisContext并使用论据anObject：

Continuation>>value: anObject
    self terminate: thisContext.
    stream := values readStream.
    [ stream atEnd ] whileFalse: [
        context := stream next.
        1 to: context class instSize do: [ :index |
            context instVarAt: index put: stream next ].
        1 to: context size do: [ :index |
            context at: index put: stream next ] ]
    thisContext swapSender: values first.
    ^ anObject

使用这两种方法，我们可以轻松构建callCC：

Continuation class>>callCC: aBlock
    ^ aBlock value: (self new initializeFromContext: thisContext sender)

这种方法的美妙之处在于打印的代码显示了实现完整延续（以及类似的其他类型的延续）所需的一切。系统 (VM) 中没有隐藏任何行为。可以使用调试器单步执行每个部分并观察执行堆栈是如何操作的。

上面的代码来自Seaside网络框架。要使用代码，您可能需要使用现成的发行版并浏览到类WAContinuation和WAContinuationTest.

score 3 · Accepted Answer

好吧，我将提供一个更短的基于方案的答案，因为这也被标记为“方案”。

要了解为什么您的实施尝试call/cc一定会失败，您必须了解什么是延续传递风格。一旦你明白了，这很简单：

call/cc不能直接实现。
然而，以连续传递风格实现是微不足道的。

但是为了提供更多信息，继续传递风格是一种流程控制规则，您放弃使用调用堆栈而支持调用约定，在这种约定中，每个过程调用都传递一个“额外”参数：假设被调用过程的闭包在“完成”时调用（将“返回值”作为参数传递）。这些额外的参数闭包称为continuations。

任何程序都可以被机械地翻译成延续传递风格，通过适当地称为CPS 转换的方法。许多 Scheme 系统实际上是这样工作的：解析程序，对其应用 CPS 转换，然后将 CPS 抽象语法树解释或翻译成目标代码。

这就是您call/cc在延续传递样式中实现的方式（continuation用作延续的额外参数的名称）：

(define (call/cc-cps proc continuation)
  (proc continuation continuation))

正如您应该能够看到的，（a）您不能以直接样式（与 CPS 相反）来实现它，并且（b）它在 CPS 中是微不足道的。 call/cc只是一个过程，它将另一个过程作为其参数和（强制性）延续，并以延续作为其参数和延续来调用该过程。

haskell - 呼叫/抄送实施？

5 回答 5

Related

Reference