Lambda returning itself: is this legal?

Question

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.

Solution 1

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

Solution 2

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

Solution 3

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.

Solution 4

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.

Solution 5

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.

View more solutions

Comments

[François Andrieux]

I'm not familiar with generic lambdas, but couldn't you make self a reference?

[Justin]

@FrançoisAndrieux Yes, if you make self a reference, this problem goes away, but Clang still rejects it for another reason

[TypeIA]

@FrançoisAndrieux Indeed and I've added that to the answer, thank you!

[Shafik Yaghmour]

The problem with this approach is that it does not eliminate possible compiler bugs. So maybe it should work but the implementation is broken.

[Cheers and hth. - Alf]

The return type of Lambda1::operator() is simply Lambda2. Then within that inner lambda expression the return type of self(self), a call of Lambda1::operator(), is known to also be Lambda2. Possibly the formal rules stand in the way of making that trivial deduction, but the logic presented here doesn't. The logic here just amounts to an assertion. If the formal rules do stand in the way, then that's a flaw in the formal rules.

[Rakete1111]

@Cheersandhth.-Alf I agree that the return type is Lambda2, but you do know that you can't have an undeduced call operator just because, because this is what you're proposing: Delay the deduction of Lambda2's call operator return type. But you can't change the rules for this, as it's pretty fundamental.

[Rakete1111]

How would you specify the return type explicitly? I can't figure it out.

[Barry]

@Rakete1111 Which one? In the original, you can't.

[Rakete1111]

oh ok. I'm not a native, but "so you have to explicitly provide a return type" seems to imply that there is a way, that's why I was asking :)

[Shafik Yaghmour]

@Cheersandhth.-Alf I ended up finding the standard quote after reading the paper so it is not relevant since the standard quote makes it clear why neither approach works

[Barry]

@Rakete1111 Oh yeah, that's misleading. I meant for the case where maybe you know what the return type is (e.g. you're writing recursive fibonacci, so you know it's int even though it depends on self)

[n. m.]

"If the name of an entity with an undeduced placeholder type appears in an expression, the program is ill-formed" I don't see an occurrence of this in the program.

[n. m.]

""If the name of an entity with an undeduced placeholder type appears in an expression, the program is ill-formed" I don't see an occurrence of this in the program though. self doesn't seem such an entity.

[Yakk - Adam Nevraumont]

See, the problem is that template< class > class Inner;'s template operator() is ...instantiated? Well, wrong word. Written? ... during Outer::operator()<Outer> before the return type of outer operator is deduced. And Inner<Outer>::operator() has a call to Outer::operator()<Outer> itself. And that isn't allowed. Now, most compilers don't notice the self(self) because they wait to deduce the return type of Outer::Inner<Outer>::operator()<int> for when int is passed in. Sensible. But it misses the ill formed ness of the code.

[n. m.]

Thank you, I've looked at this for hours and didn't see that self is captured by reference!

[Barry]

@n.m. Yeah... the wording should probably say "If an expression with an undeduced placeholder type" rather than "name of an entity," but this rule is intended to apply to cases like this (the example there is about functions with deduced placeholders, which is exactly this case - except instead of using a function like that by name, we're referring to it in a different way).

[n. m.]

It's hard to imagine how an expression with an undeduced placeholder type can avoid containing a name of an entity with an undeduced placeholder type. I don't see such an expression here either. clang doesn't complain about this, it complains about operator() of the lambda.

[Cheers and hth. - Alf]

Well I think they must wait to deduce the function template's return type until that function template, Innner<T>::operator()<U>, is instantiated. After all the return type could depend on the U here. It doesn't, but in general.

[Shafik Yaghmour]

@n.m. besides possible wording nits the examples seem to make sense with the wording and I believe the examples demonstrate the issue clearly. I don't think I could add more currently to help.

[Cheers and hth. - Alf]

Possibly (IDK) this description is correct for the formal rules about lambdas. But in terms of the template rewrite, the return type of the inner lambda's templated operator(), can't in general be deduced until it's instantiated (by being called with some argument of some type). And so a manual machine-like rewrite to template based code works nicely.

[Yakk - Adam Nevraumont]

sure; but any expression whose type is determined by an incomplete return type deduction remains illegal. Just some compilers are lazy and don't check until later, by which point everuthing works.

[Yakk - Adam Nevraumont]

@cheers your code is different; inner is a template class in your code, but it is not in my or the OP code. And that matters, as template class methods are delay instantiated until called.

[Barry]

@n.m. Does that addition help?

[Cheers and hth. - Alf]

A class defined within a templated function, is equivalent to a templated class outside that function. Defining it outside the function is necessary for the demo code when it has a templated member function, because the C++ rules don't permit a member template in a local user-defined class. That formal restriction doesn't hold for whatever the compiler generates itself.

[n. m.]

Yes, knowing which names are dependent seems to be the key here.

[Casey]

@PedroA stackoverflow.com/users/2756719/t-c is a C++ contributor. He is also either not an AI, or resourceful enough to convince a human who is also knowledgeable about C++ to attend the recent LWG mini-meeting in Chicago.

[T.C.]

@Casey Or maybe the human is just parroting what the AI told him...you never know ;)