¿Hay algún motor de JavaScript optimizado para llamadas de cola (TCO)?

91

Tengo un algoritmo de búsqueda de ruta recursiva de cola que he implementado en JavaScript y me gustaría saber si alguno (¿todos?) Los navegadores posiblemente obtendrían excepciones de desbordamiento de pila.

javascript functional-programming tail-recursion Clofresh
fuente
2
¿Es realmente un algoritmo recursivo o un algoritmo iterativo implementado con recursividad? Tengo entendido que TCO solo puede ayudar con esto último.
nmichaels
1
Solo quiero agregar que el TCO no es onlyuna optimización. Soportarlo debería ser parte de la especificación del lenguaje, no del compilador / intérprete, ya que el código escrito en un intérprete / compilador con TCO probablemente no funcionaría en un intérprete / compilador sin TCO.
Hoffmann
1
Puede ver el soporte actual y ver cómo evoluciona en todos los motores en la tabla de compatibilidad ES6 de Kangax aquí: kangax.github.io/compat-table/es6/…
Roy Tinker

Respuestas:

47

La especificación ECMAScript 4 originalmente iba a agregar soporte para TCO, pero se eliminó:

¿No más llamadas de cola en JavaScript?

Hasta donde yo sé, ninguna implementación de JavaScript ampliamente disponible actualmente genera TCO automático. Sin embargo, esto puede serle útil:

Optimización de llamadas de cola

Esencialmente, el uso del patrón acumulador logra el mismo efecto.

Tim Sylvester
fuente
1
Solo un FYI, Rhino tiene TCO automático junto con Continuaciones en modo "interpretado" (opt = -1) wiki.apache.org/cocoon/RhinoWithContinuations
Mark Porter
5
(perdón por el trolling) ECMAScript 6 ha incluido el TCO, denominado Proper Tail Calls en la especificación.
helado
@sclv: ¿Cuál es la referencia del trampolín?
bukzor
39
El patrón del acumulador no logra el mismo efecto que el TCO. Simplemente transforma algoritmos recursivos en forma recursiva de cola. Este es un requisito previo para que el TCO sea posible, pero no lo sustituye. Aún así, explotarás la pila en un lenguaje que no optimiza las llamadas finales.
Marcelo Cantos
"No hay implementaciones de JS ampliamente disponibles que tengan un TCO automático", esto es incorrecto a partir del Nodo 6.2.0, si pasa la bandera correcta
Janus Troelsen
26

No hay alegría por el momento, pero afortunadamente las llamadas de cola adecuadas están programadas para Harmony (ECMAScript versión 6) http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls

Señor presidente
fuente
1
@MarkWilbur La pregunta se refería específicamente a los navegadores , no a todas las implementaciones existentes de ECMAScript.
Código inútil
1
@UselessCode No, esta pregunta es sobre "motores Javascript" así que ... no solo navegadores
BT
1
@BT hecho, existen muchas distintas de los navegadores entornos JS, y el título hace uso de las más genéricas "motores de Javascript", pero el cuerpo de la cuestión especifica" ... me gustaría saber si hay algún (todos?) Los navegadores podrían conseguir posiblemente pila excepciones de desbordamiento ".
Código inútil
Tengo que contrarrestar "pero el título dice ...". Creo que debido a que menciona ambos, la pregunta es sobre ambos. Pero tiene razón si dice que eso no hace que la respuesta sea obsoleta.
BT
4
@MarkWilbur Hasta donde yo sé, el nodo usa la misma versión de v8 que Chrome, que actualmente no es compatible con el TCO. Tenía una idea general del JS y del ensamblador optimizado que produce el V8 actual: gist.github.com/mcfedr / 832e3553964a014621d5
mcfedr
12

Prácticamente todos los navegadores que encuentres emitirán "demasiada recursividad". Aquí hay una entrada en el rastreador de errores V8 que probablemente será una lectura interesante.

Si se trata de una simple autorrecursión, probablemente valga la pena el esfuerzo de utilizar una iteración explícita en lugar de esperar la eliminación de la llamada final.

Hank Gay
fuente
El error finalmente ha sido aceptado. Está bajo la épica: "Feature Request Harmony". Con suerte, eso significa que planean agregarlo al soporte de ES6 en V8.
Txangel
Puede votar por la compatibilidad con TCO en Internet Explorer aquí: wpdev.uservoice.com/forums/257854-internet-explorer-platform/…
Roy Tinker
12

La optimización de la llamada de cola será compatible en el modo estricto ECMAScript 6 en el futuro. Consulte http://www.2ality.com/2015/06/tail-call-optimization.html para obtener más detalles.

Consulte http://kangax.github.io/compat-table/es6/ para conocer el soporte actual del motor.

Por el momento (18-07-2019), los siguientes motores admiten la optimización de llamadas de cola:

  • Safari> = 10
  • iOS> = 10
  • Kinoma XS6
  • Duktape 2.3

soporte si la bandera "características experimentales de JavaScript" está activada:

  • Nodo 6.5
  • Chrome 54 / Opera 41 La versión actual de la tabla de compatibilidad ya no la incluye
Simon Zyx
fuente
3

La optimización de llamadas de cola ahora está disponible en LispyScript, que se compila en JavaScript. Puedes leer más sobre esto aquí .

Santosh
fuente
¿Qué pasa con la recursividad mutua?
gato
2

Actualmente, ninguna implementación de JavaScript reconoce la recursividad de cola. Se están realizando cambios en ECMAScript 6 y, como han dicho otros, hay un ticket abierto en V8 .

Aquí puede ver el ensamblador generado por V8 para una función de recursión de cola:

Ejemplo de cómo V8 compila la recursividad

Compare eso con cómo Clang ha compilado la misma función en C

Ejemplo de recursividad de la cola del compilador de C

V8 retiene la llamada recursiva, mientras que el compilador de C ha reconocido la recursividad de cola y la ha convertido en un bucle.

mcfedr
fuente
"Actualmente, ninguna implementación de JS reconoce la recursividad de la cola". eso es incorrecto a partir del Nodo 6.2.0, pero debe pasar una bandera
Janus Troelsen