sintaxis - Funciones lambda recursivas en C++ 14

recursividad programacion ats

Question

Hay un "truco" muy repetido para escribir funciones lambda recursivas en C ++ 11 que dice lo 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 )

Sin embargo, esta técnica tiene dos inconvenientes inmediatos: el objetivo del objeto std::function<Sig> está vinculado (mediante la captura por referencia) a un objeto std::function<Sig> muy particular (aquí, factorial ). Esto significa que el functor resultante normalmente no puede devolverse desde una función, de lo contrario, la referencia quedaría colgando.

Otro problema (aunque menos inmediato) es que el uso de std::function normalmente evitará las optimizaciones del compilador, un efecto secundario de la necesidad de borrado de tipo en su implementación. Esto no es hipotético y puede ser probado fácilmente.

En la situación hipotética donde las expresiones recursivas de lambda serían realmente convenientes, ¿hay alguna manera de abordar esos problemas?

Answer 1

El quid de la cuestión es que en una expresión lambda C ++ el parámetro implícito siempre se referirá al objeto del contexto adjunto de la expresión, si está presente, y no al objeto funtor resultante de la expresión lambda.

Tomando prestada una hoja de la recursión anónima (a veces también conocida como "recursión abierta"), podemos usar las expresiones lambda genéricas de C ++ 14 para volver a introducir un parámetro explícito para referirnos a nuestro functor recursivo potencial:

auto f = [](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(/* hold on */); };

La persona que llama ahora tiene una nueva carga de hacer llamadas de la forma p. Ej. f(f, 5) . Dado que nuestra expresión lambda es autorreferencial, de hecho es una persona que llama y por lo tanto deberíamos tener un return n < 2 ? 1 : n * self(self, n - 1); return n < 2 ? 1 : n * self(self, n - 1); .

Dado que el patrón de pasar explícitamente el objeto functor en sí mismo en la primera posición es predecible, podemos refactorizar esta fea 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 le permite a uno escribir:

auto factorial = fix([](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(self, n - 1); });

assert( factorial(5) == 120 );

¿Tuvimos éxito? Dado que el objeto fix_type<F> contiene su propio functor que le pasa para cada llamada, nunca existe el riesgo de una referencia colgante. Por lo tanto, nuestro objeto factorial puede ser realmente copiado sin fin, movido desde, dentro y fuera de las funciones sin problemas.

Excepto ... mientras que los llamadores "externos" pueden hacer fácilmente llamadas de la forma factorial(5) , como resulta dentro de nuestra expresión lambda, la llamada recursiva todavía se parece a self(self, /* actual interesting args */) . Podemos mejorar esto cambiando fix_type para no pasar el functor a sí mismo, pero pasando *this en *this 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 debería ser.

Finalmente, este es el código generado para un main que usa return factorial(5); en lugar de la afirmación (para cualquier sabor 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 pudo optimizar todo, como lo hubiera hecho con una función recursiva run-off-the-mill.

¿Cuáles 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 devolución explícita (es decir, -> int ). ¿Cómo?

Esto tiene que ver con el hecho de que el tipo de retorno que se deduce es el tipo de expresión condicional, que depende de la llamada a self , qué tipo se deduce. Una lectura rápida de la deducción del tipo de devolución para las funciones normales sugeriría que la reescritura de la expresión lambda de la siguiente manera 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 el functor ). No puedo determinar si es correcto quejarse sobre el otro formulario (donde *this se aprueba). Dejo que el lector elija qué compromiso hacer: menos deducción de tipo, o llamadas recursivas menos feas (también es posible tener acceso a cualquiera de los sabores).

GCC 4.9 ejemplos

• Código completo, primer sabor
• Código completo, segundo sabor
• Código completo, primer sabor, C ++ 11
• Un ejemplo de una fix variadica para un grupo de expresiones lambda mutuamente recursivas

Answer 2

No es una expresión lambda, pero apenas más código, funciona con C ++ 98 y puede recurse:

struct {
    int operator()(int n) const {
        return n < 2 ? 1 : n * (*this)(n-1);
    }
} fact;
return fact(5);

Según [class.local]/1 , tiene acceso a todos los nombres a los que tiene acceso la función [class.local]/1 , que es importante para los nombres privados en una función de miembro.

Por supuesto, al no ser un lambda, debe escribir un constructor si desea capturar el estado fuera del objeto de función.