In which I briefly mention what pure functional programming is, explain why this can be slow in C++, and use move semantics to solve that problem. Be warned that this post is a bit longer than usual for this blog, and that it assumes more knowledge of C++11 than my posts usually do.

Pure functional programming is programming without state. In short, functions should not modify their input, not modify local or global state, but return new values instead. Often, we also want to avoid variables completely.

For instance, instead of doing:

void square(vector<int>& v) { /*multiply each element with itself*/ }

void imperative()
{
    vector<int> v = getNumbers();
    square(v);
    doStuffWith(v);
}

we do

vector<int> squared(const vector<int>& v) { /*return a new vector with squared elements*/ }

void functional()
{
    doStuffWith(
        squared(
            getNumbers()));
}

As you might already have noticed, this style results in more copies than the imperative style, which will lead to less efficient code. Depending on the problem you are solving, this might or might not matter, but one of the few real arguments for using C++ is that you have a problem that needs an efficient solution.

Let’s take a look at an example program, translate it from imperative to functional style, and finally use move semantics (explained later) to eliminate the performance hit. For our example, we will compute the root mean square of a function. Wikipedia has a good definition, but in short: Given a list of numbers, square each of them, take the mean of those squares, and return the square root of that number.

First, let’s define some helper functions:

double sum(const std::vector<double>& v)
{
    return std::accumulate(v.begin(), v.end(), 0, std::plus<double>());
}

double mean(const std::vector<double>& v)
{
    return sum(v) / v.size();
}

The square root function already exists as std::sqrt, so we don’t need to define that. The only missing piece is a function computing the square of a vector of numbers. In good old C++, there are two ways of doing this:

vector<int> square(vector<int> v); //(Or the argument could be a const reference)

void square(vector<int>& v);

The first version creates a copy of the vector, containing the squared number. This is perfect for functional code, but makes a copy that might be unnecessary. The second version modifies the argument, which is faster and often seen in imperative code. Since we assume we want efficiency, we’ll go with the second one in the examples that follow.

Here is the full, traditional, stateful solution, including square and a usage example:

    void square(std::vector<double>& v)
    {
        std::transform(v.begin(), v.end(), v.begin(), [](double d) { return d*d; });
    }

    double rms(std::vector<double>& v)
    {
        square(v);
        double the_mean = mean(v);
        double the_rms = std::sqrt(the_mean);
        return the_rms;
    }

    int main()
    {
        std::vector<double> v = {1,2,3};
        double the_rms = rms(v);
        std::cout << the_rms << std::endl;
        return 0;
    }

I won’t go into the full discussion of why functional programming is nice, but with no state there is a whole class of problems we never get into. How often have you not found a bug that was due to some code you didn’t know about mutating some seemingly unrelated state? Also, functions are a lot easier to both test and reason about when the only thing they care about is their input and output.

Let’s have a look at a pure functional alternative:

    std::vector<double> squared(std::vector<double> v)
    {
        std::transform(v.begin(), v.end(), v.begin(), [](double d) { return d*d; });
        return std::move(v);
    }

    double rms(const std::vector<double>& v)
    {
        return std::sqrt(mean(squared(v)));
    }

    int main()
    {
        std::cout << rms({1,2,3}) << std::endl;
        return 0;
    }

As you can see, no state, and no variables except for the function parameters, which we cannot really avoid. The implementation of rms even reads exactly like its mathematical definition, root(mean(squared(numbers))). There is however the issue of the copy being made when squared() is called. (No copy should be made when squared() returns though, due to the return value optimization).

Enter C++11’s move semantics. If you don’t know what move semantics and rvalue references are, the simplest explanation I have come across is this StackOverflow answer. You really should read it through, but if you’re short on time, here is the even quicker intro: If a squared(std::vector v) somehow knew that whoever called that function would never need the original v again, it could just “steal” it instead of making a copy. In the example above, {1,2,3} is a temporary object that can never be referred to again, so instead of copying it into squared, we could just have the internal storage of v point to the same place in memory. And this is exactly what happens with rvalue references.

Rvalue references are denoted by a double ampersand: squared(std::vector&& v), and can only bind to temporaries. Here is the pure functional example again, this time using rvalue references. This version completely avoids copying the vector:

    std::vector<double> squared(std::vector<double>&& v)
    {
        std::transform(v.begin(), v.end(), v.begin(), [](double d) { return d*d; });
        return std::move(v);
    }

    double rms(std::vector<double>&& v)
    {
        return std::sqrt(mean(squared(std::move(v))));
    }

    int main()
    {
        std::cout << rms({1,2,3}) << std::endl;
        return 0;
    }

{1,2,3} is a temporary, and so rms(std::vector&& v) is free to steal its resources without a deep copy. Inside of rms however, v itself is not a temporary. It is a named variable than can be referred to, and thus it would not be safe for squared(std::vector&& v) to steal its resources. We however know that we will never use it again after calling squared(v), so we tell the compiler to go ahead and steal anyway by wrapping it in std::move(). The same is done for the return value in squared().

In the functional examples, the vector that we wanted to compute the root mean square of was a temporary, thus allowing move semantics. But what if we wanted to call rms() from a non-pure part of the code base? Here’s what would happen if the original vector was a normal variable:

    std::vector<double> v = {1,2,3};
    //rms(v); //invalid initialization of reference of type ‘std::vector<double>&&’ from expression of type ‘std::vector<int>’

As you can see, we can no longer use the functional rms(). If we however know that we will not be using the original v again, we could wrap it in std::move() as we did earlier:

    rms(std::move(v)); 

Finally, if that is not an option, we could manually make a copy:

    rms(std::vector<double>(v)); 

In a pure functional program, our functional version of rms would be both fast and fitting the style we’re in. In an imperative program, it would stylistically be a worse fit, but we still wouldn’t loose any performance.

Finally, a few notes:

• I have not considered to what degree copy elision would achieve the same benefits as move semantics for this example.
• I decided not to complicate the examples using templates and universal references but that would be an interesting extension.
• If you haven’t seen move semantics before; It is a general technique that has nothing to do with functional programming. I just think they make a great team.
• There is a whole lot more to rvalues and move semantics than could be presented here, it is seen as one of the defining features of C++11.

As usual, the code for this blog post is available on GitHub.

If you enjoyed this post, you can subscribe to my blog, or follow me on Twitter.