61

我已经尝试过几次来掌握延续和call/cc的概念。每一次尝试都是失败的。有人可以向我解释这些概念吗，最好用比维基百科或其他 SO 帖子中更现实的例子。

我有网络编程和 OOP 的背景。我也了解 6502 程序集，并与 Erlang 有过一次小小的交流。但是，我仍然无法理解 call/cc。

4

10 回答 10

29

将其与 C 进行比较，当前延续就像堆栈的当前状态。它的所有函数都在等待当前函数的结果完成，以便它们可以恢复执行。捕获为当前延续的变量就像一个函数一样使用，只是它获取提供的值并将其返回到等待堆栈。此行为类似于 C 函数longjmp，您可以在其中立即返回到堆栈的较低部分。

这是一个方案 REPL 交互来说明：

> (define x 0) ; dummy value - will be used to store continuation later

> (+ 2 (call/cc 
          (lambda (cc)
           (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
           3)))         ; returns 5
5

> (x 4)                 ; returns 6
6

C 堆栈和延续之间的一个关键区别是延续可以在程序中的任何位置使用，即使堆栈的状态已经改变。这意味着您基本上可以恢复堆栈的早期版本并一次又一次地使用它们，从而产生一些独特的程序流程。

(* 123 (+ 345 (* 789 (x 5)))) ; returns 7

  reason: it is because (x 5) replaces the existing continuation,
          (* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
          5 to x, creating (+ 2 5), or 7.

保存和恢复程序状态的能力与多线程有很多共同之处。事实上，您可以使用延续来实现自己的线程调度程序，正如我在此处试图说明的那样。

于 2009-03-04T22:51:15.650 回答
24

看，我找到了关于这个主题的这种延续传递风格的最佳描述。

这是该文章的详细信息副本：

作者：Marijn Haverbeke 日期：2007 年 7 月 24 日

Scheme 的 call-with-current-continuation 函数可以捕获计算、调用堆栈的状态，并在以后恢复相同的状态。在这样的原语之上，可以实现各种形式的异常处理和类似 C 的 longjmp 技巧。

function traverseDocument(node, func) {
  func(node);
  var children = node.childNodes;
  for (var i = 0; i < children.length; i++)
    traverseDocument(children[i], func);
}   

function capitaliseText(node) {
  if (node.nodeType == 3) // A text node
    node.nodeValue = node.nodeValue.toUpperCase();
}

traverseDocument(document.body, capitaliseText);

这可以转换如下：我们为每个函数添加一个额外的参数，用于传递函数的延续。这个延续是一个函数值，表示函数“返回”后必须发生的动作。（调用）堆栈在延续传递风格中变得过时了——当一个函数调用另一个函数时，这是它做的最后一件事。它不是等待被调用的函数返回，而是将之后想要做的任何工作放入一个延续中，然后传递给函数。

function traverseDocument(node, func, c) {
  var children = node.childNodes;
  function handleChildren(i, c) {
    if (i < children.length)
      traverseDocument(children[i], func,
                       function(){handleChildren(i + 1, c);});
    else
      c();
  }
  return func(node, function(){handleChildren(0, c);});
}

function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();
  c();
}

traverseDocument(document.body, capitaliseText, function(){});

想象一下，我们有一个要大写的 huuuuge 文件。一口气遍历它需要五秒钟，而冻结浏览器五秒钟是相当糟糕的风格。考虑对 capitaliseText 的这个简单修改（不要注意丑陋的全局）：

var nodeCounter = 0;
function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();

  nodeCounter++;
  if (nodeCounter % 20 == 0)
    setTimeout(c, 100);
  else
    c();
}

现在，每 20 个节点，计算就会中断 100 毫秒，以便让浏览器界面有时间响应用户输入。一种非常原始的线程形式——你甚至可以像这样同时运行多个计算。

