¿Qué es la optimización de llamadas de cola?
En pocas palabras, ¿qué es la optimización de llamadas de cola?
Más específicamente, ¿cuáles son algunos pequeños fragmentos de código en los que se podría aplicar y en los que no, con una explicación de por qué?
La optimización de llamada de cola es donde puede evitar la asignación de un nuevo marco de pila para una función porque la función que llama simplemente devolverá el valor que obtiene de la función llamada. El uso más común es la recursividad de cola, donde una función recursiva escrita para aprovechar la optimización de la llamada de cola puede utilizar un espacio de pila constante.
Scheme es uno de los pocos lenguajes de programación que garantiza en la especificación que cualquier implementación debe proporcionar esta optimización, por lo 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 debe hacer con el resultado después de que regresa la llamada. Como tal, la pila tiene el siguiente aspecto:
(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 la pila para el factorial recursivo de cola tiene el siguiente aspecto:
(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6
Como puede ver, solo necesitamos realizar un seguimiento de la misma cantidad de datos para cada llamada a fact-tail porque simplemente devolvemos el valor que obtenemos hasta la parte superior. Esto significa que incluso si llamara (hecho 1000000), solo necesitaría la misma cantidad de espacio que (hecho 3). Este no es el caso del hecho recursivo sin cola y, como tales, valores tan grandes pueden provocar un desbordamiento de la pila.
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 regrese la función es otra llamada a función. Si esta llamada invoca la misma función, es recursiva de cola.
Aunque fac()a primera vista parece recursivo en la cola, no lo es como lo que realmente sucede.
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 reescribirlo fac()para que sea recursivo de cola pasando el valor acumulado hacia abajo en la cadena de llamadas como argumento adicional y pasando solo el resultado final nuevamente como 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 bien, ¿por qué es esto útil? Debido a que regresamos inmediatamente después de la llamada final, podemos descartar el marco de pila anterior antes de invocar la función en la posición final o, en el caso de funciones recursivas, reutilizar el marco de pila tal como está.
La optimización de llamada de cola 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 se puede incorporar 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, lo cual es mucho más eficiente ya que evita la sobrecarga de llamadas a funciones y solo usa una cantidad constante de espacio de pila.
TCO (Optimización de llamadas de cola) es el proceso mediante el cual un compilador inteligente puede realizar una llamada a una función y no ocupar espacio de pila 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 de pila: simplemente llama a g y luego devuelve lo que g devolvería. En este caso, se puede optimizar que g simplemente se ejecute y devuelva cualquier valor que tenga a lo que llamó f.
Esta optimización puede hacer que las llamadas recursivas ocupen un espacio de pila constante, en lugar de explotar.
Ejemplo: esta función factorial no es TCOptimizable:
from dis import dis
def fact(n):
if n == 0:
return 1
return n * fact(n-1)
dis(fact)
2 0 LOAD_FAST 0 (n)
2 LOAD_CONST 1 (0)
4 COMPARE_OP 2 (==)
6 POP_JUMP_IF_FALSE 12
3 8 LOAD_CONST 2 (1)
10 RETURN_VALUE
4 >> 12 LOAD_FAST 0 (n)
14 LOAD_GLOBAL 0 (fact)
16 LOAD_FAST 0 (n)
18 LOAD_CONST 2 (1)
20 BINARY_SUBTRACT
22 CALL_FUNCTION 1
24 BINARY_MULTIPLY
26 RETURN_VALUE
Esta función hace cosas además de llamar a otra función en su declaración de retorno.
La siguiente funció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)
dis(fact)
2 0 LOAD_GLOBAL 0 (fact_h)
2 LOAD_FAST 0 (n)
4 LOAD_CONST 1 (1)
6 CALL_FUNCTION 2
8 RETURN_VALUE
Esto se debe a que lo último que sucede en cualquiera de estas funciones es llamar a otra función.
Probablemente la mejor descripción de alto nivel que he encontrado para llamadas de cola, llamadas de cola recursivas y optimización de llamadas de cola es la publicación del blog.
"¿Qué diablos es: una llamada de cola?"
por Dan Sugalski. Sobre la optimización de llamadas de cola, escribe:
Considere, por un momento, esta sencilla función:
sub foo (int a) { a += 15; return bar(a); }Entonces, ¿qué puedes hacer tú, o más bien tu compilador de lenguajes? Bueno, lo que puede hacer es convertir el código del formulario
return somefunc();en una secuencia de bajo nivelpop stack frame; goto somefunc();. En nuestro ejemplo, eso significa que antes de llamar abar,foose limpia y luego, en lugar de llamarbarcomo una subrutina, hacemos unagotooperación de bajo nivel al inicio debar.Fooya se limpió de la pila, por lo que cuandobarcomienza parece que quien llamófoorealmente llamóbar, y cuandobardevuelve su valor, lo devuelve directamente a quien llamófoo, en lugar de devolvérselo afooquien luego se lo devolvería a la persona que llamó.
Y en recursividad de cola:
La recursividad de cola ocurre si una función, como última operación, devuelve el resultado de llamarse a sí misma . La recursividad de cola es más fácil de manejar porque en lugar de tener que saltar al principio de alguna función aleatoria en algún lugar, simplemente vuelves al principio de ti mismo, lo cual es algo muy simple de hacer.
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 concisa y fácil que es de entender para aquellos que tienen experiencia en lenguajes imperativos (C, C++, Java).
