Clojure n'effectue pas lui-même l'optimisation de l'appel final: lorsque vous avez une fonction récursive et que vous souhaitez l'optimiser, vous devez utiliser le formulaire spécial recur
. De même, si vous avez deux fonctions mutuellement récursives, vous ne pouvez les optimiser qu'en utilisant trampoline
.
Le compilateur Scala peut effectuer un TCO pour une fonction récursive, mais pas pour deux fonctions mutuellement récursives.
Chaque fois que j'ai lu ces limitations, elles ont toujours été attribuées à des limitations inhérentes au modèle JVM. Je ne connais pratiquement rien des compilateurs, mais cela me laisse un peu perplexe. Permettez-moi de prendre l'exemple de Programming Scala
. Ici la fonction
def approximate(guess: Double): Double =
if (isGoodEnough(guess)) guess
else approximate(improve(guess))
est traduit en
0: aload_0
1: astore_3
2: aload_0
3: dload_1
4: invokevirtual #24; //Method isGoodEnough:(D)Z
7: ifeq
10: dload_1
11: dreturn
12: aload_0
13: dload_1
14: invokevirtual #27; //Method improve:(D)D
17: dstore_1
18: goto 2
Donc, au niveau du bytecode, on a juste besoin goto
. Dans ce cas, en fait, le travail difficile est effectué par le compilateur.
Quelle installation de la machine virtuelle sous-jacente permettrait au compilateur de gérer le TCO plus facilement?
En passant, je ne m'attendrais pas à ce que les machines réelles soient beaucoup plus intelligentes que la JVM. Néanmoins, de nombreuses langues compilées en code natif, telles que Haskell, ne semblent pas avoir de problèmes pour optimiser les appels en queue (et bien, Haskell peut avoir parfois à cause de la paresse, mais c’est un autre problème).
tailcall
instructions pour la machine virtuelle Java ont déjà été proposées dès 2007: blogue sur sun.com via la machine wayback . Après la prise de contrôle d'Oracle, ce lien 404. J'imagine que cela ne figure pas dans la liste des priorités de JVM 7.tailcall
instruction ne marquerait un appel de queue que comme un appel de queue. La question de savoir si la machine virtuelle Java a réellement optimisé l'appel final est une question complètement différente. La CLI CIL a un.tail
préfixe d'instruction, mais le CLR Microsoft 64 bits ne l'a pas optimisé pendant longtemps. OTOH, la machine virtuelle Java IBM J9 ne détecte les appels de la queue et les optimise, sans avoir besoin d' une instruction spéciale pour lui dire que les appels sont des appels de la queue. L'annotation des appels finaux et leur optimisation sont vraiment orthogonaux. (Mis à part le fait que déterminer statiquement quel appel est un appel final peut ou ne peut pas être indécidable. Ne sais pas.)call something; oreturn
. Le travail principal de la mise à jour d'une machine virtuelle Java ne serait pas d'introduire un enseignement explicite appel de queue , mais pour mandat qu'une telle instruction est optimisée. Une telle instruction ne fait que simplifier le travail des auteurs de compilateur: l'auteur de la machine virtuelle Java n'est pas obligé de reconnaître cette séquence d'instructions avant d'être endommagée, et le compilateur X-> bytecode peut être assuré que son bytecode est invalide ou effectivement optimisé, jamais correct, mais débordement de pile.call something; return;
ne serait équivalente à un appel final que si l'appelé appelle jamais une trace de pile; Si la méthode en question est virtuelle ou appelle une méthode virtuelle, la machine virtuelle Java n'aura aucun moyen de savoir si elle peut se renseigner sur la pile.Clojure pourrait effectuer une optimisation automatique de la récursion de la queue en boucles: il est certainement possible de le faire sur la machine virtuelle, comme le prouve Scala.
En réalité, il s'agissait d'une décision de ne pas le faire. Vous devez utiliser explicitement le
recur
formulaire spécial si vous souhaitez utiliser cette fonctionnalité. Voir le fil de discussion Re: Pourquoi l'optimisation des appels de queue sur le groupe Google Clojure.Sur la machine virtuelle Java actuelle, la seule chose impossible est l'optimisation de l'appel final entre différentes fonctions (récursivité mutuelle). Ce n'est pas particulièrement complexe à implémenter (d'autres langages comme Scheme ont cette fonctionnalité depuis le début), mais cela nécessiterait des changements dans les spécifications de la JVM. Par exemple, vous devrez modifier les règles relatives à la préservation de la pile complète d'appels de fonction.
Une future itération de la machine virtuelle Java obtiendra probablement cette fonctionnalité, bien que ce soit probablement une option permettant de conserver un comportement compatible avec les versions antérieures de l'ancien code. Dites, Aperçu des fonctionnalités sur Geeknizer répertorie ceci pour Java 9:
Bien entendu, les futures feuilles de route sont toujours sujettes à changement.
En fin de compte, ce n'est pas si grave. En plus de deux ans de codage de Clojure, je n’ai jamais connu une situation où le manque de coût total de possession était un problème. Les principales raisons à cela sont:
recur
une boucle. Le cas de récurrence de queue mutuelle est assez rare dans le code normalla source
Il ne s'agit pas d'être plus intelligent, mais d'être différent. Jusqu'à récemment, la machine virtuelle Java était conçue et optimisée exclusivement pour un seul langage (Java, évidemment), qui dispose d'une mémoire très stricte et de modèles d'appel.
Non seulement il n'y avait
goto
ni pointeur, ni même aucun moyen d'appeler une fonction "nue" (une méthode qui n'était pas définie dans une classe).Conceptuellement, lorsqu’il cible JVM, un rédacteur de compilateur doit se demander "comment puis-je exprimer ce concept en termes Java?". Et évidemment, il n'y a aucun moyen d'exprimer le TCO en Java.
Notez que ceux-ci ne sont pas considérés comme des échecs de la machine virtuelle Java, car ils ne sont pas nécessaires pour Java. Dès que Java a besoin de telles fonctionnalités, celles-ci sont ajoutées à la JVM.
Ce n'est que récemment que les autorités Java ont commencé à prendre au sérieux la machine virtuelle Java (JVM) en tant que plate-forme pour les langages non Java. Elle a donc déjà obtenu une prise en charge de fonctionnalités qui n'ont pas d'équivalent Java. Le plus connu est le typage dynamique, qui est déjà dans JVM mais pas dans Java.
la source
Avez-vous remarqué que l'adresse de la méthode commence par 0? Que toutes les méthodes d'ensembles commencent par 0? JVM ne permet pas de sauter en dehors d'une méthode.
Je n'ai aucune idée de ce qui se produirait avec une branche dont l'offset en dehors de la méthode était chargé par Java. Peut-être serait-elle capturée par le vérificateur de bytecode, peut-être que cela générerait une exception et peut-être qu'il sauterait en dehors de la méthode.
Le problème, bien sûr, est que vous ne pouvez pas vraiment garantir où seront les autres méthodes de la même classe, et encore moins les méthodes des autres classes. Je doute que JVM donne des garanties quant à l'endroit où elle chargera les méthodes, bien que je serais heureux d'être corrigé.
la source