C# await vs continuations: not quite the same?

Question

After reading Eric Lippert’s answer I got the impression that await and call/cc are pretty much two sides of the same coin, with at most syntactic differences. However, upon trying to actually implement call/cc in C# 5, I ran into a problem: either I misunderstand call/cc (which is fairly possible), or await is only reminiscent of call/cc.

Consider pseudo-code like this:

function main:
    foo();
    print "Done"

function foo:
    var result = call/cc(bar);
    print "Result: " + result;

function bar(continuation):
    print "Before"
    continuation("stuff");
    print "After"

If my understanding of call/cc is correct, then this should print:

Before
Result: stuff
Done

Crucially, when the continuation is called, the program state is restored along with the call history, so that foo returns into main and never comes back to bar.

However, if implemented using await in C#, calling the continuation does not restore this call history. foo returns into bar, and there’s no way (that I can see) that await can be used to make the correct call history part of the continuation.

Please explain: did I completely mis-understand the operation of call/cc, or is await just not quite the same as call/cc?

---

Now that I know the answer, I have to say that there’s a good reason to think of them as fairly similar. Consider what the above program looks like in pseudo-C#-5:

function main:
    foo();
    print "Done"

async function foo:
    var result = await(bar);
    print "Result: " + result;

async function bar():
    print "Before"
    return "stuff";
    print "After"

So while the C# 5 style never gives us a continuation object to pass a value to, overall the similarity is quite striking. Except that this time it’s totally obvious that "After" never gets called, unlike in the true-call/cc example, which is another reason to love C# and praise its design!

Answer 1

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.