¿Qué es la eliminación de recurrencia de cola?

Question

Steve Yegge lo mencionó en un blog post y no tengo idea de lo que significa, ¿podría alguien contarme?

¿Es lo mismo que tail call optimization?

Answer 1

Eliminación de llamada de cola es una optimización que ahorra apilar espacio. sustituye a una función llamada con un Goto eliminación recursividad. la cola es lo mismo, pero con la restricción adicional de que la función se llama a sí mismo.

Básicamente, si lo último que una función A hace es return A(params...) entonces puede eliminar la asignación de un marco de pila y en su lugar establecer los registros apropiados y saltar directamente al cuerpo de la función.

Considera una convención de llamadas (imaginaria) que pasa todos los parámetros en la pila y devuelve el valor en algún registro.

Algunas funciones podrían recopilar hasta (en un lenguaje ensamblador imaginaria):

function: 
//Reading params B, C, & D off the stack 
pop B 
pop C 
pop D 
//Do something meaningful, including a base case return 
... 
//Pass new values for B, C, & D to a new invocation of function on the stack 
push D* 
push C* 
push B* 
call function 
ret 

Cualquiera que sea la anterior hace realmente, que ocupa una trama totalmente nueva pila para cada llamada a la función. Sin embargo, dado que no ocurre nada después de la llamada de cola para funcionar, excepto un retorno, podemos optimizar de forma segura ese caso.

El resultado es:

function: 
//Reading params B, C, & D off the stack (but only on the first call) 
pop B 
pop C 
pop D 
function_tail_optimized: 
//Do something meaningful, including a base case return 
... 
//Instead of a new stack frame, load the new values directly into the registers 
load B, B* 
load C, C* 
load D, D* 
//Don't call, instead jump directly back into the function 
jump function_tail_optimized 

El resultado final es una función equivalente que ahorra mucho espacio de pila, sobre todo para las entradas que dan lugar a un gran número de llamadas recursivas.

Se requiere mucha imaginación en mi respuesta, pero creo que se puede entender.

Answer 2

de here:

" ... la eliminación de la cola de recursión es un caso especial de la cola eliminación llamada en la que la llamada cola es una llamada a la función en sí En ese caso, la llamada . puede ser sustituido por un salto al inicio de la función después de mover los nuevos argumentos a los registros o ubicaciones de pila apropiados ..."

de Wikipedia:

" ... Cuando una función se llama, el equipo debe 'recordar' el lugar que fue llamado, la dirección de retorno, de modo que pueda volver a ese lugar con el resultado una vez que el la llamada esta completa. Por lo general, esta información se guarda en la pila, una lista simple de ubicaciones de retorno en el orden en que se alcanzaron las ubicaciones de las llamadas que describen. A veces, lo último que hace una función después de completar todas las demás operaciones es simplemente llamar a una función, posiblemente ella misma, y ​​devolver su resultado. Con la repetición de cola, no hay necesidad de recordar el lugar desde el que estamos llamando; en su lugar, podemos dejar la pila sola, y la función recién llamada devolverá su resultado directamente al llamador original. Convertir una llamada a una sucursal o saltar en un caso así se llama una optimización de la cola de llamadas. Tenga en cuenta que la llamada final no tiene que aparecer léxicamente después de todas las demás declaraciones en el código fuente; solo es importante que su resultado sea devuelto inmediatamente, ya que la función de llamada nunca tendrá la oportunidad de hacer nada después de la llamada si se realiza la optimización ... "