Lambda returning itself: is this legal?
Consider this fairly useless program:
#include <iostream>
int main(int argc, char* argv[]) {
int a = 5;
auto it = [&](auto self) {
return [&](auto b) {
std::cout << (a + b) << std::endl;
return self(self);
};
};
it(it)(4)(6)(42)(77)(999);
}
Basically we are trying to make a lambda that returns itself.
- MSVC compiles the program, and it runs
- gcc compiles the program, and it segfaults
- clang rejects the program with a message:
error: function 'operator()<(lambda at lam.cpp:6:13)>' with deduced return type cannot be used before it is defined
Which compiler is right? Is there a static constraint violation, UB, or neither?
Update this slight modification is accepted by clang:
auto it = [&](auto& self, auto b) {
std::cout << (a + b) << std::endl;
return [&](auto p) { return self(self,p); };
};
it(it,4)(6)(42)(77)(999);
Update 2: I understand how to write a functor that returns itself, or how to use the Y combinator, to achieve this. This is more a language-lawyer question.
Update 3: the question is not whether it is legal for a lambda to return itself in general, but about the legality of this specific way of doing this.
Related question: C++ lambda returning itself.
Answer
The program is ill-formed (clang is right) per [dcl.spec.auto]/9:
If the name of an entity with an undeduced placeholder type appears in an expression, the program is ill-formed. Once a non-discarded 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.
Basically, the deduction of the return type of the inner lambda depends on itself (the entity being named here is the call operator) - so you have to explicitly provide a return type. In this particular case, that's impossible, because you need the type of the inner lambda but can't name it. But there are other cases where trying to force recursive lambdas like this, that can work.
Even without that, you have a dangling reference.
Let me elaborate some more, after discussing with somebody much smarter (i.e. T.C.) There is an important difference between the original code (slightly reduced) and the proposed new version (likewise reduced):
auto f1 = [&](auto& self) {
return [&](auto) { return self(self); } /* #1 */ ; /* #2 */
};
f1(f1)(0);
auto f2 = [&](auto& self, auto) {
return [&](auto p) { return self(self,p); };
};
f2(f2, 0);
And that is that the inner expression self(self) is not dependent for f1, but self(self, p) is dependent for f2. When expressions are non-dependent, they can be used... eagerly ([temp.res]/8, e.g. how static_assert(false) is a hard error regardless of whether the template it finds itself in is instantiated or not).
For f1, a compiler (like, say, clang) can try to instantiate this eagerly. You know the deduced type of of the outer lambda once you get to that ; at point #2 above (it's the inner lambda's type), but we're trying to use it earlier than that (think of it as at point #1) - we're trying to use it while we're still parsing the inner lambda, before we know what it's type actually is. That runs afoul of dcl.spec.auto/9.
However, for f2, we cannot try to instantiate eagerly, because it's dependent. We can only instantiate at point of use, by which point we know everything.
In order to really do something like this, you need a y-combinator. The implementation from the paper:
template<class Fun> class y_combinator_result { Fun fun_; public: template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {} template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
And what you want is:
auto it = y_combinator([&](auto self, auto b){
std::cout << (a + b) << std::endl;
return self;
});