什么叫/ cc?

我已经多次尝试了解延续的概念,并且呼吁/ cc 。 每一次尝试都是失败的。 有人可以解释我这些概念,理想情况下比维基百科或其他SOpost更实际的例子。

我有Web编程和面向对象的背景。 我也了解6502程序集,并与Erlang有一个小小的争执。 不过,我还是不能把头绕在call / cc上。

看,我发现这个延续传递风格最好的描述这个话题。

这里是剥离的文章的细节的副本:

作者:Marijn Haverbekedate:2007年7月24日

Scheme的call-with-current-continuation函数可以捕获计算,调用堆栈的状态,并在稍后恢复相同的状态。 在这样的原始基础之上,可以实现各种forms的exception处理和类似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(); } 

现在,每隔二十个节点,计算就会中断一百毫秒,使浏览器界面有时间响应用户的input。 一个非常原始的线程forms – 你甚至可以同时运行多个计算。

一个更常用的应用程序与XMLHttpRequests或者用于模拟它们的各种IFRAME和SCRIPT标记相关。 这些总是要求使用某种callback机制来处理服务器发回的数据。 在简单情况下,一个简单的函数将会执行,或者一些全局variables可以用来存储数据返回后必须恢复的计算状态。 对于复杂的情况,例如当一个函数正在使用数据时,函数必须返回一些值给它的调用者,连续性会大大简化。 您只需将延续注册为回叫,并在请求结束时恢复计算。

为了将它与C进行比较,当前的延续就像堆栈的当前状态。 它具有等待当前函数结果的所有function,以便它们可以恢复执行。 作为当前延续捕获的variables被用作函数,除了它提供的值并将其返回给等待的栈。 这种行为类似于C函数longjmp ,您可以立即返回到堆栈的较低部分。

 (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 (x 4) ; returns 6 

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

 (* 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. 

保存和恢复程序状态的能力与multithreading有很多相同之处。 事实上,你可以使用continuation来实现你自己的线程调度器,正如我在这里试图说明的那样。

使用continuation的一个简单的例子是在单处理器机器上实现一个线程(如果你愿意的话)。 调度器会周期性地中断执行stream程(或者在光纤的情况下,在代码中的各个关键点调用),保存继续状态 (对应于当前线程 ),然后切换到不同的继续状态 (对应于之前保存状态的另一个线程。)

参考你的程序集背景, 继续状态将捕获指令指针,寄存器和堆栈上下文(指针)等细节 ,以便随意保存和恢复。

使用continuation的另一种方法是考虑用几个线程类实体replace方法调用,它们并行共存(运行或暂停),使用延续上下文而不是“传统” call范例来传递控制权。 他们将使用全局(共享)数据而不是依赖参数。 这在某种程度上比在call时更灵活,因为堆栈不必停止( calls 嵌套 ),但是控制可以任意传递。

试图用C这样的语言将这个概念可视化 ,想象一个带有单个switch(continuation_point) { case point1: ... }语句的大循环,其中每个case对应一个continuation-savepoint,每个case里面的代码case可以改变continuation_point的值,并通过从switch并参与循环中的下一次迭代来放弃对continuation_point控制。

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

帮助我的是这样的想法,即在使用函数调用的传统语言中,只要您进行函数调用,就会隐式地传递延续。

在跳转到一个函数的代码之前,你在栈上保存了一些状态(也就是说,你把你的返回地址和堆栈已经包含了你的本地文件)。 这实质上是一个延续。 当function完成后,它必须确定在哪里发送执行stream程。 它使用存储在堆栈上的延续,popup返回地址并跳转到它。

其他语言概括了这种继续的概念,允许你明确地指定继续执行代码的位置,而不是隐式地继续执行函数调用。

编辑根据评论:

延续是完整的执行状态。 在任何执行点上,你都可以把程序分成两部分(时间,而不是空间) – 已经运行到这一点,以及从这里运行的一切。 “当前的延续”就是“从这里开始的一切”(你可以把它看作是一种function,可以完成程序其他部分的function)。 所以你提供给call/cc的函数会在call/cc时通过当前的延续。 该函数可以使用continuation将执行返回到call/cc语句(更可能的是,它将继续传递给其他的东西,因为如果直接使用它,它可以做一个简单的返回)。

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

我见过的最好的解释是Paul Graham的书On Lisp 。

理解call / cc有多个层次。 首先,您需要了解这些条款以及机制如何运作。 然后,需要了解如何以及何时在“真实生活”编程中使用call / cc。

通过学习CPS可以达到第一个层次,但也有其他select。

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

丹尼尔P.弗里德曼。 “继续的应用:受邀教程”。 1988年编程语言原理(POPL88)。 1988年1月

我从理解的angular度理解continuation的模型是它是一个指向下一条指令的指针的复制。

Call / cc调用一个函数(作为parameter passing),继续作为参数。

看一下在FScheme的call / cc的描述和实现: http : //blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with-continuations的.aspx

想象你的脚本是一个video游戏阶段。 Call / cc就像是一个奖励阶段。

奖金阶段和电话/ cc之间的parellel

只要你触摸它,你转移到奖金阶段(即函数的定义作为parameter passing给/ cc [在这种情况下])。

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

退出奖金阶段和调用/ cc函数之间的parellel参数

所以,如果有很多args ,当你达到其中的一个时,这并不重要。 所以我们的执行到达(arg 42)并且返回到和(+ 42 10)

还有一些言论值得注意:

  • 并不是所有的函数都可以使用call / cc。 因为它需要延续(这是一个函数),所以你不能有这样的f: (define f (lambda (k) (+ k 42)) ,因为你不能sum一个函数。
  • 你也不能有(define f (lambda (k) (f 42 10)))因为continuation只需要一个参数。
  • 您可以完成而不touching任何退出,在这种情况下,function像任何普通function(例如(define f (lambda (k) 42)完成并返回42)继续。