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

Question

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

我正在学习用 SML 教授的函数式编程类(class)。

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

“什么会记录我们仍然需要做的事情”
; “让我们控制调用堆栈”

他的很多例子都围绕着树木展开。在本章之前，我们做了尾递归。我知道尾递归通过使用额外的参数来“构建”答案，从而释放堆栈以保存递归调用的函数。反转列表将构建在一个新的累加器中，我们相应地附加到它。此外，他还说了一些关于函数被调用(但不被评估)的内容，除非我们到达我们向后替换的末尾。他说尾递归的改进版本将使用 CPS(Continuation Programming Style)。

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

我发现这个 stackoverflow 链接对我有帮助，但仍然没有为我澄清这个想法:

I just don't get continuations!

Answer 1

延续简单地将“接下来会发生什么”视为可以无条件使用一次、忽略其他内容或多次使用的第一类对象。

解决什么延续传球风格是，这是一些正常写的表达式:

let h x = f (g x)

g适用于 x和 f应用于结果。
请注意 g没有任何控制。无论如何，它的结果将传递给 f。

在 CPS 中是这样写的

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

g不仅有 x 作为参数，还有一个延续，它接受 g 的输出并返回最终值。此函数调用 f以同样的方式，并给出 next作为延续。

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

延续出现的一个例子是你有控制结构的命令式编程语言。 while、block、普通语句、break 和continue 都是通过continuation 泛化的，因为这些控制结构接受接下来发生的事情并决定如何处理它，例如我们可以有

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

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

当前环境包含

封闭范围

可选函数接受当前环境并返回继续

从最里面的循环中断

从最里面的循环继续

从当前函数返回。

所有与它相关的块(if-blocks、while-block 等)

继续下一个语句

并返回新环境。

在while循环中，根据当前环境评估条件。如果它被评估为真，那么块被评估并返回新环境。返回使用新环境再次评估 while 循环的结果。如果它被评估为假，则返回评估下一条语句的结果。

使用 break 语句，我们在环境中查找 break 函数。如果没有找到函数，那么我们不在循环中，我们会给出一个错误。否则，我们将当前环境提供给函数并返回评估后的延续，这将是 while 循环之后的语句。

使用 continue 语句也会发生同样的情况，除了继续是 while 循环。

使用 return 语句，延续将是调用当前函数之后的语句，但它会从环境中删除当前的封闭作用域。