寻找延续的“真实”用法的例子
-
09-06-2019 - |
题
我正在尝试掌握延续的概念,我发现了几个小的教学示例,例如来自 维基百科文章:
(define the-continuation #f)
(define (test)
(let ((i 0))
; call/cc calls its first function argument, passing
; a continuation variable representing this point in
; the program as the argument to that function.
;
; In this case, the function argument assigns that
; continuation to the variable the-continuation.
;
(call/cc (lambda (k) (set! the-continuation k)))
;
; The next time the-continuation is called, we start here.
(set! i (+ i 1))
i))
我明白这个小函数的作用,但我看不到它有任何明显的应用。虽然我不希望很快在我的代码中使用延续,但我希望我知道一些适合它们的情况。
因此,我正在寻找更明确有用的代码示例,以了解延续可以为我作为程序员提供什么。
干杯!
解决方案
在 Algo & Data II 中,我们一直使用这些来从(长)函数“退出”或“返回”
例如,用于遍历树的 BFS 算法是这样实现的:
(define (BFS graph root-discovered node-discovered edge-discovered edge-bumped . nodes)
(define visited (make-vector (graph.order graph) #f))
(define q (queue.new))
(define exit ())
(define (BFS-tree node)
(if (node-discovered node)
(exit node))
(graph.map-edges
graph
node
(lambda (node2)
(cond ((not (vector-ref visited node2))
(when (edge-discovered node node2)
(vector-set! visited node2 #t)
(queue.enqueue! q node2)))
(else
(edge-bumped node node2)))))
(if (not (queue.empty? q))
(BFS-tree (queue.serve! q))))
(call-with-current-continuation
(lambda (my-future)
(set! exit my-future)
(cond ((null? nodes)
(graph.map-nodes
graph
(lambda (node)
(when (not (vector-ref visited node))
(vector-set! visited node #t)
(root-discovered node)
(BFS-tree node)))))
(else
(let loop-nodes
((node-list (car nodes)))
(vector-set! visited (car node-list) #t)
(root-discovered (car node-list))
(BFS-tree (car node-list))
(if (not (null? (cdr node-list)))
(loop-nodes (cdr node-list)))))))))
正如您所看到的,当节点发现函数返回 true 时,算法将退出:
(if (node-discovered node)
(exit node))
该函数还将给出一个“返回值”:'节点'
函数为什么退出,是因为这样的语句:
(call-with-current-continuation
(lambda (my-future)
(set! exit my-future)
当我们使用 exit 时,它将返回到执行前的状态,清空调用堆栈并返回您给它的值。
所以基本上,call-cc 用于(此处)跳出递归函数,而不是等待整个递归自行结束(在进行大量计算工作时,这可能会非常昂贵)
另一个较小的示例对 call-cc 执行相同的操作:
(define (connected? g node1 node2)
(define visited (make-vector (graph.order g) #f))
(define return ())
(define (connected-rec x y)
(if (eq? x y)
(return #t))
(vector-set! visited x #t)
(graph.map-edges g
x
(lambda (t)
(if (not (vector-ref visited t))
(connected-rec t y)))))
(call-with-current-continuation
(lambda (future)
(set! return future)
(connected-rec node1 node2)
(return #f))))
其他提示
@拍
海滨
是的, 海滨 就是一个很好的例子。我快速浏览了它的代码,发现这条消息说明了在 Web 上以一种看似有状态的方式在组件之间传递控制。
WAComponent >> call: aComponent
"Pass control from the receiver to aComponent. The receiver will be
temporarily replaced with aComponent. Code can return from here later
on by sending #answer: to aComponent."
^ AnswerContinuation currentDo: [ :cc |
self show: aComponent onAnswer: cc.
WARenderNotification raiseSignal ]
太赞了!
我构建了自己的单元测试软件。在执行测试之前,我在执行测试之前存储延续,然后在失败时,我(可选)告诉方案解释器进入调试模式,并重新调用延续。这样我就可以非常轻松地单步调试有问题的代码。
如果您的延续是可序列化的,您还可以在应用程序失败时存储 then,然后重新调用它们以获取有关变量值、堆栈跟踪等的详细信息。
一些 Web 服务器和 Web 框架使用延续来存储会话信息。为每个会话创建一个延续对象,然后由会话中的每个请求使用。
我遇到了一个实现 amb
运算符在 这个帖子 从 http://www.randomhacks.net, ,使用延续。
这是什么 amb
操作员做:
# amb will (appear to) choose values
# for x and y that prevent future
# trouble.
x = amb 1, 2, 3
y = amb 4, 5, 6
# Ooops! If x*y isn't 8, amb would
# get angry. You wouldn't like
# amb when it's angry.
amb if x*y != 8
# Sure enough, x is 2 and y is 4.
puts x, y
这是帖子的实现:
# A list of places we can "rewind" to
# if we encounter amb with no
# arguments.
$backtrack_points = []
# Rewind to our most recent backtrack
# point.
def backtrack
if $backtrack_points.empty?
raise "Can't backtrack"
else
$backtrack_points.pop.call
end
end
# Recursive implementation of the
# amb operator.
def amb *choices
# Fail if we have no arguments.
backtrack if choices.empty?
callcc {|cc|
# cc contains the "current
# continuation". When called,
# it will make the program
# rewind to the end of this block.
$backtrack_points.push cc
# Return our first argument.
return choices[0]
}
# We only get here if we backtrack
# using the stored value of cc,
# above. We call amb recursively
# with the arguments we didn't use.
amb *choices[1...choices.length]
end
# Backtracking beyond a call to cut
# is strictly forbidden.
def cut
$backtrack_points = []
end
我喜欢 amb
!
只要程序流程不是线性的,或者甚至不是预先确定的,就可以在“现实生活”示例中使用延续。一个熟悉的情况是 网络应用程序.
在服务器编程(包括 Web 应用程序前端)中,延续是每个请求线程的一个很好的替代方案。
在此模型中,您只需在函数中开始一些工作,而不是每次收到请求时都启动一个新的(重)线程。然后,当您准备好阻塞 I/O 时(即从数据库读取),您将延续传递到网络响应处理程序中。当响应返回时,您执行延续。通过这种方案,您只需几个线程就可以处理大量请求。
这使得控制流比使用阻塞线程更复杂,但在重负载下,它更高效(至少在当今的硬件上)。
amb 运算符是一个很好的例子,它允许类似 prolog 的声明式编程。
正如我们所说,我正在Scheme中编写一个音乐作曲软件(我是一名音乐家,对音乐背后的理论几乎一无所知,我只是分析我自己的作品,看看它背后的数学是如何工作的。)
使用 amb 运算符,我只需填写旋律必须满足的约束,然后让 Scheme 计算出结果。
由于语言哲学,延续可能被放入Scheme中,Scheme是一个框架,使您能够通过在Scheme本身中定义库来实现在其他语言中找到的任何编程范例。延续用于构建您自己的抽象控制结构,例如“返回”、“中断”或启用声明式编程。方案更加“概括”,并且要求程序员也应该能够指定此类构造。
怎么样 Google Mapplet API?有很多函数(全部以 Async
) 向其传递回调。API 函数执行异步请求,获取结果,然后将该结果传递给回调(作为“下一步要做的事情”)。听起来很像 连续传球风格 大部头书。
这 例子 展示了一个非常简单的案例。
map.getZoomAsync(function(zoom) {
alert("Current zoom level is " + zoom); // this is the continuation
});
alert("This might happen before or after you see the zoom level message");
因为这是 Javascript,所以没有 尾调用优化, ,因此堆栈将随着每次调用而增长,最终将控制线程返回给浏览器。尽管如此,我认为这是一个很好的抽象。
如果您必须调用异步操作,并暂停执行直到获得结果,那么您通常会轮询结果或将其余代码放入回调中,以便异步操作完成时执行。通过延续,您不需要执行低效的轮询选项,也不需要将要在异步事件之后运行的所有代码包装在回调中 - 您只需将代码的当前状态作为回调传递- 一旦异步操作完成,代码就会被有效地“唤醒”。
延续可用于实现异常、调试器。