mjhjmtu

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__ ita;
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.