call-with-current-continuation


A short introduction to call-with-current-continuation

Scheme provides a very powerful control abstraction named call-with-current-continuation. Not only is the name intimidating, but many introductions to its semantics are as well. This introduction tries to be much gentler. C programmers can also read call-with-current-continuation-for-C-programmers.

To understand this text, you should be aware and secure in your use of higher order procedures like map and for-each, the use of lambda, passing procedures to other procedures, and returning procedures from procedures.

First of all, though, this introduction uses an abbreviation for the long-winded name: call/cc. This is somewhat less intimidating and a bit easier on the fingers. Some implementations provide an alias variable already; if not it is trivial to define for running the example code in this tutorial:

 (define call/cc call-with-current-continuation) 

Exit Continuations: Get me out of here

One of the simplest uses of call/cc is to provide a simple escape mechanism out of any nested computation. In some languages, such as Java or C, this is known under names such as break, continue, and return. I now have a problem, though. Using normal recursion, most problems that mandate the use of any of those keywords in those languages (for example, iterating over a two-dimensional array) are trivial when written in the recursive of Scheme. So you now have to bear with me when I take some far-fetched examples.

Let's take for example a simple search for an entry in a list. We can of course manually recurse over the list, and just not recurse anymore when we've found it. Yet, there's the procedure for-each for traversing a list. We somehow are forced to use it. It would be useful if we could just write the following:

 ;;; Return the first element in LIST for which WANTED? returns a true 
 ;;; value. 
 ;;; NOTE: This is not working Scheme code! 
 (define (search wanted? lst) 
   (for-each (lambda (element) 
               (if (wanted? element) 
                   (return element))) 
             lst) 
   #f) 

We use a procedure named return here which would, hopefully, return from search, and use the value of element which we pass as an argument as the return value of search. If for-each comes to an end, we haven't found what we were looking for, and can return #f.

Sadly, such a procedure does not exist in Scheme. But, call/cc to the rescue! Using it, we can get this procedure. Now, how do we use call/cc? The procedure gets as an argument another procedure, which is then called with a single argument: The return procedure we above were looking for! As soon as the return procedure is called, the call to call/cc returns. Specifically, call/cc returns the argument passed to the return procedure. In a concrete example, the code above can be written in actual working Scheme:

 ;;; Return the first element in LST for which WANTED? returns a true 
 ;;; value. 
 (define (search wanted? lst) 
   (call/cc 
     (lambda (return) 
       (for-each (lambda (element) 
                   (if (wanted? element) 
                       (return element))) 
                 lst) 
       #f))) 

Here we can see how the procedure return is introduced into the scope of the for-each expression where we are using it. As soon as we found the element we were looking for, we pass it to the return procedure. As soon as this happens, the call/cc expression returns this value. Nothing else is done. The whole expression terminates. You can picture this as a kind of goto - you just jump through the code and all the calls to the call/cc and return from it.

A note is appropriate here. Dijkstra's famous paper GOTO Statement Considered Harmful is appropriate here as well: call/cc can be very confusing for programs. Its use should be carefully limited and preferably abstracted away so that it can not interfere with the normal understanding of the program.

Now that I issued this warning, let's continue. Is your brain twisted enough already? You haven't seen much of what call/cc is able to do.

As return is just a normal variable, we can of course pass it around. Again stretching examples a bit to be able to concentrate on the issue at hand, let's say we pass not a predicate wanted?, but a procedure treat that accepts two arguments: an element, and a procedure to call if it likes that element.

 ;;; Call LIKE-IT with a custom argument when we like ELEMENT. 
 (define (treat element like-it) 
   (if (good-element? element) 
       (like-it 'fnord))) 
  
 ;;; Call TREAT with every element in the LIST and a procedure to call 
 ;;; when TREAT likes this element. 
 (define (search treat lst) 
   (call/cc 
     (lambda (return) 
       (for-each (lambda (element) 
                   (treat element return)) 
                 lst) 
       #f))) 

As you can see, we pass treat the return procedure we got from call/cc. Treat then proceeds to do some processing, and in the event that it likes it, calls the return procedure with a value it's liking. As we remember, as soon as we call the return procedure, the argument to it is returned from the call to call/cc that created the return procedure. We are effectively jumping from within the treat procedure to the invocation of call/cc in search.

This is no different from the use of return above, but as you can see, it works from anywhere in the program. That property gave this kind of operation a special name: non-local exit. We are not exiting locally at the location of the exit instruction, but at a completely different place, or locality.

Full Continuations: And back in!

So far we have seen a trivial use of call/cc only. All we did so far was escaping from a deeply nested call structure - many calls of procedures deep, we were able to use the return procedure to leave all these calls behind and go up, to exit. These are called exit continuations. Only now, the word continuation which is part of call/cc shows up again. Exit continuations are a special kind of continuation, and call/cc creates the general kind.

A continuation is something that is used to continue. The return we used above was a continuation we used to continue back up where we created it. We continued the computation at the location of call/cc.

What happens if the continuation created with call/cc escapes the body of the procedure passed to call/cc? Let's say, for example:

 (define return #f) 
  
 (+ 1 (call/cc 
        (lambda (cont) 
          (set! return cont) 
          1))) 

The evaluator will print the value 2, because the body of the call/cc expression terminated normally, returning the value of 1. This is then added to 1, which yields 2. But! We have a variable named return now, which is bound to the continuation created with this call/cc there. What happens if we call it with a parameter of, say, 22?

 > (return 22) 
 23 

Now what happened here? The return procedure did the same thing it did above: The 22 passed to return is used as the return value of the call/cc call. This return value is then added to 1, which yield 23. And this is what we got. We never returned from the call to return, but returned from the addition way above there.

The difference here is that we re-entered the computation from outside, we did not just leave it. This is a big brain-twister. Be sure to understand it!

Coroutines: And out. And in. And out...

Let's assume we have a procedure which does a lengthy task. We don't want to block the system completely, so we separate the task in little steps. After we did one of those steps, we call a procedure which lets the system carry out any task it might want to do right now. Now comes the twist: This procedure is passed a procedure, specifically a continuation, which it should call to resume the lengthy computation:

 (define (hefty-computation do-other-stuff) 
    (let loop ((n 5)) 
      (display "Hefty computation: ") 
      (display n) 
      (newline) 
      (set! do-other-stuff (call/cc do-other-stuff)) 
      (display "Hefty computation (b)")  
      (newline) 
      (set! do-other-stuff (call/cc do-other-stuff)) 
      (display "Hefty computation (c)") 
      (newline) 
      (set! do-other-stuff (call/cc do-other-stuff)) 
      (if (> n 0) 
          (loop (- n 1))))) 

When do-other-stuff calls the procedure it got passed by call/cc, the computation will resume right here, the loop will recurse, and the next step is done. Of course, besides such a hefty computation, every other computation is superfluous. Since it's superfluous, it should do the same as pointed, and let the system do other stuff when possible:

 ;; notionally displays a clock 
 (define (superfluous-computation do-other-stuff) 
    (let loop () 
      (for-each (lambda (graphic) 
                  (display graphic) 
                  (newline) 
                  (set! do-other-stuff (call/cc do-other-stuff))) 
                '("Straight up." "Quarter after." "Half past."  "Quarter til.")) 
      (loop))) 

What happens now if you enter the following input:

 > (hefty-computation superfluous-computation) 
 Hefty computation: 5 
 Straight up. 
 Hefty computation (b) 
 Quarter after. 
 Hefty computation (c) 
 Half past. 
 Hefty computation: 4 
 Quarter til. 
 . 
 . 
 . 

Now what is happening here? The hefty computation did one step, and passed the control to the superfluous computation. This in turn did one step and passed control back to the hefty computation. Now this of course did a step and passed control to the superfluous computation. And... You get the pattern. These two procedures are calling each other alternatingly, passing control between the two. Of course, this is not limited to two procedures, but could be done between any number of procedures. Procedures which pass control between them like this are called Coroutines, since they are effectively processed in parallel.

I hope you now have a basic understanding of continuations, and will be able to tell anyone who is scared about them that they're not scary at all. But let me repeat my earlier warning: Continuations can be easily abused. Don't overdo it. You don't have to use continuations everywhere, really!


See also call-with-current-continuation in the R5RS.


category-learning-scheme