寻找“真实”使用延续的例子

在阿尔戈和;我们一直使用这些数据从(长)函数中“退出”或“返回”

例如,遍历树的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))

该函数还将给出一个“返回值”:'node'

函数退出的原因是以下语句:

(call-with-current-continuation
       (lambda (my-future)
         (set! exit my-future)

当我们使用exit时,它将返回执行前的状态,清空调用堆栈并返回您给它的值。

所以基本上,调用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))))

海边:

• homepage
• wikipedia page

@帕特

海边

对, Seaside 这是一个很好的例子。我快速浏览了它的代码,发现这条消息说明了在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 ]

太好了!

我构建了自己的单元测试软件。在执行测试之前,我会在执行测试前存储延续,然后在失败时,我(可选)告诉方案解释器进入调试模式,并重新调用延续。这样我就可以很容易地遍历有问题的代码。

如果您的延续是可序列化的,您还可以在应用程序发生故障时进行存储,然后重新调用它们以获取有关变量值、堆栈跟踪等的详细信息。

一些web服务器和web框架使用延续来存储会话信息。为每个会话创建一个延续对象,然后由会话中的每个请求使用。

There's an article about this approach here.

我来这里是为了实施 amb 操作员在 this post 来自 http://www.randomhacks.net ,使用延续。

这是什么 安博 操作员执行以下操作:

# 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

我喜欢 安博 !

只要程序流不是线性的,甚至不是预先确定的,就可以在“现实生活中”的例子中使用延续。一个熟悉的情况是 web applications .

在服务器编程(包括web应用程序前端)中,连续是每个请求线程的良好替代方案。

在这种模型中,您只需在函数中开始一些工作,而不是每次收到请求时都启动一个新的(重)线程。然后,当您准备阻塞I/O(即从数据库读取)时,您将向网络响应处理程序传递一个延续。当响应返回时,您将执行延续。使用此方案,您可以用几个线程处理大量请求。

这使得控制流比使用阻塞线程更复杂,但在重负载下,它更高效(至少在当今的硬件上)。

amb运算符是一个很好的例子,它允许类似prolog的声明性编程。

就在我们说话的时候,我正在用Scheme编写一个音乐作曲软件(我是一名音乐家,对音乐背后的理论几乎一无所知,我只是在分析我自己的作品,看看它背后的数学是如何运作的。)

使用amb算子,我可以填写旋律必须满足的约束,让Scheme计算结果。

由于语言哲学的原因,延续可能会被放入Scheme中,Scheme是一个框架,通过在Scheme本身中定义库,使您能够实现其他语言中的任何编程范式。延续用于构建自己的抽象控制结构,如“return”、“break”或启用声明性编程。Scheme更具“泛化性”,并要求程序员也能指定这样的构造。

怎么样 Google Mapplets API ?有很多函数(都以结尾 Async )您可以向其传递回呼。API函数执行异步请求,获取结果,然后将结果传递给回调(作为“下一步要做的事情”)。听起来很像 continuation passing style 对我来说。

这 example 展示了一个非常简单的案例。

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,所以没有 tail call optimization ,因此堆栈将随着每次调用的继续而增长,最终将控制线程返回给浏览器。尽管如此,我认为这是一个很好的抽象。

如果你必须调用一个异步操作,并在得到结果之前暂停执行,你通常会轮询结果,或者将其余代码放入回调中,以便在完成时由异步操作执行。使用continuation,您不需要执行低效的轮询选项,也不需要将异步事件后要运行的所有代码打包在回调中——您只需将代码的当前状态作为回调传递——异步操作完成后,代码就会被有效地“唤醒”。

延续可用于实现异常,即调试器。