Type of recursive calling generic lambda expression in C++14

Question

What is the type of the lambda expression in (1) ?

Why can this code compile?

#include<functional>
#include<iostream>


int main() {
    std::cout << 
        [](auto&& f0,auto&& a0){return f0(f0,a0);}
        (
            [](auto& f,auto&& a)->int{ return (a>1) ? f(f,a-1)*a : 1; }, // (1)
            5
         )
         << std::endl;
}

I think that infinite recursion is caused by type inference for lambda expression (1) in this code. I think that auto& f is replaced to a type name such as std::function<int(std::function<int(std::function<int(......)>)>)>.

Please point out my mistake.

Answer 1

First mistake: std::function is a type unrelated to any lambda.

A lambda is an anonymous type with an operator() and a few other known properties.

std::function<R(Args...)> is a type erasure class for copy construct, destroy and invoke with Args... and return R. It can be constructed from a lambda, but is not otherwise a related type.

As you cannot name the type of a lambda, using a std::function to store it is common. The lambda is not a std::function however. std::functions have nearly unavoidable overhead from their type erasure and polymorphism: lambdas lack any polymorphism, which makes it really easy for the compiler to understand what () does at the point of invocation.

In your case you have two lambdas.

Your first lambda is:

[](auto&& f0,auto&& a0){return f0(f0,a0);}

This looks like a form of y-combinator, or a variant, used help with recursion. The operator() in this case has signature:

template<class F0, class A0>
auto operator()(F0&&,A0&&)const
-> std::result_of_t<F0&(F0&,A0&)>

roughly.

A more useful version (in my opinion) is:

[](auto&& f0){
  return [f0=std::forward<decltype(f0)>(f0)]
    (auto&&...args) {
      return f0(f0, std::forward<decltype(args)>(args)...);
    };
}

which takes an f0, stores it, and invokes it with any arguments passing f0 first. This lets you bind the recursion 'out of sight'. Making the inner lambda mutable is optional (depends if you want to invoke in a const context)

Anyhow, the next lambda:

[](auto& f,auto&& a)->int{ return (a>1) ? f(f,a-1)*a : 1; }

has an operator() signature of:

template<class F, class A>
auto operator()(F&,A&&)const
-> int

You then pass an instance of the second lambda to the first, plus an argument, and it calculates n!.

The types deduced by the template operator () do not depend on the types that the arguments themselves deduce, so there is no infinite type deduction problem. The return type of the inner lambda is hard coded to int, so you don't have to deduce what () recursively returns to know it returns int.

If you want to store the first lambda in a std::function, however, you are going to be disappointed. std::function cannot erase a template operator(): it can only erase a fixed signature, and a template member is a factory of methods, not a method itself.

However, remember my better version of y combination above?

Call your first lambda g, your second h and my lambda y and the lambda my lambda returns z.

Then g(h,x) = y(h)(x) -- and y(h) can be stored in a std::function<int(int)> no problem. We hide the part of the recursion that basically requires a recursive type signature, which std::function does not support¹. What is left, while it has a template operator(), can be bound to a simple signature.

---

¹ note that you could write std::function to support recursive signatures, like std::function< std::vector<SELF_TYPE>(int) >. You can see how this might work with how boost::variant works with recursive variants.

Answer 2

From [expr.prim.lambda], emphasis mine:

The lambda return type is auto, which is replaced by the trailing-return-type if provided and/or deduced from return statements as described in 7.1.6.4.

You provide a trailing-return-type, that is the ->int in your code, so no type deduction has to happen. The return type is just int.

However, even without the ->int, you can still get your function to compile if you just provided a if statement instead of using the conditional operator:

auto f = [](auto& f0, auto&& a) {
    if (a <= 1) {
        return 1; // this *must* be the first return case.
    }
    else {
        return f0(f0, a-1) * a;
    }
};

std::cout << f(f, 5) << std::endl; // prints 120

This case, and only this case, fits one of the rules as above mentioned in §7.1.6.4 [dcl.spec.auto]:

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 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 ]