Wie benutzt man TailCalls?

Question

Wenn ich richtig verstehe, kann scala.util.control.TailCalls verwendet werden, um Stapelüberläufe für nicht-tail-rekursive Funktionen zu vermeiden, indem Sie ein Trampolin verwenden. Das Beispiel in der API gegeben ist einfach:

import scala.util.control.TailCalls._ 

def isEven(xs: List[Int]): TailRec[Boolean] = 
    if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail)) 

def isOdd(xs: List[Int]): TailRec[Boolean] = 
    if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail)) 

isEven((1 to 100000).toList).result 

jedoch umso interessanter Fall ist, wenn Sie einige Operationen nach der recursve Anruf machen wollen. Ich habe eine „naive“ faktorielles Umsetzung irgendwie durch

def fac(n:Long): TailRec[Long] = 
    if (n == 0) done(1) else done(n * tailcall(fac(n - 1)).result) 

läuft, aber das sieht schrecklich und ich bezweifle, dass dies nicht die beabsichtigte Verwendung ist. Also meine Frage ist, wie man eine Fakultät oder Fibonacci-Funktion korrekt mit TailCalls schreiben kann (ja, ich weiß, wie man Akkumulatoren verwendet, um sie tail-rekursiv zu bekommen)? Oder ist TailCalls nicht für diese Art von Problem geeignet?

Answer 1

Ja, Ihr naiv factorial wird nicht tail rekursiv sein und wird stack space linear im Wert des Arguments verwenden. Der Zweck von scala.util.control.TailCalls besteht nicht darin, nicht-tail-rekursive Algorithmen magisch in tail-rekursive umzuwandeln. Der Zweck besteht darin, Zyklen von gegenseitig tail-aufgerufenen Funktionen in einem konstanten Stapelraum auszuführen.

Der Scala-Compiler implementiert eine Tail-Recursion-Optimierung für Methoden, die sich in Tail-Position aufrufen, wodurch der Aufrufer das Stack-Frame der aufrufenden Methode verwenden kann. Dies geschieht im wesentlichen durch Umwandlung eines nachweisbar tail-rekursiven Aufrufs in eine while-Schleife unter der Decke. Aufgrund von JVM-Einschränkungen ist es jedoch nicht möglich, eine Tail-Call-Optimierung zu implementieren, die es jedem Methodenaufruf in der Endposition ermöglicht, den Stack-Frame des Aufrufers wiederzuverwenden. Das bedeutet, wenn Sie zwei oder mehr Methoden haben, die sich gegenseitig in der Endposition aufrufen, wird keine Optimierung durchgeführt, und der Stack-Überlauf wird riskiert. scala.util.control.TailCalls ist ein Hack, mit dem Sie dieses Problem umgehen können.

BTW, Es lohnt sich, die Quelle zu scala.util.control.TailCalls zu suchen. Der "Ergebnis" -Aufruf ist der Ort, an dem die ganze interessante Arbeit erledigt wird, und es ist im Grunde nur eine While-Schleife drin.

Answer 2

Diese Frage mehr als 6 Jahre alt ist, aber die akzeptierte Antwort scheint nicht die Frage zu beantworten:

So wie meine Frage ist eine faktorielle oder Fibonacci-Funktion korrekt mit TailCalls (ja zu schreiben, Ich weiß, wie man Akkumulatoren benutzt, um sie tailrekursiv zu machen.

So, hier ist es:

object Factorial { 

    /** 
    * Returns the nth factorial 
    */ 
    def apply(n: Long): BigInt = { 
    if (n < 0) 
     throw new IllegalArgumentException("Can't factorial to an index less than 0") 
    else { 
     import scala.util.control.TailCalls._ 
     def step(current: Long): TailRec[BigInt] = { 
     if (current <= 0) 
      done(1) 
     else 
      tailcall { 
      for { 
       next <- step(current - 1) 
      } yield current * next 
      } 
     } 
     step(n).result 
    } 
    } 

} 

assert(Factorial(0) == 1) 
assert(Factorial(7) == 5040) 
assert(Factorial(10) == 3628800) 

Einer der großen Anwendungsfälle für TailCalls mit etwas zu tun, das Recht fach artig ist.