An Attempt to Explain Monads in C++

Last time, I spoke about some potential continuations that someone can do in C++ with optional types. I briefly stated, in regards to the Boost.Expected proposal:

This is all well and good, however I noticed that these choice of words 'map' or 'bind' aren't what I think when reading.

Someone pointed out to me that the 'map' call comes from one of the three operations one can perform on a monad. The other two being 'join', and 'return'. After digging into the Boost.Expected proposal some more, I finally had that epiphany where one understands what a monad is. As such, I want to keep with the time honored tradition of trying to explain it to others, and continuing to confound the congregation of programmers who haven't yet grokked it. However, I'll explain it in the context of C++, rather than trying to explain Haskell, and how some of its features map to C++. And while burritos are delicious, I won't be referencing them at all.

Before I continue, I want to preface this by saying that I am not formally trained in mathematics, or even computer science. So, if I am not 100% accurate in a mathematical sense, don't sweat it. We're using C++, not Haskell, and it has a different lexicon and different approaches to problems that Haskell can avoid. C++ is, after all, a greedily evaluated, imperatively written, object oriented, statically checked, generically functional, mostly strongly typed programming language. Of course, Haskell is not all of that. As such we have other issues to worry about, which I'll briefly posit and discuss later.

So just what is a monad? If we use the wikipedia definition, we get that a monad is a structure that represents computations defined as a sequence of steps. It's an extremely vague definition. The best definition I can conceive in regards to the C++ lexicon is that a monad is an object with some potential value and the sequence of actions to execute on the potential value.

This definition doesn't help as much, but we need to focus on object with some potential value. It can't be just an object that might have some value. It has to be an object where the potential value is completely absent. A type with a single integer member set to 0 is not a monad, because the integer has a value. In C++, something that is uninitialized may still have value depending on where it is declared. An integer declared on the stack may have a value of whatever was written to that location on the stack (such as garbage data), or an implementation's runtime may write some predefined value to it. Regardless, there will always be a value. The same applies to objects that are allocated from the free store. The objects will have value, since they've been initialized into a section of memory. Even if using malloc, the type system will treat the value returned from the call as a pointer to nothing (void*), which is technically a pointer to anything. Pointer's aren't monads. They do have value. They are, after all, simply an offset to which one can knowingly access memory without fear of interdiction from the current execution environment. Even a bad pointer has value; the execution environment is what prevents it from being used, if at all.

An object with some potential value, then, does not refer to an object that could have a value, but rather an object that can properly represent the potential absence of value. C++ does have a type to represent the absence of a type (void). In some languages this is known as the unit type. But void is not an object. It's a type in the C (and C++) type system to expect that nothing will be present. We can't instantiate an instance of void [1], only a pointer to an instance of void (which if you recall has value). Instead we need an object that can represent the potential absence of a value. We call the type of these objects optional types in the C++ lexicon.

I want to be very clear here: An optional type in C++ is not the same as an optional type in other languages. C++ borrows words, but the semantics regarding these words may change when brought into C++. Like how we use union, but it doesn't translate to a discriminate union. Technically, an optional type can also be one where we expect a specific type, but could receive an unexpected type instead. The absence of the value we expect is replaced not with empty air, but the unexpected type. What the unexpected type is does not matter. What matters is that we didn't get what we expect, and at that point we need to handle that use case.

Luckily, C++ will be adding an optional type in an upcoming technical specification and in the mean time you can use MNMLSTC Core for an implementation, as well as two additional optional types that can hold exceptions or std::error_condition as their unexpected type. Some vendors already supply an implementation, and you should check with them as well.

Optional types are just one half of the equation for a monad. We need operations that we can perform on an optional type to truly make it a monad. There are three operations that one can perform on an optional type to truly make it a monad:

  • return
  • join
  • map

The above operations are not taken from the C++ lexicon. They exist outside of C++. We have to change the wording for them, but keep the context the same. The reason for this of course is that return is a keyword, map is a type, and join has until now been used to describe the blocking operations on threads. Let's break this down one at a time using C++ terminology.

When you perform a return operation on a monad, you are simply constructing it. optional<int> f { 4 } is a monad return operation. f = {} is also a return operation. It is a mutation return operation, which is not defined by monad operations as monads imply a functionally pure language. We're not though, so throw caution { "to the wind" }. One can argue that monad operations have to be functions, and since constructors are implicit functions (that is we can't get a pointer to member function to them), they technically aren't. Which is fine, but it's also why we have functions like make_optional (the make_* convention is found quite a bit in scheme).

Moving on to map operations, these are not like the C++ algorithm equivalent of a map function (which is std::transform in case you were wondering), but can instead be seen as a visitation. However, unlike a visitor pattern, the return type of a map operation will always be inside an optional type. For example, if I have a function that returns optional<int>, and we perform a map operation, the resulting type will be optional<optional<int>>. If a function returns double, the result of a map operation is optional<double>. Fairly straightforward, though one can see where this turns into an quagmire.

