Harder to C++: Monads for Mortals [1]

The monad is a programming construct, a coding idiom, or perhaps even a design pattern. Its roots lie in Category Theory, coming to programming via programming language semantics and functional languages. I have been reading up on monads (there are multiple, closely related variants), specifically monads for C++. It turns out that the concept of a monad is quit slippery; one minute you think you have a nice understanding, the next minute you are back at zero.

It seems to me that for a thorough understanding of what monads are, you need some knowledge of Category Theory and neighboring fields in logics and algebra, and sound knowledge of the functional programming language Haskell. But alas, I’m just a simple mortal programmer. Moreover:

• I don’t want to know about Category Theory!
• I don’t care about have time for Haskell !
• I just want to write programs in C++!

An alternative route to understanding monads that suits me (simple mortal soul) better, then, is to experiment with various implementations of monads in C++, and evaluate the results, experiment with an improved implementation. And so on.

I have been busy running this experimental cycle, and will describe the condensed experiences in a number of blog posts.

Many interesting things happened, but I can’t say I found a satisfying implementation. Indeed, I have come to doubt the usefulness of monads for application in C++, despite its conceptual and syntactical beauty. Even worse, I have come to doubt the usefulness of some other additions to the C++ language, new since C++11.

But monads are hot!, They must be useful in C++! Well, let us be clear about our motive to write programs in C++. The unique selling points of C++ are (i) the fastest code, against (ii) the smallest footprint. I think people buy in on C++ for exactly these selling points.

Let’s compare with driving a car (what a boyish thing to do). Programming in C++ is then, of course, driving a formula 1 race car; fast, small, unsafe, and uncomfortable. You want comfort, drive a large American saloon, i.e. code in a language designed for developer productivity. You want to be safe, correct? Drive a Toyota Prius, i.e. program a functional language.

Of course, Formula 1 drivers want to be as safe and comfortable as possible. But not at the expense of performance!

So, the monad can be a contribution to C++, if(f) it has no time, space performance cost.

Some Background on Monads

Let’s see what monads are, where they come from, and how they got into programming.

For a C++ developer, a monad is a triple <M, u, b> where:

• M is a template (yes, m for monad 🙂 ).
• u is a factory function, in general called unitof signature a -> M<a>, that given an object or value of some type a creates a template object of type M<a>.
• b is a function application function called bind of signature (M<a>, f) -> M<b> that:
  • Retrieves the object of type a from M<a>
  • Applies a function f: a -> M<b> (from type a to a template of type M<b>)
  • Returns a template of type M<b>

This triple has to satisfy three laws in order to be a monad:

1. Left identity: bind(M<a>, u) = M<a> (so left means left argument for bind)
2. Right identity: for an f: a->M<b>, bind(M<a>, f) = f(a)
3. Associativity: bind(x, f); bind(y, g) = bind(x, f; bind(y, g))

In the description of the associative law:

• x is a variable of type M<a>
• y is the result of bind(x, f)
• the ‘;’ operator denotes left to right sequencing of operations
• f is a function of type a -> M<b> and g is a function of type b -> M<c>

Now. let’s add some intuition.

According to Eugenio Moggi, the semantics of M is that of a computation. He means to include a general class of computations, e.g. partial computations, nondeterministic computations, side-effects, exceptions, continuations, and interactive input and output, and possibly more.

Further, u is the inclusion of value a in a computation, as a parameter. So, we may think of M as a computation.

The application function b (applied to function f) is the extension of a function f from values to computations to a function from computations to computations, which first evaluates a computation and then applies f to the resulting value.

Philip Wadler took the monad to Haskell and showed it can be used to do bad things in a good way. That is, to perform imperative programming language operations in a pure functional language way. Haskell is a pure functional language. In a pure functional language all functions are pure, i.e. functions in which the input-output relation cannot be augmented by things like state, or context, or whatever; the domain – codomain relation is fixed. In a pure functional language you can thus have no side effects, or interactive input / output, etc.

The monad solves this problem by encapsulating ‘imperative operations’ in the M computation. According to Wadler a function

f: a -> M<b>

is then said to map type a onto type b, with a possible additional effect captured by M. The monad takes the ‘imperative operations’ out of the (pure) function application mechanism, and the functional composition chain, and thus saves the pure character of the pure functional language.

Does this talk about functional language has any value for C++? That is debatable. C++ is an imperative language, the idea to improve it by a construct that makes a functional language do imperative operations is preposterous. On the other hand, Bartosz Milewski is convinced that concurrency in C++ would be improved greatly if it would be structured the monadic way (think of the continuations mentioned above). Concurrency is new territory for C++, so we have to investigate this further. I intend to discuss this viewpoint somewhere in this series of articles on monads. First I want to develop a thorough understanding of monad implementations in C++.

Next in this series: a first C++ implementation of a monad.

Links to Texts on Monads

Who writes or wrote about monads, and what do they think is the merit of monads?

1. Eugenio Moggi wrote Notions of computation and monads, about. This paper introduces monads as the categorical semantics for computations. It is very hard to read, because full of funny mathematical words that have a very precise meaning which then, of course, hardly anybody knows exactly. According to Moggi, monads allow mathematicians to reason about the equivalence of a very general class of programs.
2. Philip Wadler introduced monads into Haskell in order to perform ‘imperative operations’ in a decent way. Very readable text.
3. Mike Vanier wrote an extensive introduction into monads. Hard to read because of much Haskell code. After Philip Wadler he states that monads are key in allowing programmers to write side-effecting programs in pure functional languages.
4. Bartosz Milewski is a fervent supporter of application of monads to C++, specifically in the context of concurrency. He has written much texts that might make reading Moggi’s text easier. Milewski stresses the idea that std::fucture should be monadic.
5. Eric Lippert wrote a very (very) accessible introduction to monads for C#. He saw merit of monads in the construction of LINQ-to-Objects.