How to metaprogram a generic list extraction for building a function call

Question

I have a family of classes with methods with the following signature:

double compute(list<T> pars)

This method performs a calculation with the parameters received through pars. For each compute(list) method, I have another compute(x1, x2, ..., xn) which is the method implementing the real calculation. Thus, compute(pars) should do some such as:

double compute(list<T> pars)
{
  T x1 = list.pop_back();
  T x2 = list.pop_back();
  // .. so on until last parameter xn
  T xn = list.pop_back();

  return compute(x1, x2, .., xn); // here the real implementation is called
}

This pattern repeats many times, the only thing that could change is the size of pars list and of course the implementation of compute(x1, x1, ..).

I would like to find a way for "driying" this repetitive process; concretely, extracting the parameters in pars list and building the call to compute(x1, x2, .., xn). I have been trying without success to do some macro tricks.

My question is if it exists some way based on metaprogramming that allows me to implement compute(list<T> pars) once and simply reuse it n order to perform the call to compute(x1, x2, ..., xn)

EDIT: This is the signature of the other compute(x1, ...)

VtlQuantity compute(const VtlQuantity & x1, 
                    const VtlQuantity & x2,
                    // any number of pars according the class
                    const VtlQuantity & xn) const

'VtlQuantityis a class representingdouble`'s, their units and other stuff.

Jurado

compute() does not know the size of pars, this pretty much rules out metaprogramming. P.S.: unless you enjoy copying lists all the time for no good reason, whatsoever, compute() should take its parameter by reference. – Sit

Is the size of pars known at compile-time? – Sardonic

@VittorioRomeo: not it isn't. The size is known in running time. However, it could be deduced in compiling time from the number of parameters that will receive compute(x1, x2, .., xn) – Jurado

How that could be deduced? Number of parameters to pass to compute(x1, ...) is based on size of pars, not vice-versa. – Freshman

@SamVarshavchik: yes I could receive the list by reference and getting the parameters through an iterator – Jurado

@lrleon: could you post the signature of the other compute? – Crifasi

@Zereges: compute(x1, ....) is already known. So at least from a human perspective, the number of parameters could be known. The compiler machinery also knows it. The question would be then how to know in metaprograming terms how many parameters receive compute(x1, ....) – Jurado

@Nawaz I edited the question and posted the signature of the other compute() – Jurado

Answer 1

This is a C++11 solution for the more general problem type of applying a function or functor F, taking N type T parameters and returning type Ret, to the N arguments at successive positions of some input iterator.

This gains several flexibilities over a solution parameterized by some container-of-T of the arguments:-

• You can extract the arguments from an arbitrary N-sized range within a sequence.

• The sequence need not be a container-of-T - though it must be a sequence of something convertible to T.

• You can extract the arguments either last-to-first (as you do), or first-to-last, from the standard container types or any that support forward and reverse iterators.

• You may even apply F to arguments consumed directly from some input stream, without intermediate extraction.

• And of course you can change your mind about the type of sequence in which to deliver arguments without having to change the functional-application solution.

Interface

template<typename Func, typename InIter, typename Stop = std::nullptr_t>
typename function_traits<typename std::decay<Func>::type>::return_type
invoke(Func && f, InIter it, Stop stop = Stop());

You can use this like:

auto result = invoke(func,iter);

to apply func to the arguments at N successive positions of the iterator iter.

That way, you get no range-checking that N arguments are legitimately accessible to your program at those positions. The range-checking code that you will spot in the implementation will compile to nothing and if you trespass out of bounds there will be UB.

If you want range checking you can instead code:

auto result = invoke(func,iter,end);

where end is an iterator of the same type as iter delimiting the end of the available range in the usual manner. In this case an std::out_of_range will be thrown if N exceeds the size of the range.

Implementation

#include <type_traits>
#include <functional>
#include <string>

template<typename T>
struct function_traits;

template <typename Ret, typename ArgT, typename... ArgRest>
struct function_traits<Ret(*)(ArgT, ArgRest...)>
{
    static constexpr std::size_t n_args = 1 + sizeof...(ArgRest);
    using first_arg_type = ArgT;
    using return_type = Ret;
};

