Funciones lambda recursivas en C++14
Hay un 'truco' a menudo repetido para escribir funciones lambda recursivas en C++11 que es el siguiente:
std::function<int(int)> factorial;
factorial = [&factorial](int n)
{ return n < 2 ? 1 : n * factorial(n - 1); };
assert( factorial(5) == 120 );
(por ejemplo, Funciones lambda recursivas en C++0x.)
Esta técnica tiene dos inconvenientes inmediatos: el objetivo del objeto std::function<Sig> está vinculado (a través de la captura por referencia) a un objeto std::function<Sig> muy particular (aquí, factorial). Esto significa que el funtor resultante normalmente no se puede devolver desde una función, o de lo contrario la referencia se dejaría colgar.
Otro problema (aunque menos inmediato) es que el uso de std::function normalmente va a evitar optimizaciones del compilador, un efecto secundario de la necesidad de borrar tipos en su implementación. Esto no es hipotético y se puede probar fácilmente.
En la situación hipotética donde las expresiones lambda recursivas serían realmente convenientes, ¿hay alguna manera de abordar esos problemas?
2 answers
El quid de la cuestión es que en una expresión lambda de C++ el implícito this el parámetro siempre se referirá al objeto del contexto que encierra la expresión, si está presente, y no al objeto funtor resultante de la expresión lambda.
Tomando prestada una hoja de recursión anónima (a veces también conocida como 'recursión abierta'), podemos usar las expresiones lambda genéricas de C++14 para reintroducir un parámetro explícito para referirnos a funtor recursivo potencial:
auto f = [](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(/* hold on */); };
El llamante ahora tiene una nueva carga de hacer llamadas del formulario, por ejemplo, f(f, 5). Dado que nuestra expresión lambda es autorreferencial, de hecho es un llamador de sí mismo y por lo tanto deberíamos tener return n < 2 ? 1 : n * self(self, n - 1);.
Dado que ese patrón de pasar explícitamente el objeto funtor en la primera posición es predecible, podemos refactorizar esta horrible verruga:
template<typename Functor>
struct fix_type {
Functor functor;
template<typename... Args>
decltype(auto) operator()(Args&&... args) const&
{ return functor(functor, std::forward<Args>(args)...); }
/* other cv- and ref-qualified overloads of operator() omitted for brevity */
};
template<typename Functor>
fix_type<typename std::decay<Functor>::type> fix(Functor&& functor)
{ return { std::forward<Functor>(functor) }; }
Esto permite escribir:
auto factorial = fix([](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(self, n - 1); });
assert( factorial(5) == 120 );
Tuvimos éxito? Desde el objeto fix_type<F> contiene su propio funtor que le pasa para cada llamada, nunca hay un riesgo de una referencia colgando. Por lo tanto, nuestro objeto factorial puede ser copiado sin fin, movido desde, dentro y fuera de funciones sin problemas.
Excepto... mientras que los llamantes 'externos' pueden fácilmente hacer llamadas de la forma factorial(5), como resulta dentro de nuestra expresión lambda, la llamada recursiva todavía se ve como self(self, /* actual interesting args */). Podemos mejorar esto cambiando fix_type para no pasar functor a sí mismo, sino pasando *this en su lugar. Es decir, pasamos el objeto fix_type que se encarga de pasar el argumento correcto 'implícito como explícito' en la primera posición: return functor(*this, std::forward<Args>(args)...);. Entonces la recursión se convierte en n * self(n - 1), como debe ser.
Finalmente, este es el código generado para un main que usa return factorial(5); en lugar de la afirmación (para cualquiera de los sabores de fix_type):
00000000004005e0 <main>:
4005e0: b8 78 00 00 00 mov eax,0x78
4005e5: c3 ret
4005e6: 66 90 xchg ax,ax
El compilador fue capaz de optimizar todo, como lo habría hecho con una función recursiva de run-off-the-mill.
¿Qué son los costos?
El lector astuto puede haber notado un detalle curioso. En el paso de una lambda no genérica a una lambda genérica, agregué un tipo de retorno explícito (es decir, -> int). ¿Por qué?
Esto tiene que ver con el hecho de que el tipo de retorno que se deduce es el tipo de la expresión condicional, que tipo depende de la llamada a self, el tipo se deduce. Una lectura rápida de Deducción de tipo de retorno para funciones normales sugeriría que reescribir la lambda la expresión como sigue debería funcionar:
[](auto&& self, int n)
{
if(n < 2) return 1; // return type is deduced here
else return n * self(/* args */); // this has no impact
}
GCC de hecho aceptará este código con la primera forma de fix_type solamente (la que pasa functor). No puedo determinar si es correcto quejarme sobre el otro formulario (donde *this se pasa). Dejo que el lector elija qué compensación hacer: menos deducción de tipo, o llamadas recursivas menos feas (también es completamente posible tener acceso a cualquiera de los sabores de todos modos).
CCG 4.9 ejemplos
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-08-19 06:11:14
No es una expresión lambda, pero apenas más código, funciona con C++98, y puede recurrir:
struct {
int operator()(int n) const {
return n < 2 ? 1 : n * (*this)(n-1);
}
} fact;
return fact(5);
De acuerdo con [class.local]/1, tiene acceso a todos los nombres a los que tiene acceso la función que encierra, lo cual es importante para los nombres privados en una función miembro.
Por supuesto, al no ser una lambda, debe escribir un constructor si desea capturar el estado fuera del objeto de la función.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-03-26 12:48:24