Sunday, June 1, 2008

Monads in C++ template metaprogramming

In the context of functional programming, a monad M is a type constructor (a mapping from arbitrary type a to type Ma) along with a pair of (polymorphic) functions

>>=M : Ma → (aMb) → Mb,
returnM : aMa,

(the first function is usually pronounced "bind") which are assumed to satisfy certain laws regarding the associativity of >>=M and the identity role played by returnM. Intuitively, monads of type Ma internally carry zero, one or more values of type a, along with some monad-specific information; the expression

m >>= n

is to be understood as: monad m executes some specific computation and then uses their internal a contents to feed n, whose results are possibly postprocessed and returned in a single value of type Mb. return x is expected to produce a "fresh" monad initialized with x. In a sense, monad binding performs a computation from a to b in a sequenced manner with some additional contextual information carried along the way. For this reason, monads are used in functional languages like Haskell to model imperative constructs like those involved in IO interaction.

How can we implement monads in C++ template metaprogramming? In the following we use the conventions of Boost.MPL. As C++ TMP lacks proper types we can define global metafunctions for >>= and return and let each monad M provide the appropriate associated partial specializations for the values under its control. The following is a possible formulation of this idea:

template<typename M,typename F>
struct mbind;

template<typename M,typename T>
struct mreturn;

The signature of mbind is clear enough, but mreturn seems to accept a superfluous argument M: this extra argument is meant to disambiguate the specializations for different monads which otherwise share their input types, much as we cannot overload a C++ function only on the return type. This is how an implementation of the Maybe monad looks like in this framework:

‎template<typename T> struct maybe;

‎struct nothing_arg;
‎typedef maybe<nothing_arg> nothing;

‎template<typename T,typename F>
‎struct mbind<maybe<T>,F>:boost::mpl::apply<F,T>{};

‎template<typename F>
‎struct mbind<nothing,F>
‎{
‎ typedef nothing type;
‎};

‎template<typename _,typename T>
‎struct mreturn<maybe<_>,T>
‎{
‎ typedef maybe<T> type;
‎};
We will implement more complicated monads in later entries.

2 comments :

  1. Do you know FC++? ( http://www.cc.gatech.edu/~yannis/fc++/ ).

    This file:
    http://www-static.cc.gatech.edu/~yannis/fc++/FC++.1.5/monad.h might be of special interest to you.

    ReplyDelete
  2. Hello Helium,

    Yes, I first knew about FC++ when it was reviewed for acceptance in Boost some years ago.

    Take into account, however, that FC++ is about functional programming in run-time C++, while my entry deals with C++ template metaprogramming, compile-time stuff.

    Best regards,

    ReplyDelete