-
03-07-2019 - |
解决方案
看,我已经找到了关于这个主题的延续传递风格最佳描述。
这里删除了该文章的详细信息副本:
作者: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);
这可以转换如下:我们为每个函数添加一个额外的参数,用于传递函数的延续。此延续是一个函数值,表示函数“返回”后必须执行的操作。 (call)堆栈在连续传递样式中变得过时了。当一个函数调用另一个函数时,这是它做的最后一件事。它不是等待被调用的函数返回,而是将它想要做的任何工作放到一个延续中,然后传递给函数。
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个节点,计算中断一百毫秒,以便为浏览器界面提供响应用户输入的时刻。一种非常原始的线程形式&#8213;你甚至可以像这样同时运行多个计算。
更常用的应用程序与XMLHttpRequests或用于模拟它们的各种IFRAME和SCRIPT标记hacks有关。这些总是需要一个人使用某种回调机制来处理服务器发回的数据。在简单的情况下,一个简单的函数可以做,或者可以使用一些全局变量来存储在数据返回后必须恢复的计算状态。对于复杂的情况,例如当函数使用必须向其调用者返回某个值的函数时,continuation会大大简化。您只需将延期注册为回调,并在请求完成时恢复计算。
其他提示
要将它与C进行比较,当前的延续类似于堆栈的当前状态。它具有等待当前函数结果的所有函数,以便它们可以继续执行。捕获为当前延续的变量像函数一样使用,除了它获取提供的值并将其返回到等待堆栈。此行为类似于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堆栈和延续之间的一个关键区别是,即使堆栈的状态发生了变化,也可以在程序的任何一点使用延续。这意味着您可以基本上恢复堆栈的早期版本并一次又一次地使用它们,从而产生一些独特的程序流。
(* 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.
保存和恢复程序状态的能力与多线程有很多共同之处。实际上,您可以使用continuation实现自己的线程调度程序,因为我试图说明此处。
使用continuation的一个简单例子将在单处理器计算机上实现一个线程(光纤,如果你愿意)管理器。调度程序将定期中断执行流程(或者,在光纤的情况下,在代码中的各个战略点调用),保存延续状态(对应于当前线程),然后切换到另一个继续状态(对应于之前保存状态的其他线程。)
参考你的装配背景,继续状态将捕获诸如指令指针,寄存器和堆栈上下文(指针)之类的详细信息,以便随意保存和恢复。
使用continuation的另一种方法是想到用几个类似线程的实体替换方法调用并行共存(运行或挂起)使用continuation上下文相互传递控制'经典'调用
范例。它们将对全局(共享)数据进行操作,而不是依赖于参数。这在某种程度上比 call
更灵活,因为堆栈不必先关闭(调用
嵌套),但是控制可以任意传递。
尝试用C这样的语言可视化这个概念,假设有一个带有单个开关的大循环(continuation_point){case point1:...}
语句,其中每个 case
对应一个continuation-savepoint,并且每个 case
中的代码可以改变 continuation_point
的值,并放弃对此的控制 continuation_point
通过 break
从 switch
开始,并参与循环中的下一次迭代。
您问题的背景是什么?您感兴趣的任何特定场景?任何特定的编程语言?线程/光纤示例是否足够?
对我有帮助的是这样一种想法,即在使用函数调用的传统语言中,只要进行函数调用,就会隐式传递一个延续。
在跳转到函数的代码之前,你会在堆栈中保存一些状态(即你推送你的返回地址,而堆栈已经包含你的本地人)。这基本上是一个延续。当函数完成时,它必须确定将执行流发送到何处。它使用存储在堆栈中的延续,弹出返回地址并跳转到它。
其他语言概括了这种继续的概念,允许您明确指定继续执行代码的位置,而不是从函数调用的位置隐式继续。
根据评论编辑:
延续是完整的执行状态。在任何执行点,你可以将程序分成两部分(在时间上,而不是空间) - 已经运行到这一点的部分,以及将从这里运行的所有部分。 “当前的延续”是指是“从这里开始的一切” (你可以认为它就像一个函数,可以完成你的程序其余部分所做的一切)。因此,当您调用 call / cc
时,您提供给 call / cc
的函数会传递当前的延续。该函数可以使用continuation将执行返回到 call / cc
语句(更可能的是它会将继续传递给其他东西,因为如果它直接使用它,它可以做一个简单的返回)。
当我试图理解call / cc时,我发现这是呼叫当前继续为C程序员页面很有帮助。
我见过的最好的解释是保罗格雷厄姆的书, On Lisp 一>
想象你的脚本是一个视频游戏舞台。打电话/抄送就像一个奖励阶段。
一旦你触摸它,你就会转移到奖金阶段(即。作为参数传递给 call/cc 的函数的定义 [在本例中为 f])。
奖励阶段与普通阶段不同 因为通常它们有一个元素(即传递给 call/cc 的函数的参数),如果你触摸它,你就会丢失并被传送回正常阶段。
所以有很多也没关系 args
, ,当你到达其中之一时就结束了。所以我们的执行达到 (arg 42)
并将其返回到总和 (+ 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)。
理解call / cc有多个级别。 首先,您需要了解术语以及机制的工作原理。 然后理解在“现实生活”中使用call / cc的方式和时间。 编程是必要的。
通过研究CPS可以达到第一级,但也有 的替代品。
对于第二级,我推荐弗里德曼的以下经典作品。
Daniel P. Friedman。 “Continuations的应用:邀请教程”。 1988年编程语言原则(POPL88)。 1988年1月。
查看FScheme的call / cc的描述和实现: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with -continuations.aspx
我用于从命令式角度理解延续的模型是,它是调用堆栈的副本与指向下一条指令的指针相结合。
Call/cc 调用一个函数(作为参数传递),并将延续作为参数。