Lambda returning itself: is this legal?

Question

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

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

TL;DR;

clang is correct.

It looks like the section of the standard that makes this ill-formed is [dcl.spec.auto]p9:

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. [ Example:

auto n = n; // error, n’s initializer refers to n
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 ]

Original work through

If we look at the proposal A Proposal to Add Y Combinator to the Standard Library it provides a working solution:

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 it explicitly says your example is not possible:

C++11/14 lambdas do not encourage recursion: there is no way to reference the lambda object from the body of the lambda function.

and it references a dicussion in which Richard Smith alludes to the error that clang is giving you:

I think this would be better as a first-class language feature. I ran out of time for the pre-Kona meeting, but I was intending on writing a paper to allow giving a lambda a name (scoped to its own body):

auto x = []fib(int a) { return a > 1 ? fib(a - 1) + fib(a - 2) : a; };

Here, 'fib' is the equivalent of the lambda's *this (with some annoying special rules to allow this to work despite the lambda's closure type being incomplete).

Barry pointed me to the follow-up proposal Recursive lambdas which explains why this is not possible and works around the dcl.spec.auto#9 restriction and also shows methods to achieve this today without it:

Lambdas are a useful tool for local code refactoring. However, we sometimes want to use the lambda from within itself, either to permit direct recursion or to allow the closure to be registered as a continuation. This is surprisingly difficult to accomplish well in current C++.

Example:

  void read(Socket sock, OutputBuffer buff) {
  sock.readsome([&] (Data data) {
  buff.append(data);
  sock.readsome(/*current lambda*/);
}).get();

}

One natural attempt to reference a lambda from itself is to store it in a variable and capture that variable by reference:

 auto on_read = [&] (Data data) {
  buff.append(data);
  sock.readsome(on_read);
};

However, this is not possible due to a semantic circularity: the type of the auto variable is not deduced until after the lambda-expression is processed, which means the lambda-expression cannot reference the variable.

Another natural approach is to use a std::function:

 std::function on_read = [&] (Data data) {
  buff.append(data);
  sock.readsome(on_read);
};

This approach compiles, but typically introduces an abstraction penalty: the std::function may incur a memory allocation and the invocation of the lambda will typically require an indirect call.

For a zero-overhead solution, there is often no better approach than defining a local class type explicitly.

It seems like clang is right. Consider a simplified example:

auto it = [](auto& self) {
    return [&self]() {
      return self(self);
    };
};
it(it);

Let's go through it like a compiler (a bit):

• The type of it is Lambda1 with a template call operator.
• it(it); triggers instantiation of the call operator
• The return type of the template call operator is auto, so we must deduce it.
• We are returning a lambda capturing the first parameter of type Lambda1.
• That lambda has a call operator too which returns the type of the invocation self(self)
• Notice: self(self) is exactly what we started with!

As such, the type cannot be deduced.

Well, your code doesn't work. But this does:

template<class F>
struct ycombinator {
  F f;
  template<class...Args>
  auto operator()(Args&&...args){
    return f(f, std::forward<Args>(args)...);
  }
};
template<class F>
ycombinator(F) -> ycombinator<F>;

Test code:

ycombinator bob = {[x=0](auto&& self)mutable{
  std::cout << ++x << "\n";
  ycombinator ret = {self};
  return ret;
}};

bob()()(); // prints 1 2 3

---

Your code is both UB and ill-formed no diagnostic required. Which is funny; but both can be fixed independently.

First, the UB:

auto it = [&](auto self) { // outer
  return [&](auto b) { // inner
    std::cout << (a + b) << std::endl;
    return self(self);
  };
};
it(it)(4)(5)(6);

this is UB because outer takes self by value, then inner captures self by reference, then proceeds to return it after outer finishes running. So segfaulting is definitely ok.

The fix:

[&](auto self) {
  return [self,&a](auto b) {
    std::cout << (a + b) << std::endl;
    return self(self);
  };
};

---

The code remains is ill-formed. To see this we can expand the lambdas:

