Lambda regresa: ¿es esto legal?

124

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 .

norte. 'pronombres' m.
fuente
2
Clang parece más decente en este momento, me pregunto si tal construcción puede incluso escribir, más probablemente termine en un árbol infinito.
bipll
2
Su pregunta si es legal y dice que esta es una pregunta de un abogado de idiomas, pero varias de las respuestas realmente no toman ese enfoque ... es importante tener las etiquetas correctas
Shafik Yaghmour
2
@ShafikYaghmour Gracias, agregué una etiqueta
n. 'pronombres' m.
1
@ArneVogel sí, la versión actualizada utiliza, lo auto& selfque elimina el problema de referencia pendiente.
n. 'pronombres' m.
1
@TheGreatDuck las lambdas de C ++ no son realmente expresiones lambda teóricas. C ++ tiene tipos recursivos incorporados que el cálculo lambda tipado simple original no puede expresar, por lo que puede tener cosas isomorfas a: a-> ay otras construcciones imposibles.
n. 'pronombres' m.

Respuestas:

68

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;
});
Barry
fuente
¿Cómo especificaría el tipo de retorno explícitamente? No puedo resolverlo.
Rakete1111
@ Rakete1111 ¿Cuál? En el original, no puedes.
Barry
oh ok No soy nativo, pero "así que tienes que proporcionar explícitamente un tipo de devolución" parece implicar que hay una manera, por eso estaba preguntando :)
Rakete1111
44
@PedroA stackoverflow.com/users/2756719/tc es un colaborador de C ++. También es o no una IA, o los recursos suficientes para convencer a un ser humano que también es conocedor de C ++ para asistir a la reciente GDP mini-reunión en Chicago.
Casey
3
@Casey O tal vez el humano solo está repitiendo lo que la IA le dijo ... nunca se sabe;)
TC
34

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
TypeIA
fuente
No estoy familiarizado con las lambdas genéricas, pero ¿no podrías hacer selfuna referencia?
François Andrieux
@ FrançoisAndrieux Sí, si hace selfuna referencia, este problema desaparece , pero Clang todavía lo rechaza por otra razón
Justin,
@ FrançoisAndrieux De hecho y lo he agregado a la respuesta, ¡gracias!
TypeIA
El problema con este enfoque es que no elimina posibles errores del compilador. Entonces, tal vez debería funcionar, pero la implementación está rota.
Shafik Yaghmour
¡Gracias, lo he visto durante horas y no vi que selfse haya capturado por referencia!
n. 'pronombres' m.
21

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.

Shafik Yaghmour
fuente
@ Cheersandhth.-Alf Terminé encontrando la cita estándar después de leer el documento, por lo que no es relevante ya que la cita estándar deja en claro por qué ninguno de los enfoques funciona
Shafik Yaghmour
"" 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, no veo una ocurrencia de esto en el programa. selfNo parece una entidad así.
n. 'pronombres' m.
@nm además de posibles liendres de redacción, los ejemplos parecen tener sentido con la redacción y creo que los ejemplos demuestran claramente el problema. No creo que pueda agregar más actualmente para ayudar.
Shafik Yaghmour
13

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.

Rakete1111
fuente
El tipo de retorno de Lambda1::operator()es simplemente Lambda2. Luego, dentro de esa expresión lambda interna , se sabe que el tipo de retorno de self(self), una llamada de Lambda1::operator(), también es Lambda2. Posiblemente las reglas formales se interponen en el camino de hacer esa deducción trivial, pero la lógica presentada aquí no lo hace. La lógica aquí solo equivale a una afirmación. Si las reglas formales se interponen en el camino, entonces eso es un defecto en las reglas formales.
Saludos y hth. - Alf
@ Cheersandhth.-Alf Estoy de acuerdo en que el tipo de retorno es Lambda2, pero usted sabe que no puede tener un operador de llamadas no reducido solo porque, porque esto es lo que está proponiendo: retrasar la deducción del tipo de retorno del operador de llamadas de Lambda2. Pero no puedes cambiar las reglas para esto, ya que es bastante fundamental.
Rakete1111
9

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.

Yakk - Adam Nevraumont
fuente
Posiblemente (IDK) esta descripción es correcta para las reglas formales sobre lambdas. Pero en términos de la reescritura de la plantilla, el tipo de retorno de la plantilla interna de lambda operator(), en general, no se puede deducir hasta que se instancia (al ser llamado con algún argumento de algún tipo). Y, por lo tanto, una reescritura manual similar a una máquina a un código basado en plantillas funciona bien.
Saludos y hth. - Alf
@cheers tu código es diferente; inner es una clase de plantilla en su código, pero no está en mi ni en el código OP. Y eso es importante, ya que los métodos de clase de plantilla se instancian con retraso hasta que se llama.
Yakk - Adam Nevraumont
Una clase definida dentro de una función con plantilla es equivalente a una clase con plantilla fuera de esa función. Definirlo fuera de la función es necesario para el código de demostración cuando tiene una función miembro con plantilla, porque las reglas de C ++ no permiten una plantilla miembro en una clase local definida por el usuario. Esa restricción formal no se cumple para lo que sea que el compilador genere.
Saludos y hth. - Alf
7

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.

Saludos y hth. - Alf
fuente
Mira, el problema es que esa template< class > class Inner;plantilla operator()es ... instanciada? Bueno, palabra equivocada. ¿Escrito? ... durante Outer::operator()<Outer>antes de deducir el tipo de retorno del operador externo. Y Inner<Outer>::operator()tiene un llamado a Outer::operator()<Outer>sí mismo. Y eso no está permitido. Ahora, la mayoría de los compiladores no notan el self(self)porque esperan para deducir el tipo de retorno de Outer::Inner<Outer>::operator()<int>para cuandoint se pasa en. Sensible. Pero echa de menos la mala forma del código.
Yakk - Adam Nevraumont
Bueno, creo que ellos deben esperar para deducir el tipo de retorno de la plantilla de función hasta que Innner<T>::operator()<U>se instancia esa plantilla de función . Después de todo, el tipo de retorno podría depender del Uaquí. No lo hace, pero en general.
Saludos y hth. - Alf
Por supuesto; pero cualquier expresión cuyo tipo esté determinado por una deducción de tipo de devolución incompleta sigue siendo ilegal. Solo algunos compiladores son vagos y no comprueban hasta más tarde, momento en el que todo funciona.
Yakk - Adam Nevraumont