Cuando no hay TCO, ¿cuándo preocuparse por volar la pila?

14

Cada vez que hay una discusión sobre un nuevo lenguaje de programación dirigido a la JVM, inevitablemente hay personas que dicen cosas como:

"La JVM no admite la optimización de llamadas de cola, por lo que predigo muchas pilas explosivas"

Hay miles de variaciones sobre ese tema.

Ahora sé que algunos lenguajes, como Clojure, por ejemplo, tienen una construcción recurrente especial que puedes usar.

Lo que no entiendo es: ¿qué tan grave es la falta de optimización de la cola? ¿Cuándo debería preocuparme por eso?

Mi principal fuente de confusión probablemente proviene del hecho de que Java es uno de los lenguajes más exitosos de la historia y parece que a algunos de los lenguajes JVM les está yendo bastante bien. ¿Cómo es eso posible si la falta de TCO es realmente de cualquier preocupación?

Cedric Martin
fuente
44
si tiene una recursión lo suficientemente profunda como para volar la pila sin TCO, entonces tendrá un problema incluso con TCO
fanático del trinquete el
18
@ratchet_freak Eso no tiene sentido. Scheme ni siquiera tiene bucles, pero debido a que la especificación exige el soporte de TCO, la iteración recursiva sobre un gran conjunto de datos no es más costosa que un bucle imperativo (con la ventaja de que la construcción Scheme devuelve un valor).
itsbruce
66
@ratchetfreak TCO es un mecanismo para hacer que las funciones recursivas escritas de cierta manera (es decir, recursivamente la cola) sean completamente incapaces de volar la pila, incluso si quisieran. Su declaración solo tiene sentido para la recursividad que no se escribe recursivamente, en cuyo caso está en lo correcto y el TCO no lo ayudará.
Evicatos
2
La última vez que miré, el 80x86 tampoco hace la optimización (nativa) de la cola. Pero eso no ha impedido que los desarrolladores de idiomas porten idiomas que lo usan. El compilador identifica cuándo puede usar un salto contra un jsr, y todos están contentos. Puede hacer lo mismo en una JVM.
kdgregory
3
@kdgregory: Pero el x86 tiene GOTO, la JVM no. Y x86 no se utiliza como plataforma de interoperabilidad. La JVM no tiene GOTOy una de las principales razones para elegir la Plataforma Java es la interoperabilidad. Si desea implementar TCO en la JVM, debe hacer algo a la pila. Adminístrelo usted mismo (es decir, no use la pila de llamadas JVM), use trampolines, use excepciones como GOTO, algo así. En todos esos casos, se vuelve incompatible con la pila de llamadas JVM. Es imposible ser compatible con Java, tener TCO y un alto rendimiento. Tienes que sacrificar uno de esos tres.
Jörg W Mittag

Respuestas:

16

Considere esto, digamos que nos deshicimos de todos los bucles en Java (los escritores del compilador están en huelga o algo así). Ahora queremos escribir factorial, por lo que podríamos corregir algo como esto

int factorial(int i){ return factorial(i, 1);}
int factorial(int i, int accum){
  if(i == 0) return accum;
  return factorial(i-1, accum * i);
}

Ahora nos sentimos bastante listos, ¡hemos logrado escribir nuestro factorial incluso sin bucles! Pero cuando probamos, notamos que con cualquier número de tamaño razonable, estamos obteniendo errores de stackoverflow ya que no hay TCO.

En Java real, esto no es un problema. Si alguna vez tenemos un algoritmo recursivo de cola, podemos transformarlo en un bucle y estar bien. Sin embargo, ¿qué pasa con los idiomas sin bucles? Entonces solo estás manguera. Es por eso que clojure tiene esta recurforma, sin ella, ni siquiera está completa (no hay forma de hacer bucles infinitos).

La clase de lenguajes funcionales que se dirigen a JVM, Frege, Kawa (Scheme), Clojure siempre están tratando de lidiar con la falta de llamadas de cola, porque en estos idiomas, TC es la forma idiomática de hacer bucles. Si se traduce al Esquema, ese factorial anterior sería un buen factorial. Sería muy inconveniente si el bucle de 5000 veces hiciera que su programa se bloqueara. Sin embargo, esto se puede solucionar, con recurformas especiales, anotaciones que sugieren optimizar las auto llamadas, el trampolín, lo que sea. Pero todos fuerzan los golpes de rendimiento o el trabajo innecesario en el programador.

