13

（后来的访问者：这个问题的两个答案都给出了很好的见解，如果你有兴趣，你可能应该同时阅读它们，我只能将一个作为 SO 的限制除外）

从我在网上找到的关于 continuation monad 的所有讨论中，他们要么提到了如何将它与一些琐碎的例子一起使用，要么他们解释说它是一个基本的构建块，就像这篇关于所有 monad 之母的文章中的 continuation monad一样。

我想知道是否有超出这个范围的适用性。我的意思是，在延续单子中包装递归函数或相互递归是否有意义？它有助于可读性吗？

这是取自此 SO 帖子的延续模式的 F# 版本：

type ContinuationMonad() =
    member this.Bind (m, f) = fun c -> m (fun a -> f a c)
    member this.Return x = fun k -> k x

let cont = ContinuationMonad()

它仅仅是学术兴趣，例如帮助理解单子或计算构建器？还是有一些现实世界的适用性，增加了类型安全性，或者它是否规避了其他难以解决的典型编程问题？

即，来自 Ryan Riley 的带有 call/cc 的 continuation monad表明处理异常很复杂，但它没有解释它试图解决什么问题，并且示例也没有说明为什么它特别需要这个 monad。诚然，我只是不明白它的作用，但它可能是一个宝库！

（注意：我对了解 continuation monad 的工作原理不感兴趣，我想我对它有相当的了解，只是看不出它解决了什么编程问题。）

4

3 回答 3

9

“所有单子之母”的东西并不是纯粹的学术。Dan Piponi 引用了 Andrzej Filinski 的Representing Monads，这是一篇相当不错的论文。其结果是，如果您的语言具有分隔的延续（或者可以call/cc使用单个可变状态来模仿它们），那么您可以透明地向任何代码添加任何单子效果。换句话说，如果你有分隔延续并且没有其他副作用，你可以实现（全局）可变状态或异常或回溯非确定性或协作并发。您可以通过定义一些简单的函数来完成其中的每一个。无需全局转换或任何需要。此外，您只需为使用它们时的副作用付费。事实证明，Schemers 的call/cc高度表达是完全正确的。

如果您的语言没有定界延续，您可以通过延续单子（或更好的双管延续单子）获得它们。当然，如果你无论如何都要以 monadic 风格编写——这是一种全局转换——为什么不从一开始就使用所需的 monad？对于 Haskeller 来说，这通常是我们所做的，然而，在许多情况下使用 continuation monad 仍然有好处（尽管隐藏起来）。一个很好的例子是Maybe/Optionmonad 就像有异常一样，除了只有一种类型的异常。基本上，这个 monad 捕获返回“错误代码”并在每次函数调用后检查它的模式。这正是典型定义所做的，除了“函数调用”我指的是计算的每个（单子）步骤。可以说，这是相当低效的，尤其是在绝大多数时间没有错误的情况下。但是，如果您反映Maybe到 continuation monad 中，虽然您必须支付 CPSed 代码的成本（GHC Haskell 处理得非常好），但您只需支付在重要的地方检查“错误代码”，即catch语句。在 Haskell 中，Codensitymonad 比 danidiaz 提到的是更好的选择，因为最后一个Haskellers 想要做的是让任意效果可以透明地交错在他们的代码中。

正如 danidiaz 还提到的，许多 monad 更容易或更有效地使用本质上的 continuation monad 或某些变体来实现。回溯搜索就是一个例子。虽然不是回溯的最新内容，但我最喜欢使用它的论文之一是Haskell 中的 Typed Logical Variables。其中使用的技术也用于有线硬件描述语言。同样来自 Koen Claesson 的是A Poor Man's Concurrency Monad。此示例中更现代的应用包括： 用于 Haskell 中确定性并行性的 monad 用于确定性并行性和可扩展 I/O 管理器的 Monad结合事件和线程用于可扩展网络服务. 我确信我可以找到 Scala 中使用的类似技术。如果未提供，您可以使用 continuation monad 在 F# 中实现异步工作流。事实上，Don Syme引用了我刚刚引用的完全相同的论文。如果您可以序列化函数但没有延续，则可以使用延续 monad 来获取它们并执行由Seaside等系统流行的序列化延续类型的 Web 编程。即使没有可序列化的延续，您也可以使用该模式（基本上与异步相同）来至少避免回调，同时在本地存储延续并仅发送一个键。

