Clojure no realiza la optimización de llamadas de cola por sí solo: cuando tiene una función recursiva de cola y desea optimizarla, debe usar la forma especial recur
. Del mismo modo, si tiene dos funciones recursivas entre sí, puede optimizarlas solo mediante el uso trampoline
.
El compilador Scala puede realizar TCO para una función recursiva, pero no para dos funciones recursivas mutuamente.
Siempre que leí sobre estas limitaciones, siempre se les atribuyó alguna limitación intrínseca al modelo JVM. No sé casi nada sobre compiladores, pero esto me desconcierta un poco. Déjame tomar el ejemplo de Programming Scala
. Aquí la función
def approximate(guess: Double): Double =
if (isGoodEnough(guess)) guess
else approximate(improve(guess))
se traduce a
0: aload_0
1: astore_3
2: aload_0
3: dload_1
4: invokevirtual #24; //Method isGoodEnough:(D)Z
7: ifeq
10: dload_1
11: dreturn
12: aload_0
13: dload_1
14: invokevirtual #27; //Method improve:(D)D
17: dstore_1
18: goto 2
Entonces, a nivel de bytecode, uno solo necesita goto
. En este caso, de hecho, el compilador realiza el trabajo duro.
¿Qué facilidad de la máquina virtual subyacente permitiría al compilador manejar el TCO más fácilmente?
Como nota al margen, no esperaría que las máquinas reales fueran mucho más inteligentes que la JVM. Aún así, muchos lenguajes que se compilan en código nativo, como Haskell, no parecen tener problemas para optimizar las llamadas de cola (bueno, Haskell a veces puede deberse a la pereza, pero ese es otro problema).
tailcall
instrucción para JVM ya se ha propuesto ya en 2007: bloguea en sun.com a través de la máquina wayback . Después de la adquisición de Oracle, este enlace es 404. Supongo que no llegó a la lista de prioridades de JVM 7.tailcall
instrucción solo marcaría una llamada de cola como una llamada de cola. Si la JVM realmente optimizó dicha llamada de cola es una pregunta completamente diferente. El CLI CIL tiene un.tail
prefijo de instrucción, sin embargo, el CLR de 64 bits de Microsoft durante mucho tiempo no lo optimizó. Otoh, el IBM J9 JVM hace detectar las llamadas de la cola y los optimiza, sin necesidad de una instrucción especial para decirle en que las llamadas son llamadas de cola. Anotar las llamadas de cola y optimizar las llamadas de cola son realmente ortogonales. (Aparte del hecho de que deducir estáticamente qué llamada es una cola puede o no ser indecidible. No sé.)call something; oreturn
. El trabajo principal de una actualización de la especificación JVM no sería introducir una instrucción de cola explícita, sino exigir que dicha instrucción esté optimizada. Dicha instrucción solo hace que los trabajos de los escritores de compiladores sean más fáciles: el autor de JVM no tiene que asegurarse de reconocer esa secuencia de instrucciones antes de que se estropee más allá del reconocimiento, y el compilador X-> bytecode puede estar seguro de que su bytecode es inválido o realmente optimizado, nunca correcto-pero-pila-desbordamiento.call something; return;
solo sería equivalente a una llamada de cola si la cosa que se llama nunca pide un seguimiento de la pila; Si el método en cuestión es virtual o llama a un método virtual, la JVM no tendrá forma de saber si podría preguntar sobre la pila.Clojure podría realizar una optimización automática de la recursión de la cola en bucles: ciertamente es posible hacer esto en la JVM como lo demuestra Scala.
En realidad, fue una decisión de diseño no hacer esto: debe usar explícitamente el
recur
formulario especial si desea esta función. Vea el hilo de correo Re: ¿Por qué no hay optimización de llamadas de cola en el grupo de google Clojure?En la JVM actual, lo único que es imposible de hacer es la optimización de llamadas de cola entre diferentes funciones (recursión mutua). Esto no es particularmente complejo de implementar (otros lenguajes como Scheme han tenido esta característica desde el principio) pero requeriría cambios en la especificación JVM. Por ejemplo, tendría que cambiar las reglas sobre la preservación de la pila completa de llamadas a funciones.
Es probable que una iteración futura de la JVM obtenga esta capacidad, aunque probablemente como una opción para mantener un comportamiento compatible con versiones anteriores del código anterior. Digamos, la Vista previa de características en Geeknizer enumera esto para Java 9:
Por supuesto, las hojas de ruta futuras siempre están sujetas a cambios.
Como resultado, no es un gran problema de todos modos. En más de 2 años de codificación de Clojure, nunca me he encontrado con una situación en la que la falta de TCO sea un problema. Las principales razones para esto son:
recur
o un bucle. El caso de recursión de cola mutua es bastante raro en el código normalfuente
No se trata de ser más inteligente, sino de ser diferente. Hasta hace poco, la JVM fue diseñada y optimizada exclusivamente para un solo lenguaje (Java, obviamente), que tiene una memoria muy estricta y modelos de llamadas.
No solo no había ninguno
goto
o punteros, ni siquiera había forma de llamar a una función 'desnuda' (una que no fuera un método definido dentro de una clase).Conceptualmente, cuando se dirige a JVM, un escritor compilador tiene que preguntarse "¿cómo puedo expresar este concepto en términos de Java?". Y obviamente, no hay forma de expresar TCO en Java.
Tenga en cuenta que estos no se consideran fallas de JVM, porque no son necesarios para Java. Tan pronto como Java necesite alguna característica como esta, se agrega a JVM.
Solo recientemente, las autoridades de Java comenzaron a tomar en serio a JVM como una plataforma para lenguajes que no son Java, por lo que ya ha obtenido cierto soporte para características que no tienen equivalente Java. El más conocido es la escritura dinámica, que ya está en JVM pero no en Java.
fuente
¿Has notado que la dirección del método comienza con 0? ¿Que todos los métodos de conjuntos comienzan con 0? JVM no permite que uno salte fuera de un método.
No tengo idea de lo que sucedería con una rama con desplazamiento fuera del método que Java cargó: tal vez sería atrapado por el verificador de bytecode, tal vez generaría una excepción y tal vez saltaría fuera del método.
El problema, por supuesto, es que realmente no se puede garantizar dónde estarán otros métodos de la misma clase, y mucho menos los métodos de otras clases. Dudo que JVM garantice dónde cargará los métodos, aunque me encantaría que me corrijan.
fuente