TailCalls nasıl kullanılır?

Question

Eğer doğru bir şekilde anlıyorsam, scala.util.control.TailCalls, kuyruk-özyinelemeli işlevler için bir tramplen kullanarak yığın taşmalarını önlemek için kullanılabilir. API verilen örnek nettir: recursve çağrı sonrasında bazı işlemleri yapmak istiyorsanız

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 

Ancak daha ilginç bir durumdur. Ben bir "naif" faktöryel uygulama nasılsa

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

tarafından çalışan ama bu korkunç görünüyor ve bu amaçlanan kullanımıdır şüphe var. Yani benim sorum TailCalls kullanarak doğru bir faktöriyel veya fibonacci fonksiyonu yazmak (evet, ben onları kuyruk-özyinelemeye almak için akümülatörler kullanmayı biliyorum)? Ya da TailCalls bu tür bir problem için uygun değil mi?

Answer 1

Evet, naif faktörünüzün özyinelemeli olmayacak ve argüman değerinde doğrusal yığın alanını kullanacaktır. Scala.util.control.TailCalls'ın amacı kuyruksuz özyinelemeli algoritmaları kuyruk özyinelemeli olanlara dönüştürmek değildir. Amaç, sürekli yığın adı verilen işlevlerin döngüsel yığın yığınında yürütülmesine izin vermektir.

Scala derleyicisi, arama kuyruğunun çağrı çerçevesinin arayan tarafından kullanılmasına olanak tanıyan, kuyruk pozisyonunda kendilerini çağıran yöntemler için kuyruk yineleme optimizasyonunu uygular. Bunu esasen, bir kuyruk-özyinelemeli aramayı kapakların altında bir süre-döngüsüne dönüştürerek yapar. Bununla birlikte, JVM kısıtlamaları nedeniyle, kuyruk arama optimizasyonunu uygulamak için bir yol yoktur; bu, kuyruktaki istif çerçevesini yeniden kullanmak için kuyruk pozisyonunda herhangi bir yöntemin çağrılmasına izin verir. Bu, kuyruk pozisyonunda birbirini arayan iki veya daha fazla yönteme sahipseniz, herhangi bir optimizasyon yapılmayacağı ve yığın taşması riskinin oluşacağı anlamına gelir. scala.util.control.TailCalls, bu soruna geçici bir çözüm bulunmasına izin veren bir saldırıdır.

BTW, scala.util.control.TailCalls kaynağına bakmaya değer. "Sonuç" çağrısı, tüm ilginç işlerin yapıldığı yer ve temelde sadece bir süre döngü içinde.

Answer 2

Bu soru fazla 6 yaşında, ama kabul cevap soruyu cevaplamak için görünmüyor:

Benim soru evet (doğru TailCalls kullanarak faktöryel veya Fibonacci fonksiyonunu nasıl yazılacağını olduğunu Akümülatörleri nasıl kuyruk özyinelemeyi nasıl kullanacağımı biliyorum)?

Yani, işte burada: TailCalls kullanmak için

büyük kullanım senaryoları arasında

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) 

Bir sağ kat benzeri bir şey yapmaktır.