How Could the New Async Feature in C# 5.0 Be Implemented with Call/Cc

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

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.

How does C# async/await relates to more general constructs, e.g. F# workflows or monads?

The asynchronous programming model in C# is very similar to asynchronous workflows in F#, which are an instance of the general monad pattern. In fact, the C# iterator syntax is also an instance of this pattern, although it needs some additional structure, so it is not just simple monad.

Explaining this is well beyond the scope of a single SO answer, but let me explain the key ideas.

Monadic operations.
The C# async essentially consists of two primitive operations. You can await an asynchronous computation and you can return the result from an asynchronous computation (in the first case, this is done using a new keyword, while in the second case, we're re-using a keyword that is already in the language).

If you were following the general pattern (monad) then you would translate the asynchronous code into calls to the following two operations:

Task<R> Bind<T, R>(Task<T> computation, Func<T, Task<R>> continuation);
Task<T> Return<T>(T value);

They can both be quite easily implemented using the standard task API - the first one is essentially a combination of ContinueWith and Unwrap and the second one simply creates a task that returns the value immediately. I'm going to use the above two operations, because they better capture the idea.

Translation. The key thing is to translate asynchronous code to normal code that uses the above operations.

Let's look at a case when we await an expression e and then assign the result to a variable x and evaluate expression (or statement block) body (in C#, you can await inside expression, but you could always translate that to code that first assigns the result to a variable):

[| var x = await e; body |] 
   = Bind(e, x => [| body |])

I'm using a notation that is quite common in programming languages. The meaning of [| e |] = (...) is that we translate the expression e (in "semantic brackets") to some other expression (...).

In the above case, when you have an expression with await e, it is translated to the Bind operation and the body (the rest of the code following await) is pushed into a lambda function that is passed as a second parameter to Bind.

This is where the interesting thing happens! Instead of evaluating the rest of the code immediately (or blocking a thread while waiting), the Bind operation can run the asynchronous operation (represented by e which is of type Task<T>) and, when the operation completes, it can finally invoke the lambda function (continuation) to run the rest of the body.

The idea of the translation is that it turns ordinary code that returns some type R to a task that returns the value asynchronously - that is Task<R>. In the above equation, the return type of Bind is, indeed, a task. This is also why we need to translate return:

[| return e |]
   = Return(e)

This is quite simple - when you have a resulting value and you want to return it, you simply wrap it in a task that immediately completes. This might sound useless, but remember that we need to return a Task because the Bind operation (and our entire translation) requires that.

Larger example. If you look at a larger example that contains multiple awaits:

var x = await AsyncOperation();
return await x.AnotherAsyncOperation();

The code would be translated to something like this:

