Perché il ritorno in getOrElse non rende possibile la ricorsione in coda?

Question

Sono confuso dal seguente codice: il codice è artificiale, ma continuo a pensare che sia ricorsivo in coda. Il compilatore non è d'accordo e produce un messaggio di errore:

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    None.getOrElse(return s) 
    } 
    listSize(l.tail, s + 1) 
} 

Come è possibile che il codice sopra non renda possibile la codifica della coda? Perché il compilatore mi dice:

could not optimize @tailrec annotated method listSize: it contains a recursive call not in tail position

Un codice simile (con return interno map) compila bene:

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    Some(()).map(return s) 
    } 
    listSize(l.tail, s + 1) 
} 

Anche il codice ottenuto con inlining None.isEmpty compila bene:

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    if (None.isEmpty) { 
     return s 
    } else None.get 
    } 
    listSize(l.tail, s + 1) 
} 

D'altra parte, il codice con la mappa leggermente modificata è rifiutato dalla compilation er e produce l'errore:

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    Some(()).map(x => return s) 
    } 
    listSize(l.tail, s + 1) 
} 

Answer 1

Succede perché lo return nel primo frammento di codice è non locale (è annidato all'interno di un lambda). Scala usa eccezioni per compilare non locali return espressioni, in modo che il codice viene trasformato dal compilatore da questo:

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    None.getOrElse(return s) 
    } 
    listSize(l.tail, s + 1) 
} 

Per qualcosa di simile a questo (compilare con scalac -Xprint:tailcalls):

def listSize2(l : Seq[Any], s: Int = 0): Int = { 
    val key = new Object 

    try { 
    if (l.isEmpty) { 
     None.getOrElse { 
     throw new scala.runtime.NonLocalReturnControl(key, 0) 
     } 
    } 

    listSize2(l.tail, s + 1) 
    } catch { 
    case e: scala.runtime.NonLocalReturnControl[Int @unchecked] => 
     if (e.key == key) 
     e.value 
     else 
     throw e 
    } 
} 

Il l'ultimo punto è che le chiamate ricorsive non sono chiamate di coda quando sono racchiuse in blocchi try/catch.Fondamentalmente, questo contrieved esempio:

def self(a: Int): Int = { 
    try { 
    self(a) 
    } catch { 
    case e: Exception => 0 
    } 
} 

è simile a questo, che è, ovviamente, non tail-ricorsiva:

def self(a: Int): Int = { 
    if (self(a)) { 
    // ... 
    } else { 
    // ... 
    } 
} 

Ci sono alcuni casi particolari in cui è possibile ottimizzare questo (fino a due stack frame, se non uno), ma non sembra esistere una regola universale da applicare a questo tipo di situazione.

Inoltre, il return espressione in questo frammento, non è un non locale return, motivo per cui la funzione può essere ottimizzata:

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    // `return` happens _before_ map `is` called. 
    Some(()).map(return s) 
    } 
    listSize(l.tail, s + 1) 
} 

Le opere sopra perché, a Scala, return e è un'espressione, Non una dichiarazione. Il suo tipo è Nothing, che è un sottotipo di tutto, incluso Unit => X, che è il tipo richiesto dal parametro map. La valutazione è abbastanza semplice, e viene restituito dalla funzione di inclusione prima che venga eseguito anche map (gli argomenti vengono valutati prima della chiamata al metodo, ovviamente). Potrebbe essere fonte di confusione perché ti aspetteresti che losia analizzato/interpretato come map(_ => return e), ma non lo è.

Answer 2

return rompe sempre le chiamate di ricorsione. Dovresti cambiare il tuo codice in qualcosa del genere:

@tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    l match { 
    case Nil => s 
    case head :: tail => listSize(tail, s + 1) 
    } 
} 

Answer 3

Non riesco a provarlo in questo momento, ma risolverà il problema?

@annotation.tailrec 
def listSize(l : Seq[Any], s: Int = 0): Int = { 
    if (l.isEmpty) { 
    None.getOrElse(return s) 
    } else { 
    listSize(l.tail, s + 1) 
    } 
} 

Utilizzando if-else, invece di if assicurerà la dichiarazione if restituire qualcosa sempre.

Answer 4

Questo è quasi sicuramente un bug con il compilatore o una funzionalità parzialmente implementata.

Molto probabilmente ha a che fare con l'implementazione di return in un'espressione in Scala. Le istruzioni non locali return vengono implementate utilizzando le eccezioni, in modo che quando viene chiamato lo return, venga generato un NonLocalReturnException e l'intera espressione sia racchiusa in un try-catch. Scommetto che lo x => return x viene convertito in un'espressione nidificata, che, se racchiusa in un try-catch, confonde il compilatore nel determinare se può utilizzare @tailrec. Direi che usare @tailrec in combinazione con lo standard locale return dovrebbe essere evitato.

Ulteriori informazioni sull'implementazione di return in Scala nel this post del blog o nella domanda this.