Ahora Java tampoco se libera, ya que hay más en TCO que solo recursividad, ¿qué pasa con las funciones recursivas mutuas? No se pueden traducir directamente a bucles, pero la JVM todavía no los optimiza. Esto hace que sea espectacularmente desagradable tratar de escribir algoritmos usando recursividad mutua usando Java ya que si quieres un rendimiento / rango decente debes hacer magia oscura para que encaje en los bucles.

Entonces, en resumen, esto no es un gran problema para muchos casos. La mayoría de las llamadas de cola solo proceden un frameframe de profundidad, con cosas como

return foo(bar, baz); // foo is just a simple method

o son recursivas. Sin embargo, para la clase de TC que no encaja en esto, cada lenguaje JVM siente el dolor.

Sin embargo, hay una razón decente por la que todavía no tenemos TCO. La JVM nos da rastros de pila. Con TCO eliminamos sistemáticamente los cuadros de pila que sabemos que están "condenados", ¡pero la JVM podría desearlos más tarde para un seguimiento de pila! Digamos que implementamos un FSM como este, donde cada estado llama a la siguiente. Borraríamos todos los registros de estados anteriores para que un rastreo nos muestre qué estado, pero no nada sobre cómo llegamos allí.

Además, y de manera más apremiante, gran parte de la verificación de bytecode se basa en la pila, eliminando lo que nos permite verificar bytecode no es una perspectiva agradable. Entre esto y el hecho de que Java tiene bucles, TCO parece un poco más problemático de lo que vale para los ingenieros de JVM.

Daniel Gratzer
fuente
2
El mayor problema es el verificador de código de bytes, que se basa completamente en la inspección de la pila. Ese es un error importante en la especificación JVM. Hace 25 años, cuando se diseñó la JVM, las personas ya decían que sería mejor tener el lenguaje de código de byte de JVM seguro en primer lugar en lugar de que ese lenguaje no sea seguro y luego confiar en la verificación de código de byte después del hecho. Sin embargo, Matthias Felleisen (una de las figuras principales de la comunidad de Scheme) escribió un documento que demuestra cómo se pueden agregar llamadas de cola a la JVM mientras se preserva el verificador de código de byte.
Jörg W Mittag
2
Curiosamente, la JVM J9 de IBM no realizar el TCO.
Jörg W Mittag
1
@jozefg Curiosamente, a nadie le importan las entradas de stacktrace para los bucles, por lo tanto, el argumento stacktrace no retiene el agua, al menos para las funciones recursivas de cola.
Ingo
2
@MasonWheeler Ese es exactamente mi punto: el stacktrace no te dice en qué iteración sucedió. Puede ver esto solo indirectamente, inspeccionando las variables de bucle, etc. Entonces, ¿por qué querría varias entradas de rastreo de pila de hundert de una función recursiva de cola? ¡Solo el último es interesante! Y, al igual que con los bucles, puede determinar qué recursión fue inspeccionando los valores locales, los valores de los argumentos, etc.
Ingo
3
@Ingo: si una función solo se repite consigo misma, el seguimiento de la pila puede no mostrar mucho. Sin embargo, si un grupo de funciones es recursivo mutalmente, un seguimiento de la pila a veces puede mostrar mucho.
supercat
7

La optimización de llamadas de cola es principalmente importante debido a la recursividad de cola. Sin embargo, existe un argumento de por qué es realmente bueno que la JVM no optimice las llamadas de cola: como TCO reutiliza una parte de la pila, un seguimiento de la pila de una excepción será incompleto, lo que dificultará un poco la depuración.

Hay formas de evitar las limitaciones de la JVM:

  1. El compilador puede optimizar la recursión de cola simple en un bucle.
  2. Si el programa está en estilo de paso continuo, entonces es trivial usar "trampolining". Aquí, una función no devuelve el resultado final, sino una continuación que luego se ejecuta en el exterior. Esta técnica permite que un escritor compilador modele arbitrariamente un flujo de control complejo.

Esto puede necesitar un ejemplo más amplio. Considere un lenguaje con cierres (por ejemplo, JavaScript o similar). Podemos escribir el factorial como

def fac(n, acc = 1) = if (n <= 1) acc else n * fac(n-1, acc*n)

print fac(x)

Ahora podemos hacer que devuelva una devolución de llamada:

def fac(n, acc = 1) =
  if (n <= 1) acc
  else        (() => fac(n-1, acc*n))  // this isn't full CPS, but you get the idea…

var continuation = (() => fac(x))
while (continuation instanceof function) {
  continuation = continuation()
}
var result = continuation
print result

Esto ahora funciona en un espacio de pila constante, lo cual es un poco tonto porque de todos modos es recursivo. Sin embargo, esta técnica puede aplanar todas las llamadas de cola en un espacio de pila constante. Y si el programa está en CPS, esto significa que la pila de llamadas es constante en general (en CPS, cada llamada es una llamada de cola).

