“Maybe” monad through async/await in C# (No Tasks!)

Generalized async return types — it is a new C#7 feature that allows using not only Task as a return type of async methods but also other types (classes or structures) that satisfy some specific requirements.

At the same time, async/await is a way to call a set of "continuation" functions inside some context which is an essence of another design pattern — Monad. So, can we use async/await to write a code which will behave in the same way like if we used monads? It turns out that — yes (with some reservations). For example, the code below is compilable and working:

async Task Main()
{
  foreach (var s in new[] { "1,2", "3,7,1", null, "1" })
  {
      var res = await Sum(s).GetMaybeResult();
      Console.WriteLine(res.IsNothing ? "Nothing" : res.GetValue().ToString());
  }
  // 3, 11, Nothing, Nothing
}

async Maybe<int> Sum(string input)
{
    var args = await Split(input);//No result checking
    var result = 0;
    foreach (var arg in args)
        result += await Parse(arg);//No result checking
    return result;
}

Maybe<string[]> Split(string str)
{
  var parts = str?.Split(',').Where(s=>!string.IsNullOrWhiteSpace(s)).ToArray();
  return parts == null || parts.Length < 2 ? Maybe<string[]>.Nothing() : parts;
}

Maybe<int> Parse(string str)
    => int.TryParse(str, out var result) ? result : Maybe<int>.Nothing();

Further, I will explain how the code works...

Generalized async return types

First of all let's figure out what is required to use our own type (e.g. MyAwaitable<T>) as a result type of some async function. Documentation says that such type has to have:

1. GetAwaiter() method that returns an object of a type which implements INotifyCompletion interface and has bool IsCompleted property and T GetResult() method;

   
   

2. [AsyncMethodBuilder(Type)] attribute which points to a "method builder" class (or structure) e.g. MyAwaitableTaskMethodBuilder<T> with the following methods:

   
   
   • static Create()
   • Start(stateMachine)
   • SetResult(result)
   • SetException(exception)
   • SetStateMachine(stateMachine)
   • AwaitOnCompleted(awaiter, stateMachine)
   • AwaitUnsafeOnCompleted(awaiter, stateMachine)
   • Task
   
   

[AsyncMethodBuilder(typeof(MyAwaitableTaskMethodBuilder<>))]
public class MyAwaitable<T> : INotifyCompletion
{
    private Action _continuation;

    public MyAwaitable()
    { }

    public MyAwaitable(T value)
    {
        this.Value = value;
        this.IsCompleted = true;
    }

    public MyAwaitable<T> GetAwaiter() => this;

    public bool IsCompleted { get; private set; }

    public T Value { get; private set; }

    public Exception Exception { get; private set; }

    public T GetResult()
    {
        if (!this.IsCompleted) throw new Exception("Not completed");
        if (this.Exception != null)
        {
            ExceptionDispatchInfo.Throw(this.Exception);
        }
        return this.Value;
    }

    internal void SetResult(T value)
    {
        if (this.IsCompleted) throw new Exception("Already completed");
        this.Value = value;
        this.IsCompleted = true;
        this._continuation?.Invoke();
    }

    internal void SetException(Exception exception)
    {
        this.IsCompleted = true;
        this.Exception = exception;
    }

    void INotifyCompletion.OnCompleted(Action continuation)
    {
        this._continuation = continuation;
        if (this.IsCompleted)
        {
            continuation();
        }
    }
}

public class MyAwaitableTaskMethodBuilder<T>
{
    public MyAwaitableTaskMethodBuilder() 
        => this.Task = new MyAwaitable<T>();

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

    public void Start<TStateMachine>(ref TStateMachine stateMachine) 
        where TStateMachine : IAsyncStateMachine 
        => stateMachine.MoveNext();

    public void SetStateMachine(IAsyncStateMachine stateMachine) { }

    public void SetException(Exception exception) 
        => this.Task.SetException(exception);

    public void SetResult(T result) 
        => this.Task.SetResult(result);

    public void AwaitOnCompleted<TAwaiter, TStateMachine>(
        ref TAwaiter awaiter, 
        ref TStateMachine stateMachine) 
        where TAwaiter : INotifyCompletion 
        where TStateMachine : IAsyncStateMachine
        => this.GenericAwaitOnCompleted(ref awaiter, ref stateMachine);

