C++17: Folding expression.

That is one of those new additions to the language that for the most part is not understood, but that’s not a surprise since most of the people do not understand as well for what reason on heart someone included something diabolic as the variadics in the C++ language.

The folding expressions was added to the language mostly because it’s absolutely needed in order to implement concepts! What concepts are is mostly the topic of a long new post which I’ll write sooner or later, what we need to know here in very few words, is that concepts will allow to specify a well defined set of requirement on a template argument, or (source):

"To improve the support for generic programming in C++,
we introduce concepts to express the syntactic and semantic behavior
of types and to constrain the type parameters in a C++ template"

Sadly as today, concepts are not going to be included in C++17, the reason for this exclusion is that too less time passed between the original proposal of the feature, the first test implementation in gcc (implemented by the same dude who wrote the feature specification) and the attempt to approve it in C++17. Those things need time to mature I guess.

But here, we shall concentrate on the folding expression.

Folding expression.

The idea is that thanks to this feature now is possible to expand a parameter pack as a sequence of operators, we have two possible folding expression, Unary and binary folding and we can fold to left or right:

      ( cast-expression fold-operator ... )
      ( ... fold-operator cast-expression )
      ( cast-expression fold-operator ... fold-operator cast-expression )

fold-operator: one of
    +  -  *  /  %  ^  &  |  ~  =  < >  << >>
    +=  -=  *=  /=  %=  ^=  &=  |=  <<= >>=
    ==  !=  <= >=  &&  ||  ,  .*  ->*

For a given parameter pack and a fold operator is possible to produces the following expressions:

((E1 op E2) op ...) op EN for a unary left fold,
E1 op (... op (EN-1 op EN)) for a unary right fold,
(((E op E1) op E2) op ...) op EN for a binary left fold, and
E1 op (... op (EN-1 op (EN op E))) for a binary right fold.

Where E* are the folded elements from the variadic template and op is one of the allowed operations for the expression. The expansion of the parameter pack is resolved in the application of the operator to all the elements of the pack (or, to pair of elements), the exact way this happen depends on the type of folding, binary,unary &c.

To clarify this feature, is much better to have a look at some examples.

Example 1.

We know how to implement a very simple print function using C++14, using our favorite pattern of recursive variadic templates:

void print(const T&...)

template<typename T1, typename... T2>
void print(const T1& value, const T2&... values)
	std::cout<< value;

When calling print if the amount of arguments is greater than zero then the variadic version of the function is invoked, the compiler will then recursively call print till there are parameters available, the recursion is closed by a call to print with no arguments when the expansion values… is empty.

That is simple and cleaver, we obtain something similar with much less coding using the fold expression:

template<typename... T>
void print2(T&&...values)
	( std::cout << ... << values ) << std::endl; 

print("Number ",69, " is > than ", 1.5);
print2("Number ",69, " is > than ", 1.5);

This function uses a binary fold expression over the stream operator, the call to print and print2 are producing the same output. What the compiler attempt to do here is to apply the rule for the expansion of the parameter pack values over the binary operator <<, assuming for a second that we can name each single parameter in the pack, then the compiler will produce something similar to:

( …  ( std::cout<< val1 ) << val2 ) << val3 … )  <<std::endl;

(But we’re not allowed to name the variadic template variables in this way, this is just for explanation purpose and you shall know it!)

There’s one thing you might want to check yourself, I’m not going to copy-paste the whole thing here: Open godbolt and check the assembler generated for both the versions of this little print function, you’ll notice that the fold expression assembly is much sorter, whether I’m still not sure about the details, it looks like there’s more room for compiler to optimize the code with the fold expression.

Example 2.

We want to know at compile time if all the parameter of a variadic are of the type float, for this reason we want to have a meta-function. If all the arguments are not floats then our function must return std::false_type otherwise std::true_type. For the purpose of this example here’s the C++14 meta function which perform this verification:

template<typename T>
using ifp = std::is_floating_point<T>;

struct all_float : std::true_type
{ };

template<typename T,typename... Tr>
struct all_float<T,Tr...> : std::conditional<
	ifp<typename std::decay<T>::type>::value,
{ };

