Les appels de fin de course (TCO) des moteurs JavaScript sont-ils optimisés?

91

J'ai un algorithme de recherche de chemin récursif de queue que j'ai implémenté en JavaScript et j'aimerais savoir si certains (tous?) Navigateurs pourraient éventuellement obtenir des exceptions de dépassement de pile.

javascript functional-programming tail-recursion clofresh
la source
2
S'agit-il en fait d'un algorithme récursif ou d'un algorithme itératif implémenté avec récursivité? Je crois comprendre que TCO ne peut aider que dans ce dernier cas.
nmichaels
1
Je veux juste ajouter que le TCO n'est pas onlyune optimisation. Le supporter devrait faire partie de la spécification du langage, pas du compilateur / interpréteur puisque le code écrit contre un interpréteur / compilateur avec TCO ne fonctionnerait probablement pas sur un interpréteur / compilateur sans TCO.
Hoffmann
1
Vous pouvez voir le support actuel et le voir évoluer à travers les moteurs dans le tableau de compatibilité ES6 de Kangax ici: kangax.github.io/compat-table/es6
Roy Tinker

Réponses:

47

La spécification ECMAScript 4 allait à l'origine ajouter la prise en charge du TCO, mais elle a été abandonnée:

Plus d'appels de queue en JavaScript?

Pour autant que je sache, aucune implémentation largement disponible de JavaScript n'effectue actuellement un TCO automatique. Cela peut cependant vous être utile:

Optimisation des appels de queue

Essentiellement, l'utilisation du modèle d'accumulateur produit le même effet.

Tim Sylvester
la source
1
Juste un FYI, Rhino a un TCO automatique avec des Continuations en mode "interprété" (opt = -1) wiki.apache.org/cocoon/RhinoWithContinuations
Mark Porter
5
(désolé pour la pêche à la traîne) ECMAScript 6 a inclus le TCO, appelé Proper Tail Calls dans la spécification.
frosty
@sclv: Quelle est la référence du trampoline?
bukzor le
39
Le modèle d'accumulateur n'effectue pas le même effet que le TCO. Il transforme simplement les algorithmes récursifs en forme récursive de queue. C'est une condition préalable pour que le TCO soit possible, mais ce n'est pas un substitut. Vous allez toujours faire exploser la pile dans un langage qui n'optimise pas les appels de queue.
Marcelo Cantos
"aucune implémentation largement disponible de JS n'effectue actuellement un TCO automatique" c'est incorrect à partir du Node 6.2.0, si vous passez le bon drapeau
Janus Troelsen
26

Pas de joie pour le moment, mais heureusement, des appels de queue appropriés sont prévus pour Harmony (ECMAScript version 6) http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls

Monsieur le Président
la source
1
@MarkWilbur La question concernait spécifiquement les navigateurs , pas toutes les implémentations existantes d'ECMAScript.
Code inutile
1
@UselessCode Non, cette question concerne les "moteurs Javascript" donc ... pas seulement les navigateurs
BT
1
@BT Il existe en effet de nombreux environnements JS non-navigateur, et le titre utilise les "moteurs Javascript" plus génériques mais le corps de la question spécifie "... aimerait savoir si certains (tous?) Navigateurs pourraient éventuellement obtenir une pile exceptions de débordement. "
Code inutile du
Je dois contrer "mais le titre dit ...". Je pense que parce qu'il mentionne les deux, la question porte sur les deux. Mais vous avez raison si vous dites que cela ne rend pas la réponse obsolète.
BT
4
@MarkWilbur Autant que je sache, le nœud utilisant la même version de v8 que chrome - qui ne prend actuellement pas en charge le TCO, j'avais un point essentiel avec le JS et l'assembleur optimisé produit par le V8 actuel - gist.github.com/mcfedr / 832e3553964a014621d5
mcfedr
12

Pratiquement tous les navigateurs que vous rencontrerez seront "trop ​​récursifs". Voici une entrée dans le traqueur de bogues V8 qui sera probablement une lecture intéressante.

S'il s'agit d'une simple auto-récursivité, il vaut probablement la peine d'utiliser une itération explicite plutôt que d'espérer l'élimination des appels de fin.

Hank Gay
la source
Le bogue a finalement été accepté. C'est sous l'épopée: "Feature Request Harmony". J'espère que cela signifie qu'ils prévoient de l'ajouter au support ES6 dans V8.
Txangel
Vous pouvez voter pour le support TCO dans Internet Explorer ici: wpdev.uservoice.com/forums/257854-internet-explorer-platform
Roy Tinker
12

L'optimisation des appels de queue sera prise en charge dans le mode strict d'ECMAScript 6 à l'avenir. Consultez http://www.2ality.com/2015/06/tail-call-optimization.html pour plus de détails.

Consultez http://kangax.github.io/compat-table/es6/ pour la prise en charge actuelle du moteur.

Pour le moment (18-07-2019), les moteurs suivants prennent en charge l'optimisation des appels de queue:

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

prise en charge si le drapeau "Fonctionnalités JavaScript expérimentales" est activé:

  • Nœud 6.5
  • Chrome 54 / Opera 41 La version actuelle de la table de compatibilité ne la répertorie plus
Simon Zyx
la source
3

L'optimisation des appels de queue est maintenant disponible dans LispyScript qui se compile en JavaScript. Vous pouvez en savoir plus ici .

Santosh
la source
Qu'en est-il de la récursivité mutuelle?
chat
2

Actuellement, aucune implémentation JavaScript ne reconnaît la récursivité de la queue. Des modifications sont en cours dans ECMAScript 6 et, comme d'autres l'ont dit, il existe un ticket ouvert sur V8 .

Ici, vous pouvez voir l'assembleur généré par V8 pour une fonction de récursivité de queue:

Exemple de comment V8 compile la récursivité

Comparez cela à la façon dont Clang a compilé la même fonction en C

Exemple de récursivité de la queue du compilateur C

V8 conserve l'appel récursif, tandis que le compilateur C a reconnu la récursivité de queue et l'a transformée en boucle.

mcfedr
la source
«Actuellement, aucune implémentation JS ne reconnaît la récursivité de queue. c'est incorrect à partir du nœud 6.2.0, mais vous devez passer un drapeau
Janus Troelsen