A little Call/cc in C#

Yesterday, I wanted to show someone how CallCC works in C#/async, but I couldn’t find any examples in my web search results. C#/async has been out in the world for some time, I’d be surprised if this hasn’t been done before, but just in case here’s a quick implementation.

Enjoy.

~ ~ ~

Call-with-current-continuation (commonly abbreviated as “call/cc”) is a funny little subroutine that exists in some programming languages and manipulates control flow. Unlike conditionals, loops, and normal subroutines, call/cc generalizes the return context of the currently executing subroutine, where that context is called a “continuation”. It allows you to replace the continuation, save it for later, or in some cases, duplicate it.

And thanks to C#’s latest async / await programming features, you too can write continuation manipulating programs.

First, what’s a continuation? Consider a simple arithmetic expression:

// program #1
Console.WriteLine(1 * 2 + 3 * 4);

When evaluating 1 * 2, the computer has to remember where the result will “go” once it’s finished. You can think of it as if there’s a little “hole” where to put the result:

Console.WriteLine(___ + 3 * 4);

As it gets further along, expressions are substituted with their results. When evaluating 3 * 4, the continuation now looks like this:

Console.WriteLine(2 + ___);

The result of 1 * 2, 2, has been substituted into the former hole, and now we have a new hole for the subexpression 3 * 4

What the computer is really doing is running through a sequence of instructions the compiler wrote that operate on registers and a data stack and so forth, but that’s just matters of efficiency. Mechanisms aside, your program must behave as-if it is doing these substitutions and remembering where to put the results when it’s done, in little steps.

At the end, this program results in substituting 14 as the argument to WriteLine.

If this is reminding you of simple high school algebra, then you’re on the right track.

CallCC

Normal subroutine calls are just substitutions. Above, when I multiplied 1 * 2, the multiplication subroutine did its thing on the inputs, computed a result, but the next step is always to substitute the result in the hole. That’s the only thing normal subroutines do, they fill the hole.

CallCC does something else. It calls you back reflexively with the continuation, hole and all, as an algebraic object. You can substitute whatever you want into that hole, but more importantly, you can replace whatever the current continuation is with one of your choosing. You can choose a different hole to fill.

In the simple case, CallCC works like before:

// program #2
Console.WriteLine(await TaskEx2.CallCC(async k => 1 * 2 + 3 * 4));

CallCC turns around and calls your subroutine with ‘k’, which you can ignore for now. Your subroutine runs, and if it returns a result, CallCC just substitutes that result as normal. So while 3*4 is being evaluated, the continuation looks something like:

Console.WriteLine(2 + ___)

However, that ‘k’ is the continuation for where CallCC appeared. That is, k =

Console.WriteLine(___);

Here’s where it gets tricky. I can tweak the expression slightly, and write:

// program #3
Console.WriteLine(await TaskEx2.CallCC(async k => 1 * 2 + await k(3 * 4)));

When 3 * 4 is being evaluated, the continuation now looks something like

Console.WriteLine(1*2 + await k(___))

But once 12 is substituted into k, the subroutine k will replace the current continuation with the earlier one, the one where ‘await CallCC(…)’ appeared:

Console.WriteLine(___)

So this program just prints 12, not 14.

What happened to “2+___”?

In program #3, I have a portion of one continuation that was never substituted, involving that dangling “2 + ___” addition. What happened to it?

It was thrown out.

This isn’t unusual, and you’re probably familiar with throwing away continuations with the usual conditional operator: “if” statements. Consider this program:

// program #4
if (1 < 0) { return 3; } else { return 4; }

When evaluating 1 < 0, I have a continuation that looks like:

if (___) { return 3; } else { return 4; }

An if statement has two nested continuations being considered; “return 3” and “return 4”. Once I’ve substituted the value “false” into this continuation, I’m left with:

return 4

Half of the continuation is thrown away.

Implementation

This CallCC function I’ve been using isn’t fiction. The implementation below uses custom awaiters, but other approaches are possible too. I’ll show it to you.

I’ll be skipping over many of the details of writing awaiters. Stephen Toub has given this subject an excellent treatment already.

public struct NeverAwaitable : INotifyCompletion
{
    public NeverAwaitable GetAwaiter() { return this; }
    public dynamic GetResult() { return 0; }
    public bool IsCompleted { get { return false; } }
    public void OnCompleted(Action continuation) {}
}

NeverAwaitable is the first primitive I need, and is very boring as it’s purpose is to carefully do nothing. This is what the continuation “k” will return, so that the caller can await it to ‘throw away’ the now-defunct continuation. Since k’s continuation is never used, it’s convenient to let the await result be inferred to be any type so we can use it in any expression. C# generics don’t infer return types, so I can’t declare it “public U GetResult()”. Luckily the ‘dynamic’ data type can coerce to anything, so that’s just as fine.

public partial class CallCCAwaitable<R> : INotifyCompletion
{
    R value;
    bool isCompleted;
    Action continuation;

    public CallCCAwaitable() { }

    public CallCCAwaitable<R> GetAwaiter() { return this; }
    public R GetResult() { return value; }
    public bool IsCompleted { get { return isCompleted; } }
    public void OnCompleted(Action continuation)
    {
        if (isCompleted)
            continuation();
        else
            this.continuation = continuation;
    }
    public void Complete(R value)
    {
        if (!isCompleted)
        {
            this.value = value;
            isCompleted = true;
            if (continuation != null)
            {
                var continuation_ = this.continuation;
                this.continuation = null;
                continuation_();
            }
        }
    }
}

CallCCAwaitable is the ‘glue’ for moving the result from the user’s subroutine back up to the continuation. In async/await, either the result or the continuation can occur first, so I have to be prepared for both cases. Once both are available, CallCCAwaitable invokes the continuation. You can also see the “one-shot” nature here, where it ignores extra calls to Complete.

public static CallCCAwaitable<R> CallCC<R>(
    Func<Func<R, NeverAwaitable>, Task<R>> thunk
    )
{
    var awaitable = new CallCCAwaitable();
    awaitable.Attach(thunk);
    return awaitable;
}
public partial class CallCCAwaitable<R>
{
    internal async void Attach(Func<Func<R, NeverAwaitable>, Task<R>> thunk)
    {
        this.Complete(
            await thunk(result_ =>
            {
                this.Complete(result_);
                return new NeverAwaitable();
            }));
    }
}

This is the workhorse. CallCC constructs an appropriate awaitable, and attaches the user thunk to it. “Attaching” here means that the user thunk is invoked, and can satisfy the CallCC awaiter either (a) by asynchronously returning a result, or (b) invoking the continuation delegate was passed into the user thunk. If the user thunk takes option (b), it completes the CallCC awaiter and signal to the thunk to terminate by passing it a NeverAwaitable.

Okay, that’s facinating. Now what?

You can read more about call/cc, its history and implementations at “A page about call/cc“.

Callcc in relation to C#/async is discussed on stackoverflow.com, but little treatment is given to the one-shot behavior.

Eric Lippert has multiple facinating posts on call/cc in relation to Continuation Passing Style (CPS), JavaScript, and C#.

Apparently Mono has a library that will let you write call/cc, but I haven’t had the time to try it out.

Exercise #1: why do async/await based continuations have to be one-shot? What would you need to change if you wished to support multi-shot continuations here?

Exercise #2: call/cc has a number of short comings, including memory leaks in certain use patterns. Many of these shortcomings can be alleviated with delimited continuations. Implement the delimited continuation functions “Task<object> Reset(Func<dynamic> thunk)” and “NeverAwaitable Shift(Func<Func<dynamic, dynamic>, dynamic> thunk)”.