    public void AwaitUnsafeOnCompleted<TAwaiter, TStateMachine>(
        ref TAwaiter awaiter, 
        ref TStateMachine stateMachine) 
        where TAwaiter : ICriticalNotifyCompletion 
        where TStateMachine : IAsyncStateMachine
        => this.GenericAwaitOnCompleted(ref awaiter, ref stateMachine);

    public void GenericAwaitOnCompleted<TAwaiter, TStateMachine>(
        ref TAwaiter awaiter, 
        ref TStateMachine stateMachine)
        where TAwaiter : INotifyCompletion
        where TStateMachine : IAsyncStateMachine         
        => awaiter.OnCompleted(stateMachine.MoveNext);

    public MyAwaitable<T> Task { get; }
}

Now we can use MyAwaitable as a result type of async methods:

private async MyAwaitable<int> MyAwaitableMethod()
{
    int result = 0;
    int arg1 = await this.GetMyAwaitable(1);
    result += arg1;
    int arg2 = await this.GetMyAwaitable(2);
    result += arg2;
    int arg3 = await this.GetMyAwaitable(3);
    result += arg3;
    return result;
}

private async MyAwaitable<int> GetMyAwaitable(int arg)
{
    await Task.Delay(1);//Simulate asynchronous execution 
    return await new MyAwaitable<int>(arg);
}

The code works as expected but to understand a purpose of the requirements to MyAwaitable let's take a look what the C# preprocessor does with MyAwaitableMethod. If you run some de-compilation util (e.g. dotPeek) you will see that the original method was changed as follows:

private MyAwaitable<int> MyAwaitableMethod()
{
    var stateMachine = new MyAwaitableMethodStateMachine();
    stateMachine.Owner = this;
    stateMachine.Builder = MyAwaitableTaskMethodBuilder<int>.Create();
    stateMachine.State = 0;
    stateMachine.Builder.Start(ref stateMachine);
    return stateMachine.Builder.Task;
}

sealed class MyAwaitableMethodStateMachine : IAsyncStateMachine
{
    public int State;
    public MyAwaitableTaskMethodBuilder<int> Builder;
    public BuilderDemo Owner;
    private int _result;
    private int _arg1;
    private int _arg2;
    private int _arg3;
    private MyAwaitableAwaiter<int> _awaiter1;
    private MyAwaitableAwaiter<int> _awaiter2;
    private MyAwaitableAwaiter<int> _awaiter3;

    private void SetAwaitCompletion(INotifyCompletion awaiter)
    {
        var stateMachine = this;
        this.Builder.AwaitOnCompleted(ref awaiter, ref stateMachine);
    }

    void IAsyncStateMachine.MoveNext()
    {
        int finalResult;
        try
        {
            label_begin:
            switch (this.State)
            {
                case 0:
                    this._result = 0;
                    this._awaiter1 = this.Owner.GetMyAwaitable(1).GetAwaiter();
                    this.State = 1;

                    if (!this._awaiter1.IsCompleted)
                    {
                        this.SetAwaitCompletion(this._awaiter1);
                        return;
                    }
                    goto label_begin;

                case 1:// awaiter1 should be completed
                    this._arg1 = this._awaiter1.GetResult();
                    this._result += this._arg1;

                    this.State = 2;
                    this._awaiter2 = this.Owner.GetMyAwaitable(2).GetAwaiter();

                    if (!this._awaiter2.IsCompleted)
                    {
                        this.SetAwaitCompletion(this._awaiter2);
                        return;
                    }
                    goto label_begin;

                case 2:// awaiter2 should be completed

                    this._arg2 = this._awaiter2.GetResult();
                    this._result += this._arg2;

                    this.State = 3;
                    this._awaiter3 = this.Owner.GetMyAwaitable(3).GetAwaiter();

                    if (!this._awaiter3.IsCompleted)
                    {
                        this.SetAwaitCompletion(this._awaiter3);
                        return;
                    }
                    goto label_begin;

                case 3:// awaiter3 should be completed

                    this._arg3 = this._awaiter3.GetResult();
                    this._result += this._arg3;

                    finalResult = this._result;
                    break;
                default:
                    throw new Exception();
            }
        }
        catch (Exception ex)
        {
            this.State = -1;
            this.Builder.SetException(ex);
            return;
        }

        this.State = -1;
        this.Builder.SetResult(finalResult);
    }
}

