Lambda returning itself: is this legal?

lambda capture self
c lambda dfs
lambda inside lambda c

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.


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

Java Lambda Expressions Basics, . Here's an example. You can build a function in the normal way, using def, like this: 1. 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.


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

Anonymous function, lambda calculus (λ-calculus) A formalism for representing functions and ways of the function f with itself, i.e. the function that, for any argument x, returns f(f(x))​. Lambert's law The law stating that *diffusely reflected and transmitted light is  Clash Royale CLAN TAG #URR8PPP up vote 109 down vote favorite 20 Consider this fairly useless program: #include <iostream> int


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.

What Is Lambda Expression?, This agent first signals itself: then it is invoked with a function in the environment (​of say ar, then this a is returned to a as the answer to the initial invocation. 3) The following is the well-known witness of Peirce's law, ((A D B) D A) D A, and  I wanted to write a lambda that returns itself, so I could call it multiple times on the spot. But it looks like inside of a lambda this refers not to the lambda but to the surrounding object's this, if the lambda is defines inside a member function.


Yet Another Lambda Tutorial, lambda expression or method reference expression has no type in itself and so Double::toHexString; // Legal: In return context } 12 Statements A statement  Useful recursive lambdas (or just a lambda that needs to refer to itself, say, to place itself on an asynchronous queue) really requires a keyword or something so that the lambda can literally refer to itself.


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.

A Dictionary of Computer Science, Some examples of legal identifiers are as follows: abcABC123 A1D2C3 _1a2 objects are derived from the Python language description, just as Jython itself is class except continue exec m print is raise lambda return not try or while pass  Founded in 1973, Lambda Legal is the oldest and largest national legal organization whose mission is to achieve full recognition of the civil rights of lesbians, gay men, bisexuals, transgender people and everyone living with HIV through impact litigation, education and public policy work.


Rewriting and Typed Lambda Calculi: Joint International , There is also a companion document, State of the Lambda, Libraries Edition, describing because as Moore's Law continues to give us more cores but not faster cores, serial APIs The third takes a string and prints it to the console, returning nothing. and unqualified references to this always refer to the inner class itself. To help you deal with errors in Lambda applications, Lambda integrates with services like Amazon CloudWatch and AWS X-Ray. You can use a combination of logs, metrics, alarms, and tracing to quickly detect and identify issues in your function code, API, or other resources that support your application. For more information, see Monitoring


Java Precisely, Lambda expressions let you express instances of single-method classes more compactly. If the method tester.test returns a true value, then the method printPersons is invoked The operation itself is specified by an instance of IntegerMath . About Oracle | Contact Us | Legal Notices | Terms of Use | Your Privacy Rights. Ensure the safety of LGBTQ youth in homeless shelters and child welfare facilities. Given the number of LGBTQ youth cycling between the child welfare and shelter systems of care, it’s critically important that all shelters and child welfare facilities take immediate steps to ensure the safety of these young people.


Jython for Java Programmers, Today we're announcing AWS Lambda Destinations for code within your Lambda function and manage retries and failures yourself. Lambda Destinations tester, Success returns a json blob, Failure Contact Us · AWS Careers · File a Support Ticket · Knowledge Center · AWS Support Overview · Legal. This survey is the first to examine refusal of care and barriers to health care among LGBT and HIV communities on a national scale. We hope that these data will influence decisions being made about how health care is delivered in this country now and in the future. Download the Report. Table of Contents. Executive Summary.