¿Por qué Java no tiene optimización para la recursividad de cola?

92

De lo que he leído: la razón es porque no es fácil determinar qué método se llamará realmente ya que tenemos herencia.

Sin embargo, ¿por qué Java al menos no tiene una optimización de recursión de cola para métodos estáticos y aplica la forma adecuada de llamar a métodos estáticos con el compilador?

¿Por qué Java no tiene ningún soporte para la recursividad de cola?

No estoy seguro si hay alguna dificultad aquí.


Con respecto al duplicado sugerido , como lo explica Jörg W Mittag 1 :

  • La otra pregunta es sobre TCO, esta sobre TRE. TRE es mucho más simple que TCO.
  • Además, la otra pregunta se refiere a qué limitaciones impone la JVM a las implementaciones de lenguaje que desean compilar a la JVM, esta pregunta se refiere a Java, que es el único idioma que no está restringido por la JVM, ya que la especificación de la JVM puede ser modificada por Las mismas personas que diseñan Java.
  • Y, por último, ni siquiera hay una restricción en la JVM sobre TRE, porque la JVM tiene GOTO intramétodo, que es todo lo que se necesita para TRE

1 Formato agregado para llamar los puntos realizados.

InformadoA
fuente
26
Para citar a Eric Lippert : "Las funciones no son baratas; son extremadamente caras y no solo deben justificar su propio costo, sino también el costo de oportunidad de no hacer las otras cien funciones que podríamos haber hecho con ese presupuesto". Java fue diseñado en parte para atraer a los desarrolladores de C / C ++ y la optimización de recursión de cola no está garantizada en esos lenguajes.
Doval
55
Corríjame si me equivoco, pero ¿Eric Lippert es el diseñador de C # que tiene una optimización de recursión de cola?
InformadoA
1
Está en el equipo compilador de C #, sí.
Doval
10
Por lo que entiendo, el JIT podría hacerlo , si se cumplen ciertas condiciones , tal vez. Entonces, en la práctica no puedes confiar en ello. Pero si C # lo tiene o no lo tiene, no es importante para el punto de Eric.
Doval
44
@InstructedA Si profundiza un poco más, puede ver que nunca se hace en el compilador JIT de 32 bits. El JIT de 64 bits es más nuevo e inteligente en muchos aspectos. El compilador experimental aún más nuevo (tanto para 32 como para 64 bits) es aún más inteligente y admitirá la optimización de recursión de cola en IL que no lo solicita explícitamente. Hay otro punto que debe tener en cuenta: los compiladores JIT no tienen mucho tiempo. Están muy optimizados para la velocidad: la aplicación que puede tardar horas en compilarse en C ++ aún tendrá que pasar de IL a nativa en un par de cientos de ms, como máximo (al menos parcialmente).
Luaan

Respuestas:

132

Como lo explicó Brian Goetz (Java Language Architect en Oracle) en este video :

en las clases jdk hay varios métodos sensibles a la seguridad que se basan en contar cuadros de pila entre el código de la biblioteca jdk y el código de llamada para averiguar quién los llama.

Cualquier cosa que cambiara el número de cuadros en la pila rompería esto y causaría un error. Admite que esta fue una razón estúpida, por lo que los desarrolladores de JDK han reemplazado este mecanismo.

Además, menciona que no es una prioridad, sino que la recursión de la cola

eventualmente se hará.

Nota: Esto se aplica a HotSpot y OpenJDK, otras máquinas virtuales pueden variar.

