Skip to main content

An Almost Type-Safe General Monad in C#, aka how to Abstract over Type Constructors using Dynamics

Extending the work in my last post, I've developed a way to express an almost type-safe, general monad in C#. Similar to my module translation, the single monad object becomes a pair of co-operating objects, only one of which the monad implementor must define. Since C# cannot abstract over type constructors, I had to exploit the only feature that could accomodate the flexibility I needed: C#'s dynamic typing.
// The Monad object, indexed by a singleton type that implements the
// monad operations.
public sealed class Monad<M, T>
where M : struct, IMonadOps<M> { ... }

// An object that implements operations on the monad's encapsulated
// state.
public interface IMonadOps<M>
where M : struct, IMonadOps<M>
{
/// Return the encapsulated state for the monad's zero value.
object Zero<T>();

// Return the encapsulated state for the 'unit' operation.
object Unit<T>(T t);

// Perform a bind operation given the monad's encapsulated state,
// and the binding function f.
Monad<M, R> Bind<T, R>(
object state,
Fun<T, Monad<M, R>> f,
Fun<Monad<M, R>, object> from,
Fun<object, Monad<M, R>> to);
}
Looks a bit complicated, I know, but every piece is well-motivated. IMonadOps is fortunately the only interface that new monads must implement. Note the type constraints. The interface and the general monad both have a "phantom" or "witness" type M, constraining the type of the monad operations to the same IMonadOps type that created the monad. This means that the monad is entirely closed to extension and inspection.

Each IMonadOps is effectively a stateless singleton. The constraint to a struct is merely an optimization. Every IMonadOps implementor is actually very similar to the body of an ML module. If I want to invoke Identity.Zero, I can do it thusly:
default(Identity).Zero<int>();
This reveals the magic I used to define the Monad type. Whenever the Monad<M,T> type needs to invoke the underlying monad operations, it invokes the operation on the corresponding singleton M just like the above. Indexing the Monad by an IMonadOps implementation M, is like a linking step between Monad and M.
public sealed class Monad<M, T>
where M : struct, IMonadOps<M>
{
object state;

Monad(object state)
{
this.state = state;
}

// The projection function.
static object get<R>(Monad<M, R> m)
{
return m.state;
}

// The injection function.
static Monad<M, R> ctor<R>(object state)
{
return new Monad<M, R>(state);
}

// The standard 'bind' operation. It dispatches to the
// type-indexed 'bind', defined by M.
public Monad<M, R> Bind<R>(Fun<T, Monad<M, R>> f)
{
return default(M).Bind<T, R>(state, f, get<R>, ctor<R>);
}

// The standard 'unit' operation, injecting a value into
// the monad. It dispatches to the type-indexed unit
// function defined by M.
public static Monad<M, T> Unit(T t)
{
return new Monad<M, T>(default(M).Unit<T>(t));
}

public static Monad<M, T> Zero()
{
return new Monad<M, T>(default(M).Zero<T>());
}
}
You can see the dispatching at work here. All monad operations are dispatched to the "linked" methods of M. In a sense, we have succeeded in abstracting over the concrete implementation of Monad.

Now comes the catch: it's not fully type-safe, because the encapsulated state of the monad must be stored as 'object'. This means that each monad body must ensure it properly casts to and from the appropriate type. This is again due to the type constructor abstraction limitation.

Your first thought might be, why can't the encapsulated state simply be 'T'? Well, if all you wanted was an Identity monad, then that would be fine. But consider the Maybe monad:
public struct Maybe : IMonadOps<Maybe>
{
public object Unit<T>(T t)
{
return new Option<T>(t);
}

public object Zero<T>()
{
return new Option<T>();
}

public Monad<Maybe, R> Bind<T, R>(
object state,
Fun<T, Monad<Maybe, R>> f,
Fun<Monad<Maybe, R>, object> from,
Fun<object, Monad<Maybe, R>> to)
{
Option<T> value = (Option<T>)state;
return (value.HasValue) ? f(value.Value) : Fail<R>();
}

public static Monad<Maybe, T> Fail<T>()
{
return Monad<Maybe, T>.Zero();
}
}
The encapsulated state is an Option of type T, not a T. As another example, the List monad encapsulates a list of T's. Since we can't abstract over the type constructor for the encapsulated state, we thus need to resort to dynamic typing.

