Che cos'è l'annotazione Scala per garantire che una funzione ricorsiva della coda sia ottimizzata?

Question

Penso che ci sia l'annotazione @tailrec per assicurare che il compilatore ottimizzi una funzione ricorsiva della coda. Lo metti di fronte alla dichiarazione? Funziona anche se Scala viene utilizzato in modalità di script (ad esempio utilizzando :load <file> in REPL)?

Answer 1

Dal post "Tail calls, @tailrec and trampolines" blog:

• In Scala 2.8, sarà anche in grado di utilizzare la nuova @tailrec di annotazione per ottenere informazioni su quali sono ottimizzati metodi.
  Questa annotazione consente di contrassegnare metodi specifici che si spera che il compilatore ottimizzi.
  Avrai quindi un avviso se non sono ottimizzati dal compilatore.
• In Scala 2.7 o versioni precedenti, è necessario fare affidamento sul test manuale o sull'ispezione del bytecode per stabilire se un metodo è stato ottimizzato.

Esempio:

si potrebbe aggiungere un'annotazione @tailrec in modo che si può essere certi che le modifiche hanno funzionato.

import scala.annotation.tailrec 

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

---

E funziona dal REPL (ad esempio dalla Scala REPL tips and tricks):

C:\Prog\Scala\tests>scala 
Welcome to Scala version 2.8.0.RC5 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_18). 
Type in expressions to have them evaluated. 
Type :help for more information. 

scala> import scala.annotation.tailrec 
import scala.annotation.tailrec 

scala> class Tails { 
    | @tailrec def boom(x: Int): Int = { 
    | if (x == 0) throw new Exception("boom!") 
    | else boom(x-1)+ 1 
    | } 
    | @tailrec def bang(x: Int): Int = { 
    | if (x == 0) throw new Exception("bang!") 
    | else bang(x-1) 
    | } 
    | } 
<console>:9: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position 
     @tailrec def boom(x: Int): Int = { 
        ^
<console>:13: error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden 
     @tailrec def bang(x: Int): Int = { 
        ^

Answer 2

Il compilatore Scala ottimizzerà automaticamente qualsiasi metodo veramente ricorsivo alla coda. Se annoti un metodo che ritieni sia ricorsivo in coda con l'annotazione @tailrec, il compilatore ti avviserà se il metodo non è effettivamente ricorsivo in coda. Ciò rende l'annotazione @tailrec una buona idea, sia per garantire che un metodo sia attualmente ottimizzabile e che rimanga ottimizzato in quanto modificato.

Si noti che Scala non considera un metodo per essere ricorsivo in coda se può essere sovrascritto. Quindi il metodo deve essere privato, finale, su un oggetto (al contrario di una classe o tratto) o all'interno di un altro metodo da ottimizzare.

Answer 3

L'annotazione è scala.annotation.tailrec. Si innesca un errore del compilatore se il metodo non può essere chiamata coda ottimizzata, che avviene se:

1. La chiamata ricorsiva non è nella posizione di coda
2. Il metodo potrebbe essere sovrascritto
3. Il metodo non è finale (caso speciale del precedente)

Si trova poco prima dello def in una definizione di metodo. Funziona nella REPL.

Qui importiamo l'annotazione e proviamo a contrassegnare un metodo come @tailrec.

scala> import annotation.tailrec 
import annotation.tailrec 

scala> @tailrec def length(as: List[_]): Int = as match { 
    | case Nil => 0 
    | case head :: tail => 1 + length(tail) 
    | } 
<console>:7: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position 
     @tailrec def length(as: List[_]): Int = as match { 
        ^

Oops!L'ultima chiamata è 1.+(), non length()! Cerchiamo di riformulare il metodo:

scala> def length(as: List[_]): Int = {         
    | @tailrec def length0(as: List[_], tally: Int = 0): Int = as match { 
    |  case Nil   => tally          
    |  case head :: tail => length0(tail, tally + 1)      
    | }                 
    | length0(as) 
    | } 
length: (as: List[_])Int 

noti che length0 è automaticamente privata perché è definito nell'ambito di un altro metodo.