template <typename Ret, typename ArgT, typename... ArgRest>
struct function_traits<std::function<Ret(ArgT, ArgRest...)>>
{
    static constexpr std::size_t n_args = 1 + sizeof...(ArgRest);
    using first_arg_type = ArgT;
    using return_type = Ret;
};

namespace detail {

template<typename Left, typename Right>
typename std::enable_if<!std::is_same<Left,Right>::value>::type
range_check(Left, Right, std::string const &){}

template<typename Left, typename Right>
typename std::enable_if<std::is_same<Left,Right>::value>::type
range_check(Left start, Right end, std::string const & gripe) {
    if (start == end) {
        throw std::out_of_range(gripe);
    }
}

template<
    std::size_t N, typename Func, typename InIter, typename Stop, 
    typename ...Ts
>
typename std::enable_if<
    N == function_traits<typename std::decay<Func>::type>::n_args, 
    typename function_traits<typename std::decay<Func>::type>::return_type
>::type
invoke(Func && f, InIter, Stop, Ts...args)
{
    return f(args...);
}

template<
    std::size_t N, typename Func, typename InIter, typename Stop,
    typename ...Ts
>
typename std::enable_if<
    N != function_traits<typename std::decay<Func>::type>::n_args,
    typename function_traits<typename std::decay<Func>::type>::return_type
>::type
invoke(Func && f, InIter it, Stop stop, Ts...args)
{
    range_check(it,stop,
        "Function takes more arguments than are available "
        "in `" + std::string(__PRETTY_FUNCTION__) + '`');
    using arg_type = typename 
        function_traits<typename std::decay<Func>::type>::first_arg_type;
    auto arg = static_cast<arg_type>(*it);
    return invoke<N + 1>(std::forward<Func>(f),++it,stop,args...,arg);
}

} // namespace detail

template<typename Func, typename InIter, typename Stop = std::nullptr_t>
typename function_traits<typename std::decay<Func>::type>::return_type
invoke(Func && f, InIter it, Stop stop = Stop())
{
    return detail::invoke<0>(std::forward<Func>(f),it,stop);
}

The two specializations of function_traits<T> provided will restrict compilation to functional types T that take at least one argument, which should suffice for likely applications. Should you need to support invocation on types taking 0 arguments then you can augment them with:

template <typename Ret>
struct function_traits<Ret(*)()>
{
    static constexpr std::size_t n_args = 0;
    using return_type = Ret;
};

template <typename Ret>
struct function_traits<std::function<Ret()>>
{
    static constexpr std::size_t n_args = 0;
    using return_type = Ret;
};

The specialization for free functions function_traits<Ret(*)(ArgT, ArgRest...)>, is strictly a redundant convenience, since they too could be wrapped in std::function objects, as you're obliged to do for anything fancier than a free function.

Demo

For a program that exercises the features discussed you can append:

#include <iostream>
#include <list>
#include <vector>
#include <deque>
#include <sstream>
#include <iterator>

struct num
{
    double d;
    explicit operator double() const {
        return d;
    }
};

double add4(double d0, double d1, double d2, double d3)
{
    std::cout << d0 << '+' << d1 << '+' << d2 << '+' << d3 << "\n="; 
    return d0 + d1 + d2 + d3;
}

int multiply2(int i0, int i1)
{
    std::cout << i0 << '*' << i1 << "\n="; 
    return i0 * i1;
}

struct S
{
    int subtract3(int i0, int i1, int i2) const
    {
        std::cout << i0 << '-' << i1 << '-' << i2 << "\n="; 
        return i0 - i1 - i2;
    }
    int compute(std::list<int> const & li) const {
        std::function<int(int,int,int)> bind = [this](int i0, int i1, int i2) {
            return this->subtract3(i0,i1,i2);
        };
        return invoke(bind,li.begin());
    }
};


