¿Qué Es La Optimización De Llamadas De Cola?

Veamos un ejemplo sencillo: 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 termina con una llamada de cola si la última operación antes de que la función regrese es otra llamada de función. Si esta llamada invoca la misma función, es tail-recursiva.

A pesar de que fac() parece cola recursiva 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 ser recursivo de cola pasando el valor acumulado hacia abajo en la cadena de llamadas como un argumento adicional y pasando solo el resultado final hacia arriba nuevamente como el valor devuelto:

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 de cola, podemos descartar el stackframe anterior antes de invocar la función en posición de cola, o, en caso de funciones recursivas, reutilizar el stackframe tal cual.

La optimización de tail-call 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 insertar 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 recursión de cola con la iteración, que 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 (Tail Call Optimization) es el proceso por el cual un compilador inteligente puede hacer una llamada a una función y no tomar espacio adicional en la pila. 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 pila - simplemente llama a g y luego devuelve lo que g devolvería. En este caso la optimización puede se hace que g simplemente se ejecuta y devuelve cualquier valor que tendría a la cosa que llamó f.

Esta optimización puede hacer que las llamadas recursivas tomen espacio constante en la pila, 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 sentencia return.

Esta 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)

Esto se debe a que lo último que sucede en cualquiera de estos 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 entrada del blog

"Qué diablos es: Una llamada de cola"

Por Dan Sugalski. En la optimización de llamadas de cola escribe:

Considere, por un momento, esta simple función:{[18]]}

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

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

Y en la recursión de cola:

La recursión de cola ocurre si una función, como su última operación, devuelve el resultado de llamarse. La recursión de cola es más fácil de manejar porque en lugar de tener que saltar al principio de algunos al azar función en algún lugar, usted acaba de hacer un goto de nuevo al principio de a ti mismo, que es una cosa muy simple de hacer.

De modo que esto:

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

Se convierte en silencio 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 sucinta y fácil que es de entender para aquellos que vienen de un entorno de lenguaje imperativo (C, C++, Java)

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

TCO se aplica a un caso especial de recursión. La esencia de esto es, si lo último que haces en una función es llamarse a sí misma (por ejemplo, se llama a sí misma desde la posición "tail"), esto puede ser optimizado por el compilador para actuar como iteración en lugar de recursión estándar.

Verá, normalmente durante la recursión, el tiempo de ejecución necesita mantener un registro de todas las llamadas recursivas, de modo que cuando se devuelva se pueda reanudar en el llame y así sucesivamente. (Intente escribir manualmente el resultado de una llamada recursiva para obtener una idea visual de cómo funciona esto.) Realizar un seguimiento de todas las llamadas ocupa espacio, lo que se vuelve significativo cuando la función se llama a sí misma 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 hacer eso 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 estragos en una pila; es fácil quedarse sin espacio en la pila rápidamente. La optimización de llamadas de cola es la forma en que puede crear un algoritmo de estilo recursivo que usa espacio de pila constante, por lo tanto, no crece y crece y obtiene errores de pila.

1. Debemos asegurarnos de que no haya declaraciones goto en la propia función .. cuidado por llamada de función es la última cosa en la función de llamada.

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

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

   void eternity()
   {
       eternity();
   }
   

El enfoque de función recursiva tiene un problema. Construye una pila 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 pila, donde la pila de llamadas se vuelve demasiado grande y se queda sin espacio. Esquema de Optimización de Costos de Cola (TCO). Donde puede optimizar las funciones recursivas para evitar la construcción de una pila de llamadas alta y, por lo tanto, ahorra el costo de memoria.

Hay muchos lenguajes que están haciendo TCO como (Javascript, Ruby y pocos C) donde como Python y Java no hace TCO.

El lenguaje JavaScript se ha confirmado usando :) http://2ality.com/2015/06/tail-call-optimization.html