一个更常见的有用应用程序与 XMLHttpRequests 或用于模拟它们的各种 IFRAME 和 SCRIPT 标记黑客有关。这些总是需要使用某种回调机制来处理服务器发回的数据。在简单的情况下，可以使用一个简单的函数，或者可以使用一些全局变量来存储数据返回后必须恢复的计算状态。对于复杂的情况，例如，当必须向调用者返回一些值的函数使用数据时，延续会大大简化事情。您只需将延续注册为回调，然后在请求完成时恢复您的计算。

于 2009-03-04T22:41:09.123 回答
10

使用延续的一个简单的例子是在单处理器机器上实现一个线程（如果你愿意的话）管理器。调度器会周期性地中断执行流程（或者，在纤维的情况下，在代码中的各个战略点被调用），保存延续状态（对应于当前线程），然后切换到不同的延续状态（对应于另一个线程，其状态先前已保存。）

参考您的汇编背景，继续状态将捕获诸如指令指针、寄存器和堆栈上下文（指针）等详细信息，以随意保存和恢复。

使用延续的另一种方法是考虑用几个并行共存（运行或挂起）的类线程实体替换方法调用，call使用延续上下文而不是“经典”范式相互传递控制。他们将对全局（共享）数据进行操作，而不是依赖参数。这在某种程度上比call堆栈不必先收起然后收起（嵌套calls）更灵活，但控制可以任意传递。

尝试用诸如 C 的语言来可视化这个概念，想象有一个带有单个switch(continuation_point) { case point1: ... }语句的大循环，其中每个语句case对应一个 continuation-savepoint，每个内部的代码都case可以通过从并参与循环中的下一次迭代。continuation_pointcontinuation_pointbreakswitch

你的问题的背景是什么？您感兴趣的任何特定场景？任何特定的编程语言？上面的线程/纤维示例是否足够？

于 2009-03-04T22:40:13.337 回答
9

想象您的脚本是一个视频游戏舞台。Call/cc 就像一个奖励阶段。

奖金阶段和通话/抄送之间的平行

一旦你触摸它，你就会被转移到奖励阶段（即作为参数传递给 call/cc [f 在这种情况下] 的函数的定义）。

奖励阶段与普通阶段不同，因为它们通常有一个元素（即传递给 call/cc 的函数的参数），如果您触摸它，您就会丢失并被传送回正常阶段。

退出奖励阶段和调用/抄送函数 args 之间的并行

因此，是否有很多并不重要args，当您到达其中一个时，它就结束了。所以我们的执行到达(arg 42)并返回到 sum (+ 42 10)。