Bind(AsyncOperation(), x =>
  Bind(x.AnotherAsyncOperation(), temp =>
    Return(temp));

The key trick is that every Bind turns the rest of the code into a continuation (meaning that it can be evaluated when an asynchronous operation is completed).

Continuation monad. In C#, the async mechanism is not actually implemented using the above translation. The reason is that if you focus just on async, you can do a more efficient compilation (which is what C# does) and produce a state machine directly. However, the above is pretty much how asynchronous workflows work in F#. This is also the source of additional flexibility in F# - you can define your own Bind and Return to mean other things - such as operations for working with sequences, tracking logging, creating resumable computations or even combining asynchronous computations with sequences (async sequence can yield multiple results, but can also await).

The F# implementation is based on the continuation monad which means that Task<T> (actually, Async<T>) in F# is defined roughly like this:

Async<T> = Action<Action<T>> 

That is, an asynchronous computation is some action. When you give it Action<T> (a continuation) as an argument, it will start doing some work and then, when it eventually finishes, it invokes this action that you specified. If you search for continuation monads, then I'm sure you can find better explanation of this in both C# and F#, so I'll stop here...

Do the new C# 5.0 'async' and 'await' keywords use multiple cores?

Two new keywords added to the C# 5.0 language are async and await, both of which work hand in hand to run a C# method asynchronously without blocking the calling thread.

That gets across the purpose of the feature, but it gives too much "credit" to the async/await feature.

Let me be very, very clear on this point: await does not magically cause a synchronous method to run asynchronously. It does not start up a new thread and run the method on the new thread, for example. The method you are calling has to be the thing that knows how to run itself asynchronously. How it chooses to do so is its business.

My question is, do these methods actually take advantage of multiple cores and run in parallel or does the async method run in the same thread core as the caller?

Again, that is entirely up to the method you call. All that await does is instruct the compiler to rewrite the method into a delegate that can be passed as the continuation of the asynchronous task. That is, the await FooAsync() means "call FooAsync() and whatever comes back must be something that represents the asynchronous operation that just started up. Tell that thing that when it knows that the asynchronous operation is done, it should call this delegate." The delegate has the property that when it is invoked, the current method appears to resume "where it left off".

If the method you call schedules work onto another thread affinitized to another core, great. If it starts a timer that pings some event handler in the future on the UI thread, great. await doesn't care. All it does is makes sure that when the asynchronous job is done, control can resume where it left off.

A question you did not ask but probably should have is:

When the asynchronous task is finished and control picks up where it left off, is execution in the same thread as it was before?

It depends on the context. In a winforms application where you await something from the UI thread, control picks up again on the UI thread. In a console application, maybe not.

How does the new async/await feature in C# 5 integrate with the message loop?

It uses System.Threading.SynchronizationContext.Current. Both WPF and Winforms install their own version of SynchronizationContext. Which use their message loop to marshal the call from a worker thread back to the main UI thread. Respectively with Dispatcher.Begin/Invoke and Control.Begin/Invoke().

Getting this done in a Console mode app is not easy, its main thread doesn't have a well defined 'idle' state that would allow injecting marshaled method calls in a safe manner that avoids re-entrancy headaches. You could certainly add it but you'll be re-inventing the message loop doing so.

What's the new C# await feature do?

They just talked about this at PDC yesterday!

Await is used in conjunction with Tasks (parallel programming) in .NET. It's a keyword being introduced in the next version of .NET. It more or less lets you "pause" the execution of a method to wait for the Task to complete execution. Here's a brief example:

//create and run a new task  
Task<DataTable> dataTask = new Task<DataTable>(SomeCrazyDatabaseOperation);

//run some other code immediately after this task is started and running  
ShowLoaderControl();  
StartStoryboard();

//this will actually "pause" the code execution until the task completes.  It doesn't lock the thread, but rather waits for the result, similar to an async callback  
// please so also note, that the task needs to be started before it can be awaited. Otherwise it will never return
dataTask.Start();
DataTable table = await dataTask;

//Now we can perform operations on the Task result, as if we're executing code after the async operation completed  
listBoxControl.DataContext = table;  
StopStoryboard();  
HideLoaderControl();

C# await vs continuations: not quite the same?

await is indeed not quite the same as call/cc.

The kind of totally fundamental call/cc that you are thinking of would indeed have to save and restore the entire call stack. But await is just a compile-time transformation. It does something similar, but not using the real call stack.

Imagine you have an async function containing an await expression:

async Task<int> GetInt()
{
    var intermediate = await DoSomething();
    return calculation(intermediate);
}

Now imagine that the function you call via await itself contains an await expression:

async Task<int> DoSomething()
{
    var important = await DoSomethingImportant();
    return un(important);
}

Now think about what happens when DoSomethingImportant() finishes and its result is available. Control returns to DoSomething(). Then DoSomething() finishes and what happens then? Control returns to GetInt(). The behaviour is exactly as it would be if GetInt() were on the call stack. But it isn’t really; you have to use await at every call that you want simulated this way. Thus, the call stack is lifted into a meta-call-stack that is implemented in the awaiter.

The same, incidentally, is true of yield return:

IEnumerable<int> GetInts()
{
    foreach (var str in GetStrings())
        yield return computation(str);
}

IEnumerable<string> GetStrings()
{
    foreach (var stuff in GetStuffs())
        yield return computation(stuff);
}

Now if I call GetInts(), what I get back is an object that encapsulates the current execution state of GetInts() (so that calling MoveNext() on it resumes operation where it left off). This object itself contains the iterator that is iterating through GetStrings() and calls MoveNext() on that. Thus, the real call stack is replaced by a hierarchy of objects which recreate the correct call stack each time via a series of calls to MoveNext() on the next inner object.

Is the new C# async feature implemented strictly in the compiler

No, it's not entirely in the compiler. It relies on some new interfaces such as INotifyCompletion and some framework implementation support such as AsyncTaskMethodBuilder. I don't believe there are any CLR changes required though.

The compiler does a lot of work, building a state machine - it just refers to a few of those types within the state machine. Oh, and a lot of the Task-related types were significantly modified primarily for performance reasons.

I have a series of blog posts which were initially written against the CTP but only using vanilla .NET 4 and some classes I whipped up myself. They won't work against the production implementation (as things changed a bit over time) but they'll give you a general impression of what's going on behind the scenes.

How does C# 5.0's async-await feature differ from the TPL?

I think the misunderstanding arises here:

It seems that the await keyword is serving two different purposes. The first occurrence (FetchAsync) seems to mean, "If this value is used later in the method and its task isn't finished, wait until it completes before continuing." The second instance (archive) seems to mean, "If this task is not yet finished, wait right now until it completes." If I'm wrong, please correct me.

This is actually completely incorrect. Both of these have the same meaning.

In your first case:

var document = await FetchAsync(urls[i]);

What happens here, is that the runtime says "Start calling FetchAsync, then return the current execution point to the thread calling this method." There is no "waiting" here - instead, execution returns to the calling synchronization context, and things keep churning. At some point in the future, FetchAsync's Task will complete, and at that point, this code will resume on the calling thread's synchronization context, and the next statement (assigning the document variable) will occur.

Execution will then continue until the second await call - at which time, the same thing will happen - if the Task<T> (archive) isn't complete, execution will be released to the calling context - otherwise, the archive will be set.

In the second case, things are very different - here, you're explicitly blocking, which means that the calling synchronization context will never get a chance to execute any code until your entire method completes. Granted, there is still asynchrony, but the asynchrony is completely contained within this block of code - no code outside of this pasted code will happen on this thread until all of your code completes.

---

Related Topics