A join operation handles the situation where an optional type is inside of another optional type. It effectively unwraps the value stored in the inner optional type, and then returns a new one. For example, performing a join operation on optional<optional<int>>, we will end up with optional<int>. In addition, because we're unwrapping, we can use move operations to reduce possibly expensive copies.

A map+join operation is usually given, due to how often it is used. In Haskell, this is known as a bind, but in C++ we already have std::bind, which is like python's partial. To reduce confusion, we can instead call this function then but still refer to it as a map+join or bind. The combination of these two operations in quick succession allows us to unwrap and immediately continue to the next function in our sequence of steps.

So that's a monad, as simply as I can describe it. But there are some issues we need to concern ourselves with that Haskell doesn't really have to worry about:

  • What is the exception specification of these operations?
  • Can an optional type be a literal type (that is, constexpr-able)?
  • Are all discriminate unions (boost::variant, core::variant) or class-like unions optional types? If so, is pattern matching simply a bind operation?
  • Can an optional type whose expected type is void, but unexpected type an exception or error be treated as a monad?
  • Will we have the chance to perform an early return instead of evaluating each step we execute?

Exception specifications in C++ are tough to get right. An exception thrown at the wrong time can cause quite a bit of sadness. Unfortunately for us, marking a function as noexcept does not change its function signature and a type trait used to set a noexcept could be wrong [2]. This ends up resulting in a situation where a function is marked as noexcept, but it is still capable of throwing an exception, and not all compilers warn you about it either. There's also the added bit of how we are to handle optional types that wrap different error states, and therefore have different exception specifications. For example, core::result<T> houses either a T or std::error_condition. std::error_condition can be used to create a std::system_error, which can then be stored inside of an core::expected<U>. But we can't always go back the other way. The only way that an expected<U> could be converted to a result<T> is if the expected<U>'s unexpected value was specifically a std::system_error. But expected<U> is built to house any type that can be stored within std::exception_ptr. This reduces the monadic operations we can perform on our optional types, when converting between them. Worse, we lose a lot of information when chaining multiple operations. For example, if we were to perform file I/O in several steps, there would be no way for us to know exactly when, if at all, the operation failed. Instead, we would have to either log the information, or manually check along each of the possible steps to know when a failure occurred. Of course, we can't do that, which limits the use of monadic operations that could potentially fail to simple steps which may not require transactions. Supporting exceptions as the unexpected type in an optional type will unfortunately exclude that specific type instantiaion from being a literal type.

If an optional type can be a literal type (declared as constexpr), should the operations we perform on it also be constexpr? This is a quick yes, though the exception specification mentioned above needs to be taken into account. It also results in more code being written, because we can't simply pass a lambda to the monadic operations (since lambdas are not literal types). One possibility is to make lambdas literal types, but whether that will happen in a future revision of the C++ standard remains to be seen. Implementing an optional type as a literal type requires a bit of inheritance wankery combined with a union-like class. If only we could use std::aligned_storage in a constexpr way.

Technically, variants and union-like class are optional types. For one, we can technically describe an optional<T> as variant<T, nullopt_t>. Additionally, we can describe pattern matching as a more flexible form of a bind operation. Specifically, in the case where we have no value, we can choose to instead return one as a fallback. However, the semantics don't follow that of a "true" monad, so we'll just say that we could treat a variant with two possible values as a monad, but we don't. I don't have an explanation. We can't have a union with void, however, so we can't implement every optional type that could support void as its expected type with a variant or union-like class.

An optional type can have its expected type be void, but only if the unexpected form is meant to represent an error of some kind. That is, we can't have an optional<void>, but we can have an expected<void>. What this implies to consumers of an API is that the lack of an error is expected, but no value is required to continue execution, although at that point you might as well be checking return values for possible early returns.

As of right now, there is no way to perform an early return from a series of monadic operations without modifying the language, or implementing a macro to handle the logic for you. The Boost.Expected proposal discusses adding either a do-notation much like the one found in Haskell, or adding a new keyword (expect). I would prefer the latter, as it would be easier to explain to a beginner what it does. A preprocessor macro is most likely the best approach however:

#define EXPECT(var, ...)  \
  auto var = __VA_ARGS__; \
  if (not var) return var

EXPECT(variable1, function_returning_optional_type());
EXPECT(variable2, variable1.then([] (T const& t) { /* ... */ }));

All of the answers to these questions are of course tentative. We're still a bit early on in the ability to easily express optional types and monadic operations with them (and whether they'll make it into the standard in some way will be a bit of a ways off). Hopefully, however, this post has given you, dear reader, a better idea of what a monad is, or rather, why they have use. Even if it is in relation to just C++, and without code examples.

[1] Except when using decltype. decltype(void()) is valid C++11.
[2] noexcept currently returns true for functions without a noexcept specifier, and as far as I am aware, GCC is the only compiler at the moment that will warn about incorrect noexcept specifications.