Cách sử dụng TailCalls?

Question

Nếu tôi hiểu đúng, scala.util.control.TailCalls có thể được sử dụng để tránh tràn ngăn xếp cho các chức năng không đuôi-đệ quy bằng cách sử dụng một tấm bạt lò xo. Ví dụ được đưa ra trong API là đơn giản:

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 

Tuy nhiên, trường hợp thú vị hơn là nếu bạn muốn làm một số hoạt động sau cuộc gọi recursve. Tôi nhận được triển khai giai thừa "ngây thơ" bằng cách nào đó chạy bằng cách

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

nhưng điều này có vẻ khủng khiếp và tôi nghi ngờ rằng đây là mục đích sử dụng. Vì vậy, câu hỏi của tôi là làm thế nào để viết một hàm giai thừa hoặc hàm một cách chính xác bằng cách sử dụng TailCalls (có, tôi biết làm thế nào để sử dụng accumulators để có được chúng đệ quy đuôi)? Hay là TailCalls không phù hợp với loại vấn đề này?

Answer 1

Vâng, thừa ngây thơ của bạn sẽ không đuôi đệ quy, và sẽ sử dụng ngăn xếp không gian tuyến tính vào giá trị của các đối số. Mục đích của scala.util.control.TailCalls không phải là kỳ diệu biến thuật toán không đệ quy đuôi thành đuôi đệ quy. Mục đích của nó là cho phép các chu kỳ của các hàm được gọi lẫn nhau được thực hiện trong không gian ngăn xếp không đổi.

Trình biên dịch Scala thực hiện đuôi-đệ quy tối ưu hóa cho các phương pháp mà tự gọi mình là ở vị trí đuôi, cho phép các khung stack của phương pháp gọi điện thoại để được sử dụng bởi người gọi. Nó thực hiện điều này về cơ bản bằng cách chuyển đổi một cuộc gọi có độ dài đệ quy đến một vòng lặp while, bên dưới nắp. Tuy nhiên, do hạn chế JVM không có cách nào để nó triển khai tối ưu hóa cuộc gọi đuôi, điều này sẽ cho phép bất kỳ cuộc gọi phương thức nào ở vị trí đuôi để sử dụng lại khung ngăn xếp của người gọi. Điều này có nghĩa rằng nếu bạn có hai hoặc nhiều phương thức gọi nhau ở vị trí đuôi, không có tối ưu hóa nào được thực hiện và ngăn xếp ngăn xếp sẽ bị rủi ro. scala.util.control.TailCalls là một hack cho phép bạn làm việc xung quanh vấn đề này.

BTW, Nó cũng có giá trị xem xét các nguồn để scala.util.control.TailCalls. Cuộc gọi "kết quả" là nơi tất cả các công việc thú vị được thực hiện, và về cơ bản nó chỉ là một vòng lặp while bên trong.

Answer 2

Câu hỏi này là hơn 6 tuổi, nhưng câu trả lời chấp nhận dường như không trả lời câu hỏi:

Vì vậy, câu hỏi của tôi là làm thế nào để viết một hàm giai thừa hoặc fibonacci một cách chính xác bằng TailCalls (vâng, Tôi biết làm thế nào để sử dụng ắc quy để có được chúng đệ quy đuôi)?

Vì vậy, ở đây nó là:

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) 

Một trong những trường hợp sử dụng lớn cho việc sử dụng TailCalls là để làm cái gì đó là phải gấp như thế nào.