还有一些值得注意的地方：

  • 并非所有函数都可以与 call/cc 一起使用。因为它需要一个延续（即一个函数），所以你不能有这样的 f: (define f (lambda (k) (+ k 42)) ，因为你不能sum有一个函数。
  • 您也不能拥有(define f (lambda (k) (f 42 10))) ，因为延续只需要一个参数。
  • 您可以在没有touching任何退出的情况下完成，在这种情况下，函数会像任何普通函数一样继续执行（例如(define f (lambda (k) 42) ，完成并返回 42）。
于 2017-10-02T00:38:53.597 回答
5

对我有帮助的一点是，在带有函数调用的传统语言中，每当你进行函数调用时，你都会隐式地传递一个延续。

在跳转到函数的代码之前，您在堆栈上保存一些状态（即，您推送您的返回地址并且堆栈已经包含您的本地人）。这本质上是一个延续。当函数完成时，它必须确定将执行流发送到哪里。它使用存储在堆栈中的延续，弹出返回地址并跳转到它。

其他语言概括了这种延续的想法，允许您明确指定继续执行代码的位置，而不是隐式地从进行函数调用的位置继续。

根据评论编辑：

延续是完整的执行状态。在执行的任何时候，您都可以将程序分成两部分（在时间上，而不是空间上） - 已经运行到这一点的部分，以及将从这里运行的所有部分。“当前的延续”是“将从这里开始运行的一切”（你可以把它想象成一个函数，它将完成你程序的其余部分所做的一切）。因此，您提供给的函数在被调用call/cc时传递了当前的延续。call/cc该函数可以使用延续将执行返回到call/cc语句（尽管它更有可能将延续传递给其他东西，因为如果它直接使用它，它可以做一个简单的返回）。

于 2009-03-04T22:51:11.750 回答
5

当我试图理解 call/cc 时，我发现这个call-with-current-continuation-for-C-programmers页面很有帮助。

于 2009-06-03T00:36:18.233 回答
3

理解 call/cc 有多个层次。首先，您需要了解这些术语以及该机制的工作原理。然后需要了解如何以及何时在“现实生活”编程中使用 call/cc。

第一级可以通过学习 CPS 达到，但还有其他选择。

对于第二级，我推荐弗里德曼的以下经典。

丹尼尔·弗里德曼。 “延续的应用：特邀教程”。1988 年编程语言原理 (POPL88)。1988 年 1 月。

于 2009-03-09T20:55:09.523 回答
3

看看FScheme的call/cc的描述和实现

于 2011-04-22T22:43:50.463 回答
2

我用来从命令式的角度理解延续的模型是，它是调用堆栈的副本以及指向下一条指令的指针。

Call/cc 调用一个函数（作为参数传递），并将延续作为参数。

于 2011-09-22T23:02:34.443 回答
1

您可能熟悉“控制转移”的概念，它在诸如 C 之类的语言中体现在诸如 , 和 , 之类的语句中break，或者continue在支持异常的语言中 - and语句中。returngototrycatch

您可以想象break并且continue可以使用来实现goto（即，对于使用breakor的每一段代码continue，您可以轻松编写使用goto适当放置标签的等效代码）。

所以现在让我们专注于goto，正如你应该从你的装配经验中知道的那样 - 是最基本的控制转移操作（你可以想象它很难转换return使用goto- 但我们会继续讨论）。

因此，假设您有一个如下所示的程序（例如，在 C 中）：

instruction1;
instruction2;
...
instructionN;

whereinstructionK可以是赋值或函数调用或语句if (condition) goto some_label。

您可以在每一行前面加上一个唯一的标签goto：

line1: instruction1;
line2: instruction2;
...
lineN: instructionN;

在支持一等延续的语言中，有一个特殊的函数call/cc，它的工作方式如下：假设它instructionK的形式为

...
lineK: call/cc(function(continuation) { ... })
lineK+1: instructionK+1;
...

我在这里使用 JavaScript 的匿名函数表示法，因为 C 不支持匿名函数。您可以看到该函数有一个参数，我称之为continuation.

函数的主体在call/cc被调用时立即执行，continuation参数的值将是lineK+1（粗略地说）的地址。或者，换句话说，当前的延续是-这lineKlineK+1就是你可以考虑的方式。

然而，典型的接口不仅仅是地址：continuation参数是一个过程，当被调用时，它会跳转到lineK+1. 这就是call/cc允许实现return语句的方式。

因此，您可以将其call/cc视为goto类固醇的一种。问题是，您不仅可以调用continuation参数，还可以将其存储在变量或其他数据结构中。

call/cc我见过的最有趣的用法是 Dorai Sitaram 的书Teach Yourself Scheme in Fixnum Days中 Amb 评估器的实现（您可以将它与Structure and Interpretation of Computer Programs中未使用的版本进行比较call/cc）。

我曾经也使用延续实现了我自己的资源管理机制，如此处所述。

但除此之外，一流的延续受到批评，我不建议在生产代码中使用它们（它们与 C 中可用的setjmp/longjmp机制非常相似，我也不鼓励。但如果你想看一些使用示例，这里是您如何使用它在 100 行 od 代码中实现多任务处理的方法）。

于 2020-03-10T10:37:03.083 回答