Una desventaja importante de esta técnica es que es mucho más difícil de depurar, un poco más difícil de implementar y menos eficaz: vea todos los cierres e indirectas que estoy usando.

Por estas razones, sería muy preferible que la VM implementara una llamada de cola. Los lenguajes como Java que tienen buenas razones para no admitir llamadas de cola no tendrían que usarlo.

amon
fuente
1
"A medida que el TCO reutiliza una parte de la pila, un seguimiento de la pila de una excepción estará incompleto", sí, pero entonces, una traza de la pila desde dentro de un ciclo tampoco está completa, no registra la frecuencia con la que se ejecutó el ciclo. - Por desgracia, incluso si la JVM admitiera llamadas de cola adecuadas, uno podría optar por no participar, por ejemplo, durante la depuración. Y luego, para la producción, habilite TCO para asegurarse de que el código se ejecute con 100,000 o 100,000,000 llamadas de cola.
Ingo
1
@Ingo No. (1) Cuando los bucles no se implementan como recursividad, no hay justificación para que aparezcan en la pila (llamada de cola ≠ salto ≠ llamada). (2) El TCO es más general que la optimización de recursión de cola. Mi respuesta usa la recursividad como ejemplo . (3) Si está programando en un estilo que se basa en TCO, desactivar esta optimización no es una opción: el TCO completo o los seguimientos completos de la pila son una característica del lenguaje, o no lo son. Por ejemplo, Scheme logra equilibrar los inconvenientes de TCO con un sistema de excepción más avanzado.
amon
1
(1) totalmente de acuerdo. Pero por el mismo razonamiento, no existe una justificación para mantener cientos y miles de entradas de seguimiento de pila que todos señalan return foo(....);en el método foo(2), por supuesto. Aún así, aceptamos el rastreo incompleto de bucles, asignaciones (!), Secuencias de instrucciones. Por ejemplo, si encuentra un valor inesperado en una variable, seguramente querrá saber cómo llegó allí. Pero no te quejas de las huellas faltantes en ese caso. Debido a que de alguna manera está grabado en nuestros cerebros que a) ocurre solo en llamadas b) ocurre en todas las llamadas. Ambos no tiene sentido, en mi humilde opinión.
Ingo
(3) En desacuerdo. No puedo ver ninguna razón por la que debería ser imposible depurar mi código con un problema de tamaño N, para algunos N lo suficientemente pequeños como para salirse con la pila normal. Y luego, para activar el interruptor y activar el TCO, eliminando efectivamente la restricción sobre el tamaño de la sonda.
Ingo
@Ingo “No estoy de acuerdo. No veo ninguna razón por la que debería ser imposible depurar mi código con un problema de tamaño N, para que algunos N sean lo suficientemente pequeños como para salirse con la pila normal ". Si TCO / TCE es para una transformación CPS, entonces gírelo off desbordará la pila y bloqueará el programa, por lo que no será posible la depuración. Google se negó a implementar TCO en V8 JS, debido a que este problema ocurre de manera incidental . Querrían una sintaxis especial para que el programador pueda declarar que realmente quiere TCO y la pérdida del seguimiento de la pila. ¿Alguien sabe si TCO también atornilla las excepciones?
Shelby Moore III
6

Una parte importante de las llamadas en un programa son llamadas de cola. Cada subrutina tiene una última llamada, por lo que cada subrutina tiene al menos una llamada de cola. Las llamadas de cola tienen las características de rendimiento GOTOpero la seguridad de una llamada de subrutina.

Tener llamadas de cola adecuadas le permite escribir programas que de otro modo no podría escribir. Tomemos, por ejemplo, una máquina de estados. Una máquina de estados puede implementarse muy directamente haciendo que cada estado sea una subrutina y cada transición de estado sea una llamada de subrutina. En ese caso, pasa de un estado a otro haciendo una llamada tras otra, ¡y en realidad nunca regresas! Sin llamadas de cola adecuadas, inmediatamente volarías la pila.

Sin PTC, debe usar GOTOTrampolines o excepciones como flujo de control o algo así. Es mucho más feo, y no tanto una representación directa 1: 1 de la máquina de estado.

(Observe cómo ingeniosamente evité usar el aburrido ejemplo de "bucle". Este es un ejemplo donde los PTC son útiles incluso en un lenguaje con bucles).

Deliberadamente utilicé el término "Llamadas de cola adecuadas" aquí en lugar de TCO. TCO es un compilador de optimización. PTC es una función de lenguaje que requiere que cada compilador realice TCO.

