Looking for examples of "real" uses of continuations

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!

Answer 1

Continuations can be used in "real-life" examples whenever the program flow is not linear, or not even pre-determined. A familiar situation is web applications.

Answer 2

Continuations are used by some web servers and web frameworks to store session information. A continuation object is created for each session and then used by each request within the session.

There's an article about this approach here.

Answer 3

Seaside:

• homepage
• wikipedia page

Answer 4

@Pat

Seaside

Yes, Seaside is a great example. I browsed its code quickly and found this message illustrating passing control between components in a seemingly statefull way accross the 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 ]

So nice!

Answer 5

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

Answer 6

I came accross an implementation of the amb operator in this post from http://www.randomhacks.net, using continuations.

Here's what the amb opeerator does:

# 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

And here's the post's implementation:

# 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

I like amb!

Answer 7

I built my own unit testing software. Before executing the test, I store the continuation before executing the test, and then on failure, I (optionally) tell the scheme interpreter to drop into debug mode, and re-invoke the continuation. This way I can step through the problematic code really easily.

If your continuations are serializable, you can also store then on application failure, and then re-invoke them to get detailed information about variable values, stack traces, etc.

Answer 8

Continuations are a good alternative to thread-per-request in server programming (including web application frontends.

In this model, instead of launching a new (heavy) thread every time a request comes in, you just start some work in a function. Then, when you are ready to block on I/O (i.e. reading from the database), you pass a continuation into the networking response handler. When the response comes back, you execute the continuation. With this scheme, you can process lots of requests with just a few threads.

This makes the control flow more complex than using blocking threads, but under heavy load, it is more efficient (at least on today's hardware).

Answer 9

How about the Google Mapplets API? There are a bunch of functions (all ending in Async) to which you pass a callback. The API function does an async request, gets it's result, then passes that result to your callback (as the "next thing to do"). Sounds a lot like continuation passing style to me.

This example shows a very simple case.

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");

As this is Javascript there's no tail call optimization, so the stack will grow with every call into a continuation, and you'll eventually return the thread of control to the browser. All the same, I think it's a nice abstraction.

Answer 10

Continuations can be used to implement exceptions, a debugger.

Answer 11

I love "Call with Current Continuation Patterns". It contains examples of real-life uses of continuations for exiting loops, escaping (and reentring) recursion, doing multitasking or doing non-blind backtracking, among others.

It's very well explained too.

Answer 12

If you have to invoke an asynchronous action, and suspend execution until you get the result, you would normally either poll for the result or put the rest of your code in a callback to be executed by the asynchronous action upon completion. With continuations you don't need to do the inefficient option of polling, and you don't need to wrap up all your code to be run after the asynch event in a callback - you just pass the current state of the code as your callback - and the code is effectively "woken up" as soon as the asynch action completes.

Answer 13

The amb operator is a good example that allows prolog-like declarative programming.

As we speak I'm coding a piece of music composition software in Scheme (I'm a musician with next to no knowledge of the theory behind music and I'm just analysing my own pieces to see how the maths behind it works.)

Using the amb operator I can just fill in constraints which a melody must satisfy and let Scheme figure out the result.

Continuations are probably put into Scheme because of the language philosophy, Scheme is a framework enabling you to realize about any programming paradigm found in other language by defining libraries in Scheme itself. Continuations are for making up your own abstract control structures like 'return', 'break' or to enable declarative programming. Scheme is more 'generalizing' and begs that such constructs should be able to be specified by the programmer too.