ggovan
fuente
77
¡Me sorprende que haya una respuesta tan corta y seca como esta! Pero realmente parece La respuesta: es posible ahora, por razones técnicas obsoletas que aún no se han hecho, y ahora solo esperamos que alguien decida que es lo suficientemente importante para implementar.
BrianH
1
¿Por qué no implementar una solución alternativa? ¿Como un goto de etiqueta debajo de las cubiertas que simplemente salta a la parte superior de la llamada al método con nuevos valores para los argumentos? Esta sería una optimización en tiempo de compilación y no necesitaría cambiar los marcos de la pila o causar violaciones de seguridad.
James Watkins
2
Será mucho mejor para nosotros si usted u otra persona aquí pueden profundizar y proporcionar específicamente cuáles son esos "métodos sensibles a la seguridad". ¡Gracias!
InformadoA
3
@InstructedA - consulte securingjava.com/chapter-three/chapter-three-6.html que contiene una descripción detallada de cómo funcionaba el sistema Java Security Manager alrededor del lanzamiento de Java 2.
Julio
3
Una solución alternativa es utilizar otro lenguaje JVM. Scala, por ejemplo, hace esto en el compilador, no en tiempo de ejecución.
James Moore
24

Java no tiene una optimización de llamadas de cola por la misma razón que la mayoría de los lenguajes imperativos no la tienen. Los bucles imperativos son el estilo preferido del lenguaje, y el programador puede reemplazar la recursión de cola con bucles imperativos. La complejidad no vale la pena para una característica cuyo uso se desaconseja como una cuestión de estilo.

Esto en el que los programadores quieren escribir a veces en un estilo FP en lenguajes imperativos solo entró en boga en los últimos 10 años más o menos, después de que las computadoras comenzaron a escalar en núcleos en lugar de GHz. Incluso ahora, no es tan popular. Si sugiero reemplazar un bucle imperativo con una recursión de cola en el trabajo, la mitad de los revisores del código se reirían y la otra mitad daría una mirada confusa. Incluso en la programación funcional, generalmente evita la recursión de cola a menos que otras construcciones como las funciones de orden superior no se ajusten perfectamente.

Karl Bielefeldt
fuente
36
Esta respuesta no parece correcta. El hecho de que la recursión de la cola no sea estrictamente necesaria no significa que no sea útil. Las soluciones recursivas son con frecuencia más fáciles de entender que la iteración, pero la falta de llamadas de cola significa que los algoritmos recursivos se vuelven incorrectos para los problemas de gran tamaño que podrían arruinar la pila. Se trata de la corrección, no del rendimiento (la velocidad de cambio por simplicidad a menudo vale la pena). Como señala la respuesta correcta, la falta de llamadas de cola se debe a un extraño modelo de seguridad que depende de los seguimientos de la pila, no al fanatismo imperativo.
amon
44
@amon James Gosling dijo una vez que no agregaría una característica a Java a menos que varias personas lo solicitaran , y solo entonces lo consideraría . Por lo tanto, no me sorprendería si parte de la respuesta fuera realmente "siempre se puede usar un forbucle" (y de la misma manera para funciones de primera clase frente a objetos). No iría tan lejos como para llamarlo "intolerancia imperativa", pero no creo que hubiera tenido una gran demanda en 1995, cuando la principal preocupación era probablemente la velocidad de Java y la falta de genéricos.
Doval
77
@amon, un modelo de seguridad me parece una razón legítima para no agregar TCO a un idioma preexistente, pero una mala razón para no diseñarlo en el idioma en primer lugar. No descarta una característica importante visible para el programador para incluir una característica menor detrás de escena. "¿Por qué Java 8 no tiene TCO?" Es una pregunta muy diferente a "¿Por qué Java 1.0 no tiene TCO?" Estaba respondiendo lo último.
Karl Bielefeldt
3
@rwong, puede transformar cualquier función recursiva en una iterativa. (Si puedo, he escrito un ejemplo aquí )
alain
3
@ZanLynx depende del tipo de problema. Por ejemplo, el patrón de visitante puede beneficiarse del TCO (dependiendo de los detalles de la estructura y el visitante) sin tener nada que ver con FP. Pasar por máquinas de estado es similar, aunque la transformación con trampolines parece un poco más natural (según el problema). Además, aunque puede, técnicamente, implementar árboles usando bucles, creo que el consenso es que la recursión es mucho más natural (similar para DFS, aunque en este caso puede evitar la recursión debido a los límites de pila incluso con TCO).
Maciej Piechotka
5