Now comes a slightly bizarre part: what are the injection and projection functions for? Well, despite the fact that IMonadOps is the "internal implementation" of Monad, it doesn't have direct access to the monad's internals. Unfortunately, sometimes that access is needed. Consider the List monad:
public struct ListM : IMonadOps<ListM>
{
public object Unit<T>(T t)
{
return List.Cons<T>(t, List.Nil<T>());
}

public object Zero<T>()
{
return List.Nil<T>();
}

public Monad<ListM, R> Bind<T, R>(
object state,
Fun<T, Monad<ListM, R>> f,
Fun<Monad<ListM, R>, object> from,
Fun<object, Monad<ListM, R>> to)
{
return to(
List.MapFlat<T, R>(
state as List.t<T>, delegate(T t)
{
return from(f(t)) as List.t<R>;
}));
}
}
ListM needs access to the private state of the returned list of Monads in order to flatten the list, but that access is not permitted since Monad is a separate, encapsulated type. There is no way to make this state available using inheritance or access modifiers, without also permitting the state to escape inadvertently.

Instead, the Monad provides an injection/projection pair, which are used to construct monad instances when given private state, or read out the private state of a monad instance, respectively. Note that encapsulation is maintained since this ability is granted only to the implementor of a given monad, which is already trusted with its own state.

I suspect there's a more efficient way to share the monad's state, but I'm a little tired from standing on my head all day for C#, so if anyone has any ideas, I welcome them. :-)

While this encoding is less efficient than the one described in my previous post, it's safer in some ways for users monad implementors alike, and I proved to myself that C#'s type system is powerful enough to encode the monad interface if you contort yourself appropriately. This technique for abstracting over type constructors might even be usable in my tagless Orc implementation.

Comments

Unknown said…
Very interesting stuff! Maybe you could append sample usage.
Unknown said…
Thank you very much for your inspiration!! I did some change to your code, mainly change object to IComputation of T, and use more IComputation in MonadOps interface.

Here's my code
pastebin.com/78XfVdHb

Popular posts from this blog

async.h - asynchronous, stackless subroutines in C

The async/await idiom is becoming increasingly popular. The first widely used language to include it was C#, and it has now spread into JavaScript and Rust. Now C/C++ programmers don't have to feel left out, because async.h is a header-only library that brings async/await to C! Features: It's 100% portable C. It requires very little state (2 bytes). It's not dependent on an OS. It's a bit simpler to understand than protothreads because the async state is caller-saved rather than callee-saved. #include "async.h" struct async pt; struct timer timer; async example(struct async *pt) { async_begin(pt); while(1) { if(initiate_io()) { timer_start(&timer); await(io_completed() || timer_expired(&timer)); read_data(); } } async_end; } This library is basically a modified version of the idioms found in the Protothreads library by Adam Dunkels, so it's not truly ground bre

Building a Query DSL in C#

I recently built a REST API prototype where one of the endpoints accepted a string representing a filter to apply to a set of results. For instance, for entities with named properties "Foo" and "Bar", a string like "(Foo = 'some string') or (Bar > 99)" would filter out the results where either Bar is less than or equal to 99, or Foo is not "some string". This would translate pretty straightforwardly into a SQL query, but as a masochist I was set on using Google Datastore as the backend, which unfortunately has a limited filtering API : It does not support disjunctions, ie. "OR" clauses. It does not support filtering using inequalities on more than one property. It does not support a not-equal operation. So in this post, I will describe the design which achieves the following goals: A backend-agnostic querying API supporting arbitrary clauses, conjunctions ("AND"), and disjunctions ("OR"). Implemen

Easy Automatic Differentiation in C#

I've recently been researching optimization and automatic differentiation (AD) , and decided to take a crack at distilling its essence in C#. Note that automatic differentiation (AD) is different than numerical differentiation . Math.NET already provides excellent support for numerical differentiation . C# doesn't seem to have many options for automatic differentiation, consisting mainly of an F# library with an interop layer, or paid libraries . Neither of these are suitable for learning how AD works. So here's a simple C# implementation of AD that relies on only two things: C#'s operator overloading, and arrays to represent the derivatives, which I think makes it pretty easy to understand. It's not particularly efficient, but it's simple! See the "Optimizations" section at the end if you want a very efficient specialization of this technique. What is Automatic Differentiation? Simply put, automatic differentiation is a technique for calcu