call-with-current-continuation. We will
see how this operator can be used to create a
breathtaking variety of control idioms.
call-with-current-continuationcall-with-current-continuation calls its argument, which must be a unary procedure,
with a value called the ``current
continuation''. If nothing else, this explains the
name of the operator. But it is a long name, and is
often abbreviated
call/cc.4The current continuation at any point in the execution of a program is an abstraction of the rest of the program. Thus in the program
(+ 1 (call/cc
(lambda (k)
(+ 2 (k 3)))))
the rest of the program, from the point of view of the
call/cc-application, is the following
program-with-a-hole (with [] representing the
hole):
(+ 1 [])
In other words, this continuation is a program that
will add 1 to whatever is used to fill its hole.
This is what the argument of call/cc is called
with. Remember that the argument of call/cc is
the procedure
(lambda (k)
(+ 2 (k 3)))
This procedure's body applies the continuation (bound
now to the parameter k) to the argument 3.
This is when the unusual aspect of the continuation
springs to the fore. The continuation call abruptly
abandons its own computation and replaces it with the
rest of the program saved in k! In other words,
the part of the procedure involving the addition of
2 is jettisoned, and k's argument 3 is sent
directly to the program-with-the-hole:
(+ 1 [])
The program now running is simply
(+ 1 3)
which returns 4. In sum,
(+ 1 (call/cc
(lambda (k)
(+ 2 (k 3)))))
=> 4
The above illustrates what is called an escaping continuation, one used to exit out of a
computation (here: the (+ 2 []) computation). This
is a useful property, but Scheme's continuations can
also be used to return to previously abandoned
contexts, and indeed to invoke them many times. The
``rest of the program'' enshrined in a continuation is
available whenever and how many ever times we choose to
recall it, and this is what contributes to the great
and sometimes confusing versatility of call/cc. As
a quick example, type the following at the listener:
(define r #f)
(+ 1 (call/cc
(lambda (k)
(set! r k)
(+ 2 (k 3)))))
=> 4
The latter expression returns 4 as before. The
difference between this use of call/cc and the
previous example is that here we also store the
continuation k in a global variable r.
Now we have a permanent record of the continuation in
r. If we call it on a number, it will return that
number incremented by 1:
(r 5)
=> 6
Note that r will abandon its own continuation,
which is better illustrated by embedding the call to
r inside some context:
(+ 3 (r 5))
=> 6
The continuations provided by call/cc are thus
abortive continuations.
call/cc and are very useful for programming
procedure or loop exits. Consider a procedure
list-product that takes a list of numbers and
multiplies them. A straightforward recursive
definition for list-product is:
(define list-product
(lambda (s)
(let recur ((s s))
(if (null? s) 1
(* (car s) (recur (cdr s)))))))
There is a problem with this solution. If one of the
elements in the list is 0, and if there are many
elements after 0 in the list, then the answer is a
foregone conclusion. Yet, the code will have us go
through many fruitless recursive calls to recur
before producing the answer. This is where an escape
continuation comes in handy. Using call/cc, we can
rewrite the procedure as:
(define list-product
(lambda (s)
(call/cc
(lambda (exit)
(let recur ((s s))
(if (null? s) 1
(if (= (car s) 0) (exit 0)
(* (car s) (recur (cdr s))))))))))
If a 0 element is encountered, the continuation
exit is called with 0, thereby avoiding
further calls to recur.
(same-fringe? '(1 (2 3)) '((1 2) 3))
=> #t
(same-fringe? '(1 2 3) '(1 (3 2)))
=> #f
The purely functional approach is to flatten both trees and check if the results match.
(define same-fringe?
(lambda (tree1 tree2)
(let loop ((ftree1 (flatten tree1))
(ftree2 (flatten tree2)))
(cond ((and (null? ftree1) (null? ftree2)) #t)
((or (null? ftree1) (null? ftree2)) #f)
((eqv? (car ftree1) (car ftree2))
(loop (cdr ftree1) (cdr ftree2)))
(else #f)))))
(define flatten
(lambda (tree)
(cond ((null? tree) '())
((pair? (car tree))
(append (flatten (car tree))
(flatten (cdr tree))))
(else
(cons (car tree)
(flatten (cdr tree)))))))
However, this traverses the trees completely to flatten
them, and then again till it finds non-matching
elements. Furthermore, even the best flattening
algorithms will require conses equal to the total
number of leaves. (Destructively modifying the input
trees is not an option.)
We can use call/cc to solve the problem without
needless traversal and without any consing. Each
tree is mapped to a generator, a procedure with
internal state that successively produces the leaves of
the tree in the left-to-right order that they occur in
the tree.
(define tree->generator
(lambda (tree)
(let ((caller '*))
(letrec
((generate-leaves
(lambda ()
(let loop ((tree tree))
(cond ((null? tree) 'skip)
((pair? tree)
(loop (car tree))
(loop (cdr tree)))
(else
(call/cc
(lambda (rest-of-tree)
(set! generate-leaves
(lambda ()
(rest-of-tree 'resume)))
(caller tree))))))
(caller '()))))
(lambda ()
(call/cc
(lambda (k)
(set! caller k)
(generate-leaves))))))))
When a generator created by tree->generator is
called, it will store the continuation of its call in
caller, so that it can know who to send the leaf to
when it finds it. It then calls an internal procedure
called generate-leaves which runs a loop traversing
the tree from left to right. When the loop encounters
a leaf, it will use caller to return the leaf as
the generator's result, but it will remember to store
the rest of the loop (captured as a call/cc
continuation) in the generate-leaves variable. The
next time the generator is called, the loop is resumed
where it left off so it can hunt for the next leaf.
Note that the last thing generate-leaves does,
after the loop is done, is to return the empty list to
the
caller. Since the empty list is not a valid leaf
value, we can use it to tell that the generator has
no more leaves to generate.
The procedure same-fringe? maps each of its tree
arguments to a generator, and then calls these two
generators alternately. It announces failure as soon
as two non-matching leaves are found:
(define same-fringe?
(lambda (tree1 tree2)
(let ((gen1 (tree->generator tree1))
(gen2 (tree->generator tree2)))
(let loop ()
(let ((leaf1 (gen1))
(leaf2 (gen2)))
(if (eqv? leaf1 leaf2)
(if (null? leaf1) #t (loop))
#f))))))
It is easy to see that the trees are traversed at most
once, and in case of mismatch, the traversals extend
only upto the leftmost mismatch. cons is not used.
We will view a coroutine as a unary procedure, whose
body can contain resume calls. resume is a
two-argument procedure used by a coroutine to resume
another coroutine with a transfer value.
A coroutine (let's call it A) has an internal variable called
local-control-state that stores, at any point, the
remaining computation of the coroutine. Initially
this is the entire coroutine computation. When
resume is called -- i.e., invoking another coroutine
B -- the current coroutine will update its
local-control-state value to the rest of itself,
stop itself, and then jump to the resumed coroutine
B. When coroutine A is itself
resumed at some later point, its computation will
proceed from the continuation stored in its
local-control-state.
(define-macro coroutine
(lambda (x . body)
`(letrec ((local-control-state
(lambda (,x) ,@body))
(resume
(lambda (c v)
(call/cc
(lambda (k)
(set! local-control-state k)
(c v))))))
(lambda (v)
(local-control-state v)))))
(define make-matcher-coroutine
(lambda (tree-cor-1 tree-cor-2)
(coroutine dont-need-an-init-arg
(let loop ()
(let ((leaf1 (resume tree-cor-1 'get-a-leaf))
(leaf2 (resume tree-cor-2 'get-a-leaf)))
(if (eqv? leaf1 leaf2)
(if (null? leaf1) #t (loop))
#f))))))
The leaf-generator coroutines remember who to send their leaves to:
(define make-leaf-gen-coroutine
(lambda (tree matcher-cor)
(coroutine dont-need-an-init-arg
(let loop ((tree tree))
(cond ((null? tree) 'skip)
((pair? tree)
(loop (car tree))
(loop (cdr tree)))
(else
(resume matcher-cor tree))))
(resume matcher-cor '()))))
The same-fringe? procedure can now almost
be written as
(define same-fringe?
(lambda (tree1 tree2)
(letrec ((tree-cor-1
(make-leaf-gen-coroutine
tree1
matcher-cor))
(tree-cor-2
(make-leaf-gen-coroutine
tree2
matcher-cor))
(matcher-cor
(make-matcher-coroutine
tree-cor-1
tree-cor-2)))
(matcher-cor 'start-ball-rolling))))
Unfortunately, Scheme's letrec can resolve
mutually recursive references amongst the lexical
variables it introduces only if such variable
references are wrapped inside a lambda. And so we
write:
(define same-fringe?
(lambda (tree1 tree2)
(letrec ((tree-cor-1
(make-leaf-gen-coroutine
tree1
(lambda (v) (matcher-cor v))))
(tree-cor-2
(make-leaf-gen-coroutine
tree2
(lambda (v) (matcher-cor v))))
(matcher-cor
(make-matcher-coroutine
(lambda (v) (tree-cor-1 v))
(lambda (v) (tree-cor-2 v)))))
(matcher-cor 'start-ball-rolling))))
Note that call/cc is not called directly at all in
this rewrite of same-fringe?. All the continuation
manipulation is handled for us by the
coroutine macro.
4 If your Scheme does not already have this
abbreviation, include
(define call/cc call-with-current-continuation) in
your initialization code and protect yourself from
RSI.