What's call-with-current-continuation?

A tutorial for Elisp hackers

If you know Elisp, you know catch and throw:

(defun member-p (x l)
  (catch 'exit
    (mapc #'(lambda (y)
	      (if (equal x y)
		  (throw 'exit t)))
	  l)
    nil))

Essentially, catch establishes a labelled exit point. Calling throw with the label within the extent of corresponding catch effectively makes the catch return right away, without waiting for any further evaluation. From a more low-level standpoint, throw just unwinds parts of the stack up to the activation record for the corresponding catch.

The important restriction is that throw only works within the extent of the catch. Once catch has returned, a throw to its label fails, provided there is not another catch lurking with the same label. From an implementation standpoint, this is natural.

Now, imagine first a syntactically different mechanism equivalent to catch and throw where the above code would look like this:

(defun member-p (x l)
  (let-throw exit
    (mapc #'(lambda (y)
	      (if (equal x y)
		  (funcall exit t)))
	  l)
    nil))

What we've done is, instead of using an arbitrary label to connect catch and throw, we just have a new syntactic form let-throw which binds a name to a function which subsequently performs the throw. (Exercise: Implement let-throw as a macro in Emacs Lisp.)

Now, let's say you dislike macros for some reason, but would like something equivalent to let-form. The primitive binding mechanism in Emacs Lisp is abstraction, so it might look like this:

(defun member-p (x l)
  (call-with-throw
   #'(lambda (exit)
       (mapc #'(lambda (y)
		 (if (equal x y)
		     (funcall exit t)))
	     l)
       nil)))

The call-with-throw function expects a one-argument function as its argument, and calls it right away, passing a function which performs the throw. This last explanation sounds complicated because of the multiple occurrence of the word "function", but really nothing fancy is going on.

Now, after the syntactic changes, let's change the semantic viewpoint. We've said that throw unwinds part of the stack, throwing some top part of it away. This means that, after the throw, the stack looks exactly as it looked at the time of the catch.

(That's not entirely true, as set may have mutated some of the bindings. However, the shape is the same---the same return addresses etc. etc.)

So, a slightly more brutal description of throw would be that it replaces the current stack with the catch's stack.

Now, what exactly is a stack? In traditional programming language implementations, it tells the execution engine what to do after the current function call returns. In effect, it represents the future of the computation. In the lambda calculus, where Lisp ultimately comes from, we don't talk of calls and returns, we talk of abstractions and applications. There, the future of an application (a function call) is simply the expression surrounding it, often called a context of continuation.

Normally, continuations work behind the scene, as the stack grows and shrinks. What let-throw and call-with-throw actually do is, they turn the stack (a meta object, really) into a Lisp object, that, when called, throws away the current stack and replaces it by the saved value. The restriction that the throw must happen within the extent of the call-with-throw means that a stack pointer is absolutely sufficient to represent the continuation.

Now, what about the following, totally nonsensical code:

(defvar x nil)
(call-with-throw
  #'(lambda (exit) (setq x exit)))
(funcall x 'yo-dude)

In Emacs Lisp, we have made a mistake by calling the value of exit outside the extent of its call-with-throw form. Imagine, for a second, that it would not be mistake, but that calling x could magically restore the stack that's been lost. This would mean that call-with-throw would return again, leading to an endless loop. Not exciting or useful, but it's at least possible to see what happens.

With this generalization, it makes sense to rename call-with-throw to call-with-current-continuation, as the new semantics are strictly more powerful.

The intuitive question is if call-with-current-continuation is useful for anything but producing expensive endless loops. (Of course, it's good for anything catch and throw are good for, but is its additional generality useful for anything?)

Hopefully, nobody'll kill me when I switch to Scheme notation. Remember things are lexically scoped,

(define (f ...)
    ...)

is the same as (defvar f (...) ...), funcall is unnecessary, set! is like setq, #t is "true" and #f is "false".

A frequently useful abstraction is the concept of a coroutine: Several threads run in the system, but, as opposed to threads, they transfer control among each other explicitly. Each coroutine has its own computation going, so obviously each has its own future/continuation. A coroutine is an object created by the new-coroutine procedure:

(define (new-coroutine)
  (let ((future 'dummy))
    (lambda (action)
      (if action
	  (set! future action)
	  (future #f)))))

Thus, a coroutine is a procedure which is passed a message called action. (Note the procedure is lexically closed over future. This won't work in Emacs Lisp.) The message can be:

A procedure, in which case the coroutine remembers the procedure in future.
#f, in which case the coroutine will simply call the remembered procedure stored in future.

Now, a coroutine needs to know what's supposed to happen once its running. Let's send it a message:

(define (init-coroutine! coroutine action)
  (coroutine (lambda (dummy)
               (action))))

(The dummy argument will always be bound to #f by the coroutine.) Now, the only remaining question is how control can pass between two coroutines. Let's say, the from coroutine is running, and control is to transfer to to. We need to remember how from can continue execution by getting its continuation and remembering it in the coroutine. Then, we can ask to to take control:

(define (transfer! from to)
  (call-with-current-continuation
   (lambda (c)
     (from c)
     (to #f))))

There are many other applications of call-with-current-continuation. Hopefully, this will have shed some light on the issue.

Michael Sperber [Mr. Preprocessor]

Last modified: Wed Aug 6 21:32:14 MST 2003