En informática , una llamada de cola es una llamada de subrutina realizada como la acción final de un procedimiento. [1] Si el objetivo de una cola es la misma subrutina, se dice que la subrutina es cola recursiva , que es un caso especial de recursividad directa . La recursividad de cola (o recursión de cola ) es particularmente útil y, a menudo, fácil de manejar la optimización en las implementaciones.
Las llamadas de cola se pueden implementar sin agregar un nuevo marco de pila a la pila de llamadas . La mayor parte del marco del procedimiento actual ya no es necesario y puede ser reemplazado por el marco de la llamada final, modificado según corresponda (similar a la superposición para procesos, pero para llamadas a funciones). A continuación, el programa puede saltar a la subrutina llamada. La producción de dicho código en lugar de una secuencia de llamada estándar se denomina eliminación de llamada final u optimización de llamada final . La eliminación de llamadas de cola permite que las llamadas a procedimientos en la posición de cola se implementen de manera tan eficiente como las instrucciones goto , lo que permite una programación estructurada eficiente . En las palabras deGuy L. Steele , "en general, las llamadas a procedimientos pueden considerarse útiles como sentencias GOTO que también pasan parámetros, y pueden codificarse uniformemente como instrucciones JUMP [código máquina]". [2]
No todos los lenguajes de programación requieren la eliminación de llamadas finales. Sin embargo, en los lenguajes de programación funcionales , la eliminación de las llamadas finales a menudo está garantizada por el estándar del lenguaje , lo que permite que la recursividad de la cola utilice una cantidad similar de memoria como un bucle equivalente . El caso especial de las llamadas de cola recursivas, cuando una función se llama a sí misma, puede ser más fácil de eliminar que las llamadas de cola generales. Cuando la semántica del lenguaje no admite explícitamente las llamadas de cola generales, un compilador a menudo puede optimizar las llamadas de los hermanos o las llamadas de cola a funciones que toman y devuelven los mismos tipos que el llamador. [3]
Cuando se llama a una función, la computadora debe "recordar" el lugar desde el que se llamó, la dirección de retorno , de modo que pueda regresar a esa ubicación con el resultado una vez que se complete la llamada. Por lo general, esta información se guarda en la pila de llamadas , una lista simple de ubicaciones de devolución en el orden de las horas en que se alcanzaron las ubicaciones de llamadas que describen. Para las llamadas de cola, no hay necesidad de recordar a la persona que llama; en cambio, la eliminación de la llamada de cola realiza solo los cambios mínimos necesarios en el marco de la pila antes de pasarlo, [4] y la función llamada de cola volverá directamente al originalllamador. La llamada de cola no tiene que aparecer léxicamente después de todas las demás declaraciones en el código fuente; Solo es importante que la función de llamada regrese inmediatamente después de la llamada de cola, devolviendo el resultado de la llamada de cola, si lo hubiera, ya que la función de llamada se omite cuando se realiza la optimización.
Para las llamadas de función no recursivas, esta suele ser una optimización que ahorra solo un poco de tiempo y espacio, ya que no hay tantas funciones diferentes disponibles para llamar. Sin embargo, cuando se trata de funciones recursivas o mutuamente recursivas donde la recursividad ocurre a través de llamadas de cola, el espacio de la pila y el número de retornos guardados pueden llegar a ser muy significativos, ya que una función puede llamarse a sí misma, directa o indirectamente, creando un nuevo marco de pila de llamadas. cada vez. La eliminación de la llamada de cola a menudo reduce los requisitos de espacio de pila asintóticos de lineal, u O (n), a constante, u O (1). Por lo tanto, las definiciones estándar de algunos lenguajes de programación, como Scheme , requieren la eliminación de la llamada de cola , [5][6] e idiomas de lafamilia ML, entre otros. La definición del lenguaje Scheme formaliza exactamente la noción intuitiva de la posición de la cola, especificando qué formas sintácticas permiten tener resultados en el contexto de la cola. [7] Las implementaciones que permiten que un número ilimitado de llamadas de cola estén activas en el mismo momento, gracias a la eliminación de llamadas de cola, también se pueden llamar 'apropiadamente recursivas de cola'. [5]
Además de la eficiencia del espacio y la ejecución, la eliminación de llamadas finales es importante en el lenguaje de programación funcional conocido como estilo de paso de continuación (CPS), que de otra manera se quedaría sin espacio de pila rápidamente.