Optimización de llamadas Java Tail
- ¿Qué es la optimización de llamadas de cola?
- Razones para no tener optimización de llamadas de cola en Java
- ¿Hay alguna manera de simular la optimización de llamadas de cola en Java?
Este tutorial habla sobre la optimización de llamadas de cola (también abordado como TCO) y sus razones para no existir en Java. También veremos otras formas que podemos usar para simular el TCO en Java.
¿Qué es la optimización de llamadas de cola?
La optimización de la llamada final es un proceso en el que podemos evitar asignar un nuevo marco de pila para una función porque la función que llama devolverá un valor que recibe de la función llamada.
Uno de los usos más comunes es la recursión de cola (una función recursiva en la que una función se llama a sí misma al final/cola), donde el método recursivo está escrito para aprovechar la optimización de llamadas de cola y puede usar espacio de pila constante.
El Scheme es uno de esos lenguajes de programación que garantizan en la especificación que cualquier implementación debe servir para esta optimización. Entonces, los siguientes son dos ejemplos del método factorial en el lenguaje de programación Scheme.
Código de ejemplo uno (sin cola recursiva):
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
Código de ejemplo dos (con cola recursiva):
(define (factorial n)
(define (factorial-tail n accum)
(if (= n 0) accum
(factorial-tail (- n 1) (* n accum))))
(factorial-tail n 1))
En el código de ejemplo uno, la función no es una cola recursiva. Es porque cada vez que se realiza una llamada recursiva (considerando un ejemplo factorial), el método debe realizar un seguimiento de la multiplicación que debe hacer con los resultados después de que regrese la llamada.
Como tal, una pila tiene el siguiente aspecto.
(factorial 3)
(* 3 (factorial 2))
(* 3 (* 2 (factorial 1)))
(* 3 (* 2 (* 1 (factorial 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6
Por el contrario, la traza de pila para un factorial recursivo de cola sería como se indica a continuación.
(factorial 3)
(factorial-tail 3 1)
(factorial-tail 2 3)
(factorial-tail 1 6)
(factorial-tail 0 6)
6
Solo estamos obligados a realizar un seguimiento de los mismos datos para cada llamada a factorial-tail.
La razón es que estamos devolviendo un valor que obtenemos directamente a un tope, lo que significa que, incluso si tuviéramos que llamar (factorial 1000000), solo necesitamos la misma cantidad de espacio que se requiere para ( factoriales 3).
Este no es el caso cuando consideramos factorial recursivo sin cola, y los valores grandes pueden resultar en un desbordamiento de pila.
Razones para no tener optimización de llamadas de cola en Java
Actualmente, en el nivel del compilador, la optimización de llamadas de cola de Java no se admite en Java simple. Debido a la presencia de la herencia, puede que no sea un trabajo fácil encontrar el método que se está llamando.
Además, el presente mecanismo de conteo de pilas no permite implementar pronto este tipo de optimización. Puede haber una razón para evitar el cambio drástico en la forma en que funciona el idioma cada año.
La primera razón es que Tail Call Optimization es costoso. En segundo lugar, de acuerdo con una regla en Java, obtenemos el seguimiento de la pila cada vez que enfrentamos un error.
Y los seguimientos de pila son conceptos bien definidos que difícilmente pueden rastrear un marco de pila para cada llamada lógica. Esto no será posible si la optimización de llamadas de cola existe en Java.
En tercer lugar, la optimización de llamadas de cola como modelo es la forma de hacer las cosas, pero no la única. En general, no es tan difícil refactorizar en un algoritmo no recursivo basado en bucles para cualquier cosa que se pueda escribir como la aplicación recursiva de TCO.
¿Entonces, qué debemos hacer? Podemos usar el bucle while o for en su lugar.
¿Hay alguna manera de simular la optimización de llamadas de cola en Java?
Aunque Java, la máquina virtual, tiene nuevas características que pueden facilitar las cosas para otros, los lenguajes de programación que no son de Java se compilan en los archivos de clase para ejecutarse en un tiempo de ejecución de Java para admitir la optimización de llamadas de cola.
Le sugerimos que mire los siguientes dos videos para comprender las cosas en general porque no todas las características siempre están justificadas, particularmente cuando el idioma es uno de los idiomas más populares.
- Video 1: Brian Goetz - Stewardship: the Sobering Parts
- Vídeo 2: Futuros de la plataforma y el lenguaje Java
Por lo tanto, no estamos seguros de qué enfoque se debe usar para usar TCO en Java; está bien explicado en la propuesta de Project Loom.
Sin embargo, creemos que todavía hay otras formas que podemos usar para simular la optimización de llamadas de cola en Java. La primera es usar algún otro lenguaje JVM, por ejemplo, Scala.
La segunda solución puede ser utilizando la expresión lambda. O, si te atreves, puedes intentar algo peligroso, como este.