struct __outer_lambda__ {
  template<class T>
  auto operator()(T self) const {
    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      T self;
    };
    return __inner_lambda__{a, self};
  }
  int& a;
};
__outer_lambda__ it{a};
it(it);

this instantiates __outer_lambda__::operator()<__outer_lambda__>:

  template<>
  auto __outer_lambda__::operator()(__outer_lambda__ self) const {
    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      __outer_lambda__ self;
    };
    return __inner_lambda__{a, self};
  }
  int& a;
};

So we next have to determine the return type of __outer_lambda__::operator().

We go through it line by line. First we create __inner_lambda__ type:

    struct __inner_lambda__ {
      template<class B>
      auto operator()(B b) const {
        std::cout << (a + b) << std::endl;
        return self(self);
      }
      int& a;
      __outer_lambda__ self;
    };

Now, look there -- its return type is self(self), or __outer_lambda__(__outer_lambda__ const&). But we are in the middle of trying to deduce the return type of __outer_lambda__::operator()(__outer_lambda__).

You aren't allowed to do that.

While in fact the return type of __outer_lambda__::operator()(__outer_lambda__) is not actually dependent on the return type of __inner_lambda__::operator()(int), C++ doesn't care when deducing return types; it simply checks the code line by line.

And self(self) is used before we deduced it. Ill formed program.

We can patch this by hiding self(self) until later:

template<class A, class B>
struct second_type_helper { using result=B; };

template<class A, class B>
using second_type = typename second_type_helper<A,B>::result;

int main(int argc, char* argv[]) {

  int a = 5;

  auto it = [&](auto self) {
      return [self,&a](auto b) {
        std::cout << (a + b) << std::endl;
        return self(second_type<decltype(b), decltype(self)&>(self) );
      };
  };
  it(it)(4)(6)(42)(77)(999);
}

and now the code is correct and compiles. But I think this is a bit of hack; just use the ycombinator.

It's easy enough to rewrite the code in terms of the classes that a compiler would, or rather should, generate for the lambda expressions.

When that's done it's clear that the main problem is just the dangling reference, and that a compiler that doesn't accept the code is somewhat challenged in the lambda department.

The rewrite shows that there are no circular dependencies.

#include <iostream>

struct Outer
{
    int& a;

    // Actually a templated argument, but always called with `Outer`.
    template< class Arg >
    auto operator()( Arg& self ) const
        //-> Inner
    {
        return Inner( a, self );    //! Original code has dangling ref here.
    }

    struct Inner
    {
        int& a;
        Outer& self;

        // Actually a templated argument, but always called with `int`.
        template< class Arg >
        auto operator()( Arg b ) const
            //-> Inner
        {
            std::cout << (a + b) << std::endl;
            return self( self );
        }

        Inner( int& an_a, Outer& a_self ): a( an_a ), self( a_self ) {}
    };

    Outer( int& ref ): a( ref ) {}
};

int main() {

  int a = 5;

  auto&& it = Outer( a );
  it(it)(4)(6)(42)(77)(999);
}

---

A fully templated version to reflect the way that the inner lambda in the original code, captures an item that's of a templated type:

#include <iostream>

struct Outer
{
    int& a;

    template< class > class Inner;

    // Actually a templated argument, but always called with `Outer`.
    template< class Arg >
    auto operator()( Arg& self ) const
        //-> Inner
    {
        return Inner<Arg>( a, self );    //! Original code has dangling ref here.
    }

    template< class Self >
    struct Inner
    {
        int& a;
        Self& self;

        // Actually a templated argument, but always called with `int`.
        template< class Arg >
        auto operator()( Arg b ) const
            //-> Inner
        {
            std::cout << (a + b) << std::endl;
            return self( self );
        }

        Inner( int& an_a, Self& a_self ): a( an_a ), self( a_self ) {}
    };

    Outer( int& ref ): a( ref ) {}
};

int main() {

  int a = 5;

  auto&& it = Outer( a );
  it(it)(4)(6)(42)(77)(999);
}

I guess that it's this templating in the internal machinery, that the formal rules are designed to forbid. If they do forbid the original construct.