Function composition in C++11

There is a lot of code in this post, it will probably not compile "as is" because of missing headers or compiler's incompatibilities. Nevertheless, we made available through our open source initiative the full working library on github. It has been tested on Clang 3.1, gcc 4.6.1 and MSVC 11 on FreeBSD, Linux and Windows.

Functional languages are built around function composition. However, function composition isn't limited to functional languages as every time you chain at least two calls you are actually composing functions. Although Eric Niebler already wrote on the topic of function composition in C++, in this post we'll go further and enjoy the availability of C++11 compilers for a more hands-on approach.

At Bureau 14 we use function composition a lot as our software, quasardb, is built on the principle that each treatment is composition of simple functions with a single responsibility. For example, when you add an entry to the database, it is chained call of receive, decode, store, check, build reply and send. In other words, it could be written as send(build_reply(check(store(decode(receive()))))); (I hope you stored enough parentheses for winter because winter is coming).

Time for some propaganda

Our mission is to build the fastest database on Earth and we want to be the fastest without the shadow of a doubt. It was easy to crush engines built in Java or similar languages (Cassandra, Coherence...) but topping engines written in C/C++ was harder (MongoDB, memcached, redis...) and required to be obsessive about design and implementation.

Function composition is one of the tools we used to achieve an out of this world level of performance. Function composition enables the compiler to be as clever as possible with optimizations while being a solid yet modular foundation upon which you can build highly parallel software.

Having code truly parallel is not something that is easy to do generally speaking but having the most complex parts of the software (for example automatic replication and failover) expressed as a series of simple functions helps you see where your code is multi-threaded challenged. Our approach makes parallelization a matter of accessing lock-free structures or duplicating input data.

Last but not least, writing tests and creating mock-ups is much, much easier thanks to our functional paradigm.

Some first examples

As great as function composition may be, in C++, it can quickly become cumbersome and inelegant to write. For example, let's say you have a class called server (by the way, at Bureau 14, having short variables names is our way of being green):

What's wrong with this code?

Well, it's absolutely not generic, but you could argue that at some point you have to specialize. Nevertheless, if we want to add a function, or, if for some process we need to specialize some, it can quickly be error prone. In addition, we may probably want to build the kernel object around the same logic: it would therefore be better to have a common framework to describe such objects.

Wouldn't it be great if we could write:

Implementing a server is now just a matter of writing:

Need to add encryption?

Since the kernel is built around the same logic, this will also enable us to write:

And to give you a glimpse of what it actually looks like in our production code:

More generally, we also want to be able to use regular functions and combine them easily:

In this post, I'm going to show you how we can write exactly this in C++ 11.

The trivial case

Composing two functions is the trivial case and will be our starting point.

As you can see, a composed functor takes two functors as parameters and executes them when the overloaded parenthesis operator is called. With the help of a function we can make it a little bit more usable:

And now we can write:

Provided that f and g are instantiated functors. As composed is a functor itself, we can even write:

Note that you can store the composed functor for repeated use:

You can even use regular functions thanks to decltype:

This is all well and good but we need to push this further. We want to write compose(f, g, h), not compose(compose(f, g), h). A straightforward, albeit not very elegant, way is to write all the overloads:

I don't know for you but I'm already bored to death, and I only wrote the four parameters version. Why write a dozens of overloads when you could be killing aliens in X-COM?

Preprocessor hacking

Or we can abuse the preprocessor. Yes, I know, macros are evil, you should never use them, every time you use a macro a kitten dies, yada, yada, yada. Now that the cat is out of the bag, let's do crazy stuff with macros.

Thanks to Boost.Preprocessor, we can write recursive macros in a convenient way: this will make it possible to safely write wrappers for as many parameters as we want:

I never said that the macros were going to be understandable or easy to read, but they do the job and they do it in a minimal amount of code. More importantly they reduce errors due to typos to zero: once your macro is right, all the generated functions will be correct.

How do the macros work? Remember we already have the 2 parameters function defined: this is going to be our recursion termination. We start with 3 parameters (we specify 2, but we use BOOSTPPINC()) and stop at 20. We then generate the template and functions parameters with BOOSTPPENUMPARAMSZ() and BOOSTPPENUMBINARYPARAMS_Z(). Since we generate the function incrementally, each new version is defined as the recursion of the previous one, exactly as we did when we wrote the 3 and 4 parameters versions.

