Home > Uncategorized > Call-with-current-continuation demystified

Call-with-current-continuation demystified

Many interpreted languages (though sadly not Javascript, yet) include a feature called call-with-current-continuation.

As usually described, it’s… (deep breath)… a function A that accepts a function B that will immediately be called by the language runtime, passing it a function C that when eventually (optionally) called will cause the previous call to A to return the argument previously passed to C and so take us back to where we started – but only if C was actually called. All clear?

No. Nobody ever learned what it’s for by reading a description like that. It’s the kind of description you can understand only if you’ve already had the thoughts that are expressed in it.

Well, my ambition in life is to explain it in a way that any reasonably experienced Java or C# programmer can understand, so I’ll put my current best effort here. Let me know if it helps, or hinders.

There are actually several ways to implement this feature, and any good Java programmer can invent one, once they have a description of it in Java (or OO C#) terms. In fact I suspect it’s easier to go the other way: understand a familiar practical problem in Java terms, and then see how it can be seen as an example of call-with-current-continuation. And then we’ll see why it’s not a great way to implement it, and eventually we’ll understand why the “call stack” concept (the basis for method calls, threads and local variables in Java and C#, as well as older machine-level languages) isn’t quite as fundamental as it may seem. And also why (thinking about C# 5.0), depending on how a runtime is implemented, it may not be necessary to have special keywords to support continuations.

(Although I’m talking in terms of Java, you can follow this just as well if you think of it as C#-without-delegates, which is much the same thing.)

Suppose you had an interface:

public interface AsyncResultReceiver<T> {
  void setResult(T result);
}

(C# programmers will be itching to put an I in front of that name. Let it go!) It looks like it’s part of some asynchronous programming library, a way to push a return value back to something that is waiting for it.

And suppose you had another interface:

public interface AsyncRunnable<T> {
  void doStuff(AsyncResultReceiver<T> receiver);
}

This represents some operation that you can start off by calling doStuff, and you pass it your implementation of AsyncResultReceiver so you can receive the result whenever it’s ready.

So for example you might write a class such as DownloadUrl that implement doStuff so it downloads in a background thread. When it finishes, it has a String of downloaded content, and internally it says:

notifyComplete.setResult(content);

Now, suppose the bit of application code you’re writing needs to block (wait) until the operation has finished. You’d prefer to be able to say:

String url = askUserForUrl();

byte[] html = downloadUrl(url); // much more helpful

displayHtml(html);

But you can’t, because of this pain-in-the-neck fancy asynchronous system. You need some kind of helper class to receive the result:

String url = askUserForUrl();

DownloadUrl downloader = new DownloadUrl(url);
BlockingReceiver<String> receiver = new BlockingReceiver<String>();
downloader.doStuff(receiver);
byte[] html = receiver.getResult();

displayHtml(html);

BlockingReceiver is a simple stock implementation of AsyncResultReceiver designed to solve your exact problem. I imagine, with my limited knowledge of Java concurrency primatives, it would look like this:

class BlockingReceiver<T> 
  implements AsyncResultReceiver<T> {

  CountDownLatch signal = new CountDownLatch(1);
  T result;

  public void setResult(T r) {
    result = r; // stash the result
    signal.countDown(); // wake up anyone waiting for it
  }
  
  public T getResult() {
    signal.await(); // sleep until there's a result
    return result;
  }
}

It seems simple enough, but we can make it even more easy to use by writing a static helper method, with a curiously familiar name:

public T callCC(AsyncRunnable<T> func) {
  BlockingReceiver<T> receiver = new BlockingReceiver<T>();
  func.doStuff(receiver);
  return receiver.getResult();
}

That captures the standard pattern so our example call shrinks to:

String url = askUserForUrl();

String html = callCC(new DownloadUrl(url));

displayHtml(html);

We could use that same callCC helper for any asynchronous operation, as long as it is encapsulated in a class that implements AsyncRunnable. It’s a general tool for bridging the mismatch that occurs when we have information being returned via a callback, and we would prefer to receive the information in a return value.

Let’s go back to that opaque abstract description we started with:

A function A that accepts a function B that will immediately be called by the language runtime, passing it a function C that when eventually (optionally) called will cause the previous call to A to return the argument previously passed to C and so take us back to where we started – but only if C was actually called.

We need to label some pieces of the Java example to see how it matches up. Function A is callCC. So it accepts a function B… wait a second, looking at our code we can see it actually accepts an object that implements AsyncRunnable. But that interface only has one method, doStuff. So that object is a “function”, in the sense that there is only one way you can interact with it: to call its single method. So logically speaking, it’s no more than a function.

Therefore function B must be that instance of our DownloadUrl class. According to the description, it is immediately called back and passed a function C. In our Java code we see:

BlockingReceiver<T> receiver = new BlockingReceiver<T>();
asyncRunnable.doStuff(receiver);

Sure enough, we immediately call asyncRunnable.doStuff, and we pass it a fresh instance of BlockingReceiver… which must therefore be function C!

So we’ve successfully labeled all the pieces. One of the functions is a static method, and the other two are really objects with one method, but they’re functions too, logically speaking. Fine.

The description then notes that C can optionally be called. This caveat refers to the fact that whoever writes the DownloadUrl class has a responsibility: they have to at some point call AsyncResultReceiver.setResult from the background thread, or we’ll never find out what was downloaded.

When they do call it, passing a string hopefully containing some downloaded HTML, the BlockingReceiver stashes it and wakes up the original thread, which then returns the string. Or as the description has it, it will “cause the previous call to A return the argument previously passed to C and so take us back to where we started.”

Okay, so we can be certain that callCC is call-with-current-continuation implemented in a certain way. But it’s not quite the way it gets implemented in interpreted languages. It has a particular disadvantage.

I’ve drawn attention to the fact that calling C (a.k.a. AsyncResultReceiver.setResult) is optional. If it isn’t called, then A (callCC) never returns. This is certainly true in our Java implementation – what happens is that the thread that called callCC stays locked up forever! It’s waiting for someone to call CountDownLatch.countDown.

So we’re interpreting the word “optional” very liberally here. It’s only optional if you don’t mind your program leaking locked threads. Can anything be done to avoid this? On the other hand, what would it mean to simply avoid the problem – would that be useful?

What we’re saying is that we could write a sequence of statements like:

String url = askUserForUrl();

String html = callCC(new DownloadUrl(url));

displayHtml(html);

… and if the download fails, we are quite happy if the callCC never returns (maybe the DownloadUrl class takes care of displaying an error?) and so the sequence of statements doesn’t continue executing. It somehow gets garbage collected away into nothing.

This is quite neat. It’s an alternative approach to exception handling. We don’t have to write code to say what the thread should do if there’s an error. The thread simply pops out of existence; it is absolved of all future responsibilities.

To achieve this, we’d need to modify how the JVM works. Right now it has threads, and every thread has a call stack containing the local variables (including parameters) for every currently incomplete method call in the thread. None of this is under the control of the garbage collector, so it can’t help clean up after us.

Instead, let’s make it work by allocating a garbage collectable object to represent each incomplete method call. These objects will contain the local variables and parameters as fields, and also an integer field indicating where they have reached inside the method’s bytecode. Finally, they hold a reference to another method call object, the one that called them and that they will eventually return to.

For example, given a Java method:

public int foo(int x, int y) {
  System.out.writeln("Going to add some numbers");
  int z = x + y;
  System.out.writeln("Answer was: " + z);
  return z;
}

That would need this class to store its local variables and parameter values:

public class FooCall extends MethodCall {
  public int x, y, z;
}

The base class would take care of the stuff common to all method calls:

public class MethodCall {
  public byte[] code;
  public int position;
  public MethodCall returnTo;
}

So the new model JVM would start by loading a class, looking for the main method, and allocating a suitable MethodCall to represent a call to it. It would put the method’s definition in the code field, and leave returnTo set to null and position at zero (pointing to the start of the method’s bytecode in the code array).

When it hits a call to another method, it sets the position to the right place to return to, and creates another MethodCall object for the called method, in which the returnTo field is set to point to the calling method. So at any given moment there is a chain of objects all the way back to main.

This means that the JVM itself only has to hold a reference to the top-most MethodCall object – the one it is executing. That alone will cause the garbage collector to keep the chain of objects alive. But it also means that if the JVM ever abandoned that top-most object, then the chain would automatically get collected by the GC. Nifty!

With these underpinnings, the JVM can implement callCC for us, in a different way, using some butt-ugly primitive operations:

public T callCC(AsyncRunnable<T> asyncRunnable) {

  BlockingReceiver<T> receiver = new BlockingReceiver<T>(CALLER);
  
  asyncRunnable.doStuff(receiver);
  return null; // we never get here!
}

And so it must implement BlockingReceiver a different way as well:

class BlockingReceiver<T> 
  implements AsyncResultReceiver<T> {

  MethodCall returnTo;
  
  public BlockingReceiver(MethodCall r) {
    returnTo = r;
  }

  public void setResult(T r) {
    GOTO(returnTo, r);
  }
}

Here I’m imagining that the JVM has two low-level instructions: CALLER is a pseudo-variable containing the MethodCall that called the currently executing method. GOTO is a pseudo-method that swaps in a different MethodCall to be the currently executing one (abandoning the existing one). It expects that method call to be stuck in a position where it is about to return from a method call, and so it needs to know the return value to pass back (if any).

So the statement return "A string"; really means:

GOTO(CALLER, "A string");

This is how call-with-current-continuation works in interpreted languages. In these ugly, technical terms, a “continuation” is literally just an object of a class derived from MethodCall, which has its position field pointing to the bytecode instruction that comes right after a call to a method and is expecting a return value (unless it called a void method, of course).

Sometimes people describe a continuation as a snapshot of the state of the program at some point in the past, but that is incorrect. It’s not a complete snapshot of all state. It’s just a reference to a MethodCall and hence the chain of other calls that led to its creation. But when we bring it back to life using GOTO, various other things might have changed; the values stored in the fields of various objects will have been modified. So the program is definitely not put back into exactly the state it was in previously.

This is enough for one blog post, but there are implications to deal with. Somewhere further down the line, I’ll tie this into my series of posts on exceptions (like, what the heck happens to try/finally in this alternative runtime model?)

In my next post I’ll address the first question that probably springs to mind: why is it customary to expose callCC as the primitive operation for public use, instead of exposing CALLER and GOTO directly? And if a method call can sometimes never return, is it okay for it return more than once?!

About these ads
  1. Trillian
    December 16, 2010 at 7:14 pm

    Hi, just dropping a word to say that I appreciate your blog posts on programming languages, they are usually nicely written and instructive.

    • earwicker
      December 19, 2010 at 10:19 am

      Why thank you!

  2. May 27, 2012 at 7:27 am

    This post cleared up things after trying and failing to understand the definition from wiki. Thanks.

  1. June 25, 2014 at 11:35 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: