Function composition in C++14
A few days ago, a friend of mine told me that he needed a way to compose functions and defer the call to the composed functions. That is, instead of writing something like
bool res = intersect(b0, difference(b1, b2));he wanted something like
auto f = intersect(_, difference(_, _));
//... later
bool res = f(b0, b1, b2);where “intersect” and “difference” are boolean functions, and “_” is a placeholder for arguments. As a C++ developer fond of metaprogramming and used to expression templates, my first thought was “simple, let’s build an expression tree”
A naive expression tree
The idea is quite simple: each function should build a node of the expression tree. Such a node is a template class whose template parameters are the function to apply and the operands:
template <class F, class... T>
struct function_node
{
template <class FA, class... TA>
function_node(FA&& fa, TA&&... t)
: m_func(std::forward<FA>(fa)),
m_operand(std::forward<TA>(t)...);
{
} F m_func;
std::tuple<T...> m_operand;
};
Let’s now rewrite the intersect function so it returns a node of the expression tree:
template <class T1 ,class T2>
auto intersect(T1&& t1, T2&& t2)
{
auto f = [](bool a, bool b) { return a && b; };
return function_node<decltype(f), T1, T2>(
f,
std::forward<T1>(t1),
std::forward<T2>(t2)
);
}That’s a bit verbose, the need to explicitly specify the return type is annoying. Especially if we need to repeat that code in the implementation of every function that returns a “function_node”. Let’s simplify this with the help of a maker:
template <class F, class T>
auto make_function_node(F&& f, T&&... t)
{
using return_type = function_node<F, T...>;
return return_type(std::forward<F>(f), std::forward<T>(t)...);
}Our intersect function then simplifies in
template <class T1, class T2>
auto intersect(T1&& t1, T2&& t2)
{
return make_function_node(
[](bool a, bool b) { return a && b; },
std::forward<T1>(t1),
std::forward<T2>(t2)
);
}That’s better! Let’s now implement a structure for the leaves of the expression tree. Since we are composing functions, a leaf of such an expression tree is the identity function:
struct identity
{
template <class T>
T&& operator()(T&& t)
{
return std::forward<T>(t);
}
};identity _;
“_” is a global instance of identity so we can now write
auto f = intersect(_, difference(_, _));
// The type of f is function_node<F1,
// identity,
// function_node<F2,
// identity,
// identity>>
// where F1 and F2 are the lambda encoding the functions to apply.Perfect, we have all the elements required to build an expression tree, we can now focus on the call operator. Each function node should forward some of the arguments to its operands and then apply the lambda to the result. In the previous example the call operator of “f” should accept 3 arguments, forward the first one to the identity node (that is, its first operand) and the other ones to the “function_node” that computes the difference (that is, the second operand of “f”) and eventually computes the intersection of the results:
template <class F, class... T>
struct function_node
{
template <class U1, class U2, class U3>
auto operator()(U1&& u1, U2&& u2, U3&& u3)
{
return m_func(std::get<0>(m_operand)(std::forward<U1>(u1)),
std::get<1>(m_operand)(std::forward<U2>(u2),
std::forward<U3>(u3)));
}
};But wait! The second “function_node” should accept two arguments only. And what if instead of an intersection, I had a ternary function?
auto f = ternary_function(_, difference(_, _), _);Then “f” should accept four arguments. The generic case implies computing the arity of each operand in the expression, and the split the list of arguments accordingly. Although this it technically possible, that would quickly become a nightmare!
The solution
The problem is how to split and forward the arguments. Now, what if we forward them all and let the leaves decide which one to return? The implementation of the call operator becomes really generic:
template <class F, class... T>
struct function_node
{
template <class... U>
auto operator()(U&&... u)
{
return access_impl(std::make_index_sequence<sizeof...(U)>(),
std::forward<U>(u)...);
} template <size_t... I, class... U>
auto access_impl(std::index_sequence<I...>, U&&... u)
{
return m_func(std::get<I>(m_operand)(std::forward<U>(u)...)...);
}
};
Why an indirection through an additional “access_impl” method? Simply because we need a double expansion: one for the arguments (remember that we want to forward all the arguments) and one for the operands (we want to forward all the arguments to all the operands). Since the operands are stored in a tuple, we create an index sequence and use it to expand the access of an element in the tuple.
Alright, now that we have a full implementation of “function_node”, let’s go back to the leaves. A leaf should accept a list of arguments and return only one of them. Besides, which argument is returned should be known at compile time. Identity is not a good name anymore, let’s call it “argument_picker”, its implementation looks like
template <size_t I>
struct argument_picker
{
template <class... T>
decltype(auto) operator()(T&&... t)
{
return ???
}
};For those not familiar with decltype(auto), this syntax means “deduce the return type but with the rules of decltype, that is, do not drop the references during the deduction”. We can then define convenient placeholders:
argument_picker<0> _0;
argument_picker<1> _1;
argument_picker<2> _2;
// ... as many as needed, but functions with too many arguments are // usually discouraged// We can now write
auto f = intersect(_0, difference(_1, _2));
A few remarks before I go on with the implementation of the call operator. First, the placeholders start at 0, contrary to the ones of the STL which start at 1. I find it more consistent with array and tuple indexing. Secondly, the syntax is a bit more verbose: the user must now specify the number of the argument. It is still possible to implement an unnamed placeholder “_” that will return the right “argument_picker” depending on its position in its expression, but that goes beyond the purpose of this article. Besides, the new syntax is actually more flexible than the first one! Indeed we can reuse the same argument in a more complex expression, and even reorder the arguments:
auto f = intersect(_1, difference(_0, _1));Now “f” is a binary function that forwards its second argument as the first argument of “intersect” and as the second one of “difference”; this would not have been possible with the initial syntax.
Now that we have a more powerful syntax, let’s finish the implementation of “argument_picker”. We want to select the “I-th” argument of a parameter pack. The easiest way to do that is to use a recursion: we removed the first argument of the argument list, decrease “I” until it reaches 0. The first argument of the new list will be the one we need. So we need something like:
template <size_t I, class Arg, class... Args>
decltype(auto) argument(Arg&& /*arg*/, Args&&... args)
{
// Recursive call
return argument<I - 1>(std::forward<Args>(args)...);
}// End of the recursion
template <class Arg, class... Args>
decltype(auto) argument<0>(Args&& arg, Args&&... /*args*/)
{
return std::forward<Arg>(arg);
}
The problem is that C++ does not allow partial specialization of template functions. Alright, let’s wrap them in structures and provide an API function:
template <size_t I>
struct argument_getter
{
template <size_t I, class Arg, class... Args>
static decltype(auto) get(Arg&& /*arg*/, Args&&... args)
{
return argument_getter<I - 1>(std::forward<Args>(args)...);
}
};template <>
struct argument_getter<0>
{
template <class Arg, class... Args>
static decltype(auto) get(Args&& arg, Args&&... /*args*/)
{
return std::forward<Arg>(arg);
}
};template <std::size_t I, class... Args>
decltype(auto) argument(Args&&... args)
{
return argument_getter<I>::get(std::forward<Args>(args)...);
}
We’re almost done, the last thing to do is to call the “argument” function from the “argument_picker” call operator:
template <size_t I>
struct argument_picker
{
template <class... T>
decltype(auto) operator()(T&&... t)
{
return argument<I>(std::forward<T>(t)...);
}
};Conclusion
Altogether, the code of the “argument_picker” and the “function_node” are less than 100 lines of code. Pretty nice for such a powerful feature! Now all you need to do to get a real framework is to implement overloads of the common operators and mathematical functions so they return “function_node” and you can write funny things like:
auto f = exp(cos(_0 + _1) + sin(_2));