For the past few nights I have been reading up on F# from fsharpforfunandprofit.com specifically on things like monads, bind functions and the language support for them, computation expressions (which I encourage you to read to help understand what’s going on here).

Computation expressions are a nice syntactic sugar provided by the language to easily be able to chain up continuations together using a imperative looking meta-language that gets translated to pre-defined function calls.

One of such computation expression is maybe which allows to specify a serie of operation that can potentially individually fail and, if so, short-circuit the rest of the computation automatically (without having to throw an exception or return early with a bunch of if statements)

As an example of what a maybe workflow (shamelessly borrowed from the website) looks like, given the following divideBy function that leverage the Option<T> type to model divide-by-zero errors:

let divideBy bottom top =
    if bottom = 0
    then None
    else Some(top/bottom)

You could do a manual series of bind expressions like the following in F#:

let Bind (m,f) = Option.bind f m

let Return x = Some x
   
let divideByWorkflow x y w z = 
    Bind (x |> divideBy y x, fun a ->
    Bind (a |> divideBy w a, fun b ->
    Bind (b |> divideBy z b, fun c ->
    Return c 
    )))

Or instead defines the Bind and Return as member methods of a type and use it to create the maybe computation expression like this:

type MaybeBuilder() =
    member this.Bind(m, f) = Option.bind f m
    member this.Return(x) = Some x

let maybe = new MaybeBuilder()

let divideByWorkflow x y w z = 
    maybe {
        let! a = x |> divideBy y 
        let! b = a |> divideBy w
        let! c = b |> divideBy z
        return c
    }

The two forms are equivalent, the second one just being more imperative looking and nicer to read.

Computation expressions are pretty powerful and can be used to express all sorts of things in F#. One of the most popular is the async computation expression that lead to the creation of async/await in C# as a specialized form of it.

Although async/await is definitely geared towards asynchronous programming, the fundamental idea it shares with computation expression is the same: convert a stream of “statements” into a serie of chained up continuations. The difference being that C# does so using a state machine versus F# use of a more generic function paradigm.

With the advent of generalized async task types in C# 7 (and its main user, ValueTask), we now have much more flexibility in tuning the async/await pipeline than ever before when it was hardcoded to use Task<T>.

Knowing this, the more I thought about that maybe computation expression the more I figured it should now be possible to implement something very similar in C# by re-purposing the async/await machinery.

Without further ado, here it is:

// Add the System.Threading.Tasks.Extensions NuGet to get AsyncMethodBuilderAttribute
[AsyncMethodBuilder (typeof (MaybeAsyncMethodBuilder<>))]
interface Option<T> { }

// Could use the closed type hierarchy Roslyn feature
// to be an approximation of a discriminated union
// https://github.com/dotnet/csharplang/issues/485
sealed class None<T> : Option<T> { public static readonly None<T> Value = new None<T> (); }
sealed class Some<T> : Option<T>
{
   public readonly T Item;
   public Some (T item) => Item = item;
   public static explicit operator T (Some<T> maybe) => maybe.Item;
}

static class Some
{
   public static Some<T> Of<T> (T value) => new Some<T> (value);
}

class MaybeAsyncMethodBuilder<T>
{
   Option<T> result = None<T>.Value;

   public static MaybeAsyncMethodBuilder<T> Create () => new MaybeAsyncMethodBuilder<T> ();

   public void Start<TStateMachine> (ref TStateMachine stateMachine) where TStateMachine : IAsyncStateMachine
   {
      // Simply start the state machine which will execute our code
      stateMachine.MoveNext ();
   }

   public Option<T> Task => result;
   public void SetResult (T result) => this.result = Some.Of (result);
   public void SetException (Exception ex) { /* We leave the result to None */ }
   

   // Unused methods
   public void SetStateMachine (IAsyncStateMachine stateMachine) { }

   public void AwaitOnCompleted<TAwaiter, TStateMachine> (ref TAwaiter awaiter, ref TStateMachine stateMachine)
      where TAwaiter : INotifyCompletion
      where TStateMachine : IAsyncStateMachine
   {
   }

