A call-with-current-continuation example

The call-with-current-continuation (or call/cc for short) function in Scheme allows the creation of powerful control structures. It basically allows you to capture the current state of a computation as a first class value. This value could be assigned to a variable and invoked later.

For a great introduction to this function see the call/cc entry in the Community-Scheme-Wiki .

The following toy example shows how this function is used to do an incremental search inside a tree. Say that you have the following tree structure definition:

(define tree-data
    '(html
        (head (title "test"))
        (body
           (p "foo" (i "goo"))
           (ol
            (li "xoo" (i "moo"))
            (li (i "loo")))
           (p))))

We want to define a function to search for elements identified by a predicate. For example, if looking for a "i" element we can write:

(define (is-italic? element)
  (and (list? element) 
       (not (null? element))
       (eq? 'i (car element))))

We want to create a function to perform an incremental search inside a tree structure. That is, we want to find the first element and then request the next element if needed.

Here's a demo of the function we want to create:

> (define hit (search is-italic? tree-data))
                                           
> hit
((i "goo") #<continuation>)
> (set! hit (get-next-result hit))
> hit
((i "moo") #<continuation>)
> (set! hit (get-next-result hit))
> hit
((i "loo") #<continuation>)
> (set! hit (get-next-result hit))
> hit
(() #<continuation>)

This function is defined using call-with-current-continuation as follows:

(define (search pred? tree)
  (call-with-current-continuation
   (lambda (c)
     (searching pred? tree c))))

(define (searching pred? tree return)
  (set! return
        (call-with-current-continuation
         (lambda (continuation)
           (if (pred? tree)
               (return (list tree continuation))
               return))))
  (if (list? tree)
      (for-each
       (lambda (item)
         (set! return (cadr (searching pred? item return))))
       tree))
  (list '() return))

The entry point is the search function which captures the current continuation in the return variable. This continuation value allows us to jump to the point where call-with-current-continuation was called. We pass this value to the searching function which contains the logic to search inside the tree.

The first expression of the searching function seems confusing since it contains another call to call-with-current-continuation and an assignment of return. This code is used to do the following things:

1. Return a search result (remember that return contains a continuation)
2. Capture the current state of the tree traversal (this is done by the call-with-current-continuation call)

...
  (set! return
        (call-with-current-continuation
         (lambda (continuation)
           (if (pred? tree)
               (return (list tree continuation))
               return))))
...

Notice that a search result contains two things:

1. The tree fragment that makes the predicate true
2. The continuation of the point where the element was found (which can be used to restore the traversal)

One key thing to understand is that we change the value of return to the result of the call/cc call. This is done this way because we will change the return continuation to retrieve new results. This is done using the get-next-result function as follows:

(define (get-next-result result)
  (if (not (null? (car result)))
      (call-with-current-continuation (cadr result))
      result))

Calling call-with-current-continuation with the last captured continuation will result on setting it to the return variable in searching.