vi esta cita en la pregunta: What is a good functional language on which to build a web service?¿Evita la JVM las optimizaciones de cola?
Scala, en particular, no soporta la eliminación de llamada final, excepto en las funciones de auto-recursivo, lo que limita el tipo de composición que puede hacer (esto es una limitación fundamental de la JVM).
¿Es esto verdad? Si es así, ¿qué tiene la JVM que crea esta limitación fundamental?
Este post: Recursion or Iteration? podría ayudar.
En resumen, la optimización de la cola de llamada es difícil de realizar en la JVM debido al modelo de seguridad y la necesidad de tener siempre un rastro de pila disponible. En teoría, estos requisitos podrían ser compatibles, pero probablemente requerirían un nuevo bytecode (ver John Rose's informal proposal).
También hay una discusión más Sun bug #4726340, donde la evaluación (de 2002) termina:
creo que esto podría hacerse, sin embargo, pero no es una tarea fácil.
Actualmente, hay algunos trabajos en curso en el proyecto Da Vinci Machine. El estado del subproyecto de llamada final se enumera como "proto 80%"; es poco probable que llegue a Java 7, pero creo que tiene muchas posibilidades Java 8.
Además del documento vinculado en Lambda The Ultimate (del enlace de mmyers publicado arriba), John Rose de Sun tiene algo más que decir sobre la optimización de llamadas de cola.
http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm
He oído que podría implementarse en la JVM algún día. El soporte de llamada de cola, entre otras cosas, se está estudiando en la máquina Da Vinci.
La limitación fundamental es simplemente que la JVM no proporciona cola de llamadas en su código de bytes y, en consecuencia, no hay forma directa de un lenguaje construido sobre la JVM para proporcionar la cola llama a sí misma. Hay soluciones que pueden lograr un efecto similar (por ejemplo, trampolín) pero tienen el grave costo de un rendimiento horrible y oscurecen el código intermedio generado que hace que un depurador sea inútil.
Por lo tanto, la JVM no puede admitir ningún lenguaje de programación funcional de calidad de producción hasta que Sun implemente las llamadas de cola en la propia JVM. Lo han estado discutiendo durante años, pero dudo que alguna vez implementen llamadas finales: será muy difícil porque han optimizado prematuramente su máquina virtual antes de implementar dicha funcionalidad básica, y el esfuerzo de Sun se centra fuertemente en lenguajes dinámicos en lugar de lenguajes funcionales.
Por lo tanto, existe un argumento muy fuerte de que Scala no es un lenguaje de programación funcional real: estos lenguajes han considerado las llamadas finales como una característica esencial desde que se introdujo Scheme hace más de 30 años.
'Por lo tanto, hay un argumento muy fuerte de que Scala no es un lenguaje de programación funcional real: el argumento es realmente bastante débil. Seguramente son 'tail calls [como] una característica esencial', y agradable si el hardware subyacente (o virtal machine) lo admite directamente. Pero son los detalles de implementación. – Ingo
@Ingo: solo si no considera que los desbordamientos de pila en su programa en tiempo de ejecución considerados por el usuario son un problema importante. De acuerdo con su rastreador de fallas, incluso el propio compilador Scala ha estado plagado de desbordamientos de pila. Así que incluso los desarrolladores más experimentados de Scala todavía están equivocándose ... –
Está bien ser un defensor de, digamos F #. Pero te he observado durante mucho tiempo (incluso años antes en usenet) por ser hostil a todo lo que no es F #, y sin embargo tus elaboraciones demuestran que no sabes de lo que estás hablando. Al igual que aquí: su argumento parece ser que un lenguaje donde puedo escribir un programa que aborta con desbordamiento de pila no es funcional? Pero ¿no podría hacerse el mismo argumento para los idiomas en los que puedo provocar el desbordamiento del montón? Por lo tanto, el santo F # en sí mismo no contaría como funcional. – Ingo
Scala 2.7.x es compatible con la optimización de la llamada final para la auto-recursión (una función que se llama a sí misma) de los métodos finales y las funciones locales.
Scala 2.8 podría venir con soporte de biblioteca para trampolín también, que es una técnica para optimizar funciones mutuamente recursivas.
Se puede encontrar mucha información sobre el estado de la recurrencia de Scala en Rich Dougherty's blog.
¿Puede actualizar la pregunta sobre el estado actual de scala? –
@ om-nom-nom AFAIK, nada ha cambiado, ni en el lado de Scala, ni en el lado de JVM. –
Todas las fuentes apuntan a que la JVM no puede optimizar en el caso de repetición de cola, pero al leer Java performance tuning (2003, O'reilly) encontré al autor afirmando que puede lograr un mayor rendimiento de recursión implementando recursividad de cola.
Puede encontrar su reclamo en la página 212 (buscar 'repetición de cola' debería ser el segundo resultado). ¿Lo que da?
IBM ha admitido alguna forma de TCO en su implementación de JVM (como una optimización, por lo que no hay garantías). Tal vez los autores de la optimización del rendimiento de Java pensaron que esta característica finalmente sería implementada por todas las JVM. http://www.ibm.com/developerworks/java/library/j-diag8.html – llemieng
No acabo de seguir la explicación. Pensé que la optimización de la cola de cola fue implementada por el compilador. Suponiendo que tiene una función que podría ser optimizada por el compilador, también podría tener una función no recursiva equivalente que implemente la misma funcionalidad mediante un bucle, ¿correcto? Si es así, ¿no podría hacer esto el compilador? No soy capaz de seguir la dependencia de la JVM. ¿Cómo se compara esto con un compilador de Scheme que generó el código i386 nativo? –
Ok, acabo de ver la respuesta de Jon a continuación. Por lo tanto, no es que no se pueda implementar, es que no se puede implementar con la debida compatibilidad con el depurador –
@Gautham: Mi afirmación sobre la depuración fue en referencia al uso de trampolines como una solución para la falta de eliminación de llamadas finales en la JVM. La eliminación de llamada de cola puede y se ha implementado en la JVM (Arnold Schaighofer lo hizo en OpenJDK, y también en LLVM), por lo que no hay dudas sobre si se puede o no hacer. CLR de Microsoft, por supuesto, ha apoyado la eliminación de llamadas de cola durante 10 años y el lanzamiento de F # ha demostrado que es un cambio de juego. Creo que la respuesta es que la JVM hace tiempo que se ha estancado. –