Jörg W Mittag
fuente
The vast majority of calls in a program are tail calls. No, si "la gran mayoría" de los métodos llamados realizan más de una llamada propia. Every subroutine has a last call, so every subroutine has at least one tail call. Esta es trivialmente demostrable como falso: return a + b. (A menos que esté en un lenguaje loco donde las operaciones aritméticas básicas se definen como llamadas a funciones, por supuesto).
Mason Wheeler
1
"Agregar dos números es agregar dos números". Excepto por los idiomas donde no lo es. ¿Qué pasa con la operación + en Lisp / Scheme donde un solo operador aritmético puede tomar un número arbitrario de argumentos? (+ 1 2 3) La única forma sensata de implementar eso es como una función.
Evicatos
1
@Mason Wheeler: ¿Qué quieres decir con inversión de abstracción?
Giorgio
1
@MasonWheeler Esa es, sin duda, la entrada de Wikipedia sobre un tema técnico más ondulada que jamás haya visto. He visto algunas entradas dudosas pero eso es solo ... wow.
Evicatos
1
@MasonWheeler: ¿Estás hablando de las funciones de longitud de la lista en las páginas 22 y 23 de On Lisp? La versión de cola es aproximadamente 1.2x como complicada, ni mucho menos 3x. Tampoco tengo claro qué quiere decir con inversión de abstracción.
Michael Shaw
4

"La JVM no admite la optimización de llamadas de cola, por lo que predigo muchas pilas explosivas"

Cualquiera que diga esto, ya sea (1) no entiende la optimización de la cola, o (2) no entiende la JVM, o (3) ambos.

Comenzaré con la definición de llamadas de cola de Wikipedia (si no te gusta Wikipedia, aquí hay una alternativa ):

En informática, una llamada de cola es una llamada de subrutina que ocurre dentro de otro procedimiento como su acción final; puede producir un valor de retorno que luego es devuelto inmediatamente por el procedimiento de llamada

En el siguiente código, la llamada a bar()es la llamada de cola de foo():

private void foo() {
    // do something
    bar()
}

La optimización de la llamada de cola ocurre cuando la implementación del lenguaje, al ver una llamada de cola, no utiliza la invocación de método normal (que crea un marco de pila), sino que crea una rama. Esta es una optimización porque un marco de pila requiere memoria, y requiere ciclos de CPU para insertar información (como la dirección de retorno) en el marco, y porque se supone que el par de llamada / retorno requiere más ciclos de CPU que un salto incondicional.

El TCO a menudo se aplica a la recursividad, pero ese no es su único uso. Tampoco es aplicable a todas las recursiones. El código recursivo simple para calcular un factorial, por ejemplo, no puede ser optimizado, porque lo último que sucede en la función es una operación de multiplicación.

public static int fact(int n) {
    if (n <= 1) return 1;
    else return n * fact(n - 1);
}

Para implementar la optimización de llamadas de cola, necesita dos cosas:

  • Una plataforma que admite la ramificación además de las llamadas de subtrutina.
  • Un analizador estático que puede determinar si es posible la optimización de llamadas de cola.

Eso es. Como he señalado en otra parte, la JVM (como cualquier otra arquitectura completa de Turing) tiene un goto. Resulta que tiene un goto incondicional , pero la funcionalidad podría implementarse fácilmente utilizando una rama condicional.

El análisis estático es lo que es complicado. Dentro de una sola función, no hay problema. Por ejemplo, aquí hay una función Scala recursiva de cola para sumar los valores en a List:

def sum(acc:Int, list:List[Int]) : Int = {
  if (list.isEmpty) acc
  else sum(acc + list.head, list.tail)
}

Esta función se convierte en el siguiente código de bytes:

public int sum(int, scala.collection.immutable.List);
  Code:
   0:   aload_2
   1:   invokevirtual   #63; //Method scala/collection/immutable/List.isEmpty:()Z
   4:   ifeq    9
   7:   iload_1
   8:   ireturn
   9:   iload_1
   10:  aload_2
   11:  invokevirtual   #67; //Method scala/collection/immutable/List.head:()Ljava/lang/Object;
   14:  invokestatic    #73; //Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
   17:  iadd
   18:  aload_2
   19:  invokevirtual   #76; //Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
   22:  checkcast   #59; //class scala/collection/immutable/List
   25:  astore_2
   26:  istore_1
   27:  goto    0

