En informática , una llamada de cola es una llamada de subrutina que se realiza como acción final de un procedimiento. [1] Si el objetivo de una llamada de cola es la misma subrutina, se dice que la subrutina es recursiva de cola , que es un caso especial de recursión directa . La recursión de cola (o recursión de fin de cola ) es particularmente útil y, a menudo, es fácil de optimizar 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 se puede reemplazar por el marco de la llamada de cola, modificado según corresponda (similar a la superposición para procesos, pero para llamadas de función). El programa puede entonces saltar a la subrutina llamada. Producir dicho código en lugar de una secuencia de llamada estándar se llama eliminación de llamada de cola u optimización de llamada de cola . La eliminación de llamada de cola permite que las llamadas de procedimiento en posición de cola se implementen de manera tan eficiente como las instrucciones goto , lo que permite una programación estructurada eficiente . En palabras de Guy L. Steele , "en general, las llamadas de procedimiento pueden considerarse de manera útil como instrucciones GOTO que también pasan parámetros y pueden codificarse uniformemente como instrucciones JUMP [código de máquina]". [2]
No todos los lenguajes de programación requieren la eliminación de llamadas de cola. Sin embargo, en los lenguajes de programación funcional , la eliminación de llamadas de cola suele estar garantizada por el estándar del lenguaje , lo que permite que la recursión de cola utilice una cantidad de memoria similar a la de un bucle equivalente . El caso especial de las llamadas recursivas de cola, cuando una función se llama a sí misma, puede ser más susceptible a la eliminación de llamadas que las llamadas de cola generales. Cuando la semántica del lenguaje no admite explícitamente llamadas de cola generales, un compilador a menudo puede optimizar las llamadas hermanas 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 , para que pueda regresar a esa ubicación con el resultado una vez que se complete la llamada. Normalmente, esta información se guarda en la pila de llamadas , una lista de ubicaciones de retorno en el orden en que se alcanzaron las ubicaciones de llamada. Para las llamadas de cola, no es necesario recordar al llamador; en cambio, la eliminación de llamadas de cola solo realiza los cambios mínimos necesarios en el marco de la pila antes de pasarlo, [4] y la función llamada de cola regresará directamente al llamador original . 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 que llama regrese inmediatamente después de la llamada de cola, devolviendo el resultado de la llamada de cola si lo hay, ya que la función que llama se omite cuando se realiza la optimización.
En el caso de las llamadas a funciones no recursivas, esta suele ser una optimización que ahorra poco tiempo y espacio, ya que no hay tantas funciones diferentes disponibles para llamar. Sin embargo, cuando se trata de funciones recursivas o recursivas mutuas en las que la recursión se produce a través de llamadas de cola, el espacio de pila y la cantidad de retornos ahorrados 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 llamadas de cola a menudo reduce los requisitos de espacio de pila asintótico de lineal, u O (n), a constante, u O (1). Por lo tanto, la eliminación de llamadas de cola es requerida por las definiciones estándar de algunos lenguajes de programación, como Scheme , [5] [6] y lenguajes de la familia ML , entre otros. La definición del lenguaje Scheme formaliza exactamente la noción intuitiva de posición de cola, al especificar qué formas sintácticas permiten tener resultados en el contexto de cola. [7] Las implementaciones que permiten que una cantidad ilimitada de llamadas de cola estén activas al mismo tiempo, gracias a la eliminación de llamadas de cola, también pueden denominarse "recursivas de cola propiamente dichas". [5]
Además del espacio y la eficiencia de 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 lo contrario se quedaría rápidamente sin espacio en la pila.
Una llamada de cola se puede ubicar justo antes del final sintáctico de una función:
función foo ( datos ) { a ( datos ); return b ( datos ); } Aquí, tanto a(data)y como b(data)son llamadas, pero bes lo último que ejecuta el procedimiento antes de regresar y, por lo tanto, está en la posición de cola. Sin embargo, no todas las llamadas de cola se ubican necesariamente en el extremo sintáctico de una subrutina:
función barra ( datos ) { si ( a ( datos )) { devolver b ( datos ); } devolver c ( datos ); } Aquí, ambas llamadas a by cestán en posición de cola. Esto se debe a que cada una de ellas se encuentra al final de la rama if respectivamente, aunque la primera no se encuentra sintácticamente al final del barcuerpo de .
En este código:
función foo1 ( datos ) { devolver a ( datos ) + 1 ; } función foo2 ( datos ) { var ret = a ( datos ); return ret ; } función foo3 ( datos ) { var ret = a ( datos ); retorno ( ret == 0 ) ? 1 : retirado ; } La llamada a a(data)está en la posición de cola en , pero nofoo2 está en la posición de cola ni en ni en , porque el control debe regresar al llamador para permitirle inspeccionar o modificar el valor de retorno antes de devolverlo.foo1foo3
El siguiente programa es un ejemplo en Scheme : [8]
;; factorial : numero -> numero ;; para calcular el producto de todos los enteros positivos ;; menores o iguales a n. ( define ( factorial n ) ( if ( = n 0 ) 1 ( * n ( factorial ( - n 1 ))))) Esto no está escrito en un estilo recursivo de cola, porque la función de multiplicación ("*") está en la posición de cola. Esto se puede comparar con:
;; factorial : numero -> numero ;; para calcular el producto de todos los enteros positivos menores o iguales a n. ( define ( factorial n ) ( fact-iter 1 n )) ( define ( fact-iter product n ) ( if ( = n 0 ) product ( fact-iter ( * product n ) ( - n 1 )))) Este programa supone una evaluación en orden aplicativo . El procedimiento interno fact-iterse llama a sí mismo en último lugar en el flujo de control. Esto permite que un intérprete o compilador reorganice la ejecución, que normalmente se vería así: [8]
llamar factorial (4) Llamar al iterador de hechos (1 4) Llamada iteradora de hechos (4 3) Llamada iteradora de hechos (12 2) Llamada iteradora de hechos (24 1) volver 24 volver 24 volver 24 volver 24 volver 24
en la variante más eficiente , tanto en términos de espacio como de tiempo:
llamar factorial (4) Llamar al iterador de hechos (1 4) Reemplazar argumentos con (4 3) Reemplazar argumentos con (12 2) Reemplazar argumentos con (24 1) volver 24 volver 24
Esta reorganización ahorra espacio porque no es necesario guardar ningún estado, excepto la dirección de la función que realiza la llamada, ni en la pila ni en el montón, y el marco de la pila de llamadas fact-iterse reutiliza para el almacenamiento de los resultados intermedios. Esto también significa que el programador no tiene que preocuparse por quedarse sin espacio en la pila o en el montón para las recursiones extremadamente profundas. En las implementaciones típicas, la variante recursiva de cola será sustancialmente más rápida que la otra variante, pero solo por un factor constante.
Algunos programadores que trabajan con lenguajes funcionales reescriben el código recursivo para que sea recursivo en la cola y así puedan aprovechar esta característica. Esto suele requerir la adición de un argumento "acumulador" ( producten el ejemplo anterior) a la función.
La recursión de cola módulo cons es una generalización de la optimización de recursión de cola introducida por David HD Warren [9] en el contexto de la compilación de Prolog , visto como un lenguaje explícitamente establecido una vez . Fue descrito (aunque no nombrado) por Daniel P. Friedman y David S. Wise en 1974 [10] como una técnica de compilación LISP . Como sugiere el nombre, se aplica cuando la única operación que queda por realizar después de una llamada recursiva es anteponer un valor conocido delante de la lista devuelta de ella (o realizar un número constante de operaciones simples de construcción de datos, en general). Esta llamada sería, por tanto, una llamada de cola salvo (" módulo ") la operación cons mencionada . Pero anteponer un valor al comienzo de una lista al salir de una llamada recursiva es lo mismo que agregar este valor al final de la lista creciente al ingresar a la llamada recursiva, construyendo así la lista como un efecto secundario , como si fuera un parámetro acumulador implícito. El siguiente fragmento de Prolog ilustra el concepto:
Por lo tanto, en la traducción recursiva de cola, dicha llamada se transforma en la primera creación de un nuevo nodo de lista y la configuración de su firstcampo, y luego se realiza la llamada de cola con el puntero al restcampo del nodo como argumento, para que se complete de forma recursiva. El mismo efecto se logra cuando la recursión se protege con un constructor de datos evaluado de forma diferida, lo que se logra automáticamente en lenguajes de programación diferida como Haskell.
El siguiente fragmento define una función recursiva en C que duplica una lista enlazada (con algún código Scheme y Prolog equivalente como comentarios, para comparación):
En esta forma, la función no es recursiva de cola, porque el control regresa al invocador después de que la llamada recursiva duplica el resto de la lista de entrada. Incluso si asignara el nodo principal antes de duplicar el resto, aún necesitaría insertar el resultado de la llamada recursiva en el nextcampo después de la llamada. [a]
Por lo tanto, la función es casi recursiva de cola. El método de Warren traslada la responsabilidad de completar el nextcampo a la propia llamada recursiva, que así se convierte en llamada de cola. [b] Usando el nodo principal centinela para simplificar el código,
Ahora, el destinatario de la llamada añade al final de la lista creciente, en lugar de que el autor de la llamada la anteponga al principio de la lista devuelta. El trabajo ahora se realiza en el camino hacia adelante desde el comienzo de la lista, antes de la llamada recursiva que luego continúa, en lugar de hacia atrás desde el final de la lista, después de que la llamada recursiva haya devuelto su resultado. Por lo tanto, es similar a la técnica de acumulación de parámetros, que convierte un cálculo recursivo en uno iterativo.
De manera característica de esta técnica, se crea un marco padre en la pila de llamadas de ejecución, que el llamado recursivo final puede reutilizar como su propio marco de llamada si la optimización de llamada final está presente.
La implementación recursiva de cola ahora se puede convertir en una implementación explícitamente iterativa, como un bucle acumulativo :
En un artículo presentado en la conferencia ACM en Seattle en 1977, Guy L. Steele resumió el debate sobre GOTO y la programación estructurada , y observó que las llamadas a procedimientos en la posición de cola de un procedimiento pueden tratarse mejor como una transferencia directa de control al procedimiento llamado, eliminando típicamente operaciones de manipulación de pila innecesarias. [2] Dado que estas "llamadas de cola" son muy comunes en Lisp , un lenguaje donde las llamadas a procedimientos son omnipresentes, esta forma de optimización reduce considerablemente el costo de una llamada a procedimiento en comparación con otras implementaciones. Steele argumentó que las llamadas a procedimientos mal implementadas habían llevado a una percepción artificial de que GOTO era barato en comparación con la llamada a procedimiento. Steele argumentó además que "en general, las llamadas a procedimientos pueden considerarse de manera útil como instrucciones GOTO que también pasan parámetros y pueden codificarse uniformemente como instrucciones JUMP [código de máquina]", con las instrucciones de manipulación de pila de código de máquina "consideradas una optimización (¡en lugar de al revés!)". [2] Steele citó evidencia de que los algoritmos numéricos bien optimizados en Lisp podían ejecutarse más rápido que el código producido por los compiladores Fortran comerciales disponibles en ese momento porque el costo de una llamada a un procedimiento en Lisp era mucho menor. En Scheme , un dialecto de Lisp desarrollado por Steele con Gerald Jay Sussman , se garantiza que la eliminación de llamadas finales se implementará en cualquier intérprete. [11]
La recursión de cola es importante para algunos lenguajes de alto nivel , especialmente los lenguajes funcionales y lógicos y los miembros de la familia Lisp . En estos lenguajes, la recursión de cola es la forma más utilizada (y a veces la única forma disponible) de implementar la iteración. La especificación del lenguaje de Scheme requiere que las llamadas de cola se optimicen para no hacer crecer la pila. Las llamadas de cola se pueden realizar explícitamente en Perl , con una variante de la declaración "goto" que toma un nombre de función: goto &NAME;[12]
Sin embargo, para las implementaciones de lenguajes que almacenan argumentos de funciones y variables locales en una pila de llamadas (que es la implementación predeterminada para muchos lenguajes, al menos en sistemas con una pila de hardware , como x86 ), la implementación de la optimización generalizada de llamadas finales (incluida la recursión de cola mutua) presenta un problema: si el tamaño del registro de activación del llamado es diferente al del llamador, entonces puede ser necesaria una limpieza adicional o un cambio de tamaño del marco de la pila. Para estos casos, optimizar la recursión de cola sigue siendo trivial, pero la optimización general de llamadas finales puede ser más difícil de implementar de manera eficiente.
Por ejemplo, en la máquina virtual Java (JVM), las llamadas recursivas de cola se pueden eliminar (ya que esto reutiliza la pila de llamadas existente), pero no las llamadas de cola generales (ya que esto cambia la pila de llamadas). [13] [14] Como resultado, los lenguajes funcionales como Scala que apuntan a la JVM pueden implementar de manera eficiente la recursión de cola directa, pero no la recursión de cola mutua.
Los paquetes de compiladores GCC , LLVM/Clang e Intel realizan una optimización de llamada de cola para C y otros lenguajes en niveles de optimización más altos o cuando -foptimize-sibling-callsse pasa la opción. [15] [16] [17] Aunque la sintaxis del lenguaje dado puede no admitirla explícitamente, el compilador puede realizar esta optimización siempre que pueda determinar que los tipos de retorno para el llamador y el llamador son equivalentes, y que los tipos de argumentos pasados a ambas funciones son los mismos o requieren la misma cantidad de espacio de almacenamiento total en la pila de llamadas. [18]
Hay varios métodos de implementación disponibles.
Los intérpretes y compiladores de lenguajes de programación funcional y lógica suelen optimizar las llamadas de cola para lograr formas de iteración más eficientes . Por ejemplo, los programadores de Scheme suelen expresar los bucles while como llamadas a procedimientos en posición de cola y confían en que el compilador o intérprete de Scheme sustituya las llamadas de cola por instrucciones de salto más eficientes . [19]
Para los compiladores que generan directamente el ensamblado, la eliminación de las llamadas de cola es sencilla: basta con reemplazar un código de operación de llamada por uno de salto, después de fijar los parámetros en la pila. Desde la perspectiva de un compilador, el primer ejemplo anterior se traduce inicialmente a un lenguaje pseudoensamblador (de hecho, se trata de un lenguaje ensamblador x86 válido ):
foo: llamar a B llamar a A ret La eliminación de llamada de cola reemplaza las dos últimas líneas con una única instrucción de salto:
foo: llamar a B jmp A Una vez completada la subrutina A, regresará directamente a la dirección de retorno de foo, omitiendo la retdeclaración innecesaria.
Por lo general, las subrutinas que se llaman deben recibir parámetros . Por lo tanto, el código generado debe asegurarse de que el marco de llamada para A esté configurado correctamente antes de saltar a la subrutina llamada de cola. Por ejemplo, en plataformas donde la pila de llamadas no solo contiene la dirección de retorno , sino también los parámetros para la subrutina, el compilador puede necesitar emitir instrucciones para ajustar la pila de llamadas. En una plataforma de este tipo, para el código:
función foo(datos1, datos2) B(datos1) devuelve A(datos2)
(donde data1y data2son parámetros) un compilador podría traducirlo como: [c]
Foo: mov reg ,[ sp + data1 ] ; obtiene el parámetro data1 de la pila (sp) en un registro temporal. push reg ; coloca datos1 en la pila donde B lo espera llamar a B ; B usa data1 pop ; eliminar datos1 de la pila mov reg ,[ sp + data2 ] ; obtiene el parámetro data2 de la pila (sp) en un registro temporal. push reg ; coloca datos2 en la pila donde A lo espera llamar a A ; A usa datos2 pop ; elimina datos2 de la pila. retiradoUn optimizador de llamadas finales podría entonces cambiar el código a:
Foo: mov reg ,[ sp + data1 ] ; obtiene el parámetro data1 de la pila (sp) en un registro temporal. push reg ; coloca datos1 en la pila donde B lo espera llamar a B ; B usa data1 pop ; eliminar datos1 de la pila mov reg ,[ sp + data2 ] ; obtiene el parámetro data2 de la pila (sp) en un registro temporal. mov [ sp + data1 ], reg ; coloca data2 donde A lo espera jmp A ; A usa data2 y regresa inmediatamente al llamador. Este código es más eficiente tanto en términos de velocidad de ejecución como de uso del espacio de la pila.
Dado que muchos compiladores de Scheme utilizan C como código de destino intermedio, la recursión de cola debe codificarse en C sin hacer crecer la pila, incluso si el compilador de C no optimiza las llamadas de cola. Muchas implementaciones logran esto mediante el uso de un dispositivo conocido como trampolín , un fragmento de código que llama repetidamente a funciones. Todas las funciones se ingresan a través del trampolín. Cuando una función tiene que llamar a otra, en lugar de llamarla directamente y luego devolver el resultado, devuelve la dirección de la función que se llamará y los parámetros de llamada al trampolín (desde donde se llamó a sí mismo), y el trampolín se encarga de llamar a esta función a continuación con los parámetros especificados. Esto garantiza que la pila de C no crezca y la iteración pueda continuar indefinidamente.
Es posible implementar trampolines utilizando funciones de orden superior en lenguajes que las soportan, como Groovy , Visual Basic .NET y C# . [20]
El uso de un trampolín para todas las llamadas de función es bastante más costoso que la llamada de función C normal, por lo que al menos un compilador de Scheme, Chicken , utiliza una técnica descrita por primera vez por Henry Baker a partir de una sugerencia no publicada de Andrew Appel [21] , en la que se utilizan llamadas C normales pero se comprueba el tamaño de la pila antes de cada llamada. Cuando la pila alcanza su tamaño máximo permitido, los objetos de la pila se recolectan como basura utilizando el algoritmo de Cheney moviendo todos los datos activos a un montón separado. Después de esto, la pila se desenrolla ("se extrae") y el programa se reanuda desde el estado guardado justo antes de la recolección de basura. Baker dice que "el método de Appel evita hacer una gran cantidad de pequeños rebotes de trampolín saltando ocasionalmente del Empire State Building". [21] La recolección de basura garantiza que la recursión de cola mutua pueda continuar indefinidamente. Sin embargo, este enfoque requiere que ninguna llamada de función C regrese nunca, ya que no hay garantía de que el marco de pila de su llamador aún exista; por lo tanto, implica una reescritura interna mucho más dramática del código del programa: estilo de paso de continuación .
La recursión de cola se puede relacionar con la declaración while , una iteración explícita, por ejemplo, transformando
procedimiento foo( x ) si p ( x ) retorna bar( x ) de lo contrario retorna foo(baz( x ))
en
procedimiento foo( x ) mientras sea verdadero si p ( x ) devuelve bar( x ) de lo contrario x ← baz( x )
donde x puede ser una tupla que incluye más de una variable: en ese caso, se debe tener cuidado al implementar la sentencia de asignación x ← baz( x ) para que se respeten las dependencias. Es posible que sea necesario introducir variables auxiliares o utilizar una construcción de intercambio .
De manera más general,
procedimiento foo( x ) si p ( x ) retorna bar( x ) de lo contrario si q ( x ) retorna baz( x ) ... de lo contrario, si r ( x ) devuelve foo(qux( x )) ... de lo contrario devuelve foo(quux( x ))
se puede transformar en
procedimiento foo( x ) mientras sea verdadero si p ( x ) devuelve bar( x ) de lo contrario si q ( x ) devuelve baz( x ) ... de lo contrario si r ( x ) x ← qux( x ) ... de lo contrario x ← quux( x )
Por ejemplo, este programa de Julia proporciona una definición recursiva no de cola factdel factorial:
función factorial ( n ) si n == 0 volver 1 demás devuelve n * factorial ( n - 1 ) finfinDe hecho, n * factorial(n - 1)envuelve la llamada a factorial. Pero se puede transformar en una definición recursiva de cola agregando un argumento allamado acumulador . [8]
Este programa de Julia proporciona una definición recursiva de cola fact_iterdel factorial:
función factorial ( n :: Entero , a :: Entero ) si n == 0 : devolver un demás devuelve factorial ( n - 1 , n * a ) finfinfunción factorial ( n :: Entero ) devuelve factorial ( n , 1 ) finEste programa de Julia da una definición iterativa fact_iterdel factorial:
función fact_iter ( n :: Integer , a :: Integer ) mientras n > 0 a = n * a n = n - 1 fin devuelve a fin función factorial ( n : : Integer ) devuelve fact_iter ( n , uno ( n )) fin recuruna forma especial. [22]tailrecmodificadores para funciones [30]goto &NAME;[32]@tailrecanotación, lo que hace que sea un error de compilación si la función no es recursiva de cola [39]
si ( ls != NULL ) { cabeza = malloc ( sizeof * cabeza ); cabeza -> valor = ls -> valor ; cabeza -> siguiente = duplicado ( ls -> siguiente ); } si ( ls != NULL ) { cabeza = malloc ( sizeof * cabeza ); cabeza -> valor = ls -> valor ; duplicado ( ls -> siguiente , & ( cabeza -> siguiente )); } callinstrucción primero inserta la ubicación del código actual en la pila y luego realiza un salto incondicional a la ubicación del código indicada por la etiqueta. La retinstrucción primero extrae una ubicación de código de la pila y luego realiza un salto incondicional a la ubicación del código recuperada.