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?

Wilk

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://mcmap.net/q/21025/-c-await-vs-continuations-not-quite-the-same

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.

Renown

Eric, I'm always amazed at how you seem to magically "detect" these questions and answer them in no time... is there a hidden "eric-lippert" tag that notifies you automatically ? ;) – Telegenic

I think I finally got it. await helps with the continuation passing style. It is semantically quite different to call/cc even if you rewrite the entire program into CPS: you still never get an object (the continuation) to which you can pass an argument to be returned by the original call/cc invocation. – Slipway

Answer 2

I'm no expert at continuations, but I'll take a stab at explaining the difference between async/await and call/cc. Of course this explanation assumes I understand call/cc and async/await, which I'm not sure I do. Nevertheless, here goes...

With C# 'async', you are telling the compiler to generate a special version of that specific method which understands how to bottle it's state into a heap-data-structure, so it can be "removed from the real stack" and resumed later. Within an async-context, "await" is then like "call/cc" in that it uses the compiler-generated objects to bottle up the state and get off the "real stack" until the task completes. However, because it's the compiler rewriting of an async-method that allows the state to be bottled up, await can only be used within an async context.

In first-class call/cc, the language runtime generates all code such that the current continuation can be bottled up into a call-continuation-function (making the async keyword unnecessary). call/cc still acts like await, causing the current-continuation state (think of the stack state) to be botled up and passed in as a function to the called-function. One way to do this is to use heap-frames for all function invocation, instead of 'stack' frames. (sometimes referred to as 'stackless', as in 'stackless python' or many scheme implementations) Another way is to remove all the data from the "real stack" and stuff it into a heap data-structure before calling the call/cc target.

Some tricky issues can arise if there are calls to external functions (think DllImport) intermixed on the stack. I suspect this is the reason they went with the async/await implementation.

http://www.madore.org/~david/computers/callcc.html

---

Because in C#, a function must be marked as "async" in order to use these mechanics, I wonder if this async keyword will become a virus that spreads to lots of functions in lots of libraries. If this happens. they may eventually realize they should implement first-class call/cc at the VM level, instead of this compiler-rewriting based async model. Only time will tell. However, it's certainly a useful tool in the context of the current C# environment.

Canton

Answer 3

Kinda pointless I'd say. Scheme interpreters often implement call/cc with a state machine that captures local state onto the heap. Which is exactly what C# 5.0 (or more correctly C# 2.0's iterator) does as well. They did implement call/cc, the abstraction they came up with is quite elegant.

Raddie

The point is to wrap my head around continuations. Are you saying that await is call/cc ? – Wilk

Yes, it is implemented the exact same way. Study the IL that's generated by an iterator with ildasm or Reflector to understand how it works. Note the state machine in the class with the mysterious name. – Raddie

While it is implemented the same way, it doesn’t follow that await is call/cc. It is actually a subset, and a very small one at that. The important difference is that call/cc lets you pass an argument from the invocation to the continuation. See also my answer here in response to which Eric Lippert edited his answer here. – Yours