问题 在学术用途之外的延续monad是否有真实的适用性?


(后来的访问者:这个问题的两个答案都给出了很好的见解,如果你感兴趣的话,你应该把它们都读出来,我只能把它作为SO的限制除外)

从我在网上找到的关于延续monad的所有讨论中,他们要么提到它如何与一些简单的例子一起使用,要么他们解释它是一个基本的构建块,如本文中的 所有monad的母亲是继续monad

我想知道是否有适用范围。我的意思是,在continuation monad中包装递归函数或相互递归是否有意义?它有助于提高可读性吗?

这是一个F#版本的延续模式 这个SO帖子

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的电话/ cc继续monad 表明处理异常很复杂,但它没有解释它试图解决的问题,并且示例没有说明为什么它需要特定的monad。不可否认,我只是不明白它的作用,但它可能是一个宝库!

(注意:我对理解延续monad的工作原理并不感兴趣,我认为我对它有一个很好的掌握,我只是看不出它解决了什么编程问题。)


1325
2017-12-17 20:27


起源

我想不出一个很好的例子,但我认为在某些情况下它会简化用于使用尾调的CPS代码。 - Gustavo
@Gustavo,如果像你这样狂热的F#程序员不会在日常代码中使用它,那么这可能足以证明你可以在没有烦恼的情况下生活。 - Abel
嗯,可能像大多数monad一样,在某种意义上它们以初始学习曲线的复杂性为代价提供简单性,这是巨大的。但是,我可以想象一种情况,你需要使用一个以CPS风格编码的库,它会对它有所帮助。我打算退出Either / Option错误处理并迁移到我的一个库中的双桶异常,如果我对这些CPS函数有很多链接,我最终可能会使用它。为什么不添加Haskell标签?如果你这样做,我相信你会得到有趣的答案。 - Gustavo
在Haskell中,Continuation monad有时用于实现快速回溯搜索。此外,如果以“默认”顺序(差异列表的推广)进行评估,则使用称为密度monad的Continuation monad的受限变体来重新关联效率低的操作。 - danidiaz
Yoneda 是另一种CPS变体,在某些情况下可能有用(即收集多个 fmap 操作成一个,或将任意类型“升级”为 Functor)。我个人不知道怎么做 Cont 和 ContT 在野外使用,但这反映了我的知识限制,而不是限制其使用。 - dfeuer


答案:


“所有monad的母亲”的东西并不纯粹是学术性的。 Dan Piponi引用了Andrzej Filinski的 代表Monads,一篇相当不错的论文。它的结果是你的语言是否有分隔的延续(或者可以模仿它们 call/cc 然后你就可以了 透明 加 任何 任何代码的monadic效果。换句话说,如果你有分隔的延续 没有其他副作用, 您可以 实行 (全局)可变状态或异常或回溯非确定性或协同并发。您可以通过定义一些简单的函数来完成其中的每一项。没有全球转型或任何需要。此外,您只需在使用时支付副作用。事实证明,Schemers完全正确 call/cc 表现力很强。

如果你的语言没有分隔的延续,你可以通过延续monad(或者更好的双管延续monad)获得它们。当然,如果你打算以monadic风格写作 - 无论如何  全球转型 - 为什么不从一开始就使用所需的monad?对于Haskellers,这通常是我们所做的,但是,在许多情况下使用continuation monad仍然有好处(虽然隐藏起来)。一个很好的例子是 Maybe/Option monad就像有例外,除了只有一种例外。基本上,这个monad捕获返回“错误代码”的模式,并在每次函数调用后检查它。这正是典型定义所做的,除了“函数调用”,我的意思是计算的每个(monadic)步骤。可以说,这是非常低效的,特别是在绝大部分时间没有错误时。如果你反思 Maybe 但是,虽然你必须支付CPSed代码的成本(GHC Haskell处理得非常好),你只需支付费用来检查重要地方的“错误代码”,即 catch 声明。在哈斯克尔, Codensity monad比danidiaz提到的是一个更好的选择,因为 持续 Haskellers想要做的就是让任意效果在代码中透明地交错。

正如danidiaz所提到的,使用基本上连续monad或某些变体更容易或更有效地实现许多monad。回溯搜索就是一个例子。虽然不是回溯中最新的东西,但我最喜欢的一篇论文是使用它 Haskell中的类型逻辑变量。其中使用的技术也用于有线硬件描述语言。同样来自Koen Claesson 一个穷人的并发Monad。在这个例子中,对思想的更现代的用法包括:Haskell中确定性并行性的monad 确定性并行性的Monad 和可扩展的I / O管理器 结合可扩展网络服务的事件和线程。我确信我可以找到Scala中使用的类似技术。如果未提供,则可以使用continuation monad在F#中实现异步工作流。事实上,Don Syme 引用 我刚引用的文章完全相同。如果你可以序列化函数但没有continuation,你可以使用continuation monad来获取它们,并进行像系统那样受欢迎的序列化延续类型的web编程 海滨。即使没有可序列化的延续,您也可以使用该模式(与async基本相同)至少避免回调,同时在本地存储延续并仅发送密钥。

最终,Haskellers之外的人很少使用任何容量的monad,正如我前面提到的,Haskellers倾向于使用比继续monad更多的可控制monad,尽管他们在内部使用它们相当多。然而,继续monad或continuation monad之类的东西,尤其是异步编程,变得不那么罕见。随着C#,F#,Scala,Swift甚至Java开始采用支持monadic或至少monadic风格的编程,这些想法将得到更广泛的使用。如果Node开发人员对此更熟悉,也许他们会意识到你可以拥有自己的蛋糕,并且在事件驱动编程方面也可以吃掉它。


5
2017-12-19 01:12



谢谢,德里克,这个广泛的答案。我不得不承认我不遵循它的一切。虽然写得很好,但我很难理解什么 分隔的延续 是的,更不用说了 双桶连续单子。不过,我可能会问这个问题的后续问题。我不知道你为什么这么说 “Haskellers以外很少有人使用monads”,因为monad无处不在,无论名称如何,在F#(可能,Either,State)和其他函数语言(Scheme,Scala,Erlang?)中都是如此。这需要一些时间来消化这一切,谢谢! - Abel


为了提供更直接的F#特定答案(即使Derek已经涵盖了这一点), 继续monad 几乎抓住了核心的方式 异步工作流程 工作。

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

我认为这与monad在经典学术作品或Haskell中的使用方式有很大的不同,在Haskell中,它们倾向于“按原样”使用,并且可能以各种方式组成,以构建捕捉更复杂行为的更复杂的monad。

这可能只是我个人的观点,但我会说延续monad本身并不实用,但它是一些非常实用的想法的基础。 (就像lambda演算本身并没有真正实用,但它可以被看作是很好的实用语言的灵感!)


6
2017-12-19 14:08



谢谢,托马斯,这是德里克的一个很好的补充。它有助于您解释它是更高级实现的基础(异步非常接近)。有了这些签名,我现在意识到我在实践中多次使用它,最近在将FsCheck框架改编成一个有用的单元测试迷你框架。理解我写这篇文章可以更容易地扩展它,概括它,拥抱它,了解范例。 - Abel


我肯定发现使用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

但是,当在深树上调用时,天真的折叠会打击堆栈,因为它不是尾递归,而使用延续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

2
2017-12-21 18:33



精彩,简洁,清晰。这意味着我的假设 “continuation monads神奇地将递归转换为尾递归” 错了。他们确实把它变成了尾递归。这非常有用,意味着它非常适用 “现代F#编程”。 - Abel