Monads in C++

This is a crosspost from www.ModernesCpp.com.

Monads in C++? What a strange name for a post. But it's not so strange. With std::optional C++17 gets a monad. The ranges library from Eric Niebler and the extended futures are also monads. For both, we can hope for in C++20.

Bjarne Stroustrup presented in his Secret Lightning Talk at the Meeting C++ 2016 a few of the concepts of Concepts Lite that we will get with high probability in C++20. There were also mathematical concepts such as ring and monad. My assumption becomes more and more reality. Modern C++ will be hardened for the future.

std::optional

std::optional is inspired by Haskell's Maybe Monad. std::optional that was originally intended to be part of C++14 stands for a calculation that maybe has a value. Therefore, a find algorithm or a query of a hash table has to deal with the fact that the question can not be answered. Often, you use for such cases special values that stand for the presence of no value, so-called no-result. Often we use a null pointer, empty strings of special integer values for no-results. This technique is expensive and error-prone because you have to deal with the no-results in a special way. No-results are of the same type as regular results. std::optional has in case of a no-result no value.

Here is a short example.

std::optional is currently in the namespace experimental. That will change with C++17. I use std::optional in the function getFirst (line 7). getFirst returns the first element if it exists (line 8). If not, you will get a std::optional<int> object (line 9). I use in the main function two vectors. The calls getFirst in line 17 and 27 return the std::optional objects. In case of myInt (line 19), the object has a value; in case of myEmptyInt (Zeile 29), the object has no value. Now I can display the value of myInt (line 20 - 22). The method value_or in line 22 and 30 returns the value or a default value. This is due to the fact whether std::optional has a value.

The screenshot shows the output of the program using the online-compiler at cppreference.com.

Extended futures

Modern c++ supports tasks.

Tasks are pairs of std::promise and std::future objects connected by a channel. Both communication endpoints may exist in different threads. The std::promise (sender) pushes its value into the channel the std::future (receiver) is waiting for. The sender can push a value, a notification, or an exception into the channel. I've written a few posts about tasks. Here are the details: Tasks.

The easiest way to create a promise is to use the function std::async. std::async behave like an asynchronous function call.

int a= 2000
int b= 11;
std::future<int> sum= std::async([=]{ return a+b; });
std::cout << sum.get() << std::endl;

The call std::async performs more actions. First, it creates the communication endpoints promise and future; second, it connects them both via a channel. The lambda function [=]{ return a+b;} is the work package of the promise. It captures the arguments a and b from it defining context. The C++ run time decides if the promise will run in the same or in a different thread. Criteria for its decision may be size of the work package, the load of the system, or the number of cores.

The future calls sum.get() to get the value from the promise. You can only once call sum.get(). If the promise is not done with its job, the get call will block.

Tasks provide the similar and safer handling of threads because they have no shared state that has to be protected. Therefore, race conditions are not possible and dead locks much rarer. But, the C++11 implementation of futures has a big disadvantage. The composition of std::future objects is not possible. This will not hold true for the extended futures of C++20.

The table shows the functions for extended futures.

Here are a few code snippets from the proposal n3721.

The future f2 in line 3 is ready, if the future f2 is ready. You can enlarge the chain of futures: f1.then(...).then(...).then(...). The future any_f in line 10 becomes ready if any of its futures become ready. In contrary, the future all_f in line 16 becomes ready, if all its futures become ready.

One question is still not answered. What have futures in common with functional programming? A lot! The extended futures are a monad. I explained in the post Pure Functions the idea of monads. The key idea of a monad is that a monad encapsulates a simple type in an enriched type and supports the compositions of functions on these enriched types. Therefore, the monad needs a function for lifting the simple type into an enriched type. Additionally, a monad needs a function that empowers them to compose functions on enriched types. This is the job for the functions make_ready_future, then, and future<future<T>>. make_ready_future maps a simple type into an enriched type; a so-called monadic value. This function is called identity and has the name return in Haskell. The two functions then and future<future<T>> are equivalent to the bind operator in Haskell. The bind operators job is it to transform one monadic value into another monadic value. bind is the function composition in a monad. 

Thanks to the method when_any std::future becomes even a Monad Plus. A Monad Plus requires from its instances that they are monads and have an operator msum. Therefore, std::future supports a kind of an addition operation in C++20.

If you want to know the details, you should read the excellent blog of Bartosz Milelweski and watch his video: "C++17: I See a Monad in Your Future!".

What's next?

In my post Recursion, List Manipulation, and Lazy Evaluation, I wrote: The story about lazy evaluation in C++ is quite short. But I made my conclusion without templates. Thanks to the CRTP idiom and expression templates C++ is lazy. Therefore, I will write in the next post about the infamous CRTP idiom.