asynchronous - How could the new async feature in c# 5.0 be implemented with call/cc?

Question

I've been following the new announcement regarding the new async feature that will be in c# 5.0. I have a basic understanding of continuation passing style and of the transformation the new c# compiler makes to code like this snippet from Eric Lippert's post:

async void ArchiveDocuments(List<Url> urls)
{
  Task archive = null;
  for(int i = 0; i < urls.Count; ++i)
  {
    var document = await FetchAsync(urls[i]);
    if (archive != null)
      await archive;
    archive = ArchiveAsync(document);
  }
}

I know that some languages implement continuations natively, via call-with-current-continuation (callcc), but I don't really understand how that works or what it does exactly.

So here's the question: if Anders et al. had decided to bite the bullet and just implement callcc in c# 5.0 instead of the async/await special case, what would the above snippet look like?

Answer 1

Original answer:

Your question, as I understand it, is "what if instead of implementing "await" specifically for task-based asynchrony, rather, the more general control flow operation of call-with-current-continuation had been implemented?"

Well, first of all let's think about what "await" does. "await" takes an expression of type Task<T>, obtains an awaiter, and calls the awaiter with the current continuation:

await FooAsync()

becomes effectively

var task = FooAsync();
var awaiter = task.GetAwaiter();
awaiter.BeginAwait(somehow get the current continuation);

Now suppose we had an operator callcc which takes as its argument a method, and calls the method with the current continuation. That would look like this:

var task = FooAsync();
var awaiter = task.GetAwaiter();
callcc awaiter.BeginAwait;

In other words:

await FooAsync()

is nothing more than

callcc FooAsync().GetAwaiter().BeginAwait;

Does that answer your question?

---

Update #1:

As a commenter points out, the answer below assumes the code generation pattern from the "Technology Preview" version of the async/await feature. We actually generate slightly different code in the beta version of the feature, though logically it is the same. The present codegen is something like:

var task = FooAsync();
var awaiter = task.GetAwaiter();
if (!awaiter.IsCompleted)
{
    awaiter.OnCompleted(somehow get the current continuation);
    // control now returns to the caller; when the task is complete control resumes...
}
// ... here:
result = awaiter.GetResult();
// And now the task builder for the current method is updated with the result.

Notice that this is somewhat more complicated, and handles the case where you are "awaiting" a result that has already been computed. There's no need to go through all the rigamarole of yielding control to the caller and picking up again where you left off if the result that you are waiting for is in fact already cached in memory for you right there.

Thus the connection between "await" and "callcc" is not quite as straightforward as it was in the preview release, but it is still clear that we are essentially doing a callcc on the "OnCompleted" method of the awaiter. We just don't do the callcc if we don't have to.

---

Update #2:

As this answer

https://stackoverflow.com/a/9826822/88656

from Timwi points out, the semantics of call/cc and await are not quite the same; a "true" call/cc requires either that we "capture" the entire continuation of a method including its whole call stack, or equivalently that the whole program be rewritten into continuation passing style.

The "await" feature is more like a "cooperative call/cc"; the continuation only captures "what is the current task-returning method about to do next at the point of the await?" If the caller of the task-returning method is going to do something interesting after the task is complete then it is free to sign up its continuation as the continuation of the task.