Java no tiene una optimización de llamadas altas porque la JVM no tiene un código de bytes para las llamadas de cola (a algún puntero de función estáticamente desconocido , por ejemplo, un método en alguna vtable).

Parece que por razones sociales (y quizás técnicas), agregar una nueva operación de bytecode en la JVM (lo que lo haría incompatible con versiones anteriores de esa JVM) es terriblemente difícil para el propietario de la especificación JVM.

Las razones técnicas para no agregar un nuevo código de bytes en la especificación JVM incluyen el hecho de que las implementaciones JVM de la vida real son piezas de software terriblemente complejas (por ejemplo, debido a las muchas optimizaciones JIT que está haciendo).

Las llamadas de cola a alguna función desconocida requieren reemplazar el marco de pila actual por uno nuevo, y esa operación debe ubicarse en la JVM (no se trata solo de cambiar el compilador generador de bytecode).

Basile Starynkevitch
fuente
17
La pregunta no se trata de llamadas de cola, se trata de la recursividad de cola. Y la pregunta no es sobre el lenguaje de código de bytes JVM, sino sobre el lenguaje de programación Java, que es un lenguaje completamente diferente. Scala compila a JVM bytecode (entre otros) y tiene eliminación de recursión de cola. Las implementaciones de esquemas en la JVM tienen llamadas completas adecuadas. Java 7 (JVM Spec, 3rd Ed.) Agregó un nuevo bytecode. J9 JVM de IBM realiza TCO incluso sin necesidad de un bytecode especial.
Jörg W Mittag
1
@ JörgWMittag: Eso es cierto, pero luego, me pregunto si es realmente cierto que el lenguaje de programación Java no tiene llamadas de cola adecuadas. Puede ser más preciso afirmar que el lenguaje de programación Java no tiene que tener llamadas de cola adecuadas, ya que nada en las especificaciones lo exige. (Es decir: no estoy seguro de que algo en la especificación realmente prohíba que una implementación elimine las llamadas de cola. Simplemente no se menciona.)
ruakh
4

A menos que un idioma tenga una sintaxis especial para hacer una llamada de cola (recursiva o no) y un compilador graznará cuando se solicite una llamada de cola pero no se pueda generar, la optimización de "cola" o recursión de cola "opcional" generará situaciones en las que una pieza de código puede requerir menos de 100 bytes de pila en una máquina, pero más de 100,000,000 bytes de pila en otra. Tal diferencia debería considerarse cualitativa más que simplemente cuantitativa.

Se espera que las máquinas puedan tener diferentes tamaños de pila y, por lo tanto, siempre es posible que el código funcione en una máquina, pero sople la pila en otra. En general, sin embargo, el código que funcionará en una máquina incluso cuando la pila está artificialmente restringida probablemente funcionará en todas las máquinas con tamaños de pila "normales". Sin embargo, si un método que tiene una profundidad de 1,000,000 es optimizado en una máquina pero no en otra, la ejecución en la máquina anterior probablemente funcionará incluso si su pila es inusualmente pequeña, y fallará en la segunda incluso si su pila es inusualmente grande .

Super gato
fuente
2

Creo que la recursión de llamadas de cola no se usa en Java principalmente porque hacerlo alteraría los rastros de la pila y, por lo tanto, haría que la depuración de un programa sea mucho más difícil. Creo que uno de los objetivos principales de Java es permitir que los programadores depuren fácilmente su código, y el seguimiento de la pila es esencial para hacerlo, especialmente en un entorno de programación altamente orientado a objetos. Dado que la iteración podría usarse en su lugar, el comité de idiomas debe haber pensado que no vale la pena agregar una recursión de cola.

molesto_quid
fuente