clojure jvm lisp jvm-languages abcl

clojure - ¿Por qué no se pueden optimizar las llamadas de cola en Lisps basados en JVM?



jvm-languages abcl (3)

El TCO real funciona para llamadas arbitrarias en la posición de cola, no solo para las llamadas automáticas, por lo que el código como el siguiente no causa un desbordamiento de pila:

(letfn [(e? [x] (or (zero? x) (o? (dec x)))) (o? [x] (e? (dec x)))] (e? 10))

Claramente, necesitarías soporte de JVM para esto, ya que los programas que se ejecutan en JVM no pueden manipular la pila de llamadas. (A menos que esté dispuesto a establecer su propia convención de llamadas e imponer la sobrecarga asociada a las llamadas de función; Clojure pretende utilizar las llamadas de método JVM regulares).

En cuanto a la eliminación de llamadas automáticas en la posición de cola, ese es un problema más simple que puede resolverse siempre que todo el cuerpo de la función se compile en un solo método de JVM. Esa es una promesa limitante de hacer, sin embargo. Además, recur es bastante querido por su explicación.

Pregunta principal: veo la aplicación más significativa de la optimización de la llamada de cola (TCO) como una traducción de una llamada recursiva a un bucle (en los casos en que la llamada recursiva tiene cierta forma). Más precisamente, cuando se traduce a un lenguaje de máquina, esto generalmente se traduce en una serie de saltos. Algunos compiladores de Common Lisp y Scheme que se compilan en código nativo (por ejemplo, SBCL) pueden identificar el código recursivo de cola y realizar esta traducción. Los Lisps basados ​​en JVM como Clojure y ABCL tienen problemas para hacer esto. ¿Qué tiene la JVM como máquina que previene o dificulta esto? No lo entiendo La JVM obviamente no tiene problemas con los bucles. Es el compilador que tiene que averiguar cómo hacer el TCO, no la máquina a la que se compila.

Pregunta relacionada: Clojure puede traducir código aparentemente recursivo en un bucle: actúa como si estuviera realizando un TCO, si el programador reemplaza la llamada de cola a la función con la palabra clave recur . Pero si es posible hacer que un compilador identifique las llamadas de cola, como hacen SBCL y CCL, por ejemplo, ¿por qué no puede el compilador de Clojure darse cuenta de que se supone que debe tratar una llamada de cola de la misma manera que se trata?

(Lo siento, esto es sin duda una pregunta frecuente, y estoy seguro de que los comentarios anteriores muestran mi ignorancia, pero no logré encontrar preguntas anteriores).

Hay una razón por la que la JVM no es compatible con el TCO: ¿Por qué la JVM todavía no admite la optimización de llamadas de cola?

Sin embargo, hay una forma de evitar esto abusando de la memoria del montón y algunos trucos explicados en el documento A de primer orden de un solo pase de transformación de CPS ; se implementa en Clojure por Chris Frisz y Daniel P. Friedman (ver repo ).

Ahora que Rich Hickey podría haber elegido realizar dicha optimización de manera predeterminada, Scala lo hace en algunos puntos. En su lugar, optó por confiar en el usuario final para especificar los casos en los que Clojure puede optimizarlos con las construcciones de trampoline o trampoline loop-recur . La decisión se ha explicado aquí: groups.google.com/d/msg/clojure/4bSdsbperNE/tXdcmbiv4g0J