Again I’m using the old school recursive pattern here, the first all_float is our base for the recursion, it has std::true_type as base class from which inherits the typedef type which is a boolean true. The specialized all_float inherit conditionally, either from itself or from std::false_type. The condition which decide whether it shall inherit from one or the other class is the first template argument to std::conditional.

Ifis a floating point type, then the recursion continues with the next element from the variadic pack, if it’s not then the recursion stop and gives to all_float an inherited typedef from std::false_type which is a boolean false.

Now that’s a hell of typing, we can make our life simpler implementing the same thing using the new folding expression:

template<typename T>
using ifp = std::is_floating_point<T>;

struct all_float2
	static const bool value = (ifp<typename std::decay<T>::type>::value && ...);

In this example we’re folding the result of the evaluation if ifp for all the parameter in the pack, applying the operator && to generate the boolean which we need to use in order to verify if all the elements in T… are floats.

At this point you might have noticed two things, first I’m always putting the fold expression within round parenthesis, that’s required in order to allow the compiler to properly parse the expression. Secondly, I’m applying std::decay to all the types from the pack, this is required to make sure that we have the proper type T, avoiding in this way a wrong type deduction.

I suggest you to have a look again at the assembly output, for this example the compiler generate exactly the same output for bot the old style and new style version of all_float

Example 3.

That’s a real classic!

Let’s say we want to perform a sum at compile time, we want our summing function to perform the proper promotion/conversion on different types in order to avoid loss of precision. If we sum a double with an int, then the result shall be a double, &c.

Let’s see how it looks like in C++14:

struct decltype_all;

template<typename T1>
struct decltype_all<T1>
	typedef T1 type;

template<typename T1,typename...Tr>
struct decltype_all<T1,Tr...>
	typedef decltype(std::declval<T1>() + std::declval<typename decltype_all<Tr...>::type>()) type;

template<typename T>
T sum_all(const T& last)
	return last;

template<typename T1,typename...Tr>
auto sum_all(const T1& v1, const Tr&...vr) ->
	typename decltype_all<T1,Tr...>::type
	return v1 + sum_all(vr...);

That’s not very readable! The hard part is the procedure responsible for the deduction of the proper return type of the sum, decltype_all will recursively check all the parameter provided in the variadic and will perform a type deduction on the return type of the operation  T0 + ( … ( Tn -2 + ( Tn + Tn-1 ) ) ).

Now how we can obtain the same functionality using some C++17? Let’s have a look:

auto sum_all2(const Tr&...vr) ->
	decltype( ( vr + ... ) )
	return ( vr + ... );

Here the code is applying to operator + pairwise to all the elements in Tr…, this allows decltype to properly deduce the return type of the whole summation on the base of all the operators.

The body function then just run again the operator + on all the arguments, in a form similar to: vr0 + ( vr1 + … (vrN-k + … + ) ). The compiler given the types has the ability to properly guess the return type in the deduction, and has also no problems in reducing this template function in nothing more than few assembly instructions, but that was possible as well in the old C++14 implementation, what we’re saving here is time for typing and clarity!


There might be other interesting examples of how to use the folding expression, fold expressions are not limited to pure evaluation but can be used as well to write powerfull generic wrappers for callable:

template<typename Fnc, typename... T>
void my_call(Fnc callable, T&&... vr)
	( callable( std::forward<T>(vr) ), ...);

int main()
	my_call([](auto v) { std::cout<<v<<" "; }, "The num ", 69 ," is < than ",3.33);
	return 0;

The theory behind it’s  simple as many of the new features which are coming with recent C++ updates, the problem is not in understanding how a certain thing work but in understanding why it was added and this required more and more background and experience with the code, which in a certain way increase the slope of the learning curve for the language.

C++ is growing complex, when I was moving my first steps with it the standard I had at hand was C++98, which was a long step ahead of say C, but still was much simpler and easier to learn that modern C++14.

Anyway, to fully appreciate the folding expression (if you’re not already excited about it) you have to wait for C++17 to be release and people to start writing the real code, then you’ll see how coding templates will became for easier (for some cases), hope the samples has provided you with some basic idea of what I’m talking about.

For many more details about the topic covered here I invite you to have a look here.

Thanks for reading!

Leave a Reply