How to create in C ++ based on SFINAE Y combinator?
I was thinking about C ++ 14 implicit templates and I am trying to declare a function to match a specific type of argument (SFINAE and traits are still giving me headaches). I'm not sure how to explain what I want, but I'm trying to do a Y combinator (just to be sure, not intended for production).
I am trying to declare a function:
template<typename T>
my_traits<T>::return_type Y(T t) {
// ...
};
So what T
is the function (or functor) that matches
std::function<R(F, Args...)>
// where F (and above return_type) will be
std::function<R(Args...)>
Which will take any number of arguments, but the first must be a function with the same return type and the same arguments (except for the function itself). The first parameter of the operator ()
functor is the template.
The usage I want to achieve:
auto fib = [](auto myself, int x) {
if(x < 2)
return 1;
return myself(x - 1) + myself(x - 2);
};
// The returned type of fib should be assignable to std::function<int(int)>
I was unable to take the return type of the type T
(due to overload operator ()
). What I am trying to do is possible? How can i do this?
Edit:
Seeing this from a different angle, I am trying to make this work:
struct my_functor {
template<typename T>
char operator () (T t, int x, float y) { /* ... */ };
};
template<typename T>
struct my_traits {
typedef /* ... */ result_type;
/* ... */
};
// I want this to be std::function<char(int, float)>, based on my_functor
using my_result =
my_traits<my_functor>::result_type;
source to share
It is not possible in C ++ 14 type inference to infer the output int(int)
from int(T, int)
OP as desired.
However, we can mask the first parameter of the result using the following approach. struct YCombinator
is created using a non-recursive member of a function object whose first argument is the version itself without the first argument. YCombinator
provides a call operator that takes arguments to a non-recursive function and then returns its function object member after substituting itself for the first argument. This method allows the programmer to avoid the messy calls myself(myself, ...)
in the definition of the recursive function.
template<typename Functor>
struct YCombinator
{
Functor functor;
template<typename... Args>
decltype(auto) operator()(Args&&... args)
{
return functor(*this, std::forward<Args>(args)...);
}
};
A make_YCombinator
utility template allows you to simplify your usage pattern. This compiler runs in GCC 4.9.0.
template<typename Functor>
decltype(auto) make_YCombinator(Functor f) { return YCombinator<Functor> { f }; }
int main()
{
auto fib = make_YCombinator([](auto self, int n) -> int { return n < 2 ? 1 : self(n - 1) + self(n - 2); });
for (int i = 0; i < 10 ; ++i)
cout << "fib(" << i << ") = " << fib(i) << endl;
return 0;
}
Since a non-recursive function is not defined in time when the recursive function is defined, in general, a recursive function must have an explicit return type.
Edit:
However, it is possible that the compiler can infer the return type in some cases, if the programmer takes care to specify the return type of the recursive function before using the non-recursive function. Although the above construct requires an explicit return type, the following GCC 4.9.0 has no problem with return type inference:
auto fib = make_YCombinator([](auto self, int n) { if (n < 2) return 1; return self(n - 1) + self(n - 2); });
To reinforce this a bit, here is a quote from the C ++ 14 draft for return type inference [7.1.6.4.11]:
If you need an object type with an unapproved placeholder type to determine the type of the expression, your program is ill-formed. However, once a return statement has been seen in a function, the return type inferred from this statement can be used in the rest of the function, including other return statements. [Example:
auto n = n; // error, n’s type is unknown auto f(); void g() { &f; } // error, f’s return type is unknown auto sum(int i) { if (i == 1) return i; // sum’s return type is int else return sum(i-1)+i; // OK, sum’s return type has been deduced }
-end example]
source to share
This is indeed a hacky approach and has serious limitations, but here it goes:
First, we need a class that claims to support every possible operation (as much as possible), such as a class fake_anything
. Please note that this is not ideal, as a minimum .
and ::
will not work. To fake a functor, we give it a function call operator:
template<class... Ts> fake_anything operator()(Ts&&...) const;
Knowing that the lambda has only one operator()
and that it operator()
has only one template parameter, we can retrieve our signature using decltype(&T::operator()<fake_anything>)
. For this to work, the return type of the lambda must be explicitly specified; it cannot use deduction, as otherwise the inferred return types are likely to be in conflict.
Finally, we can get other arguments for the lambda and return type using the standard partial specialization method:
template<class T>
struct extract_signature;
template<class T, class R, class FA, class...Args>
struct extract_signature<R (T::*)(FA, Args...)> {
static_assert(std::is_same<fake_anything, std::decay_t<FA>>::value, "Unexpected signature");
using type = std::function<R(Args...)>;
};
template<class T, class R, class FA, class...Args>
struct extract_signature<R (T::*)(FA, Args...) const> {
static_assert(std::is_same<fake_anything, std::decay_t<FA>>::value, "Unexpected signature");
using type = std::function<R(Args...)>;
};
// other cv- and ref-qualifier versions omitted - not relevant to lambdas
// we can also static_assert that none of Args is fake_anything, or reference to it, etc.
And add an alias pattern to hide all the ugliness of the hack:
template<class T>
using signature_t = typename extract_signature<decltype(&T::template operator()<fake_anything>)>::type;
Finally, we can check that
static_assert(std::is_same<signature_t<decltype(fib)>,
std::function<int(int)>>::value, "Oops");
Demo .
Limitations:
- The return type must be explicitly specified
operator()
. You cannot use automatic return type inference unless all operatorsreturn
return the same type, regardless of the functor's return type. - The counterfeit is very imperfect.
- This only works for a
operator()
specific form only:template<class T> R operator()(T, argument-types...)
with or withoutconst
, where the first parameterT
or reference is possibly cv-qualifiedT
.
source to share