Pourquoi le compilateur Scala n'applique-t-il pas l'optimisation de l'appel final si une méthode n'est pas finale?

Question

Pourquoi le compilateur Scala n'applique-t-il pas l'optimisation de l'appel final si une méthode n'est pas finale?

Par exemple, ceci:

 class C {
    @tailrec def fact(n: Int, result: Int): Int =
        if(n == 0)
            result
        else
            fact(n - 1, n * result)
}
 

résulte en

error: impossible d'optimiser la méthode annotée @tailrec: elle n'est ni privée ni finale, elle peut donc être remplacée

Qu'est-ce qui se passerait exactement si le compilateur appliquait le TCO dans un cas comme celui-ci?

Answer 1

Considérons la suite de l'interaction avec le REPL. Nous avons d'abord définir une classe avec une méthode factorielle:

scala> class C {
         def fact(n: Int, result: Int): Int =
         if(n == 0) result else fact(n - 1, n * result)
       }
defined class C

scala> (new C).fact(5, 1)
res11: Int = 120

Maintenant, nous allons le remplacer dans une sous-classe pour le double de la super-classe de la réponse:

scala> class C2 extends C {
         override def fact(n: Int, result: Int): Int = 2 * super.fact(n, result)
       }
defined class C2

scala> (new C).fact(5, 1)
res12: Int = 120

scala> (new C2).fact(5, 1)

Quels résultats attendez-vous de ce dernier appel? Vous pourriez attendre de 240. Mais non:

scala> (new C2).fact(5, 1)
res13: Int = 7680

C'est parce que lors de la super-classe de la méthode fait appel récursif, l'appel récursif passe par la sous-classe.

Si une substitution travaillé tels que 240 était la bonne réponse, alors il serait sans danger pour la queue-appel d'optimisation pour être exécutée dans la super-classe ici. Mais ce n'est pas comment Scala (ou Java) fonctionne.

À moins qu'une méthode est marqué en finale, il pourrait ne pas être l'appel de lui-même quand il fait un appel récursif.

Et c'est pourquoi @tailrec ne fonctionne pas sauf si une méthode est définitive (ou privé).

Mise à JOUR: je vous recommande de lire les deux autres réponses (Jean et de Rex) ainsi.

Answer 2

Les appels récursifs peut-être à une sous-classe à la place d'une super-classe; final permettra d'éviter que. Mais pourquoi voudriez-vous ce comportement? La suite de Fibonacci ne fournit pas d'indices. Mais ce n':

class Pretty {
  def recursivePrinter(a: Any): String = { a match {
    case xs: List[_] => xs.map(recursivePrinter).mkString("L[",",","]")
    case xs: Array[_] => xs.map(recursivePrinter).mkString("A[",",","]")
    case _ => a.toString
  }}
}
class Prettier extends Pretty {
  override def recursivePrinter(a: Any): String = { a match {
    case s: Set[_] => s.map(recursivePrinter).mkString("{",",","}")
    case _ => super.recursivePrinter(a)
  }}
}

scala> (new Prettier).recursivePrinter(Set(Set(0,1),1))
res8: String = {{0,1},1}

Si la Jolie appel a été récursives terminales, nous avions imprimer {Set(0, 1),1} plutôt car l'extension ne s'applique pas.

Puisque ce genre de récursivité est plausible utile, et serait détruite si la queue d'appels sur non-finale méthodes ont été autorisés, le compilateur insère un véritable appel à la place.

Answer 3

Laissez foo::fact(n, res) indiquent que votre routine. Laissez-baz::fact(n, res) denone de quelqu'un d'autre remplacement de votre routine.

Le compilateur est vous dire que la sémantique permettent baz::fact() pour être un wrapper, qui PEUT upcall (?) foo::fact() si elle veut. Dans un tel scénario, la règle est que les foo::fact(), quand il revient, doit activer baz::fact() plutôt que de foo::fact(), et, tandis que les foo::fact() est récursives terminales, baz::fact() ne peut pas être. À ce point, plutôt que d'en boucle sur la queue-appel récursif, foo::fact() doit retourner à baz::fact(), de sorte qu'il peut se détendre lui-même.

Answer 4

Qu'est-ce qui se passerait exactement si le compilateur appliquait le TCO dans un cas comme celui-ci?

Rien n'irait mal. Cela s’appliquera à toutes les langues avec élimination des appels de queue appropriés (SML, OCaml, F #, Haskell, etc.). La seule raison pour laquelle Scala ne le fait pas, c'est que la machine virtuelle Java ne prend pas en charge la récursion de la queue et que le piratage habituel de Scala consistant à remplacer les appels auto-récursifs en position de queue par goto ne fonctionne pas dans ce cas. Scala sur le CLR pourrait le faire comme le fait F #.