Lambda volviendo a sí mismo: ¿es esto legal?

Editar: Parece haber cierta controversia sobre si esta construcción es estrictamente válida según la especificación de C++. La opinión predominante parece ser que no es válida. Vea las otras respuestas para una discusión más completa. El resto de esta respuesta se aplica si la construcción es válida; el código ajustado a continuación funciona con MSVC++ y gcc, y el OP ha publicado código modificado adicional que también funciona con clang.

Esto no está definido comportamiento, porque la lambda interna captura el parámetro self por referencia, pero self sale del ámbito después de la return en la línea 7. Por lo tanto, cuando la lambda devuelta se ejecuta más tarde, está accediendo a una referencia a una variable que ha salido del ámbito.

#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
}

Ejecutar el programa con valgrind ilustra esto:

==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.

En su lugar, puede cambiar la lambda externa para tomar auto por referencia en lugar de por valor, evitando así un montón de copias innecesarias y también resolviendo la problema:

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

Esto funciona:

==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 es correcto.

Parece que la sección del estándar que hace que este mal formado es [dcl.spec.auto]p9 :

Si el nombre de una entidad con un tipo de marcador de posición sineducar aparece en una expresión, el programa es mal formado. Una vez que se ha visto una sentencia return no descartada en una función, sin embargo, el tipo return deducido de esa declaración se puede utilizar en el resto de la función, incluyendo en otro retorno instrucción. [ Ejemplo:

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
}

- ejemplo final ]

Trabajo original a través de

Si nos fijamos en la propuesta Una Propuesta para Agregar Y Combinator a la Biblioteca Estándar proporciona una solución de trabajo:

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

Y dice explícitamente que su ejemplo no es posible:

C++11/14 las lambdas no fomentan la recursividad: no hay forma de hacer referencia al objeto lambda desde el cuerpo de la función lambda.

Y referencias una discusión en la que Richard Smith alude al error que clang te está dando :

Creo que esto sería mejor como una característica de lenguaje de primera clase. Me quedé sin tiempo para la reunión de pre-Kona, pero tenía la intención de escribir un documento para permitir que se le diera un nombre a una lambda (con alcance a su propio cuerpo):

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

Aquí, ' fib ' es el equivalente de la lambda * this (con algunas reglas especiales molestas para permitir que esto funcione a pesar del cierre de la lambda tipo incompleto).

Barry me señaló la propuesta de seguimiento lambdas recursiva que explica por qué esto no es posible y funciona alrededor de la restricción dcl.spec.auto#9 y también muestra métodos para lograr esto hoy sin ella:

Las lambdas son una herramienta útil para refactorizar código local. Sin embargo, a veces queremos usar la lambda desde dentro, ya sea para permitir la recursión directa o para permitir que el cierre se registre como una continuación. Este es sorprendentemente difícil de lograr bien en C++actual.

Ejemplo:

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

}

Un intento natural de hacer referencia a una lambda de sí mismo es almacenarla en una variable y capturar esa variable por referencia:

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

Sin embargo, esto no es posible debido a una circularidad semántica: el tipo de la variable automática no se deduce hasta después de que se procesa la expresión lambda, lo que significa que la expresión lambda no puede haga referencia a la variable.

Otro enfoque natural es usar una función std:::

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

Este enfoque compila, pero típicamente introduce una penalización de abstracción: la función std::puede incurrir en una asignación de memoria y la invocación de la lambda típicamente requerirá una llamada indirecta.

Para una solución de sobrecarga cero, a menudo no hay mejor enfoque que definir explícitamente un tipo de clase local.

Parece que Clang tiene razón. Considere un ejemplo simplificado:

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

Vamos a ir a través de él como un compilador (un poco):

• El tipo de it es Lambda1 con un operador de llamada de plantilla.
• it(it); activa la instanciación del operador de llamada
• El tipo de retorno del operador de llamada de plantilla es auto, por lo que debemos deducirlo.
• Estamos devolviendo una lambda capturando el primer parámetro de tipo Lambda1.
• Que lambda tiene un operador de llamada también que devuelve el tipo de invocación self(self)
• Aviso: self(self) es exactamente con lo que empezamos!

Como tal, el tipo no se puede deducir.

Bueno, tu código no funciona. Pero esto sí:

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

Código de prueba:

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

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

Su código es UB y mal formado no requiere diagnóstico. Lo cual es gracioso; pero ambos se pueden arreglar de forma independiente.

Primero, la UB:

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

Esto es UB porque outer toma self por valor, luego inner captura self por referencia, luego procede a devolverlo después de que outer termine de ejecutarse. Así que segfaulting está definitivamente bien.

El fix:

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

El código permanece está mal formado. Para ver esto podemos expandir las 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);

Esto crea una instancia __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;
};

Así que a continuación tenemos que determinar el tipo de retorno de __outer_lambda__::operator().

Vamos a través de él línea por línea. Primero creamos __inner_lambda__ tipo:

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

Ahora, mira allí-su tipo de retorno es self(self), o __outer_lambda__(__outer_lambda__ const&). Pero estamos en medio de tratar de deducir el tipo de retorno de __outer_lambda__::operator()(__outer_lambda__).

No se le permite hacer que.

Mientras que en realidad el tipo de retorno de __outer_lambda__::operator()(__outer_lambda__) no depende del tipo de retorno de __inner_lambda__::operator()(int), a C++ no le importa cuando se deducen tipos de retorno; simplemente comprueba el código línea por línea.

Y self(self) se usa antes de deducirlo. Programa mal formado.

Podemos arreglar esto ocultando self(self) hasta más tarde:

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

Y ahora el código es correcto y compila. Pero creo que esto es un poco de truco; simplemente use el ycombinator.

Es bastante fácil reescribir el código, en términos de las clases que un compilador, o más bien, generar las expresiones lambda.

Cuando eso está hecho, está claro que el problema principal es solo la referencia colgando, y que un compilador que no acepta el código es algo desafiado en el departamento lambda.

La reescritura muestra que no hay dependencias circulares.

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

Una versión totalmente templada para reflejar la forma en que la lambda interna en el código original, captura un elemento de tipo plantilla:

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

Supongo que es esta plantilla en la maquinaria interna, que las reglas formales están diseñadas para prohibir. Si prohíben la construcción original.