La JVM empêche-t-elle les optimisations des appels de fin?

99

J'ai vu cette citation sur la question: Qu'est-ce qu'un bon langage fonctionnel sur lequel construire un service Web?

Scala en particulier ne prend pas en charge l'élimination des appels de fin, sauf dans les fonctions auto-récursives, ce qui limite les types de composition que vous pouvez faire (c'est une limitation fondamentale de la JVM).

Est-ce vrai? Si tel est le cas, qu'est-ce qui crée cette limitation fondamentale dans la JVM?

java jvm scala tail-recursion Jason Dagit
la source

Réponses:

74

Cet article: récursion ou itération? pourrait aider.

En bref, l'optimisation des appels de fin est difficile à faire dans la JVM en raison du modèle de sécurité et de la nécessité de toujours disposer d'une trace de pile. Ces exigences pourraient en théorie être prises en charge, mais il faudrait probablement un nouveau bytecode (voir la proposition informelle de John Rose ).

Il y a aussi plus de discussion dans le bogue Sun # 4726340 , où l'évaluation (à partir de 2002) se termine:

Je pense que cela pourrait néanmoins être fait, mais ce n’est pas une mince tâche.

Actuellement, des travaux sont en cours dans le cadre du projet Da Vinci Machine . Le statut du sous-projet de l'appel de fin est répertorié comme "proto 80%"; il est peu probable qu'il devienne Java 7, mais je pense qu'il a de très bonnes chances sur Java 8.

Michael Myers
la source
Je n'ai pas bien suivi l'explication. Je pensais que l'optimisation des appels de fin était implémentée par le compilateur. En supposant que vous ayez une fonction qui pourrait être optimisée pour les appels finaux par le compilateur, vous pourriez également avoir une fonction non récursive équivalente qui implémente la même fonctionnalité en utilisant une boucle, n'est-ce pas? Si tel est le cas, cela ne pourrait pas être fait par le compilateur. Je ne suis pas en mesure de suivre la dépendance à la JVM. Comment cela se compare-t-il à un compilateur Scheme qui a généré du code i386 natif?
Gautham Ganapathy
4
@Gautham: Ma déclaration sur le débogage faisait référence à l'utilisation de trampolines comme solution de contournement pour le manque d'élimination des appels de queue sur la JVM. L'élimination des appels de queue peut et a été implémentée sur la JVM (Arnold Schaighofer l'a fait dans OpenJDK, et aussi LLVM) donc il n'y a pas de question de savoir si cela peut être fait ou non. Le CLR de Microsoft a, bien sûr, pris en charge l'élimination des appels de queue pendant 10 ans et la sortie de F # a démontré que cela change la donne. Je pense que la réponse est que la JVM stagne depuis longtemps.
JD
3
C'est une idée fausse courante et une excuse souvent répétée, mais elle est incorrecte. Il est bien établi depuis un certain nombre d'années que la sécurité par inspection de pile (et fourniture de traces utiles de pile) n'est pas incompatible avec des appels de queue appropriés. Par exemple, voir cet article de 2004. citeseerx.ist.psu.edu/viewdoc/… Downvoting, car la réponse est incorrecte.
Justin Sheehy
5
@JustinSheehy: Qu'est-ce qui est incorrect? La question était: "La JVM empêche-t-elle les optimisations des appels de fin?" Et la réponse est: "Non, mais c'est difficile."
Michael Myers
5
savez-vous si dans java8 cela est inclus?
nachokk
27

La limitation fondamentale est simplement que la JVM ne fournit pas d'appels de queue dans son code d'octet et, par conséquent, il n'y a aucun moyen direct pour un langage construit sur la JVM de fournir des appels de queue lui-même. Il existe des solutions de contournement qui peuvent obtenir un effet similaire (par exemple le trampoline), mais elles se font au prix de performances épouvantables et d'obscurcir le code intermédiaire généré qui rend un débogueur inutile.

Ainsi, la machine virtuelle Java ne peut prendre en charge aucun langage de programmation fonctionnel de qualité production tant que Sun n'a pas implémenté les appels de queue dans la machine virtuelle Java elle-même. Ils en discutent depuis des années mais je doute qu'ils implémenteront un jour des appels de queue: ce sera très difficile car ils ont prématurément optimisé leur VM avant d'implémenter ces fonctionnalités de base, et l'effort de Sun est fortement axé sur les langages dynamiques plutôt que sur les langages fonctionnels.