Tenga goto 0en cuenta el al final. En comparación, una función Java equivalente (que debe usar un Iteratorpara imitar el comportamiento de romper una lista Scala en cabeza y cola) se convierte en el siguiente código de bytes. Tenga en cuenta que las dos últimas operaciones son ahora una invocación , seguida de un retorno explícito del valor producido por esa invocación recursiva.

public static int sum(int, java.util.Iterator);
  Code:
   0:   aload_1
   1:   invokeinterface #64,  1; //InterfaceMethod java/util/Iterator.hasNext:()Z
   6:   ifne    11
   9:   iload_0
   10:  ireturn
   11:  iload_0
   12:  aload_1
   13:  invokeinterface #70,  1; //InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
   18:  checkcast   #25; //class java/lang/Integer
   21:  invokevirtual   #74; //Method java/lang/Integer.intValue:()I
   24:  iadd
   25:  aload_1
   26:  invokestatic    #43; //Method sum:(ILjava/util/Iterator;)I
   29:  ireturn

La optimización de la llamada de cola de una sola función es trivial: el compilador puede ver que no hay código que use el resultado de la llamada, por lo que puede reemplazar la invocación con a goto.

Donde la vida se vuelve difícil es si tienes múltiples métodos. Las instrucciones de ramificación de la JVM, a diferencia de las de un procesador de uso general como el 80x86, se limitan a un solo método. Todavía es relativamente sencillo si tiene métodos privados: el compilador es libre de incorporar esos métodos según corresponda, por lo que puede optimizar las llamadas de cola (si se pregunta cómo podría funcionar esto, considere un método común que use un switchpara controlar el comportamiento). Incluso puede extender esta técnica a varios métodos públicos en la misma clase: el compilador integra los cuerpos de los métodos, proporciona métodos de puentes públicos y las llamadas internas se convierten en saltos.

Pero, este modelo se rompe cuando considera los métodos públicos en diferentes clases, particularmente a la luz de las interfaces y cargadores de clases. El compilador de nivel de origen simplemente no tiene suficiente conocimiento para implementar optimizaciones de cola. Sin embargo, a diferencia de las implementaciones "bare-metal", el * JVM (tiene la información para hacer esto, en la forma del compilador Hotspot (al menos, el compilador ex-Sun sí lo tiene). No sé si realmente funciona optimizaciones de llamada de cola, y sospecho que no, pero podría .

Lo que me lleva a la segunda parte de su pregunta, que reformularé como "¿debería importarnos?"

Claramente, si su lenguaje usa la recursividad como su única primitiva para la iteración, le importa. Pero los idiomas que necesitan esta característica pueden implementarla; El único problema es si un compilador para dicho lenguaje puede producir una clase que pueda llamar y ser llamada por una clase arbitraria de Java.

Fuera de ese caso, voy a invitar votos negativos diciendo que es irrelevante. La mayor parte del código recursivo que he visto (y he trabajado con muchos proyectos gráficos) no es optimizable . Al igual que el factorial simple, utiliza la recursividad para construir el estado, y la operación de cola es una combinación.

Para el código que es optimizable en cola, a menudo es sencillo traducir ese código en una forma iterable. Por ejemplo, esa sum()función que mostré anteriormente se puede generalizar como foldLeft(). Si observa la fuente , verá que en realidad se implementa como una operación iterativa. Jörg W Mittag tenía un ejemplo de una máquina de estado implementada mediante llamadas de función; Hay muchas implementaciones de máquinas de estado eficientes (y mantenibles) que no dependen de llamadas de funciones que se traducen en saltos.

Terminaré con algo completamente diferente. Si busca en Google las notas al pie en el SICP, puede terminar aquí . Personalmente considero que un lugar mucho más interesante que tener mi compilador sustituir JSRpor JUMP.

kdgregory
fuente
Si existiera un código operativo de llamada de cola, ¿por qué la optimización de la llamada de cola requeriría algo más que observar en cada sitio de llamada si el método que realiza la llamada necesitaría ejecutar algún código después? Puede ser que, en algunos casos, una declaración como return foo(123);podría ejecutarse mejor en línea fooque generando código para manipular la pila y realizar un salto, pero no veo por qué la llamada de cola sería diferente de una llamada ordinaria en a ese respecto.
supercat
@supercat: no estoy seguro de cuál es tu pregunta. El primer punto de esta publicación es que el compilador no puede saber cómo se vería el marco de la pila de todos los posibles callejeros (recuerde que el marco de la pila contiene no solo los argumentos de la función sino también sus variables locales). Supongo que podría agregar un código de operación que verifique en tiempo de ejecución los marcos compatibles, pero eso me lleva a la segunda parte de la publicación: ¿cuál es el valor real ?
kdgregory