Discovering the Continuation Monad in C#

When it comes to asynchronous operations there are many different techniques that arose during the years. Futures, callbacks, promises, Tasks etc. At this point the await/async syntax has taken the lead.

When i wanted to make sense of the continuation monad, i started from the basics : Callbacks and refactoring after refactoring i discovered the mother of all monads as its called. The Continuation Monad.

Part 1

lets say you have a simple function

int Square(int x ){return (x * x);}

1) Use Callback and remove return type

you can pass a callback and remove the return type. This the famous Continuation-passing style

public static void Square(int x, Action<int> callback)
{
 callback(x * x);
}

and you can compose functions with callbacks like this :

Square(4,
 (result) => {
   Square(result, 
      (result2) => { });
   });

which of course leads to callback hell which is special case of the arrow anti-pattern…

2) Curry the Callback

What if we curry the action and return it as a result ?! we could do this :

public static Action<Action<int>> Square(int x)
{
     return (callback) => { callback(x * x); };
}

if you look at this for a long time and rename callback to resolve you will see that this is actually a promise.

and use it like this:

Square(4)
(result => { Console.Write(result); });

it looks a bit better but we can do a few more refactoring moves. This return type of Action<Action<int>> is actually (int → ⊥) → ⊥where ⊥ is the terminal element or void. This says, if you give me a function that takes an int i and returns nothing (int → ⊥) i will do something with it and then return nothing ⊥.

3) Generalize the returned Continuation

what if we wanted to generalize this and instead of ⊥ return an arbitrary type T. Then we should have :

(int → T) → T that is :

Func<Func<int,T>,T>

This says, if you give me a function that takes an int i and gives a T i will do something with it and return T which is an conservative extension of (int → ⊥) → ⊥

public static Func<Func<int,T>,T> Square<T>(int x)
{
     return (callback) => { callback(x * x); };
}

This function signature (U→ T) → T we can call it continuation and write it as a delegate

delegate T Cont<U, T>(Func<U, T> f);

Part 2

We can form a Monad from this Continuation type. For all those who do not know what monad is:

• Functor is an something that can be mapped. A List for example. Here is the Continuation (U→ T) → T.
• Endofunctor is a functor from a category to itself. You can check the theory behind functors at my previous post here. A List that maps to a List for example. Or in this case a continuation to a continuation.
• Monoid is an algebraic structure with a single associative binary operation and an identity element. You can check the theory behind Monoids at my previous post here. in a Sense figure out how to “multiply (combine) continuations” somehow.

Monads have two operations :

c → T(c)          //Return
T(T(c))→ T(c)     //join

1)In this first operation c → T(c) we can start from an object C and get an container T(c).

2)The second one T(T(c))→ T(c) means that we can join/flatten the two containers in one.

4) Extract the Continuation Structure

now we only need to extract the Continuation mechanism from the square function so we could reuse it. So we can have the first part of the Monad, which is the wrapping of the value with a continuation like this :

public static Cont<U, T> ToContinuation<U, T>(this U x)
 {
   return (callback) => callback(x);
 }

so finally, the initial

public static Func<Func<int,T>,T> Square<T>(int x)
{
     return (callback) => { callback(x * x); };
}

can be written in this manner :

square.ToContinuation<Func<int, int>, int>()

in order to finally get the Continuation monad we have to Add the Bind Method: T (A) → (A → T (B)) → T (B) that composes continuations. This is by far the most difficult part to comprehend and you cannot really grasp it if you don’t try to build it on your own one time.

Cont<A, T> , Func<A,Cont<B, T>> → Cont<B, T>

if we replace T that is the Monad with (A→ T) → T in this

T (A) → (A → T (B)) → T (B)

we get something ridiculous like this in Type form

((A→ T) → T)→( A→((B→ T) → T))→ ((B→ T) → T)

This means if you give me a continuation for A [(A→ T) → T] and a function that takes an A and gives a continuation for B [ A→((B→ T) → T)] then i can give you a continuation for B [(B→ T) → T]

one can meditate on why the bind method below works its like a c# zen koan when you grasp it becomes obvious .

and this will concludes the construct:

public static Cont<V, Answer> Bind<T, U, V, Answer>(
this Cont<T, Answer> m,
Func<T, Cont<U, Answer>> k, 
Func<T, U, V> selector)
{
 return (Func<V, Answer> c) => 
m(t => k(t)(y => c(selector(t, y))));
}

you can try it in this .netfiddle :

Continuation Monad | C# Online Compiler | .NET Fiddle

In Summary :

1. Starting from an initial Function

int Square(int x ){return (x * x);}

2. Use Callback and remove return type

public static void Square(int x, Action<int> callback)
{
 callback(x * x);
}

3. Curry the Callback

public static Action<Action<int>> Square(int x)
{
     return (callback) => { callback(x * x); };
}

4. Generalize the returned Continuation

public static Func<Func<int,T>,T> Square<T>(int x)
{
     return (callback) => { callback(x * x); };
}

5. Extract the Continuation Structure Also Known As the Return Method of the monad

delegate T Cont<U, T>(Func<U, T> f);
public static Cont<U, T> ToContinuation<U, T>(this U x)
{
   return (callback) => callback(x);
}
square.ToContinuation<Func<int, int>, int>()

6. Add The bind Monadic method and thus Complete the Monad

public static Cont<V, Answer> Bind<T, U, V, Answer>(
this Cont<T, Answer> m,
Func<T, Cont<U, Answer>> k, 
Func<T, U, V> selector)
{
 return (Func<V, Answer> c) => 
m(t => k(t)(y => c(selector(t, y))));
}

you can play around with the code in this .net fiddle here :

Continuation Monad | C# Online Compiler | .NET Fiddle

Async/await — Continuation CoMonad in C#

Also you can Check out the Javascript Version of this here :

Promises & Continuation Monad in JavaScript

https://leanpub.com/functional-programming-in-cSharp-with-categories

feel free to connect with me in LinkedIn