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 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 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 o 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 , permitiendo así 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 de cola. Sin embargo, en los lenguajes de programación funcionales , la eliminación de la llamada 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 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 hermanos o las llamadas de cola a funciones que toman y devuelven los mismos tipos que el llamador. [3]
Descripción
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 su lugar, la eliminación de la llamada de cola solo realiza los cambios mínimos necesarios en el marco de la pila antes de pasarlo, [4] y la función de llamada de cola volverá directamente a la persona que llama 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 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 a funciones 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 llamadas de cola a menudo reduce los requisitos de espacio de pila asintóticos de lineal, o O (n), a constante, o O (1). Por lo tanto, las definiciones estándar de algunos lenguajes de programación, como Scheme , [5] [6] y los lenguajes de la familia ML, entre otros , requieren la eliminación de la llamada de cola . 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 de cola 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 sin espacio de pila rápidamente.
Forma sintáctica
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í, ambos a(data)
y b(data)
son llamadas, pero b
es lo último que ejecuta el procedimiento antes de regresar y, por lo tanto, está en la posición final. Sin embargo, no todas las llamadas de cola están necesariamente ubicadas en el extremo sintáctico de una subrutina:
barra de función ( datos ) { if ( a ( datos ) ) { devolver b ( datos ); } return c ( datos ); }
En este caso, ambas llamadas a b
y c
están en posición de la 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 bar
cuerpo de.
En este código:
function foo1 ( datos ) { return a ( datos ) + 1 ; }
función foo2 ( datos ) { var ret = a ( datos ); return ret ; }
función foo3 ( datos ) { var ret = a ( datos ); volver ( ret == 0 ) ? 1 : ret ; }
la llamada a a(data)
se encuentra en posición de la cola en el foo2
, pero es no en la posición de la cola, ya sea en foo1
o en foo3
, ya que el control debe volver a la llamada para permitir que se inspeccione o modificar el valor de retorno antes de devolverlo.
Programas de ejemplo
El siguiente programa es un ejemplo en Scheme : [8]
;; factorial: número -> número ;; calcular el producto de todo positivo ;; enteros menores o iguales an. ( definir ( factorial n ) ( si ( = n 1 ) 1 ( * n ( factorial ( - n 1 )))))
Esto no está escrito en un estilo de recursividad 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 ;; calcular el producto de todo positivo ;; enteros menores o iguales an. ( definir ( factorial n ) ( fact-iter 1 n )) ( definir ( fact-iter producto n ) ( if ( < n 2 ) product ( fact-iter ( * producto n ) ( - n 1 ))))
Este programa asume una evaluación de orden aplicativo . El procedimiento interno se fact-iter
llama a sí mismo ú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]
llamada factorial (4) llamar fact-iter (1 4) llamar fact-iter (4 3) llamar fact-iter (12 2) llamar fact-iter (24 1) volver 24 volver 24 volver 24 volver 24 volver 24
en la variante más eficiente , en términos de espacio y tiempo:
llamada factorial (4) llamar 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 para fact-iter
se reutiliza para el almacenamiento de resultados intermedios. Esto también significa que el programador no necesita preocuparse por quedarse sin pila o espacio de pila para recursiones extremadamente profundas. En implementaciones típicas, la variante de cola recursiva será sustancialmente más rápida que la otra variante, pero solo por un factor constante.
Algunos programadores que trabajan en lenguajes funcionales reescribirán código recursivo para que sea recursivo en cola para que puedan aprovechar esta característica. Esto a menudo requiere la adición de un argumento "acumulador" ( product
en el ejemplo anterior) a la función. En algunos casos (como listas de filtrado) y en algunos lenguajes, la recursividad de cola completa puede requerir que se escriba una función que antes era puramente funcional, de modo que mute las referencias almacenadas en otras variables. [ cita requerida ]
Contras del módulo de recursión de cola
Tail recurssion modulo cons es una generalización de la optimización de la recursividad de la 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 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 una lista devuelta (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 para (" módulo ") dicha operación de contras . 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 entrar en la llamada recursiva, construyendo así la lista como un efecto secundario , como en un parámetro acumulador implícito. El siguiente fragmento de Prolog ilustra el concepto:
Ejemplo de prólogo
% tail recursive modulo contras: partición ([], _ , [], []). partición ([ X | Xs ], Pivot , [ X | Rest ], Bigs ) : - X @ < Pivot , !, partición ( Xs , Pivot , Rest , Bigs ). partición ([ X | Xs ], Pivot , Smalls , [ X | Rest ]) : - partición ( Xs , Pivot , Smalls , Rest ). | - En Haskell, recursividad protegida: partición :: Ord a => [ a ] -> a -> ([ a ], [ a ]) partición [] _ = ( [] , [] ) partición ( x : xs ) p | x < p = ( x : a , b ) | de lo contrario = ( a , x : b ) donde ( a , b ) = partición xs p |
% Con unificaciones explícitas: % traducción recursiva no final: partición ([], _ , [], []). partición ( L , Pivot , Smalls , Bigs ) : - L = [ X | Xs ], ( X @ < Pivot -> partición ( Xs , Pivot , Rest , Bigs ), Smalls = [ X | Rest ] ; partición ( Xs , Pivot , Smalls , Rest ), Bigs = [ X | Rest ] ). | % Con unificaciones explícitas: % cola traducción recursiva: partición ([], _ , [], []). partición ( L , Pivot , Smalls , Bigs ) : - L = [ X | Xs ], ( X @ < Pivot -> Smalls = [ X | Rest ], partición ( Xs , Pivot , Rest , Bigs ) ; Bigs = [ X | Rest ], partición ( Xs , Pivot , Smalls , Rest ) ). |
Por lo tanto, en la traducción recursiva de cola, dicha llamada se transforma para crear primero un nuevo nodo de lista y establecer su first
campo, y luego hacer una llamada de cola con el puntero al rest
campo del nodo como argumento, que se completará de forma recursiva.
C ejemplo
El siguiente fragmento define una función recursiva en C que duplica una lista vinculada:
typedef struct list { void * value ; lista de estructuras * siguiente ; } lista ; lista * duplicado ( lista constante * ls ) { lista * cabeza = NULL ; if ( ls ! = NULL ) { lista * p = duplicado ( ls -> siguiente ); cabeza = malloc ( tamaño de * cabeza ); cabeza -> valor = ls -> valor ; cabeza -> siguiente = p ; } cabeza de retorno ; } | ;; en Scheme, ( definir ( duplicar ls ) ( si ( no ( nulo? ls )) ( cons ( car ls ) ( duplicar ( cdr ls ))) ' ())) |
%% en Prólogo, dup ([ X | Xs ], R ): - dup ( Xs , Ys ), R = [ X | Ys ]. dup ([], []). |
De esta forma, la función no es recursiva en cola, porque el control regresa a la persona que llama después de que la llamada recursiva duplica el resto de la lista de entrada. Incluso si se tratara de asignar la cabeza nodo antes de duplicar el resto, todavía tendría que conectar el resultado de la llamada recursiva en el next
campo después de la llamada. [a] Entonces, la función es casi recursiva en la cola. El método de Warren empuja la responsabilidad de completar el next
campo en la propia llamada recursiva, que por lo tanto se convierte en llamada de cola:
typedef struct list { void * value ; lista de estructuras * siguiente ; } lista ; void duplicate_aux ( lista constante * ls , lista * fin ); lista * duplicado ( lista constante * ls ) { encabezado de lista ; duplicate_aux ( ls , & head ); cabeza de retorno . siguiente ; }void duplicate_aux ( const list * ls , list * end ) { if ( ls ! = NULL ) { end -> next = malloc ( sizeof * end ); fin -> siguiente -> valor = ls -> valor ; duplicate_aux ( ls -> siguiente , final -> siguiente ); } else { end -> next = NULL ; } } | ;; en Scheme, ( define ( duplicar ls ) ( let (( head ( lista 1 ))) ( let dup (( ls ls ) ( end head )) ( cond (( not ( null? ls )) ( set-cdr! end ( lista ( car ls ))) ( dup ( cdr ls ) ( cdr end ))))) ( cdr head ))) |
%% en Prólogo, dup ([ X | Xs ], R ): - R = [ X | Ys ], dup ( Xs , Ys ). dup ([], []). |
(Se utiliza un nodo de cabeza centinela para simplificar el código). El destinatario de la llamada ahora se agrega al final de la lista en crecimiento, en lugar de que la persona que llama antepone el comienzo 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 avanza, en lugar de hacia atrás 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, convirtiendo un cálculo recursivo en uno iterativo.
De manera característica para esta técnica, se crea un marco padre 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 la llamada de cola está presente.
La implementación recursiva de cola ahora se puede convertir en una forma explícitamente iterativa, como un bucle acumulativo :
typedef struct list { void * value ; lista de estructuras * siguiente ; } lista ; lista * duplicado ( lista constante * ls ) { encabezado de lista , * fin ; end = & head ; while ( ls ! = NULL ) { end -> next = malloc ( sizeof * end ); fin -> siguiente -> valor = ls -> valor ; ls = ls -> siguiente ; fin = fin -> siguiente ; } fin -> siguiente = NULO ; cabeza de retorno . siguiente ; } | ;; en Scheme, ( define ( duplicar ls ) ( let (( head ( lista 1 ))) ( do (( end head ( cdr end )) ( ls ls ( cdr ls ))) (( null? ls ) ( cdr head ) ) ( set-cdr! end ( list ( car ls )))))) |
%% en Prolog, %% N / A |
Historia
En un documento entregado a la conferencia ACM en Seattle en 1977, Guy L. Steele resumió el debate sobre el 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 a el procedimiento llamado, que normalmente elimina las operaciones de manipulación de pila innecesarias. [2] Dado que tales "llamadas de cola" son muy comunes en Lisp , un lenguaje donde las llamadas a procedimientos son ubicuas, 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 de procedimiento mal implementadas habían llevado a una percepción artificial de que el GOTO era barato en comparación con la llamada de procedimiento. 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 [código máquina]", y las instrucciones de manipulación de pila de código máquina "se consideran una optimización (en lugar de ¡viceversa!)". [2] Steele citó evidencia de que los algoritmos numéricos bien optimizados en Lisp podrían ejecutarse más rápido que el código producido por los compiladores comerciales Fortran disponibles en ese momento porque el costo de una llamada a procedimiento en Lisp era mucho menor. En Scheme , un dialecto Lisp desarrollado por Steele con Gerald Jay Sussman , se garantiza la implementación de la eliminación de llamadas de cola en cualquier intérprete. [11]
Métodos de implementación
La recursividad de cola es importante para algunos lenguajes de alto nivel , especialmente lenguajes funcionales y lógicos y miembros de la familia Lisp . En estos lenguajes, la recursividad de cola es la forma más utilizada (y a veces la única forma disponible) de implementar la iteración. La especificación de lenguaje de Scheme requiere que las llamadas de cola se optimicen para no hacer crecer la pila. Las llamadas de cola se pueden hacer explícitamente en Perl , con una variante de la instrucción "goto" que toma un nombre de función: goto &NAME
[12]
Sin embargo, para implementaciones de lenguaje que almacenan argumentos de función 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 ), implementar la optimización de llamadas de cola generalizada (incluida la cola mutua recursividad) presenta un problema: si el tamaño del registro de activación de la persona que llama es diferente al de la persona que llama, es posible que se requiera una limpieza adicional o un cambio de tamaño del marco de la pila. Para estos casos, optimizar la recursividad de la 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 finales se pueden eliminar (ya que esto reutiliza la pila de llamadas existente), pero las llamadas finales generales no pueden ser (ya que esto cambia la pila de llamadas). [13] [14] Como resultado, los lenguajes funcionales como Scala que apuntan a la JVM pueden implementar eficientemente la recursividad de cola directa, pero no la recursividad de cola mutua.
Los conjuntos de compiladores GCC , LLVM / Clang e Intel realizan la optimización de llamadas de cola para C y otros lenguajes en niveles de optimización más altos o cuando -foptimize-sibling-calls
se pasa la opción. [15] [16] [17] Aunque la sintaxis del lenguaje dada puede no admitirla explícitamente, el compilador puede hacer esta optimización siempre que pueda determinar que los tipos de retorno para el llamador y el destinatario son equivalentes, y que los tipos de argumentos pasados a ambos función son iguales o requieren la misma cantidad de espacio de almacenamiento total en la pila de llamadas. [18]
Hay varios métodos de implementación disponibles.
En montaje
Los intérpretes y compiladores de programación funcional y lenguajes de programación lógica optimizan las llamadas de cola a formas más eficientes de iteración . Por ejemplo, los programadores de Scheme comúnmente expresan bucles while como llamadas a procedimientos en posición de cola y confían en el compilador o intérprete de Scheme para sustituir las llamadas de cola con instrucciones de salto más eficientes . [19]
Para los compiladores que generan ensamblado directamente, la eliminación de la llamada final es fácil: basta con reemplazar un código de operación de llamada con 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 pseudo- ensamblador (de hecho, este es un ensamblado x86 válido ):
foo: llamar B llamar A ret
La eliminación de la llamada de cola reemplaza las dos últimas líneas con una sola instrucción de salto:
foo: llamar B jmp A
Una vez A
completada la subrutina , volverá directamente a la dirección de retorno de foo
, omitiendo la ret
declaración innecesaria .
Normalmente, las subrutinas a las que se llama deben proporcionarse 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 final. 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, el compilador puede necesitar emitir instrucciones para ajustar la pila de llamadas. En tal plataforma, para el código:
función foo (datos1, datos2) B (dato1) devuelve A (data2)
(donde data1
y data2
son parámetros) un compilador podría traducir eso como: [b]
foo: mov reg , [ sp + data1 ] ; recuperar datos1 del parámetro stack (sp) en un registro temporal. empujar reg ; poner data1 en la pila donde B lo espera llamar a B ; B usa data1 pop ; eliminar data1 de la pila mov reg , [ sp + data2 ] ; recuperar datos2 del parámetro stack (sp) en un registro temporal. empujar reg ; poner data2 en la pila donde A lo espera llamar A ; A usa data2 pop ; eliminar data2 de la pila. retirado
Un optimizador de llamadas de cola podría cambiar el código a:
foo: mov reg , [ sp + data1 ] ; recuperar datos1 del parámetro stack (sp) en un registro temporal. empujar reg ; poner data1 en la pila donde B lo espera llamar a B ; B usa data1 pop ; eliminar data1 de la pila mov reg , [ sp + data2 ] ; recuperar datos2 del parámetro stack (sp) en un registro temporal. mov [ sp + data1 ], reg ; poner data2 donde A lo espera jmp A ; 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 en el uso del espacio de la pila.
A través del trampolín
Dado que muchos compiladores de Scheme usan C como código de destino intermedio, la recursividad 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 a llamar y los parámetros de llamada al trampolín (desde el cual 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 asegura que la pila de C no crezca y la iteración pueda continuar indefinidamente.
Es posible implementar trampolines usando funciones de orden superior en lenguajes que los 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 caro 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 C normal se utilizan llamadas, pero el tamaño de la pila se comprueba 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 al mover todos los datos en vivo a un montón separado. Después de esto, la pila se desenrolla ("reventa") 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 saltos en el trampolín saltando ocasionalmente desde el Empire State Building". [21] La recolección de basura asegura que la recursividad de cola mutua pueda continuar indefinidamente. Sin embargo, este enfoque requiere que nunca regrese ninguna llamada a la función C, ya que no hay garantía de que el marco de pila de su llamador todavía exista; por lo tanto, implica una reescritura interna mucho más dramática del código del programa: estilo de continuación-paso .
Relación con la construcción while
La recursividad de cola se puede relacionar con el operador de flujo de control while mediante una transformación como la siguiente:
la función foo ( x ) es : si el predicado ( x ) a continuación, volver foo (bar ( x )) otra vuelta Baz ( x )
La construcción anterior se transforma en:
la función foo ( x ) es : while predicado ( x ) hacer : x ← bar ( x ) return baz ( x )
En lo anterior, x puede ser una tupla que involucra más de una variable: si es así, se debe tener cuidado al diseñar la instrucción de asignación x ← bar ( x ) para que se respeten las dependencias. Es posible que deba introducir variables auxiliares o utilizar una construcción de intercambio .
Los usos más generales de la recursividad de cola pueden estar relacionados con los operadores de flujo de control, como romper y continuar , como se muestra a continuación:
función foo ( x ) es : si p ( x ) a continuación de retorno bar ( x ) más si q ( x ) a continuación, volver baz ( x ) ... else if t ( x ) a continuación, volver foo (quux ( x )) ... si no devuelve foo (quuux ( x ))
donde bar y baz son llamadas de retorno directas, mientras que quux y quuux implican una llamada de cola recursiva a foo . Se da una traducción de la siguiente manera:
la función foo ( x ) es : hacer : si p ( x ) entonces x ← barra ( x ) romper de lo contrario si q ( x ) entonces x ← baz ( x ) romper ... de lo contrario, si t ( x ) entonces x ← quux ( x ) continuar ... else x ← quuux ( x ) continuar bucle return x
Por idioma
- Haskell - Sí [22]
- Erlang - Sí
- Common Lisp : algunas implementaciones realizan la optimización de la llamada de cola durante la compilación si se optimizan para la velocidad
- JavaScript : los motores compatibles con ECMAScript 6.0 deben tener llamadas de cola [23] que ahora se implementan en Safari / WebKit [24] pero rechazadas por V8 y SpiderMonkey
- Lua - La recursividad de la cola es requerida por la definición del lenguaje [25]
- OCaml - Sí
- Python : las implementaciones estándar de Python no realizan la optimización de llamadas finales, aunque hay un módulo de terceros disponible para hacer esto. [26] El inventor del lenguaje Guido van Rossum sostiene que los seguimientos de la pila se alteran mediante la eliminación de llamadas de cola, lo que dificulta la depuración, y prefiere que los programadores usen iteraciones explícitas en su lugar [27]
- Rust : la optimización del tail-call puede realizarse en circunstancias limitadas, pero no está garantizada [28]
- Esquema - Requerido por la definición de lenguaje [29] [30]
- Raqueta - Sí [31]
- Tcl - Desde Tcl 8.6, Tcl tiene un comando tailcall [32]
- Kotlin - Tiene modificador tailrec para funciones [33]
- Elixir : Elixir implementa la optimización de la llamada de cola [34] Al igual que todos los lenguajes que actualmente se dirigen a BEAM VM.
- Perl : explícito con una variante de la declaración "goto" que toma un nombre de función:
goto &NAME
[35] - Scala - El compilador optimiza automáticamente las funciones recursivas de cola. Dichas funciones también se pueden marcar opcionalmente con una
@tailrec
anotación, lo que lo convierte en un error de compilación si la función no es recursiva al final [36] - Objective-C : el compilador optimiza las llamadas de cola cuando se especifica la opción -O1 (o superior), pero las llamadas agregadas por el conteo automático de referencias (ARC) lo altera fácilmente .
- F # : F # implementa el TCO de forma predeterminada siempre que sea posible [37]
- Clojure : Clojure tiene una forma especial recurrente . [38]
- Ir - no [39]
Ver también
- Recursión de curso de valores
- Recursión (informática)
- Expansión en línea
- Subrutina de hojas
- Corecursion
Notas
- ^ Así:
if ( ls ! = NULL ) { head = malloc ( sizeof * head ); cabeza -> valor = ls -> valor ; cabeza -> siguiente = duplicar ( ls -> siguiente ); }
- ^ La
call
instrucción primero empuja 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. Laret
instrucción primero saca una ubicación de código de la pila, luego realiza un salto incondicional a la ubicación del código recuperado.
Referencias
- ^ Steven Muchnick; Muchnick y Asociados (15 de agosto de 1997). Implementación avanzada del diseño del compilador . Morgan Kaufmann. ISBN 978-1-55860-320-2.
- ^ a b c Steele, Guy Lewis (1977). "Desmentir el mito de la" llamada a procedimiento costoso "o las implementaciones de llamadas a procedimiento consideradas perjudiciales o, LAMBDA: The Ultimate GOTO". Actas de la conferencia anual de 1977 sobre - ACM '77 . págs. 153-162. doi : 10.1145 / 800179.810196 . hdl : 1721,1 / 5753 . ISBN 978-1-4503-2308-6.
- ^ "El generador de código independiente de destino LLVM - documentación LLVM 7" . llvm.org .
- ^ "recursividad - uso de memoria de pila para llamadas de cola - informática teórica" . Cstheory.stackexchange.com. 2011-07-29 . Consultado el 21 de marzo de 2013 .
- ^ a b "Revisado ^ 6 Informe sobre el esquema de lenguaje algorítmico" . R6rs.org . Consultado el 21 de marzo de 2013 .
- ^ "Informe revisado ^ 6 sobre el esquema de lenguaje algorítmico - Justificación" . R6rs.org . Consultado el 21 de marzo de 2013 .
- ^ "Revisado ^ 6 Informe sobre el esquema de lenguaje algorítmico" . R6rs.org . Consultado el 21 de marzo de 2013 .
- ^ a b Sussman, GJ; Abelson, Hal (1984). Estructura e interpretación de programas informáticos . Cambridge, MA: MIT Press. ISBN 0-262-01077-1.
- ^ DHD Warren, Informe de investigación de DAI 141 , Universidad de Edimburgo, 1980.
- ^ Daniel P. Friedman y David S. Wise, Informe técnico TR19: Desenrollar recursiones estructuradas en iteraciones , Universidad de Indiana, diciembre de 1974.
- ^ R5RS Sec. 3,5, Richard Kelsey; William Clinger; Jonathan Rees; et al. (Agosto de 1998). " 5 Informe revisado sobre el esquema de lenguaje algorítmico" . Computación simbólica y de orden superior . 11 (1): 7–105. doi : 10.1023 / A: 1010051815785 .
- ^ Detalles de contacto. "ir a" . perldoc.perl.org . Consultado el 21 de marzo de 2013 .
- ^ " ¿Cuál es la diferencia entre las llamadas de cola y la recursión de cola? ", Stack Overflow
- ^ " ¿Qué limitaciones impone la JVM en la optimización de llamadas finales ", Stack Exchange de programadores
- ^ Lattner, Chris. "Manual de referencia de lenguaje LLVM, sección: Generador de código independiente de destino LLVM, sub: Optimización de llamadas de cola" . La infraestructura del compilador LLVM . El Proyecto LLVM . Consultado el 24 de junio de 2018 .
- ^ "Uso de la colección de compiladores GNU (GCC): Optimizar opciones" . gcc.gnu.org .
- ^ "foptimize-sibling-calls" . software.intel.com .
- ^ "Abordar las llamadas de cola de C ++" .
- ^ Probst, Mark (20 de julio de 2000). "recursividad de cola adecuada para gcc" . Proyecto GCC . Consultado el 10 de marzo de 2015 .
- ^ Samuel Jack, rebotando en tu cola . Diversión funcional . 9 de abril de 2008.
- ^ a b Henry Baker, "Los contras no deben contrarrestar sus argumentos, parte II: Cheney sobre la MTA"
- ^ "Recursión de cola - HaskellWiki" . wiki.haskell.org . Consultado el 8 de junio de 2019 .
- ^ Beres-Deak, Adam. "Vale la pena verlo: Douglas Crockford hablando sobre las nuevas partes buenas de JavaScript en 2014" . bdadam.com .
- ^ "ECMAScript 6 en WebKit" . 13 de octubre de 2015.
- ^ "Manual de referencia de Lua 5.3" . www.lua.org .
- ^ "baruchel / tco" . GitHub .
- ^ Rossum, Guido Van (22 de abril de 2009). "Neopythonic: Eliminación de la recursividad de la cola" .
- ^ "Preguntas frecuentes sobre Rust" . prev.rust-lang.org .
- ^ "Informe revisado ^ 5 sobre el esquema de lenguaje algorítmico" . www.schemers.org .
- ^ "Revisado ^ 6 Informe sobre el esquema de lenguaje algorítmico" . www.r6rs.org .
- ^ "La referencia de la raqueta" . docs.racket-lang.org .
- ^ "página de manual tailcall - Comandos integrados de Tcl" . www.tcl.tk .
- ^ "Funciones: infix, vararg, tailrec - Lenguaje de programación Kotlin" . Kotlin .
- ^ "Recursión" . elixir-lang.github.com .
- ^ "goto - perldoc.perl.org" . perldoc.perl.org .
- ^ "Biblioteca estándar de Scala 2.13.0 - scala.annotation.tailrec" . www.scala-lang.org . Consultado el 20 de junio de 2019 .
- ^ "Tail Calls en F #" . msdn . Microsoft.
- ^ "(recur expr *)" . clojure.org .
- ^ "propuesta: Ir 2: agregar convertido en declaración para apoyar llamadas de cola" . github.com .
Este artículo se basa en material extraído del Diccionario gratuito de informática en línea antes del 1 de noviembre de 2008 e incorporado bajo los términos de "renovación de licencias" de la GFDL , versión 1.3 o posterior.