延续单子在学术之外是否有实际应用？

Question

延续单子在学术之外是否有实际应用？

haskellf#monadscontinuation-passingcomputation-expression

13

(后来的访客：这个问题有两个回答都给出了很好的见解，如果你感兴趣，应该都读一下，我只能接受一个作为SO的限制)

在我发现的所有关于 continuation monad 的在线讨论中，要么是提到它如何与某些微不足道的示例一起使用，要么就是解释它是一个基本构建块，就像这篇文章中所描述的那样：所有单子中的母亲——continuation monad。

我想知道它是否适用于这个范围之外。我的意思是，将递归函数或相互递归函数包装在 continuation monad 中是否有意义？这是否有助于可读性？

这里是从此 SO 帖子中提取的 continuation mode 的 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的continuation monad with call/cc展示了处理异常是复杂的，但它并没有解释它试图解决什么问题，而且示例也没有说明为什么需要特别使用这个单子。诚然，我只是不明白它到底是做什么的，但它可能是一个宝藏！

（注意：我对理解 continuation monad 如何工作不感兴趣，我认为我已经相当掌握了它，我只是看不出它解决了什么编程问题。）

- Abel

2

我想不出一个好的例子，但我认为有些情况下，简化 CPS 代码以使用尾调用是有必要的。 - Gus

1

@Gustavo，如果像您这样热衷于F#编程的程序员在日常代码中不使用它，那么这可能足以证明您可以不必担心它。 - Abel

2

嗯，可能像大多数单子一样，它们提供了简单性，但代价是初始学习曲线的复杂性，这是巨大的。然而，我可以想象一种情况，你需要使用以 CPS 风格编码的库，这将是有帮助的。我计划从 Either/Option 错误处理中移出，并在我的一个库中迁移到双重异常，也许如果我在这些 CPS 函数上有很多链接，我最终会使用它。为什么不添加 Haskell 标签呢？如果你这样做，我相信你会得到有趣的答案。 - Gus

这是一个关于编程的内容，以下是翻译文本：这是一个应用于FsCheck的“Gen”类型的示例。 - Nikos Baxevanis

2

在Haskell中，Continuation monad有时用于实现快速回溯搜索。此外，还使用了Continuation monad的一种受限变体，称为Codensity monad，以重新关联那些如果按照“默认”顺序计算将会很低效的操作（差异列表的一般化）。 - danidiaz

1

Yoneda是另一种CPS变体，可以在某些情况下非常有用（即将多个fmap操作收集到一个中，或将任意类型“升级”为Functor）。我个人不知道Cont和ContT在实际中如何使用，但这反映了我的知识限制而不是它们使用的限制。 - dfeuer

3个回答

6

为了提供更直接的针对F#的答案（尽管Derek已经涵盖了这一点），continuation monad基本上捕获了asynchronous workflows的核心。

一个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，它与 continuation monad 差不多。在 F# 中，我认为“经典”的 monads 更适合作为灵感，而不是作为直接实现机制。这里，continuation monad 提供了一个有用的模型来处理某些类型的计算 - 并且具有许多额外的异步特定方面，其核心思想可以用于实现异步计算。

我认为这与 monads 在经典学术著作或 Haskell 中的使用方式非常不同，在那里它们往往被“原样”使用，并可能以各种方式组合以构建更复杂的 monads，以捕获更复杂的行为。

这可能只是我的个人观点，但我认为 continuation monad 本身并不实用，但它是一些非常实用的思路的基础。（就像 lambda calculus 本身并不实用，但可以看作是实用语言的灵感！）

- Tomas Petricek

谢谢，Tomas，这是对Derek的极好补充。你解释了它是更高级实现的基础（其中async非常接近），这很有帮助。通过这些签名，我现在意识到我在实践中已经多次使用过它，最近在将FsCheck框架改编为一个有用的单元测试迷你框架时也使用了它。理解我写这个的原因使得扩展、概括和应用它更容易，知道这些范式。 - Abel

3

我发现使用continuation monad实现递归函数比使用显式递归更易于阅读。例如，给定这个树类型：

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

除了天真的折叠（fold）函数之外，使用 continuation monad 编写的折叠函数将不会在调用深度树时引发堆栈溢出问题，因为它是尾递归的。当然，您也可以使用显式 continuation 来编写相同的函数，但在我看来，它们添加的混杂程度会分散算法结构的注意力（并且放置它们并非完全傻瓜式操作）：

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

- kvb

精彩、简洁、清晰。这意味着我的假设——“连续单子可以神奇地将递归转换为尾递归”是错误的。它们确实将其转换为尾递归。这非常有帮助，意味着它在“现代 F# 编程”中非常适用。 - Abel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Derek Elkins left SE · Accepted Answer

“所有单子的母亲”并不纯粹是学术性的。丹·皮波尼引用了安德烈·菲林斯基的《表示单子》，这是一篇相当好的论文。其要点是，如果你的语言具有分界续体（或可以通过call/cc和单个可变状态模仿它们），那么你可以在任何代码中透明地添加任何单子效应。换句话说，如果你有分界续体而且没有其他副作用，你可以实现（全局）可变状态、异常、回溯非确定性或协作并发。你只需要定义一些简单的函数就可以做到这些。不需要进行全局转换或任何其他操作。而且，只有在使用副作用时才需要付出代价。结果表明，Schemers对于call/cc非常具有表现力的看法是完全正确的。

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

正如danidiaz所提到的，许多单子更容易或更有效地使用基本上是一个连续单子或某个变体来实现。回溯搜索就是一个例子。虽然回溯不是最新的技术，但我最喜欢的一篇论文Typed Logical Variables in Haskell中使用了它。其中使用的技术也被用于Wired Hardware Description Language中。Koen Claesson还有A Poor Man's Concurrency Monad。这个例子中的思想的更现代化的应用包括：Haskell中用于确定性并行性的单子A Monad for Deterministic Parallelism和可扩展的I/O管理器Combining Events And Threads For Scalable Network Services。我相信我可以找到在Scala中使用类似技术的例子。如果没有提供，您可以使用连续单子在F#中实现异步工作流程。事实上，Don Symereferences引用了我刚刚引用的同样的论文。如果您可以序列化函数但没有连续，则可以使用连续单子来获得它们，并执行由系统（例如Seaside）推广的序列化连续类型的Web编程。即使没有可序列化的连续性，您也可以使用该模式（本质上与async相同）来避免回调，同时在本地存储连续性并仅发送密钥。

最终，除了Haskellers以外，相对较少的人在任何情况下都在使用monads。正如我之前所说，Haskellers倾向于使用更可控的monads而不是continuation monad，尽管他们在内部经常使用它们。然而，continuation monads或类似continuation monad的东西，特别是用于异步编程，正在变得越来越常见。随着C＃，F＃，Scala，Swift甚至Java开始支持monadic或至少monadic-style编程，这些想法将变得更广泛使用。如果Node开发人员更熟悉此技术，也许他们会意识到在事件驱动编程方面可以兼顾两全。