   public void AwaitUnsafeOnCompleted<TAwaiter, TStateMachine> (ref TAwaiter awaiter, ref TStateMachine stateMachine)
      where TAwaiter : ICriticalNotifyCompletion
      where TStateMachine : IAsyncStateMachine
   {
   }
}

class MaybeAwaiter<T> : INotifyCompletion
{
   Option<T> maybe;

   public MaybeAwaiter (Option<T> maybe) => this.maybe = maybe;

   public bool IsCompleted => maybe is Some<T>;

   public void OnCompleted (Action continuation)
   {
      /* We never need to execute the continuation cause
       * we only reach here when the result is None which
       * means we are trying to short-circuit everything
       * else
       */
   }

   public T GetResult () => ((Some<T>)maybe).Item;
}

static class OptionExtensions
{
   public static MaybeAwaiter<T> GetAwaiter<T> (this Option<T> maybe) => new MaybeAwaiter<T> (maybe);
}

The top part of the code re-implements a form of Option<T> type and some helpers (nothing new here). The two more interesting things that pertains to async/await are the corresponding MaybeAwaiter and MaybeAsyncMethodBuilder types that allow us to plug into that pipeline.

The trick is to reuse an optimization baked into the async/await state machine where if the awaiter has its IsCompleted property equal to true after it’s created, the rest of the computation is immediately executed. If that’s not the case, the same computation remainder is (theorically) transformed into a continuation and fed into OnCompleted.

In our case, we use that fact to propagate successful Some-producing operation immediately and stop as soon as the first None is returned by never executing the continuation that’s passed to OnCompleted.

If our computation expression successfully and eagerly executes until the end, the SetResult method of the MaybeAsyncMethodBuilder type will be called thus setting the final result in a nicely wrapped Some. Otherwise the default None will be returned by the Task property.

Roughly speaking in this example, the Bind of F# is here implemented by MaybeAwaiter while MaybeAsyncMethodBuilder is the equivalent of Return.

Armed with this toolkit, here is how you would be able to code the same F# division workflow in C# using async/await:

public static void Main (string [] args)
{
   var resultGood = TestMaybeGood ();
   PrintResult (resultGood);

   var resultBad = TestMaybeBad ();
   PrintResult (resultBad);
}

static async Option<int> TestMaybeGood ()
{
   var val1 = await TryDivide (120, 2);
   var val2 = await TryDivide (val1, 2);
   var val3 = await TryDivide (val2, 2);

   return val3;
}

static async Option<int> TestMaybeBad ()
{
   var val1 = await TryDivide (120, 2);
   var val2 = await TryDivide (val1, 0); // Should stop execution there
   var val3 = await TryDivide (val2, 2);

   return val3;
}

static Option<int> TryDivide (int top, int bottom)
{
   Console.WriteLine ($"Trying to execute division {top}/{bottom}");
   if (bottom == 0)
      return None<int>.Value;
   
   return Some.Of (top / bottom);
}

static void PrintResult<T> (Option<T> maybe)
{
   switch (maybe) {
   case None<T> n:
      Console.WriteLine ("None");
      break;
   case Some<T> s:
      Console.WriteLine ($"Some {(T)s}");
      break;
   }
}

In the above code, await has absolutely nothing to do with asynchronous programming but is instead closer to the F# let! syntax which unwraps the value of a successful computation and names it for the next phase (basically var val1 = await TryDivide (120, 2); ⬄ let! val1 = tryDivide 120 2).

Executing the snippet gives the following output (if you want to play with this code using Mono you will have to use a recent version to have the Roslyn-based C# compiler):

% mono --debug MaybeComputationExpression.exe
Trying to execute division 120/2
Trying to execute division 60/2
Trying to execute division 30/2
Some 15
Trying to execute division 120/2
Trying to execute division 60/0
None

As you can see, in the first case all three divisions execute properly and we get back the result wrapped in a Some<int> while in the second case, as soon as the error case is detected (at the second statement) the rest of the computation is pre-empted and None is returned instead.