Our recursion works in a "pop back" fashion, that is, we build the composition in appending the last parameter and recurring on the remainder, on the left. It has to be done in this order as we want our composition to work from left to right: when we write compose(f, g, h), we want f to be executed first, we want h(g(f(x))). We could have a more functional semantic where compose(f, g, h) would actually be f(g(h(x))) but this would be confusing as in C++ we write calls from left to right (Remember Ghostbusters: don't cross the streams).

For example when we write compose(receive, decode, process), we expect to receive, decode and finally process. Writing compose(process, decode, receive) wouldn't be very C++ish.

A more formal recursion description

For a given list of parameters [h:t] where h are all the elements except the last one and t is the last element, the recursion is defined as:

Until we reach a list of two elements [a, b] where compose becomes:

But Edouard, we are writing C++ 11! Why don't we use variadic templates?

Variadic templates unfortunately work in a "pop front" logic, making the code actually much less straightforward (because these unintelligible recursive preprocessor macros are obviously mundane). You could nevertheless write a pop front variadic template version with an adapter that reverses the list of parameters.

Using tuples and Boost.Fusion

All is good and well but we still can't write:

which is a shame because it's what we really need for generic programming.

The first order of business is to somehow be able to know the right "composed" functor type given a list of types. We'll work with Boost.MPL and more precisely boost::mpl::vector to list our types.

Of course this will not compile if the size of your MPL vector is less than 2 (pretty hard to combine less than 2 functions, isn't it?).

If you want to compose functors of type receiver, decoder, kernel, encoder and sender you can have the final composed type in writing:

Until now we didn't have the need for this because we used the C++11 decltype feature, but as we will use a Boost.Fusion vector to carry all our parameters listing the types in a MPL structure will become necessary. Why do we want to use a Boost.Fusion vector? We need a meta-programming friendly structure to work on the parameters as we build the composed functor. Boost.Fusion vector is exactly that and will enable us to write the meta-programming equivalent of our satanic macros.

Boost.Fusion is a library one may sum up as compile-time introspection through meta-programming. With Boost.Fusion you can create multi type containers, associate values with types, transform structures into containers, iterate on structures' members and much more!

Without further ado:

We can't use decltype anymore because of a chicken-egg problem: we would need to know the result of the recursion we're currently building. That's why we use makecomposed for the return value of makefromvector.

The functor takes a Vector type (hopefully a Boost.Fusion vector, but any RandomAccess Boost.Fusion container will work) and split it in two, exactly like our macro did. We pop the last element and recurse on the remaining vector. We therefore need to define the recursion termination, which can be written as:

We're almost there! All that is left to do is to convert a tuple into a Boost.Fusion vector:

We can now happily write compose(std::maketuple(f, g, h))!

Perfect forwarding

Thanks to copy elision, the compiler can avoid a lot of unnecessary copies. For functions or simple functors this is even not a problem as the copy itself may be negligible, but should you use larger functors or functors that cannot be copied this becomes an issue. Fortunately, in C++11 rvalues references and perfect forwarding enables us to make sure no copy is ever made.

If you're new to rvalue references, I strongly advise you to read this article by Hinnant, Stroustrup and Kozicki.

The difficulty with perfect forwarding is that you have to make sure the forwarding chain is never broken. To do this, we will use our library with a functor that cannot be copied but supports move semantics:

If we call:

We will get an error. We will use this error to implement perfect forwarding all the way down.

The first thing to do is to modify to the compose function:

It nevertheless will not compile yet as the constructor of composed has to be changed as well:

And to have composed fully support perfect forwarding, we need to add move support via a new constructor and a new assignment operator:

Now the first call compiles!

Since we want to support more than two parameters, we need to modify our macro. This modification isn't as trivial as it may sound because of the forwarding:

This forces us to add intermediary macros to properly forward the arguments to the next level of recursion.

What about tuples? Unfortunately Boost.Fusion does not fully support perfect forwarding yet, which makes it impossible, for now, to have perfect forwarding through the tuple interface (unless you write one without Boost.Fusion). I'll post an update as soon as this changes.

Conclusion

I hope you enjoyed this post. If you'd like to use the composition paradigm in your own program, feel free to use our BSD-licensed library! It is tested against VC11, gcc 4.6.1 and clang 3.1 on Windows, Linux and FreeBSD. Fetch it on github!