Lambda regresa: ¿es esto legal?

Considere este programa bastante inútil:

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

Básicamente estamos tratando de hacer una lambda que regrese.

• MSVC compila el programa y se ejecuta
• gcc compila el programa, y ​​se daña por defecto
• clang rechaza el programa con un mensaje:

  error: function 'operator()<(lambda at lam.cpp:6:13)>' with deduced return type cannot be used before it is defined

¿Qué compilador es el correcto? ¿Existe una violación de restricción estática, UB o ninguna de las dos?

Actualizar esta ligera modificación es aceptada por 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);

Actualización 2 : entiendo cómo escribir un functor que se devuelve solo, o cómo usar el combinador Y, para lograr esto. Esta es más una pregunta de abogado de idiomas.

Actualización 3 : la pregunta no es si es legal que una lambda regrese en general, sino la legalidad de esta forma específica de hacerlo.

Pregunta relacionada: C ++ lambda regresando a sí mismo .

El programa está mal formado (clang es correcto) según [dcl.spec.auto] / 9 :

Si el nombre de una entidad con un tipo de marcador de posición no reducido aparece en una expresión, el programa está mal formado. Sin embargo, una vez que se ha visto una declaración de devolución no descartada en una función, el tipo de devolución deducido de esa declaración se puede usar en el resto de la función, incluso en otras declaraciones de devolución.

Básicamente, la deducción del tipo de retorno del lambda interno depende de sí misma (la entidad que se nombra aquí es el operador de llamada), por lo que debe proporcionar explícitamente un tipo de retorno. En este caso particular, eso es imposible, porque necesita el tipo de lambda interior pero no puede nombrarlo. Pero hay otros casos en los que intentar forzar lambdas recursivas como esta puede funcionar.

Incluso sin eso, tienes una referencia pendiente .

Permítanme elaborar un poco más, después de discutir con alguien mucho más inteligente (es decir, TC). Hay una diferencia importante entre el código original (ligeramente reducido) y la nueva versión propuesta (igualmente reducida):

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

Y es que la expresión interna self(self)no es dependiente de f1, sino que self(self, p)es dependiente de f2. Cuando las expresiones no son dependientes, se pueden usar ... con entusiasmo ( [temp.res] / 8 , p. Ej., ¿Cómo static_assert(false)es un error grave independientemente de si la plantilla en la que se encuentra está instanciada o no?).

Porque f1un compilador (como, por ejemplo, clang) puede intentar crear una instancia con entusiasmo. Usted sabe el tipo deducido de la lambda externa una vez que llega a eso ;en el punto #2anterior (es el tipo de la lambda interna), pero estamos tratando de usarlo antes que eso (piense en ello como en el punto #1): estamos tratando usarlo mientras todavía estamos analizando el lambda interno, antes de saber qué tipo es realmente. Eso va en contra de dcl.spec.auto/9.

Sin embargo, para f2, no podemos tratar de crear instancias con entusiasmo, porque depende. Solo podemos crear instancias en el punto de uso, momento en el cual sabemos todo.

Para realmente hacer algo como esto, necesitas un combinador y . La implementación del documento:

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 lo que quieres es:

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

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 modificado a continuación funciona con MSVC ++ y gcc, y el OP ha publicado más código modificado que también funciona con clang.

Este es un comportamiento indefinido, porque el lambda interno captura el parámetro selfpor referencia, pero selfsale del alcance después de la returnlínea 7. Por lo tanto, cuando el lambda devuelto se ejecuta más tarde, está accediendo a una referencia a una variable que se ha salido del alcance.

#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 valgrindilustra 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 el lambda externo para tomarlo por referencia en lugar de por valor, evitando así un montón de copias innecesarias y también resolviendo el 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 sea [dcl.spec.auto] p9 :

Si el nombre de una entidad con un tipo de marcador de posición no reducido aparece en una expresión, el programa está mal formado. Sin embargo, una vez que se ha visto una declaración de devolución no descartada en una función, el tipo de devolución deducido de esa declaración se puede usar en el resto de la función, incluso en otras declaraciones de devolució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]

Trabajo original a través de

Si miramos la propuesta Una propuesta para agregar un Combinador Y 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 tu ejemplo no es posible:

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

y hace referencia a una discusión en la que Richard Smith alude al error que te está dando el sonido metálico :

Creo que esto sería mejor como una función de lenguaje de primera clase. Se me acabó el tiempo para la reunión previa a Kona, pero tenía la intención de escribir un documento que permitiera darle un nombre a una lambda (en su propio cuerpo):

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

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

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

Las lambdas son una herramienta útil para la refactorización de código local. Sin embargo, a veces queremos usar el lambda desde dentro de sí mismo, ya sea para permitir la recursión directa o para permitir que el cierre se registre como una continuación. Esto 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 un lambda de sí mismo es almacenarlo 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 que se procesa la expresión lambda, lo que significa que la expresión lambda no puede hacer 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 generalmente introduce una penalización por abstracción: la función std :: puede incurrir en una asignación de memoria y la invocación de la lambda generalmente requerirá una llamada indirecta.

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

Parece que el sonido metálico es correcto. Considere un ejemplo simplificado:

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

Vamos a verlo como un compilador (un poco):

• El tipo de ites Lambda1con un operador de llamada de plantilla.
• it(it); desencadena la creación de instancias 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 que captura el primer parámetro de tipo Lambda1.
• Esa lambda también tiene un operador de llamada que devuelve el tipo de invocación self(self)
• Aviso: ¡ self(self)es exactamente con lo que comenzamos!

Como tal, el tipo no puede deducirse.

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

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 está mal formado, no se 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 las tomas externas selfpor valor, luego las capturas internas selfpor referencia, luego proceden a devolverlo después de que outertermina de ejecutarse. Entonces segfaulting definitivamente está bien.

La solución:

[&](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 instancias __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;
};

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

Lo revisamos 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, mire allí: su tipo de retorno es self(self), o __outer_lambda__(__outer_lambda__ const&). Pero estamos en el medio de tratar de deducir el tipo de retorno de __outer_lambda__::operator()(__outer_lambda__).

No tienes permitido hacer eso.

Si bien, de hecho, el tipo de retorno de __outer_lambda__::operator()(__outer_lambda__)no depende realmente del tipo de retorno de __inner_lambda__::operator()(int), C ++ no le importa al deducir los tipos de retorno; simplemente verifica el código línea por línea.

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

Podemos parchear esto escondiéndonos 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 se compila. Pero creo que esto es un poco hack; solo usa el combinador.

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

Una vez hecho esto, está claro que el problema principal es solo la referencia colgante, y que un compilador que no acepta el código es algo desafiado en el departamento de 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 con plantilla para reflejar la forma en que la lambda interna del 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 ellos prohíben la construcción original.