寻找延续的"实际"用法的例子

Question

I'm trying to grasp the concept of continuations and I found several small teaching examples like this one from the Wikipedia article:

(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))

I understand what this little function does, but I can't see any obvious application of it. While I don't expect to use continuations all over my code anytime soon, I wish I knew a few cases where they can be appropriate.

So I'm looking for more explicitely usefull code samples of what continuations can offer me as a programmer.

Cheers!

转载于:https://stackoverflow.com/questions/34155/looking-for-examples-of-real-uses-of-continuations

Answer 1

In Algo & Data II we used these all the times to "exit" or "return" from a (long) function

for example the BFS algorthm to traverse trees with was implemented like this:

(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)))))))))

As you can see the algorithm will exit when the node-discovered function returns true:

    (if (node-discovered node)
      (exit node))

the function will also give a "return value": 'node'

why the function exits, is because of this statement:

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

when we use exit, it will go back to the state before the execution, emptying the call-stack and return the value you gave it.

So basically, call-cc is used (here) to jump out of a recursive function, instead of waiting for the entire recursion to end by itself (which can be quite expensive when doing lots of computational work)

another smaller example doing the same with 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))))