Scala prend-il en charge l'optimisation de la récursion de la queue ?

Question

Scala prend-il en charge l'optimisation de la récursion de la queue ?

Answer 1

Scala optimise la récursion de la queue au moment de la compilation, comme l'ont dit d'autres posteurs. En d'autres termes, une fonction récursive de queue est transformée en une boucle par le compilateur (un appel de méthode est transformé en un saut), comme on peut le voir dans la trace de la pile lors de l'exécution d'une fonction récursive de queue.

Essayez l'extrait suivant :

def boom(n: Int): Nothing = if(n<=0) throw new Exception else boom(n-1)
boom(10)

et inspecter la trace de la pile. Il ne montrera qu'un seul appel à la fonction boom - donc le bytecode compilé n'est pas récursif.

Il y a une proposition qui circule pour implémenter les appels de queue au niveau de la JVM - ce qui, à mon avis, serait une excellente chose à faire, car la JVM pourrait alors effectuer des optimisations au moment de l'exécution, plutôt que de se contenter d'optimisations du code au moment de la compilation - et pourrait éventuellement signifier une récursion de queue plus flexible. Fondamentalement, un tailcall invoke se comporterait exactement comme une méthode normale invoke La spécification de la JVM stipule que les cadres de pile doivent être préservés. Le JIT doit donc procéder à une analyse statique du code pour déterminer si les cadres de pile ne seront jamais utilisés.

Son état actuel est le suivant proto 80 . Je ne pense pas que cela sera fait à temps pour Java 7 ( invokedynamic a une plus grande priorité, et l'implémentation est presque terminée) mais Java 8 pourrait le voir implémenté.

Answer 2

En Scala 2.8, vous pouvez utiliser @tailrec pour marquer une méthode spécifique que vous souhaitez voir optimisée par le compilateur :

import scala.annotation.tailrec

@tailrec def factorialAcc(acc: Int, n: Int): Int = {
  if (n <= 1) acc
  else factorialAcc(n * acc, n - 1)
}

Si une méthode ne peut pas être optimisée, vous obtenez une erreur de compilation.

Answer 3

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

Scala 2.8 pourrait également être doté d'une bibliothèque prenant en charge le trampoline, qui est une technique permettant d'optimiser les fonctions récursives mutuelles.

Une bonne quantité d'informations sur l'état de la récursion en Scala peut être trouvée dans Le blog de Rich Dougherty .

Answer 4

Seulement dans des cas très simples où la fonction est auto-récursive.

Preuve de la capacité de récursion de la queue.

Il semble que Scala 2.8 pourrait améliorer la reconnaissance des récursions de queue, cependant.