int main()
{
    std::vector<double> vd{1.0,2.0,3.0,4.0};
    std::vector<double> vdshort{9.0};
    std::list<int> li{5,6,7,8};
    std::deque<num> dn{num{10.0},num{20.0},num{30.0},num{40.0}};
    std::istringstream iss{std::string{"10 9 8"}};
    std::istream_iterator<int> it(iss); 
    std::cout << invoke(add4,vd.rbegin()) << '\n';
    std::cout << invoke(multiply2,li.begin()) << '\n';
    std::cout << invoke(add4,dn.rbegin()) << '\n';   
    std::cout << invoke(multiply2,++it) << '\n';
    S s;
    std::cout << '=' << s.compute(li) << '\n';
    try {
        std::cout << invoke(add4,vdshort.begin(),vdshort.end()) << '\n';
    } catch(std::out_of_range const & gripe) {
        std::cout << "Oops :(\n" << gripe.what() << '\n';
    }

    return 0;
}

The case of:

    S s;
    std::cout << '=' << s.compute(li) << '\n';

is particularly pertinent to your particular problem, since here we call S::compute(std::list<int> const & li) to apply another non-static method of S to arguments delivered in the list li. See in the implementation of S::compute how the use of a lambda can conveniently bind both the calling S object and S::compute into an std::function we can pass to invoke.

Live demo

Grapple

Answer 2

You may do the following:

template <typename Func, typename T, std::size_t ... Is>
decltype(auto) apply(Func&& f, const std::list<T>& pars, std::index_sequence<Is...>)
{
    std::vector<T> v(pars.rbegin(), pars.rend());

    return std::forward<Func>(f)(v.at(Is)...);
}

template <std::size_t N, typename Func, typename T>
decltype(auto) apply(Func&& f, const std::list<T>& pars)
{
    return apply(std::forward<Func>(f), pars, std::make_index_sequence<N>());
}

With usage similar to:

apply<6>(print, l);

Demo

To compute automatically the arity of the function, you may create a traits:

template <typename F> struct arity;

template <typename Ret, typename ...Args> struct arity<Ret(Args...)>
{
    static constexpr std::size_t value = sizeof...(Args);
};

and then

template <typename Func, typename T>
decltype(auto) apply(Func&& f, const std::list<T>& pars)
{
    constexpr std::size_t N = arity<std::remove_pointer_t<std::decay_t<Func>>>::value;
    return apply(std::forward<Func>(f), pars, std::make_index_sequence<N>());
}

Demo

You have to enrich arity to support Functor (as the lambda).

Everetteeverglade

Thanks for your interest. Is there any way to explain to compiler the number of parameters? Some that looks a function name and deduces how many parameters it receives. I think that would be the only thing missing. – Jurado

@Jurado Remove N, replace Func by R and Args... and use R f(Args...) and use sizeof...(Args) instead of N. – Wherefore

It would be better to use an array an avoid the extra dynamic allocation, but that is tricker, so I guess not. You could also pre-reserve the vector then insert the elements, which might be a touch more performant. – Checklist

This works pretty assuming that compute is a C++ function. The problem is that compute(x1, x2, ..., xn) is a method. I'll try to find out how to do it – Jurado

Done! I used arity from [github.com/kennytm/utils/blob/master/traits.hpp] in order to get the arity of a member. Then I modified the recursive metaprogramming pattern you proposed, which, for a method is much simpler. Again, thanks to you and others – Jurado

Answer 3

C++17 solution below. wandbox link

(Greatly simplified thanks to Jarod42)

• Assumes the number of arguments N is known at compile-time, but the list can have any size.

• This calls pop_back() multiple times as shown in the example, then calls a function.

---

template <typename T>
struct list
{
    T pop_back() { return T{}; }
};

namespace impl
{    
    template<typename TList, std::size_t... TIs>
    auto list_to_tuple(TList& l, std::index_sequence<TIs...>)
    {
        using my_tuple = decltype(std::make_tuple((TIs, l.pop_back())...));
        return my_tuple{((void)TIs, l.pop_back())...};
    }
}