Reviewing the generated code we can see that the "method builder" has the following responsibilities:

1. Scheduling the state machine MoveNext() method call when a child asynchronous operation is done (in the simplest scenario we just pass MoveNext() into OnCompleted() of the async operation awaiter).
2. Creation of an asynchronous operation context object (public MyAwaitable<T> Task { get; })
3. Reacting on final states of generated state machines: SetResult or SetException.

In other words, with "method builders" we can get a control on how asynchronous methods are executed and it looks like a feature which will help us to achieve our goal — an implementation of Maybe monad behavior. But what is good about that monad? Well… you can find a lot of articles about that monad in the Internet, so here I will describe just basics.

Maybe monad

In short, Maybe monad is a design pattern which allows interruption of a function call chain if some function from the chain cannot produce a valuable result (e.g. parsing error).

Historically, imperative programming languages have been solving the problem in two ways:

1. Lot of conditional logic
2. Exceptions

The both ways have obvious disadvantages, so a third way was invented:

1. Create a type which can be in 2 states: "Some Value" and "Nothing" — let's call it "Maybe"
2. Create a function (lets' call it "SelectMany") which retrieves 2 arguments:
   2.1. An object of "Maybe" type
   2.2. A next function from the call set — the function should also return an object of "Maybe" which will contain a result or "Nothing" if its result cannot be evaluated (e.g. the function parameters are not in correct format)
3. "SelectMany" function checks if "Maybe" has some value and then calls the next function using the value (extracted from "Maybe") as an argument and then returns its result, otherwise it returns an "Maybe" object in "Nothing" state.

In C# it can be implemented like that:

public struct Maybe<T>
{
    public static implicit operator Maybe<T>(T value) => Value(value);

    public static Maybe<T>  Value(T value) => new Maybe<T>(false, value);

    public static readonly Maybe<T> Nothing = new Maybe<T>(true, default);

    private Maybe(bool isNothing, T value)
    {
        this.IsNothing = isNothing;
        this._value = value;
    }

    public readonly bool IsNothing;

    private readonly T _value;

    public T GetValue() => this.IsNothing ? throw new Exception("Nothing") : this._value;
}

public static class MaybeExtensions
{
    public static Maybe<TRes> SelectMany<TIn, TRes>(
        this Maybe<TIn> source, 
        Func<TIn, Maybe<TRes>> func)

        => source.IsNothing ? 
            Maybe<TRes>.Nothing : 
            func(source.GetValue());
}

and usage:

static void Main()
{
    for (int i = 0; i < 10; i++)
    {
        var res = Function1(i).SelectMany(Function2).SelectMany(Function3);
        Console.WriteLine(res.IsNothing ? "Nothing" : res.GetValue().ToString());
    }

    Maybe<int> Function1(int acc) => acc < 10 ? acc + 1 : Maybe<int>.Nothing;

    Maybe<int> Function2(int acc) => acc < 10 ? acc + 2 : Maybe<int>.Nothing;

    Maybe<int> Function3(int acc) => acc < 10 ? acc + 3 : Maybe<int>.Nothing;
}

var res = Function1(i)
    .SelectMany(x2 => 
        Function2(x2).SelectMany(x3 => 
            Function3(x3.SelectMany<int, int>(x4 => 
                x2 + x3 + x4)));

var res = from x2 in Function1(i)
    from x3 in Function2(x2)
    from x4 in Function3(x3)
    select x2 + x3 + x4;

public static Maybe<TJ> SelectMany<TIn, TRes, TJ>(
    this Maybe<TIn> source, 
    Func<TIn, Maybe<TRes>> func, 
    Func<TIn, TRes, TJ> joinFunc)
{
    if (source.IsNothing)
        return Maybe<TJ>.Nothing;

    var res = func(source.GetValue());
    return res.IsNothing 
        ? Maybe<TJ>.Nothing 
        : joinFunc(source.GetValue(), res.GetValue());
}

static void Main()
{
    foreach (var s in new[] {"1,2", "3,7,1", null, "1"})
    {
        var res = Sum(s);
        Console.WriteLine(res.IsNothing ? "Nothing" : res.GetValue().ToString());
    }

    Console.ReadKey();
}

static Maybe<int> Sum(string input)
    => Split(input).SelectMany(items => Acc(0, 0, items));

//Recursion is used to process a list of "Maybes"
static Maybe<int> Acc(int res, int index, IReadOnlyList<string> array) 
    => index < array.Count 
        ? Add(res, array[index])
            .SelectMany(newRes => Acc(newRes, index + 1, array)) 
        : res;

static Maybe<int> Add(int acc, string nextStr) 
    => Parse(nextStr).SelectMany<int, int>(nextNum => acc + nextNum);

static Maybe<string[]> Split(string str)
{
    var parts = str?.Split(',')
        .Where(s => !string.IsNullOrWhiteSpace(s)).ToArray();
    return parts == null || parts.Length < 2 ? Maybe<string[]>.Nothing : parts;
}

static Maybe<int> Parse(string value)
    => int.TryParse(value, out var result) ? result : Maybe<int>.Nothing;

Async Maybe

The essence of Maybe monad is to control a function call chain, but it is exactly that "async/await" does. So let's try to combine them together. First, we need to make Maybe type compatible with asynchronous functions and we already know how to do that:

[AsyncMethodBuilder(typeof(MaybeTaskMethodBuilder<>))]
public class Maybe<T> : INotifyCompletion
{
    ...
    public Maybe<T> GetAwaiter() => this;

    public bool IsCompleted { get; private set; }

    public void OnCompleted(Action continuation){...}

    public T GetResult() =>...
}

Now let's take a look how the "classical Maybe" can be rewritten as a state machine to be able to find any similarities:

static void Main()
{
    for (int i = 0; i < 10; i++)
    {
        var stateMachine = new StateMachine();
        stateMachine.state = 0;
        stateMachine.i = i;
        stateMachine.MoveNext();

        var res = stateMachine.Result;

        Console.WriteLine(res.IsNothing ? "Nothing" : res.GetValue().ToString());
    }

    Console.ReadKey();
}

class StateMachine
{
    public int state = 0;

    public int i;
    public Maybe<int> Result;

    private Maybe<int> _f1;
    private Maybe<int> _f2;
    private Maybe<int> _f3;

    public void MoveNext()
    {
        label_begin:
        switch (this.state)
        {
            case 0:
                this._f1 = Function1(this.i);
                this.state = Match ? -1 : 1;
                goto label_begin;
            case 1:
                this._f2 = Function2(this._f1.GetValue());
                this.state = this._f2.IsNothing ? -1 : 2;
                goto label_begin;
            case 2:
                this._f3 = Function3(this._f2.GetValue());
                this.state = this._f3.IsNothing ? -1 : 3;
                goto label_begin;
            case 3:
                this.Result = this._f3.GetValue();
                break;
            case -1:
                this.Result = Maybe<int>.Nothing;
                break;
        }
    }
}

If we match this state machine with the generated by the C# preprocessor one (see above — 'MyAwaitableMethodStateMachine') we can notice that Maybe state checking can be implemented inside:

this.Builder.AwaitOnCompleted(ref awaiter, ref stateMachine);

where ref awaiter is an object of Maybe type. The only problem here is that we cannot set the machine into the "final" (-1) state. Does that mean that we cannot control the execution flow? Actually, it does not. The thing is that for each asynchronous action C# sets a callback action trough INotifyCompletion interface, so if we want to break an execution flow we can just call the callback action in a case when we cannot continue the flow.
Another challenge here is that the generated state machine passes a next action (as a continuation callback) of a current flow, but we need a continuation callback of the initial flow which would allow bypassing the rest of async operations:

So, we need to somehow connect a child async action with its ancestors. We can do that using our "method builder" which has a link to a current async operation — Task. Links to all child async operations will be passed into AwaitOnCompleted(ref awaiter as awaiter, so we just need to check if the parameter is an instance of Maybe and if it is then set the current Maybe as as a parent for the child one:

[AsyncMethodBuilder(typeof(MaybeTaskMethodBuilder<>))]
public class Maybe<T> : IMaybe, INotifyCompletion
{
    private IMaybe _parent;

    void IMaybe.SetParent(IMaybe parent) => this._parent = parent;
    ...
}

public class MaybeTaskMethodBuilder<T>
{
    ...
    private void GenericAwaitOnCompleted<TAwaiter, TStateMachine>(
        ref TAwaiter awaiter,
        ref TStateMachine stateMachine) 
        where TAwaiter : INotifyCompletion 
        where TStateMachine : IAsyncStateMachine
    {
        if (awaiter is IMaybe maybe)
        {
            maybe.SetParent(this.Task);
        }
        awaiter.OnCompleted(stateMachine.MoveNext);
    }  
    ...  
}

Now all Maybe objects can be joined into a tree and and, as a result, we will get access to a continuation of the root Maybe (Exit method) from any descendant node:

[AsyncMethodBuilder(typeof(MaybeTaskMethodBuilder<>))]
public class Maybe<T> : IMaybe, INotifyCompletion
{
    private Action _continuation;

    private IMaybe _parent;
    ...
    public void OnCompleted(Action continuation)
    {
        ...
        this._continuation = continuation;
        ...
    }
    ...
    void IMaybe.Exit()
    {
        this.IsCompleted = true;

        if (this._parent != null)
        {
            this._parent.Exit();
        }
        else
        {
            this._continuation();
        }
    }
    ...
}

That Exit method should be called when (during moving over the tree) we found an already resolved Maybe object in Nothing state. Such Maybe objects can be returned by a method like this one:

Maybe<int> Parse(string str)
    => int.TryParse(str, out var result) ? result : Maybe<int>.Nothing();

To store a state of resolved Maybe let's introduce a new separate structure:

public struct MaybeResult
{
    ...
    private readonly T _value;

    public readonly bool IsNothing;

    public T GetValue() 
        => this.IsNothing ? throw new Exception("Nothing") : this._value;
}

[AsyncMethodBuilder(typeof(MaybeTaskMethodBuilder<>))]
public class Maybe<T> : IMaybe, INotifyCompletion
{
    private MaybeResult? _result;
    ...
    internal Maybe() { }//Used in async method

    private Maybe(MaybeResult result) => this._result = result;// "Resolved" instance 
    ...
}

When an async state machine calls (through the method builder) OnCompleted method of an already resolved Maybe instance and it is in Nothing state we will be able to break an entire flow:

public void OnCompleted(Action continuation)
{
    this._continuation = continuation;
    if(this._result.HasValue)
    {
        this.NotifyResult(this._result.Value.IsNothing);
    }
}

internal void SetResult(T result)
//Is called by a "method builder" when an async method is completed
{
    this._result = MaybeResult.Value(result);
    this.IsCompleted = true;
    this.NotifyResult(this._result.Value.IsNothing);
}

private void NotifyResult(bool isNothing)
{
    this.IsCompleted = true;
    if (isNothing)
    {
        this._parent.Exit();//Braking an entire flow
    }
    else
    {
        this._continuation?.Invoke();
    }
}

Now the only thing remains — how to get a result of an async Maybe outside of its scope (any async method whose return type is not Maybe). If you try to use just await keyword with a Maybe instance then an exception will be thrown due to this code:

[AsyncMethodBuilder(typeof(MaybeTaskMethodBuilder<>))]
public class Maybe<T> : IMaybe, INotifyCompletion
{
    private MaybeResult? _result;

    public T GetResult() => this._result.Value.GetValue();
}
...
public struct MaybeResult
{
    ...
    public T GetValue() 
        => this.IsNothing ? throw new Exception("Nothing") : this._value;
}

To solve the issue we can just add a new Awaiter which would return an entire MaybeResult structure and we will be able to write a code like this:

var res = await GetResult().GetMaybeResult();
if(res.IsNothing){
    ...
}
else{
    res.GetValue();
    ...
};

That's all for now. In the code samples I omit some details to focus only on the most important parts. You can find a full version on github.

However, I would not recommend using this version in any production code since it has a significant issue — when we brake an execution flow by calling a continuation of the root Maybe we will bypass EVERYTHING! including all finally blocks (it is an answer to the question "Are finally blocks always called?"), so all using operators will not work as expected and that might lead to resource leaking. The issue can be solved if instead of calling the initial continuation callback we will throw a special exception which will be handled internally (here you can find the version), but this solution apparently has performance imitations (which might be acceptable in some scenarios). With the current version of the C# compiler I do not see any other solution but that might be changed in future.

These limitations do not mean that all the tricks described in this article are completely useless, they can be used to implement other monads which do not require changes in execution flows, for example "Reader". How to implement that "Reader" monad trough async/await I will show in the next article.