How to make a SFINAE-based Y combinator in C++?

Question

I was thinking about the implicit templates of C++14, and I'm trying to declare a function to match an specific argument type (SFINAE and traits still give me headaches). I'm not sure how to explain what I want, but I'm trying to make a Y combinator (just to see if it's possible, not intended for production).

I'm trying to declare a function:

template<typename T>
my_traits<T>::return_type Y(T t) {
  // ...
};

Such that T is a function (or a functor) that matches

std::function<R(F, Args...)>

// where F (and above return_type) will be
std::function<R(Args...)>

Which would take any number of arguments, but the first should be a function with the same return type and the same arguments (except this function itself). The first parameter to the operator () of the functor is a 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 wasn't able to take the return type of the T type (because of the overloaded operator ()). What I'm trying to make is possible? How could I make it?

---

Edit:

Seeing it from a different angle, I'm 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;

Answer 1

It's a really hacky approach, and has severe limitations, but here it goes:

First, we need a class that pretends to support every possible operation (as far as possible), such as the fake_anything class. Note that this isn't perfect since at a minimum . and :: won't 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 operator() has only one template parameter allows us to extract its signature with decltype(&T::operator()<fake_anything>). For this to work, the lambda's return type must be explicitly specified; it can't use deduction, since otherwise the deduced return types will probably conflict.

Finally we can obtain the other arguments to the lambda and the return type using the standard partial specialization approach:

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 template to hide all the ugliness of the hack:

template<class T>
using signature_t = typename extract_signature<decltype(&T::template operator()<fake_anything>)>::type;

And finally we can check that

static_assert(std::is_same<signature_t<decltype(fib)>,
                           std::function<int(int)>>::value, "Oops");

Demo.

The limitations:

• The return type of operator() must be explicitly specified. You cannot use automatic return type deduction, unless all of the return statements return the same type regardless of the return type of the functor.
• The faking is very imperfect.
• This works for operator() of a particular form only: template<class T> R operator()(T, argument-types...) with or without const, where the first parameter is T or a reference to possibly cv-qualified T.

Answer 2

It is not possible in C++14 return type deduction to deduce int(int) out of int(T, int) as OP desires.

However, we can mask the first parameter of the result using the following approach. The struct YCombinator is instantiated with a non-recursive function object member, whose first argument is a version of itself without the first argument. YCombinator provides a call operator that receives the arguments of the non-recursive function and then returns its function object member after substituting itself for the first argument. This technique allows the programmer to avoid the messiness of myself(myself, ...) calls within 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 for a streamlined usage pattern. This compiles run 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 the non-recursive function is not defined at time that the recursive function is defined, in general the recursive function must have an explicit return type.

Edit:

However, it may be possible for the compiler to deduce the return type in certain cases if the programmer takes care to indicate the return type of the recursive function before use of the non-recursive function. While the above construction requires an explicit return type, in the following GCC 4.9.0 has no problem deducing the return type:

    auto fib = make_YCombinator([](auto self, int n) { if (n < 2) return 1; return self(n - 1) + self(n - 2); });

To pin this down just a bit further, here is a quote from the draft C++14 standard on return type deduction [7.1.6.4.11]:

If the type of an entity with an undeduced placeholder type is needed to determine the type of an expression, the program is ill-formed. Once a return statement has been seen in a function, however, the return type deduced from that statement can be used in the rest of the function, including in 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 ]