Monthly Archives: January 2007

Monads, REST and C++ Template Metaprogramming

OK, with that title, I’m sure to please almost no one. If you want to know how to do REST-ful programming in Haskell, or tie REST to C++, move along, there’s nothing to see here. The connection isn’t at the implementation level. Which is the whole point.
So what do REST, Monads and (successful) Template Metaprogramming have in common?
Strict maintenance of levels of abstraction, and extremely narrow interfaces between those levels.
What does that get you?
Extremely (and possibly maximally) reusable abstractions (code).
What triggered the realization for me was a paper on Arrows by Hughes, which asked the question ‘Why are Monads so reusable when the have such a small interface’, although not in those exact words. It dawned on me that they are so reusable exactly because they have such a narrow, but still very well defined, interface. They can do that because Monads are all about abstracting out features. A particular Monad will delagate all the real work down to the type it is being run over. Its real job is constraining the ways the values of the types it is a Monad over can be combined.
The analogue I have in mind for C++ MP is the swap() method. In a C++ template, we can assume that we can call swap on two values, that we otherwise know nothing about, and that the two values will be exchanged in a way that does not throw any exceptions, and is the best way of exchanging two values of that type. The abstract notion of swapping two values is delegated to the concrete implementation of the type being templated over.
A REST-ful web application exposes PUT, GET, POST, and DELETE on resources named by a URI. Nominally not much to have a really rich experience. OTOH, Google Map mashups contradict that.
It’s not the richness of the interface of the metalevel, it’s the richness allowed at level below. The narrow, but well defined, interface, where that interface delegates to a lower level abstraction, is exactly what enables composeability.
Monads, being firmly grounded in Functors in Category Theory, take this to an extreme level of rigor. There are laws that must be satisfied for a thing to be called a Monad, and those laws ensure that other Monads can interoperate, and achieve the Principle of Least Surprise.
I’m not intending this to be Yet Another Monad Tutorial. So I won’t go too deep here. But monad transformers show a degree of generic reusability that is awfully hard to achieve with C++ templates, even though C++ templates have similar expressive power (with a horribly clumsy syntax).
Monads are functions (functors) that take types to types, and so correspond to mpl metafunctions. But they preserve the underlying structure on the types they operate over. In particular, composition is preserved. So if I have an function of type a -> M b, and a function b -> c, I get a working a -> M c for free, just by using fmap. In C++ it would be like
template foo(A)
C bar(B)
getting you to
template foo(A) by saying template fmap(a,b), or even better just fmap(a,b) and letting the compiler figure out types.
(where foo is something like
template foo(A a);)
That looks so impossible in C++, that most C++ programmers have no intuition about it.
But every time you wish that you didn’t have to write some type that the compiler already knows, like the iterator or value_type or return_value, particularly when they get really messy, you’re looking for what Monads, or at least what Hindley-Milner type inference, provide.