我不会试图解释所有连续性有用的地方,但我希望能够简要介绍我自己经验中发现连续性最常用的主要地方。与其谈论Scheme的call/cc
,我会把注意力集中在continuation passing style上。在一些编程语言中,变量可以动态作用域,在没有动态作用域的语言中,可以使用全局变量的样板代码(假设没有多线程代码等问题)。例如,假设有一个当前活动日志流列表*logging-streams*
,我们想在动态环境中调用function
,其中*logging-streams*
被logging-stream-x
增加。在Common Lisp中,我们可以这样做:
(let ((*logging-streams* (cons logging-stream-x *logging-streams*)))
(function))
如果我们没有动态作用域变量,就像Scheme一样,我们仍然可以做到
(let ((old-streams *logging-streams*))
(set! *logging-streams* (cons logging-stream-x *logging-streams*)
(let ((result (function)))
(set! *logging-streams* old-streams)
result))
现在假设我们实际上得到了一个cons-tree,它的非
nil
叶子是日志流,当调用
function
时,所有这些日志流都应该在
*logging-streams*
中。我们有两个选择:
- 我们可以展开树,收集所有的日志流,扩展
*logging-streams*
,然后调用function
。
- 我们可以使用延续传递风格,遍历树,逐渐扩展
*logging-streams*
,最后在没有更多的tree
可遍历时调用function
。
选项2看起来像这样:
(defparameter *logging-streams* '())
(defun extend-streams (stream-tree continuation)
(cond
((null stream-tree)
(funcall continuation))
((atom stream-tree)
(let ((*logging-streams* (cons stream-tree *logging-streams*)))
(funcall continuation)))
(t
(extend-streams (car stream-tree)
#'(lambda ()
(extend-streams (cdr stream-tree)
continuation))))))
根据这个定义,我们有
CL-USER> (extend-streams
'((a b) (c (d e)))
#'(lambda ()
(print *logging-streams*)))
=> (E D C B A)
现在,这个有用吗?在这种情况下,可能没有。一些小的好处可能是
extend-streams
是尾递归的,所以我们没有很多的堆栈使用,虽然中间闭包弥补了它的堆空间。我们确实有这样一个事实:最终的 continuation 在
extend-streams
设置的任何中间内容的动态范围内执行。在这种情况下,这并不是非常重要,但在其他情况下可能会很重要。
能够抽象掉一些控制流,并具有非局部退出或能够从长时间之前的某个地方继续计算,可以非常方便。例如,在回溯搜索中,这可能很有用。下面是一个基于 continuation passing style 的命题演算求解器,其中一个公式是一个符号(命题文字),或者是一个形如
(not formula)
、
(and left right)
或
(or left right)
的列表。
(defun fail ()
'(() () fail))
(defun satisfy (formula
&optional
(positives '())
(negatives '())
(succeed #'(lambda (ps ns retry) `(,ps ,ns ,retry)))
(retry 'fail))
(if (symbolp formula)
(if (member formula negatives)
(funcall retry)
(funcall succeed (adjoin formula positives) negatives retry))
(destructuring-bind (op left &optional right) formula
(case op
((not)
(satisfy left negatives positives
#'(lambda (negatives positives retry)
(funcall succeed positives negatives retry))
retry))
((and)
(satisfy left positives negatives
#'(lambda (positives negatives retry)
(satisfy right positives negatives succeed retry))
retry))
((or)
(satisfy left positives negatives
succeed
#'(lambda ()
(satisfy right positives negatives
succeed retry))))))))
如果找到满足的赋值,则会调用
succeed
函数,该函数带有三个参数:正文字面量列表、负文字面量列表和可以重试搜索(即尝试查找另一个解决方案)的函数。例如:
CL-USER> (satisfy '(and p (not p)))
(NIL NIL FAIL)
CL-USER> (satisfy '(or p q))
((P) NIL #<CLOSURE (LAMBDA #) {1002B99469}>)
CL-USER> (satisfy '(and (or p q) (and (not p) r)))
((R Q) (P) FAIL)
第二种情况很有趣,因为第三个结果不是“FAIL”,而是一些可调用函数, 它将尝试找到另一个解决方案。在这种情况下,我们可以看到通过使
p
或
q
为真,可以满足
(or p q)
的条件。
CL-USER> (destructuring-bind (ps ns retry) (satisfy '(or p q))
(declare (ignore ps ns))
(funcall retry))
((Q) NIL FAIL)
如果我们不使用延续传递风格来保存备选流并稍后返回,那将会非常困难。使用这种方法,我们可以做一些聪明的事情,比如收集所有满足条件的赋值:
(defun satisfy-all (formula &aux (assignments '()) retry)
(setf retry #'(lambda ()
(satisfy formula '() '()
#'(lambda (ps ns new-retry)
(push (list ps ns) assignments)
(setf retry new-retry))
'fail)))
(loop while (not (eq retry 'fail))
do (funcall retry)
finally (return assignments)))
CL-USER> (satisfy-all '(or p (or (and q (not r)) (or r s))))
(((S) NIL)
((R) NIL)
((Q) (R))
((P) NIL))
我们可以略微改变
loop
并获取仅限于某些
n的分配或类似主题的变化。通常情况下,不需要使用继续传递样式,或者可能会使代码难以维护和理解,但在其有用的情况下,它可以使一些本来非常困难的事情变得相对容易。
k isn't even defined!
of course it is(lambda (k) ... )
- leppie