"continuations"在函数式编程中是什么意思?(特别是SML)

What do "continuations" mean in functional programming?(Specfically SML)

我已经阅读了很多关于延续的内容,我看到的一个非常常见的定义是,它 returns 控制状态。

我正在学习 SML 教授的函数式编程课程。

我们的教授将延续定义为:

"What keeps track of what we still have to do" ; "Gives us control of the call stack"

他的很多例子都围绕着树木。在本章之前,我们做了尾递归。我知道尾递归通过向 "build" 添加一个附加参数来释放堆栈来保存递归调用的函数。反转列表将构建在一个新的累加器中,我们将相应地附加到它。此外,他说一些关于函数的东西被调用(但不被评估),除非我们到达我们向后替换的终点。他说尾递归的改进版本将使用 CPS(Continuation Programming Style)。

有人可以简单解释一下什么是延续以及为什么它们比其他编程风格更受青睐吗?

我发现这个 Whosebug link 对我有帮助,但仍然没有为我阐明思路:

I just don't get continuations!

Continuations 只是将 "what happens next" 视为第一个 class 对象,可以无条件地使用一次,忽略以支持其他内容,或多次使用。

为了解决 Continuation Passing Style 的问题,这里是一些正常编写的表达式:

let h x = f (g x)

g 应用于 xf 应用于结果。 请注意 g 没有任何控制权。它的结果无论如何都会传递给f。

在 CPS 中是这样写的

let h x next = (g x (fun result -> f result next))

g 不仅有 x 作为参数,还有一个延续,它采用 g 和 returns 的输出作为最终值。此函数以相同的方式调用 f,并给出 next 作为延续。

发生了什么事?是什么改变使它比 f (g x) 有用得多?不同的是,现在 g 处于控制之中。它可以决定是否使用接下来发生的事情。这就是延续的本质。

延续性出现的一个例子是具有控制结构的命令式编程语言。 whiles、blocks、普通语句、break 和 continues 都是通过 continuations 概括的,因为这些控制结构接受接下来发生的事情并决定如何处理它,例如我们可以有

...
while(condition1) {
    statement1;
    if(condition2) break;
    statement2;
    if(condition3) continue;
    statement3;
}
return statement3;
...

while、块、语句、break 和 continue 都可以通过延续在功能模型中进行描述。每个构造都可以被认为是一个函数,它接受

  • 当前环境包含
    • 封闭范围
    • 可选函数接受当前环境并return继续
      • 从最内层循环跳出
      • 从最里面的循环继续
      • return 来自当前函数。
  • 与其关联的所有块(if 块、while 块等)
  • 下一个语句的延续

和return新环境。

在while循环中,根据当前环境对条件进行评估。如果它被评估为真,那么块被评估并且 returns 新环境。使用新环境再次评估 while 循环的结果是 returned。如果它被评估为 false,则评估下一条语句的结果是 returned。

通过 break 语句,我们在环境中查找 break 函数。如果没有找到函数,那么我们不在循环内,我们会报错。否则,我们将当前环境提供给函数和 return 评估的延续,这将是 while 循环之后的语句。

使用 continue 语句会发生同样的情况,只是继续将是 while 循环。

对于 return 语句,延续将是调用当前函数之后的语句,但它会从环境中删除当前封闭范围。