Par conséquent, il existe un argument très fort selon lequel Scala n'est pas un véritable langage de programmation fonctionnel: ces langages ont considéré les appels de queue comme une caractéristique essentielle depuis que Scheme a été introduit pour la première fois il y a plus de 30 ans.

JD
la source
5
Hence there is a very strong argument that Scala is not a real functional programming language - l'argument est en fait assez faible. Bien sûr tail calls [as] an essential feature, et bien si le matériel sous-jacent (ou la machine virtuelle) le supporte directement. Mais ce sont les détails de la mise en œuvre.
Ingo
8
@Ingo: Seulement si vous ne considérez pas que les débordements de pile dans votre programme au moment de l'exécution sont perçus par l'utilisateur comme un problème important. Selon son outil de suivi de bogues, même le compilateur Scala lui-même a été en proie à des débordements de pile. Donc, même les développeurs Scala les plus chevronnés se trompent toujours ...
JD
7
Il n'y a rien de mal à être un partisan de, disons F #. Mais je vous ai noté pendant longtemps (même des années auparavant dans usenet) pour être hostile à tout ce qui n'est pas F #, et pourtant vos élaborations montrent que vous ne savez pas de quoi vous parlez. Comme ici: votre argument semble être qu'un langage dans lequel je peux écrire un programme qui abandonne avec un débordement de pile n'est pas un langage fonctionnel? Mais le même argument ne pourrait-il pas être avancé pour les langues dans lesquelles je peux provoquer un débordement de tas? Par conséquent, le saint F # lui-même ne serait pas considéré comme fonctionnel.
Ingo
7
@Ingo: Plusieurs idiomes dans la programmation fonctionnelle, comme la récursion mutuelle et le style de passage de continuation, peuvent nécessiter l'élimination des appels de queue pour fonctionner. Sans cela, vos programmes vont déborder. Si un langage ne peut pas exécuter un code fonctionnel idiomatique de manière fiable, est-il fonctionnel? La réponse est un jugement, comme vous dites, mais une distinction importante dans la pratique. Martin Trojer vient de publier un article de blog intéressant à ce sujet: martinsprogrammingblog.blogspot.com/2011/11/…
JD
2
encore, juste parce que la JVM (malheureusement, pas de question) ne peut pas faire d'appels de queue, cela ne signifie pas que l'élimination des appels de queue est impossible. C'est comme si l'on affirmait que les calculs en virgule flottante ne sont possibles que sur les ordinateurs avec FPU.
Ingo
22

Scala 2.7.x prend en charge l'optimisation des appels de fin pour l'auto-récursivité (une fonction qui s'appelle elle-même) des méthodes finales et des fonctions locales.

Scala 2.8 pourrait également être fourni avec le support de la bibliothèque pour le trampoline, qui est une technique pour optimiser les fonctions mutuellement récursives.

De nombreuses informations sur l'état de la récursivité Scala sont disponibles sur le blog de Rich Dougherty .

Daniel C. Sobral
la source
Pouvez-vous, s'il vous plaît, mettre à jour la question sur l'état actuel de la scala?
om-nom-nom
@ om-nom-nom AFAIK, rien n'a changé, ni côté Scala, ni côté JVM.
Daniel C.Sobral
0

Toutes les sources indiquent que la JVM est incapable d'optimiser dans le cas de la récursivité de la queue, mais en lisant le réglage des performances de Java (2003, O'reilly), j'ai trouvé l'auteur affirmant qu'il pouvait obtenir de meilleures performances de récursivité en implémentant la récursivité de la queue.

Vous pouvez trouver sa revendication à la page 212 (recherchez 'tail recursion', cela devrait être le deuxième résultat). Ce qui donne?

penseur
la source
IBM a pris en charge une certaine forme de TCO dans leur implémentation JVM (en tant qu'optimisation, donc aucune garantie). Peut-être que les auteurs du réglage des performances Java pensaient que cette fonctionnalité serait éventuellement implémentée par toutes les machines virtuelles Java. ibm.com/developerworks/java/library/j-diag8.html
llemieng