Warum Rückkehr in getOrElse Tail-Rekursion nicht möglich?

Question

Ich bin durch folgenden Code verwirrt: Der Code ist künstlich, aber ich denke immer noch, es ist Schwanz rekursiv. Der Compiler stimmt nicht zu und erzeugt eine Fehlermeldung:

Wie ist der oben genannte Code, der die Tail Recusion nicht möglich macht? Warum sagt der Compiler mir:

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

Einen ähnlichen Code (mit return innerhalb von map) fein kompiliert:

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

Auch der Code, der durch None.isEmpty inlining kompiliert fein:

@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) 
} 

Auf der anderen Seite ist Code mit leicht modifizierten Karte von der Compil abgelehnt er und erzeugt den Fehler:

@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

Es passiert, weil die return in Ihrem ersten Snippet eine nicht lokale ist (es ist in einem Lambda verschachtelt). Scala nutzt Ausnahmen nicht lokale return Ausdrücke zu kompilieren, so dass der Code wird vom Compiler aus dieser transformierten:

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

Um etwas ähnliche dazu (mit scalac -Xprint:tailcalls kompilieren):

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 
    } 
} 

Die Letzter Punkt ist, dass rekursive Aufrufe keine Tail-Aufrufe sind, wenn sie in try/catch-Blöcke eingeschlossen sind.Im Grunde ist dies contrieved Beispiel:

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

ist verwandt mit diesem, was offensichtlich nicht Schwanz-rekursiv ist:

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

Es gibt einige besondere Fälle, in denen Sie diese optimieren können (bis zu zwei Stapelrahmen, wenn nicht eins), aber es scheint keine universelle Regel für diese Art von Situation zu geben.

Auch der return Ausdruck in diesem Code-Schnipsel, ist kein nicht-lokal return, weshalb die Funktion optimiert werden kann:

@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) 
} 

Die oben genannten Arbeiten, weil in Scala, return e ein Ausdruck ist, keine Stellungnahme. Sein Typ ist Nothing, obwohl das ein Subtyp von allem ist, einschließlich Unit => X, welches der Typ ist, der von map param benötigt wird. Die Auswertung ist jedoch ziemlich einfach, e wird von der umschließenden Funktion zurückgegeben, bevor map sogar ausgeführt wird (Argumente werden offensichtlich vor dem Methodenaufruf ausgewertet). Es kann verwirrend sein, weil Sie erwarten, dass map(return e) als map(_ => return e) geparst/interpretiert wird, aber das ist es nicht.

Answer 2

return immer Rekursion Anrufe bricht. Sie sollten Ihren Code in etwa so ändern:

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

Answer 3

Ich kann es jetzt nicht ausprobieren, aber wird dies das Problem beheben?

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

Mit if-else, statt nur if die if Aussage immer wieder zurückkehren etwas versichern.

Answer 4

Dies ist fast sicher ein Fehler mit dem Compiler oder ein teilweise implementiertes Feature.

Es hat am wahrscheinlichsten mit der Implementierung von return in einem Ausdruck in Scala zu tun. Nicht-lokale return-Anweisungen werden mithilfe von Ausnahmen implementiert. Wenn return aufgerufen wird, wird NonLocalReturnException ausgelöst, und der gesamte Ausdruck wird in eine try-catch verpackt. Ich wette, dass x => return x in einen verschachtelten Ausdruck umgewandelt wird, der, wenn er in eine try-catch eingebunden wird, den Compiler verwirrt, wenn er feststellt, ob er @tailrec verwenden kann. Ich würde so weit gehen zu sagen, dass die Verwendung @tailrec in Verbindung mit nicht-lokalen return sollte vermieden werden.

Lesen Sie mehr über die Implementierung von return in Scala in this Blogpost oder in this Frage.