¿El uso de la repetición de la cola en Erlang reduce la velocidad?

Question

He estado leyendo acerca de Erlang últimamente y cómo la recursividad de cola es muy utilizada, debido a la dificultad de usar bucles iterativos.

¿No desacelera este alto uso de la recursividad, con todas las llamadas a funciones y el efecto que tienen en la pila? ¿O la recursividad de la cola niega la mayor parte de esto?

Answer 1

La recurrencia de cola iterativa se implementa generalmente utilizando Tail calls. Esto es básicamente una transformación de una llamada recursiva a un bucle simple.

ejemplo de C#:

uint FactorialAccum(uint n, uint accum) { 
    if(n < 2) return accum; 
    return FactorialAccum(n - 1, n * accum); 
}; 
uint Factorial(uint n) { 
    return FactorialAccum(n, 1); 
}; 

a

uint FactorialAccum(uint n, uint accum) { 
start: 
    if(n < 2) return accum; 
    accum *= n; 
    n -= 1; 
goto start; 
}; 
uint Factorial(uint n) { 
    return FactorialAccum(n, 1); 
}; 

o incluso mejor:

uint Factorial(uint n) { 
    uint accum = 1; 
start: 
    if(n < 2) return accum; 
    accum *= n; 
    n -= 1; 
goto start; 
}; 

---

C no # real de la recursión de cola, esto se debe a que se modifique el valor de retorno , la mayoría de los compiladores no romperán esto wn en un bucle:

int Power(int number, uint power) { 
    if(power == 0) return 1; 
    if(power == 1) return number; 
    return number * Power(number, --power); 
} 

a

int Power(int number, uint power) { 
    int result = number; 
start: 
    if(power == 0) return 1; 
    if(power == 1) return number; 
    result *= number; 
    power--; 
goto start; 
} 

Answer 2

El punto es que Erlang optimiza llamadas de cola (no sólo recursión). La optimización de las llamadas de cola es bastante simple: si el valor de retorno se calcula mediante una llamada a otra función, esta otra función no solo se pone en la pila de llamadas de función en la parte superior de la función de llamada, sino que el marco de pila de la función actual es reemplazó por una de las funciones llamadas. Esto significa que las llamadas de cola no se suman al tamaño de la pila.

Por lo tanto, no, el uso de la recursividad de cola no desacelera Erlang, ni supone un riesgo de desbordamiento de la pila.

Con la optimización de la cola de llamadas en su lugar, no solo puede usar la recursividad de cola simple, sino también la recursión de cola mutua de varias funciones (llamadas de cola b, llamadas de cola c, que llama a un ...) . Esto a veces puede ser un buen modelo de computación.

Answer 3

No debería afectar el rendimiento en la mayoría de los casos. Lo que está buscando no son solo las llamadas de cola, sino la optimización de llamadas de cola (o la eliminación de llamadas de cola). La optimización de llamadas en cola es una técnica de compilación o tiempo de ejecución que se da cuenta cuando una llamada a una función es el equivalente a 'abrir la pila' para volver a la función adecuada en lugar de simplemente regresar. En general, la optimización de llamadas de cola solo se puede realizar cuando la llamada recursiva es la última operación de la función, por lo que debe tener cuidado.

Answer 4

Una optimización similar que separa las llamadas de funciones de texto de programa de las llamadas a funciones de implementación es 'inline'. En los lenguajes modernos/reflexivos, las llamadas a funciones tienen poca relación con las llamadas a funciones a nivel de máquina.

Answer 5

Existe un problema relacionado con la recursividad de cola pero no está relacionado con el rendimiento: la optimización de recursión de cola de Erlang también implica la eliminación del seguimiento de pila para la depuración.

Por ejemplo, vea el Punto 9.13 de la Erlang FAQ:

Why doesn't the stack backtrace show the right functions for this code: 

     -module(erl). 
     -export([a/0]). 

     a() -> b(). 
     b() -> c(). 
     c() -> 3 = 4.   %% will cause badmatch 

The stack backtrace only shows function c(), rather than a(), b() and c(). 
This is because of last-call-optimisation; the compiler knows it does not need 
to generate a stack frame for a() or b() because the last thing it did was 
call another function, hence the stack frame does not appear in the stack 
backtrace. 

Esto puede ser un poco de dolor cuando se pulse un accidente (pero sí un poco va con el territorio de la programación funcional ...)