¿Qué es la optimización de llamadas de cola?

Muy simple, ¿qué es la optimización de la cola de llamada? Más específicamente, ¿alguien puede mostrar algunos pequeños fragmentos de código donde podría aplicarse, y dónde no, con una explicación de por qué?

    La optimización de llamada de cola es donde puede evitar asignar un nuevo marco de stack para una función porque la función de llamada simplemente devolverá el valor que obtiene de la función llamada. El uso más común es recursividad de cola, donde una función recursiva escrita para aprovechar la optimización de la cola de llamada puede usar el espacio de stack constante.

    Scheme es uno de los pocos lenguajes de progtwigción que garantiza en la especificación que cualquier implementación debe proporcionar esta optimización (JavaScript también lo hace, comenzando con ES6) , así que aquí hay dos ejemplos de la función factorial en Scheme:

    (define (fact x) (if (= x 0) 1 (* x (fact (- x 1))))) (define (fact x) (define (fact-tail x accum) (if (= x 0) accum (fact-tail (- x 1) (* x accum)))) (fact-tail x 1)) 

    La primera función no es recursiva de cola porque cuando se realiza la llamada recursiva, la función necesita realizar un seguimiento de la multiplicación que necesita hacer con el resultado después de que la llamada retorna. Como tal, la stack se ve de la siguiente manera:

     (fact 3) (* 3 (fact 2)) (* 3 (* 2 (fact 1))) (* 3 (* 2 (* 1 (fact 0)))) (* 3 (* 2 (* 1 1))) (* 3 (* 2 1)) (* 3 2) 6 

    Por el contrario, el seguimiento de stack para el factorial recursivo de cola se ve de la siguiente manera:

     (fact 3) (fact-tail 3 1) (fact-tail 2 3) (fact-tail 1 6) (fact-tail 0 6) 6 

    Como puede ver, solo necesitamos hacer un seguimiento de la misma cantidad de datos para cada llamada a fact-tail porque simplemente estamos devolviendo el valor que obtenemos directamente a la parte superior. Esto significa que incluso si tuviera que llamar (hecho 1000000), necesito solo la misma cantidad de espacio que (hecho 3). Este no es el caso con el hecho no recursivo de cola, y como tales valores grandes pueden causar un desbordamiento de stack.

    Veamos un ejemplo simple: la función factorial implementada en C.

    Comenzamos con la definición recursiva obvia

     unsigned fac(unsigned n) { if (n < 2) return 1; return n * fac(n - 1); } 

    Una función finaliza con una llamada final si la última operación antes de que la función regrese es otra llamada a función. Si esta invocación invoca la misma función, es recursiva de cola.

    Aunque fac() parece recursivo de cola a primera vista, no es como lo que realmente sucede es

     unsigned fac(unsigned n) { if (n < 2) return 1; unsigned acc = fac(n - 1); return n * acc; } 

    es decir, la última operación es la multiplicación y no la llamada a la función.

    Sin embargo, es posible reescribir fac() para que sea recursivo de cola al pasar el valor acumulado por la cadena de llamadas como un argumento adicional y pasar nuevamente el resultado final como el valor de retorno:

     unsigned fac(unsigned n) { return fac_tailrec(1, n); } unsigned fac_tailrec(unsigned acc, unsigned n) { if (n < 2) return acc; return fac_tailrec(n * acc, n - 1); } 

    Ahora, ¿por qué es esto útil? Debido a que regresamos inmediatamente después de la llamada final, podemos descartar el fotogtwig de stack anterior antes de invocar la función en la posición de cola, o, en el caso de funciones recursivas, reutilizar el fotogtwig de la stack tal como está.

    La optimización de la llamada final transforma nuestro código recursivo en

     unsigned fac_tailrec(unsigned acc, unsigned n) { TOP: if (n < 2) return acc; acc = n * acc; n = n - 1; goto TOP; } 

    Esto puede incluirse en fac() y llegamos a

     unsigned fac(unsigned n) { unsigned acc = 1; TOP: if (n < 2) return acc; acc = n * acc; n = n - 1; goto TOP; } 

    que es equivalente a

     unsigned fac(unsigned n) { unsigned acc = 1; for (; n > 1; --n) acc *= n; return acc; } 

    Como podemos ver aquí, un optimizador suficientemente avanzado puede reemplazar la recursividad de cola con iteración, que es mucho más eficiente ya que evita la sobrecarga de llamada de función y solo utiliza una cantidad constante de espacio de stack.

    TCO (Tail Call Optimization) es el proceso mediante el cual un comstackdor inteligente puede realizar una llamada a una función y no tomar espacio de stack adicional. La única situación en la que esto sucede es si la última instrucción ejecutada en una función f es una llamada a una función g (Nota: g puede ser f ). La clave aquí es que f ya no necesita espacio en la stack, simplemente llama a g y luego devuelve lo que g devolvería. En este caso, se puede hacer la optimización de que g simplemente se ejecute y devuelva el valor que tendría para lo que se llamó f.

    Esta optimización puede hacer que las llamadas recursivas tomen un espacio de stack constante, en lugar de explotar.

    Ejemplo: esta función factorial no es TCOptimizable:

     def fact(n): if n == 0: return 1 return n * fact(n-1) 

    Esta función hace cosas además de llamar a otra función en su statement de devolución.

    Esta función a continuación es TCOptimizable:

     def fact_h(n, acc): if n == 0: return acc return fact_h(n-1, acc*n) def fact(n): return fact_h(n, 1) 

    Esto se debe a que lo último que ocurre en cualquiera de estas funciones es llamar a otra función.

    Probablemente la mejor descripción de alto nivel que he encontrado para las llamadas finales, las llamadas de cola recursivas y la optimización de la cola de cola es la publicación del blog

    “¿Qué diablos es: una llamada de cola”

    por Dan Sugalski. En la optimización de la cola de llamada, escribe:

    Considera, por un momento, esta simple función:

     sub foo (int a) { a += 15; return bar(a); } 

    Entonces, ¿qué puede usted, o más bien su comstackdor de lenguaje, hacer? Bueno, lo que puede hacer es convertir el código del formulario return somefunc(); en el pop stack frame; goto somefunc(); secuencia pop stack frame; goto somefunc(); secuencia de bajo nivel pop stack frame; goto somefunc(); pop stack frame; goto somefunc(); . En nuestro ejemplo, eso significa que antes de llamar a la bar , foo limpia y luego, en lugar de llamar a la bar como una subrutina, hacemos una operación goto bajo nivel al comienzo de la bar . Foo ya se ha limpiado de la stack, así que cuando comienza la bar parece que quien llamó foo realmente ha llamado bar , y cuando la bar devuelve su valor, la devuelve directamente a quien haya llamado a foo , en lugar de devolverlo a foo que haría luego regréselo a su interlocutor.

    Y en la recursividad de la cola:

    La recursividad de cola ocurre si una función, como su última operación, devuelve el resultado de llamarse a sí mismo . La recursividad de la cola es más fácil de tratar porque en lugar de tener que saltar al principio de alguna función aleatoria en alguna parte, simplemente regresas al principio de ti mismo, lo cual es una cosa muy simple.

    Para que esto:

     sub foo (int a, int b) { if (b == 1) { return a; } else { return foo(a*a + a, b - 1); } 

    se convierte silenciosamente en:

     sub foo (int a, int b) { label: if (b == 1) { return a; } else { a = a*a + a; b = b - 1; goto label; } 

    Lo que me gusta de esta descripción es lo sucinto y fácil de entender para quienes provienen de un contexto de lenguaje imperativo (C, C ++, Java)

    Tenga en cuenta en primer lugar que no todos los idiomas lo admiten.

    TCO se aplica a un caso especial de recursión. La esencia de esto es que si lo último que haces en una función es llamarse a sí mismo (por ejemplo, se llama a sí mismo desde la posición de “cola”), el comstackdor puede optimizarlo para que actúe como una iteración en lugar de la recursión estándar.

    Verá, normalmente durante la recursión, el tiempo de ejecución necesita realizar un seguimiento de todas las llamadas recursivas, de modo que cuando se devuelve puede reanudarse en la llamada anterior y así sucesivamente. (Intente escribir manualmente el resultado de una llamada recursiva para tener una idea visual de cómo funciona esto). Hacer un seguimiento de todas las llamadas ocupa espacio, lo que se vuelve significativo cuando la función se autodenomina mucho. Pero con TCO, solo puede decir “volver al principio, solo que esta vez cambie los valores de los parámetros a estos nuevos”. Puede hacerlo porque nada después de la llamada recursiva se refiere a esos valores.

    Mira aquí:

    http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

    Como probablemente sepa, las llamadas a funciones recursivas pueden causar esgulps en una stack; es fácil quedarse rápidamente sin espacio en la stack. La optimización de llamada de cola es la forma mediante la cual puede crear un algoritmo de estilo recursivo que utiliza el espacio de stack constante, por lo tanto, no crece y crece y obtiene errores de stack.

    1. Deberíamos asegurarnos de que no haya declaraciones goto en la función en sí … atendidas por la función de llamada que es lo último en la función llamada.

    2. Las recurrencias a gran escala pueden usar esto para optimizaciones, pero a pequeña escala, la sobrecarga de instrucciones para hacer que la función llame a una llamada final reduce el propósito real.

    3. TCO podría causar una función de ejecución permanente:

       void eternity() { eternity(); } 

    El enfoque de función recursiva tiene un problema. Construye una stack de llamadas de tamaño O (n), lo que hace que nuestra memoria total cueste O (n). Esto lo hace vulnerable a un error de desbordamiento de stack, donde la stack de llamadas se hace demasiado grande y se queda sin espacio. Plan de Optimización del Costo de Cola (TCO). Donde puede optimizar las funciones recursivas para evitar la acumulación de una stack de llamadas altas y, por lo tanto, ahorra el costo de la memoria.

    Hay muchos idiomas que están haciendo TCO (Javascript, Ruby y algunos C) mientras que Python y Java no hacen TCO.

    El lenguaje de JavaScript ha confirmado el uso de 🙂 http://2ality.com/2015/06/tail-call-optimization.html