En informática , una llamada de cola es una llamada a una subrutina realizada como acción final de un procedimiento. [1] Si el objetivo de una cola es la misma subrutina, se dice que la subrutina es recursiva de cola , que es un caso especial de recursividad directa . La recursión de cola (o recursión 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 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. Producir dicho código en lugar de una secuencia de llamadas estándar se denomina eliminación de llamadas de cola u optimización de llamadas de cola . La eliminación de llamadas de cola permite que las llamadas a procedimientos en la posición de cola se implementen tan eficientemente como las declaraciones goto , lo que permite una programación estructurada eficiente . En palabras de Guy L. Steele , "en general, las llamadas a procedimientos pueden considerarse útiles como declaraciones 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 finales. Sin embargo, en los lenguajes de programación funcionales , la eliminación de llamadas de cola a menudo está garantizada por el estándar del lenguaje , lo que permite que la recursividad de cola use una cantidad similar de memoria como un bucle equivalente . El caso especial de llamadas recursivas de cola, cuando una función se llama a sí misma, puede ser más susceptible de eliminación de llamadas que las llamadas de cola generales. Cuando la semántica del lenguaje no admite explícitamente llamadas finales generales, un compilador a menudo aún puede optimizar las llamadas entre hermanos o llamadas finales a funciones que toman y devuelven los mismos tipos que la persona que llama. [3]
Cuando se llama a una función, la computadora debe "recordar" el lugar desde donde se llamó, la dirección del remitente , para poder 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 devolución en el orden en que se alcanzaron las ubicaciones de llamadas. Para las llamadas de cola, no es necesario 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 regresará directamente a la persona que llama original. . 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 la función de llamada regrese inmediatamente después de la llamada final, devolviendo el resultado de la llamada final, si corresponde, ya que la función de llamada se omite cuando se realiza la optimización.
Para llamadas a funciones no recursivas, esto suele ser una optimización que ahorra sólo 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 recursión ocurre a través de llamadas de cola, el espacio de la pila y la cantidad de devoluciones guardadas 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, las definiciones estándar de algunos lenguajes de programación, como Scheme , [5] [6] y lenguajes de la familia ML , entre otros, exigen la eliminación de llamadas de cola. La definición del lenguaje Scheme formaliza exactamente la noción intuitiva de posición de la cola, especificando qué formas sintácticas permiten obtener resultados en el contexto de la cola. [7] Las implementaciones que permiten que un número ilimitado de llamadas de cola estén activas al mismo tiempo, gracias a la eliminación de llamadas de cola, también pueden denominarse "correctamente recursivas de cola". [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 otro modo se quedaría rápidamente sin espacio en la pila.
Una llamada final se puede ubicar justo antes del final sintáctico de una función:
función foo ( datos ) { a ( datos ); devolver b ( datos ); } Aquí, ambos a(data)y 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 están necesariamente ubicadas al final sintáctico de una subrutina:
barra de funciones ( datos ) { if ( a ( datos )) { return b ( datos ); } devolver c ( datos ); } Aquí, ambas llamadas a by cestán en posición de cola. Esto se debe a que cada uno de ellos se encuentra al final de if-branch respectivamente, aunque el primero no esté sintácticamente al final del barcuerpo de '.
En este código:
función foo1 ( datos ) { retornar a ( datos ) + 1 ; } función foo2 ( datos ) { var ret = a ( datos ); volver atrás ; } función foo3 ( datos ) { var ret = a ( datos ); retorno ( ret == 0 ) ? 1 : retirado ; } la llamada a a(data)está en la posición final en , pero nofoo2 está en la posición final ni en ni en , porque el control debe regresar a la persona que llama para permitirle inspeccionar o modificar el valor de retorno antes de devolverlo.foo1foo3
El siguiente programa es un ejemplo en Scheme : [8]
;; factorial: número -> número ;; para calcular el producto de todos los positivos ;; números enteros menores o iguales que n. ( definir ( factorial n ) ( si ( = 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: número -> número ;; para calcular el producto de todos los positivos ;; números enteros menores o iguales que n. ( definir ( factorial n ) ( fact-iter 1 n )) ( definir ( fact-iter producto n ) ( if ( = n 0 ) producto ( fact-iter ( * producto n ) ( - n 1 )))) Este programa asume una evaluación del orden de la aplicación . El procedimiento interno fact-iterse autodenomina último 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 fact-iter (1 4) llamar al fact-iter (4 3) llamar al fact-iter (12 2) llamar al fact-iter (24 1) volver 24 volver 24 volver 24 volver 24 volver 24
a la variante más eficiente , tanto en términos de espacio como de tiempo:
llamar factorial (4) llamar al fact-iter (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 llama, ya sea en la pila o en el montón, y el marco de la pila de llamadas fact-iterse reutiliza para el almacenamiento de resultados intermedios. Esto también significa que el programador no necesita preocuparse por quedarse sin espacio en la pila o en el montón para recursiones extremadamente profundas. En implementaciones típicas, la variante recursiva de cola será sustancialmente más rápida que la otra variante, pero sólo por un factor constante.
Algunos programadores que trabajan en lenguajes funcionales reescribirán el código recursivo para que sea recursivo de cola para poder aprovechar esta característica. Esto a menudo requiere agregar un argumento "acumulador" ( producten el ejemplo anterior) a la función. En algunos casos (como el filtrado de listas) y en algunos lenguajes, la recursividad completa puede requerir que una función que antes era puramente funcional se escriba de manera que mute las referencias almacenadas en otras variables. [ cita necesaria ]
Contras del módulo de recursividad de cola es una generalización de la optimización de recursividad de cola introducida por David HD Warren [9] en el contexto de la compilación de Prolog , visto como un lenguaje establecido explícitamente una vez . Fue descrita (aunque sin nombre) 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 (o realizar un número constante de operaciones simples de construcción de datos, en general). Por lo tanto, esta llamada sería una llamada de cola salvo (" módulo ") de dicha operación de contras . Pero anteponer un valor al inicio de una lista al salir de una llamada recursiva es lo mismo que agregar este valor al final de la lista creciente al entrar en la llamada recursiva, creando así la lista como un efecto secundario , como en un Parámetro implícito del acumulador. El siguiente fragmento de prólogo ilustra el concepto:
Por lo tanto, en la traducción recursiva de cola, dicha llamada se transforma creando primero un nuevo nodo de lista y configurando su firstcampo, y luego haciendo la llamada de cola con el puntero al restcampo del nodo como argumento, para ser completado recursivamente. El mismo efecto se logra cuando la recursividad está protegida bajo un constructor de datos evaluado de forma diferida, lo que se logra automáticamente en lenguajes de programación diferidos como Haskell.
El siguiente fragmento define una función recursiva en C que duplica una lista enlazada (con algún código equivalente de Scheme y Prolog como comentarios, para comparar):
De esta forma, la función no es recursiva de cola, porque el control regresa al autor de la llamada 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 ingresar el resultado de la llamada recursiva en el nextcampo después de la llamada. [a]
Entonces 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 una llamada final. [b] Usando el nodo principal centinela para simplificar el código,
La persona que llama ahora se agrega al final de la lista en crecimiento, en lugar de que la persona que llama se anteponga al principio de la lista devuelta. El trabajo ahora se realiza en el camino hacia adelante desde el inicio de la lista, antes de la llamada recursiva que luego continúa, en lugar de retroceder desde el final de la lista, después de que la llamada recursiva haya devuelto su resultado. Por tanto, es similar a la técnica de acumulación de parámetros, que convierte un cálculo recursivo en iterativo.
Característicamente para esta técnica, se crea un marco principal en la pila de llamadas de ejecución, que el destinatario de la llamada recursiva de cola puede reutilizar como su propio marco de llamada si la optimización de llamada de cola 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 final de un procedimiento pueden tratarse mejor como una transferencia directa de control a el procedimiento llamado, eliminando normalmente operaciones innecesarias de manipulación de la pila. [2] Dado que este tipo de "llamadas finales" 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 procedimientos 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 el GOTO era barato en comparación con la llamada a procedimientos. Steele argumentó además que "en general, las llamadas a procedimientos pueden considerarse útiles como declaraciones GOTO que también pasan parámetros y pueden codificarse uniformemente como instrucciones JUMP [de código de máquina]", con las instrucciones de manipulación de la pila de código de máquina "consideradas una optimización (en lugar de ¡viceversa!)". [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 comerciales de Fortran disponibles en ese momento porque el costo de una llamada a un procedimiento en Lisp era mucho menor. En Scheme , un dialecto Lisp desarrollado por Steele con Gerald Jay Sussman , se garantiza que la eliminación de llamadas de cola se implementará en cualquier intérprete. [11]
La recursividad 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 recursividad de cola es la forma más utilizada (y a veces la única disponible) de implementar la iteración. La especificación del lenguaje de Scheme requiere que las llamadas finales 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 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 el x86 ), implementar optimización generalizada de llamadas de cola (incluida la mutua recursión de cola) presenta un problema: si el tamaño del registro de activación del destinatario es diferente del de la persona que llama, entonces puede ser necesaria una limpieza adicional o un cambio de tamaño del marco de la pila. Para estos casos, optimizar la recursividad de cola sigue siendo trivial, pero la optimización general de la llamada de cola 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 las llamadas de cola generales no pueden eliminarse (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 recursividad de cola directa, pero no la recursividad de cola mutua.
Los conjuntos de compiladores GCC , LLVM/Clang e Intel realizan una optimización final 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 es posible que la sintaxis del lenguaje dada no lo admita explícitamente, el compilador puede realizar esta optimización siempre que pueda determinar que los tipos de retorno para la persona que llama y la persona que llama son equivalentes, y que los tipos de argumentos pasados a ambos La función es la misma o requiere la misma cantidad de espacio de almacenamiento total en la pila de llamadas. [18]
Hay varios métodos de implementación disponibles.
Las llamadas de cola a menudo son optimizadas por intérpretes y compiladores de programación funcional y lenguajes de programación lógica para formas de iteración más eficientes . Por ejemplo, los programadores de Scheme comúnmente expresan los bucles while como llamadas a procedimientos en la posición final y confían en el compilador o intérprete de Scheme para sustituir las llamadas finales con instrucciones de salto más eficientes . [19]
Para los compiladores que generan ensamblaje directamente, la eliminación de llamadas de cola es fácil: 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 al lenguaje pseudoensamblador (de hecho, este es un ensamblador x86 válido ):
foo: llamar a B llamar a A ret La eliminación de tail-call 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.
Normalmente, 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 cola. Por ejemplo, en plataformas donde la pila de llamadas no solo contiene la dirección de retorno , sino también los parámetros de la subrutina, es posible que el compilador deba emitir instrucciones para ajustar la pila de llamadas. En dicha plataforma, para el código:
función foo (datos1, datos2) B(datos1) devolver A(datos2)
(donde data1y data2son parámetros) un compilador podría traducirlo como: [c]
foo: mov reg ,[ sp + datos1 ] ; recuperar datos1 del parámetro de pila (sp) en un registro temporal. empujar registro ; poner datos1 en la pila donde B los espera llamar a B ; B usa datos1 estallido ; eliminar datos1 de la pila mov reg ,[ sp + datos2 ] ; recuperar datos2 del parámetro de pila (sp) en un registro temporal. empujar registro ; poner datos2 en la pila donde A lo espera llamar a ; A usa datos2 estallido ; eliminar datos2 de la pila. retiradoUn optimizador de llamadas de cola podría cambiar el código a:
foo: mov reg ,[ sp + datos1 ] ; recuperar datos1 del parámetro de pila (sp) en un registro temporal. empujar registro ; poner datos1 en la pila donde B los espera llamar a B ; B usa datos1 estallido ; eliminar datos1 de la pila mov reg ,[ sp + datos2 ] ; recuperar datos2 del parámetro de pila (sp) en un registro temporal. mov [ sp + datos1 ], reg ; poner datos2 donde A lo espera jmpA ; A usa data2 y regresa inmediatamente a la persona que llama. Este código es más eficiente tanto en términos de velocidad de ejecución como de uso del espacio de pila.
Dado que muchos compiladores de Scheme utilizan C como código de destino intermedio, la recursión final debe codificarse en C sin hacer crecer la pila, incluso si el compilador de C no optimiza las llamadas finales. Muchas implementaciones logran esto mediante el uso de un dispositivo conocido como trampolín , un fragmento de código que llama funciones repetidamente. A todas las funciones se accede 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 a llamar y los parámetros de llamada al trampolín (desde donde se llamó a sí misma), y el trampoline 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 que la iteración pueda continuar indefinidamente.
Es posible implementar trampolines utilizando funciones de orden superior en lenguajes que los admitan, como Groovy , Visual Basic .NET y C# . [20]
Usar un trampolín para todas las llamadas a funciones es bastante más costoso que la llamada a funciones normales en C, 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 inédita de Andrew Appel , [21] en la que C normal Se utilizan llamadas, pero el tamaño de la pila se verifica 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 ("explota") 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 en el trampolín al saltar ocasionalmente desde el Empire State Building". [21] La recolección de basura garantiza que la recursión mutua de cola pueda continuar indefinidamente. Sin embargo, este enfoque requiere que ninguna llamada a función C regrese nunca, ya que no hay garantía de que el marco de pila de la persona que llama 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 recursividad de cola puede estar relacionada con la declaración while , una iteración explícita, por ejemplo transformando
procedimiento foo( x ) si p ( x ) devolver bar( x ) en caso contrario devolver foo(baz( x ))
en
procedimiento foo( x ) mientras es verdadero si p ( x ) return bar( x ) else x ← baz( x )
donde x puede ser una tupla que involucra más de una variable: si es así, se debe tener cuidado al implementar la declaración 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 .
Más generalmente,
procedimiento foo( x ) si p ( x ) devolver bar( x ) de lo contrario si q ( x ) devolver baz( x ) ... de lo contrario, si r ( x ) regresa foo(qux( x )) ... de lo contrario , devuelve foo(quux( x ))
se puede transformar en
procedimiento foo( x ) mientras es verdadero si p ( x ) devuelve bar( x ) en caso contrario si q ( x ) devuelve baz( x ) ... de lo contrario si r ( x ) x ← qux( x ) ... más x ← quux( x )
Por ejemplo, este programa de Julia proporciona una definición recursiva sin cola factdel factorial:
función factorial ( n ) si norte == 0 regresar 1 demás devolver n * factorial ( n - 1 ) finfinDe hecho, n * factorial(n - 1)concluye 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 da una definición recursiva de cola fact_iterdel factorial:
función factorial ( n :: Entero , a :: Entero ) si norte == 0 : devolver un demás retorno factorial ( n - 1 , n * a ) finfinfunción factorial ( n :: Entero ) retorno 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 end return a end función factorial ( n :: Entero ) retorno fact_iter ( n , uno ( n )) fin recuruna forma especial. [22]tailrecmodificador para funciones [30]goto &NAME;[32]@tailrecanotación, lo que genera un error de compilación si la función no es recursiva al final [38]
if ( ls ! = NULL ) { cabeza = malloc ( tamaño de * cabeza ); cabeza -> valor = ls -> valor ; encabezado -> siguiente = duplicar ( ls -> siguiente ); } if ( ls ! = NULL ) { cabeza = malloc ( tamaño de * cabeza ); cabeza -> valor = ls -> valor ; duplicar ( ls -> siguiente , & ( head -> siguiente )); } callinstrucción primero coloca 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 recuperado.