最终，Haskellers 之外的人相对较少以任何身份使用 monad，正如我之前提到的，Haskellers 倾向于使用比 continuation monad 更多的可控 monad，尽管他们确实在内部使用了很多。然而，延续单子或类似延续单子的东西，特别是对于异步编程，正变得越来越少见。随着 C#、F#、Scala、Swift 甚至 Java 开始支持单子或至少是单子风格的编程，这些想法将得到更广泛的应用。如果 Node 开发人员更熟悉这一点，也许他们会意识到，在事件驱动编程方面，您也可以吃到自己的蛋糕。

于 2016-12-19T01:12:12.543 回答
6

为了提供更直接的特定于 F# 的答案（尽管 Derek 已经涵盖了这一点），continuation monad几乎抓住了异步工作流如何工作的核心。

continuation monad 是一个函数，当给定一个 continuation 时，最终会使用结果调用 continuation（它可能永远不会调用它，也可能会重复调用它）：

type Cont<'T> = ('T -> unit) -> unit

F# 异步计算稍微复杂一些——它们需要继续（在成功的情况下）、异常和取消继续，还包括取消标记。使用稍微简化的定义，F# 核心库使用（请参阅此处的完整定义）：

type AsyncParams =
    { token : CancellationToken
      econt : exn -> unit
      ccont : exn -> unit } 

type Async<'T> = ('T -> unit) * AsyncParams -> unit

如您所见，如果您忽略AsyncParams，它几乎就是延续单子。在 F# 中，我认为“经典”单子作为一种灵感比作为一种直接实现机制更有用。在这里，continuation monad 提供了一个有用的模型来处理某些类型的计算——并且具有许多额外的异步特定方面，核心思想可用于实现异步计算。

我认为这与 monad 在经典学术著作或 Haskell 中的使用方式完全不同，它们倾向于“按原样”使用，并且可能以各种方式组合以构建更复杂的 monad，从而捕获更复杂的行为。

这可能只是我个人的看法，但我想说的是 continuation monad 本身并没有实际用途，但它是一些非常实用的想法的基础。（就像 lambda 演算本身并没有真正的实用性一样，但它可以被视为很好的实用语言的灵感！）

于 2016-12-19T14:08:07.647 回答
3

与使用显式递归实现的递归函数相比，我当然发现使用延续单子实现的递归函数更容易阅读。例如，给定这种树类型：

type 'a Tree = 
| Node of 'a * 'a Tree * 'a Tree
| Empty

这是在树上编写自下而上折叠的一种方法：

let rec fold e f t = cont {
    match t with
    | Node(a,t1,t2) ->
        let! r1 = fold e f t1
        let! r2 = fold e f t2
        return f a r1 r2
    | Empty -> return e
}

这显然类似于天真的折叠：

let rec fold e f t =
    match t with
    | Node(a,t1,t2) ->
        let r1 = fold e f t1
        let r2 = fold e f t2
        f a r1 r2
    | Empty -> return e

除了天真的折叠在深树上调用时会破坏堆栈，因为它不是尾递归，而使用 continuation monad 编写的折叠不会。您当然可以使用显式延续来编写相同的东西，但在我看来，它们添加的混乱程度会分散算法结构的注意力（并且将它们放置在适当的位置并不是完全万无一失的）：

let rec fold e f t k = 
    match t with
    | Node(a,t1,t2) -> 
        fold e f t1 (fun r1 ->
        fold e f t2 (fun r2 ->
        k (f r1 r2)))
    | Empty -> k e

请注意，为了使其正常工作，您需要修改您的定义ContinuationMonad以包含

member this.Delay f v = f () v
于 2016-12-21T18:33:59.477 回答