template<std::size_t TN, typename TList>
auto list_to_tuple(TList& l)
{
    return impl::list_to_tuple(l, std::make_index_sequence<TN>());
}

template <std::size_t TN, typename TList, typename TF>
auto call_with_list(TList& l, TF&& f)
{
    return std::experimental::apply(f, list_to_tuple<TN>(l));
}

void test_compute(int, int, int)
{
    // ...
}

int main()
{
    list<int> l{};
    call_with_list<3>(l, test_compute);
}

---

How does it work?

The idea is that we "convert" a list to a tuple, specifying how many elements we want to pop from the list at compile-time using list_to_tuple<N>(list).

After getting a tuple from the list, we can use std::experimental::apply to call a function by applying the elements of the tuple as arguments: this is done by call_with_list<N>(list, func).

To create a tuple from the list, two things needs to be done:

1. Creating an std::tuple<T, T, T, T, ...>, where T is repeated N times.

2. Call list<T>::pop_back() N times, putting the items in the tuple.

To solve the first problem, decltype is used to get the type of the following variadic expansion: std::make_tuple((TIs, l.pop_back())...). The comma operator is used so that TIs, l.pop_back() evaluates to decltype(l.pop_back()).

To solve the second problem, a variadic expansion is used inside the std::initializer_list tuple constructor, which guarantees order-of-evaluation: return my_tuple{((void)TIs, l.pop_back())...};. The same comma operator "trick" described above is used here.

---

Can I write it in C++11?

Yes, but it will be slightly more "annoying".

• std::experimental::apply is not available: look online for solutions like this one.

• std::index_sequence is not available: you will have to implement your own.

Sardonic

using my_tuple = decltype(std::make_tuple((Is, l.pop_back())...)); (unspecified order, but doesn't change the type) and my_tuple res{(Is, l.pop_back())...}; (initializer_list force order evaluation) seems to be simpler. – Everetteeverglade

@Jarod42: good points, I will improve the answer - thanks. Any simple way evaluation order could be forced in make_tuple to avoid always_t and only have return std::make_tuple(((void)TIs, l.pop_back())...); ? – Sardonic

No with function call as make_tuple, but as I said, we can use it to know the type, and then just use initializer_list. – Everetteeverglade

Answer 4

template<class T> using void_t = void;

template<class T, class F, std::size_t N=0, class=void>
struct arity:arity<T, F, N+1> {};

template<class F, class T, class Indexes>
struct nary_result_of{};

template<std::size_t, class T>
using ith_T=T;

template<class F, class T, std::size_t...Is>
struct nary_result_of<F, T, std::index_sequence<Is...>>:
  std::result_of<F( ith_T<Is, T> )>
{};

template<class T, class F, std::size_t N>
struct arity<T, F, N, void_t<
  typename nary_result_of<F, T, std::make_index_sequence<N>>::type
>>:
  std::integral_constant<std::size_t, N>
{};

arity uses one C++14 feature (index sequences, easy to write in C++11).

It takes types F and a T and tells you the least number of Ts you can pass to F to make the call valid. If no number of T qualify, it blows your template instantiation stack and your compiler complains or dies.

template<class T>
using strip = typename std::remove_reference<typename std::remove_cv<T>::type>::type;

namespace details {
  template<class T, std::size_t N, class F, class R,
    std::size_t...Is
  >
  auto compute( std::index_sequence<Is...>, F&& f, R&& r ) {
    std::array<T, N> buff={{
      (void(Is), r.pop_back())...
    }};
    return std::forward<F>(f)( buff[Is]... );
  }
}
template<class F, class R,
  class T=strip< decltype( *std::declval<R&>().begin() ) >
>
auto compute( F&& f, R&& r ) {
  return details::compute( std::make_index_sequence<arity<F,T>{}>{}, std::forward<F>(f), std::forward<R>(r) );
}

The only thing really annoying to convert to C++11 is the auto return type on compute. I'd have to rewrite my arity.

This version should auto detect the arity of even non-function pointers, letting you call this with lambdas or std::functions or what have you.

Checklist