Lambda returning itself: is this legal?

Edit: There seems to be some controversy over whether this construction is strictly valid per the C++ specification. Prevailing opinion seems to be that it is not valid. See the other answers for a more thorough discussion. The remainder of this answer applies if the construction is valid; the tweaked code below works with MSVC++ and gcc, and the OP has posted further modified code that works with clang also.

This is undefined behavior, because the inner lambda captures the parameter self by reference, but self goes out of scope after the return on line 7. Thus, when the returned lambda is executed later, it's accessing a reference to a variable that has gone out of scope.

#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); // <-- using reference to 'self'
      };
  };
  it(it)(4)(6)(42)(77)(999); // <-- 'self' is now out of scope
}

Running the program with valgrind illustrates this:

==5485== Memcheck, a memory error detector
==5485== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5485== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5485== Command: ./test
==5485== 
9
==5485== Use of uninitialised value of size 8
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485== 
==5485== Invalid read of size 4
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485==  Address 0x4fefffdc4 is not stack'd, malloc'd or (recently) free'd
==5485== 
==5485== 
==5485== Process terminating with default action of signal 11 (SIGSEGV)
==5485==  Access not within mapped region at address 0x4FEFFFDC4
==5485==    at 0x108A20: _ZZZ4mainENKUlT_E_clIS0_EEDaS_ENKUlS_E_clIiEEDaS_ (test.cpp:8)
==5485==    by 0x108AD8: main (test.cpp:12)
==5485==  If you believe this happened as a result of a stack
==5485==  overflow in your program's main thread (unlikely but
==5485==  possible), you can try to increase the size of the
==5485==  main thread stack using the --main-stacksize= flag.
==5485==  The main thread stack size used in this run was 8388608.

Instead you can change the outer lambda to take self by reference instead of by value, thus avoiding a bunch of unnecessary copies and also solving the problem:

#include <iostream>
int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto& self) { // <-- self is now a reference
      return [&](auto b) {
        std::cout << (a + b) << std::endl;
        return self(self);
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

This works:

==5492== Memcheck, a memory error detector
==5492== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5492== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5492== Command: ./test
==5492== 
9
11
47
82
1004

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;
});