c++ - examples - Lambda devolviéndose: ¿es esto legal?
lambda examples c++ (6)
Considera 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 un lambda que se devuelva a sí mismo.
- MSVC compila el programa, y se ejecuta
- gcc compila el programa, y segfaults
-
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 tiene razón? ¿Existe una violación de restricción estática, UB, o ninguna?
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 a sí mismo, o cómo usar el combinador de Y para lograr esto. Esto es más una pregunta de lenguaje-abogado.
Actualización 3 : la pregunta no es si es legal que un lambda se devuelva en general, sino sobre la legalidad de esta forma específica de hacer esto.
Pregunta relacionada: C ++ lambda devolviéndose .
TL; DR;
clang es correcto
Parece que la sección de la norma que hace que esta formada de forma [dcl.spec.auto]/9 sea [dcl.spec.auto]/9 :
Si el nombre de una entidad con un tipo de marcador de posición sin detalles 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 utilizar 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 }—En ejemplo]
Obra original a través de
Si observamos la propuesta y-combinator , 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 fomenta la recursión: 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 se le está produciendo :
Creo que esto sería mejor como una característica de lenguaje de primera clase. Me quedé sin tiempo para la reunión previa a Kona, pero tenía la intención de escribir un documento para permitir darle un nombre a la 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 * esto (con algunas reglas especiales molestas para permitir que esto funcione a pesar de que el tipo de cierre de la lambda está incompleto).
Barry me señaló la propuesta de seguimiento de
lambdas recursivas,
que explica por qué esto no es posible y funciona en torno a la restricción
dcl.spec.auto#9
y también muestra métodos para lograrlo hoy sin ella:
Las Lambdas son una herramienta útil para la refactorización de códigos locales. Sin embargo, a veces queremos usar la lambda desde dentro, ya sea para permitir una 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 desde 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 después de 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 de abstracción: la función std :: puede incurrir en una asignación de memoria y la invocación de la lambda normalmente requerirá una llamada indirecta.
Para una solución de sobrecarga cero, a menudo no hay un mejor enfoque que definir explícitamente un tipo de clase local.
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. Que es gracioso; Pero ambos pueden ser arreglados independientemente.
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 external toma
self
por valor, luego se captura interior
self
por referencia, luego procede a devolverlo después de que se ejecuta el
outer
.
Así que segfaulting está definitivamente bien.
La solución:
[&](auto self) {
return [self,&a](auto b) {
std::cout << (a + b) << std::endl;
return self(self);
};
};
El código que queda está mal formado. Para ver esto podemos ampliar 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
__outer_lambda__::operator()<__outer_lambda__>
instancia de
__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 tenemos que determinar el tipo de retorno de
__outer_lambda__::operator()
.
Lo atravesamos 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 medio de intentar deducir el tipo de retorno de
__outer_lambda__::operator()(__outer_lambda__)
.
No se te permite hacer eso.
Mientras que en realidad el tipo de retorno de
__outer_lambda__::operator()(__outer_lambda__)
no es realmente dependiente del tipo de retorno de
__inner_lambda__::operator()(int)
, a C ++ no le importa al deducir los tipos de retorno;
simplemente verifica el código línea por línea.
Y el
self(self)
se usa antes de que lo deduzcamos.
Programa mal formado.
Podemos parchear esto ocultando el
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 hack; solo usa el ycombinator.
El programa está mal formado (clang is right) según [dcl.spec.auto]/9 :
Si el nombre de una entidad con un tipo de marcador de posición sin detalles 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 utilizar en el resto de la función, incluso en otras declaraciones de devolución.
Básicamente, la deducción del tipo de devolución del lambda interno depende de sí misma (la entidad que se nombra aquí es el operador de la llamada), por lo que debe proporcionar explícitamente un tipo de devolución. En este caso particular, eso es imposible, porque necesita el tipo de lambda interna 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 colgando .
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 (también reducido):
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
, pero
self(self, p)
es dependiente de
f2
.
Cuando las expresiones no son dependientes, se pueden usar ... con entusiasmo (
[temp.res]/8
, por ejemplo,
static_assert(false)
es un error
static_assert(false)
independientemente de si la plantilla en la que se encuentra está instanciada o no).
Para
f1
, un compilador (como, por ejemplo, clang) puede intentar crear una instancia de esto con entusiasmo.
Usted sabe el tipo deducido de la lambda exterior una vez que llegue a eso
;
en el punto
#2
anterior (es el tipo de lambda interna), pero estamos tratando de usarlo antes que eso (piense en él como en el punto
#1
) - estamos tratando de usarlo mientras aún estamos analizando el interior lambda, antes de que sepamos lo que realmente es su tipo.
Eso va en contra de dcl.spec.auto/9.
Sin embargo, para
f2
, no podemos intentar crear instancias con entusiasmo, porque es dependiente.
Solo podemos crear una instancia en el punto de uso, por lo que sabemos todo.
Para realmente hacer algo como esto, necesitas un y-combinator . La implementación desde el papel:
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;
});
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.
Cuando se hace eso, queda claro que el problema principal es solo la referencia, 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 con plantilla para reflejar la forma en que la lambda interna en el código original captura un elemento de tipo con 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.
Parece que Clang tiene razón. 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
itesLambda1con un operador de llamada de plantilla. -
it(it);activa la instanciación del operador de llamada -
El tipo de devolución 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 la invocación
self(self) -
Aviso:
self(self)es exactamente con lo que empezamos!
Como tal, el tipo no puede ser deducido.
Edición : 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 siguiente código ajustado funciona con MSVC ++ y gcc, y el OP ha publicado un código modificado adicional que también funciona con clang.
Este es un comportamiento indefinido, porque el lambda interno captura el parámetro
self
por referencia, pero el
self
sale fuera del alcance después del
return
en la línea 7. Por lo tanto, cuando el lambda devuelto se ejecuta más tarde, accede a una referencia a una variable que se ha ido de 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
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 el lambda externo para que se tome a sí mismo por referencia en lugar de por valor, evitando así un montón de copias innecesarias y 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