## A Simple Application of Continuations

Beginning Scheme programmers—and, indeed, even those with more experience—often have difficulty with continuations. It can be hard to get your head around the concept of continuations. Because they are so powerful and flexible, it sometimes seems as if every use must involve some heavy duty technique.

Here is a simple example that shows how to perform a return from deep
within a series of recursive calls. Given a binary tree, such as that
below, we want to write a function that will return the path from the
root to any specified node in the tree. If the node is not found, the
function should return `#f`

.

(value (left-subtree) (right-subtree))

Thus our sample tree is represented as

(define tr '(5 (4 (9 () ()) (8 () ())) (3 (1 () ()) (6 () ()))))

We will use the standard depth first search technique of recursing
down the left subtree and then the right subtree looking for the desired
node. When we find it, we would like to return the result
immediately. We could do this by having our search routine pass back
the path or #f at each call and then act accordingly, but the logic of
the function then becomes more complicated. Instead we use `call/cc`

to just return immediately.

1: ;; Return the path from the root of tree to the specified vertex 2: ;; Each vertex has the form (value (left-substree) (right-subtree)) 3: (define dfs 4: (lambda (tree vertex) 5: (letrec ((dfs1 (lambda (tree path ret) 6: (unless (null? tree) 7: (let* ((value (car tree)) 8: (new-path (cons value path))) 9: (if (= value vertex) 10: (ret (reverse new-path))) 11: (dfs1 (cadr tree) new-path ret) 12: (dfs1 (caddr tree) new-path ret)))))) 13: (call/cc 14: (lambda (ret) 15: (dfs1 tree '() ret) 16: #f) ; lambda returns here 17: ) ; call/cc returns here 18: )))

All the work is done in the `dfs1 letrec`

. We either find the correct
node and call the `ret`

function (actually, `ret`

is a continuation)
to return the path (lines 9–10) or we recurse down the left and right
subtrees (lines 11–12).

The continuation is created by the `call/cc`

on line 13. It takes a
single argument, which must be a function of a single variable. In
our case, the function is the `lambda`

function on lines 14–16. The
`call/cc`

passes the continuation to its function argument as the
function's single argument. If the node isn't in the tree, `dfs1`

will return normally and the `call/cc`

will return `#f`

. If the node
is found, calling the continuation causes control to pass to the end
of the `call/cc`

at line 17. I've abused the formatting a little so
that the extent of the `lambda`

function and the `call/cc`

are
clearer.

This example barely hints at the power of continuations but it does show that they can be used to solve everyday problems in an easy and natural way.

**Update**: Fixed typos and import of picture

## No comments:

## Post a Comment