Chú thích Scala để đảm bảo chức năng đệ quy đuôi được tối ưu hóa là gì?

Question

Tôi nghĩ rằng có chú thích @tailrec để đảm bảo trình biên dịch sẽ tối ưu hóa chức năng đệ quy đuôi. Bạn chỉ cần đặt nó trước tờ khai? Liệu nó cũng làm việc nếu Scala được sử dụng trong chế độ kịch bản (ví dụ bằng cách sử dụng :load <file> dưới REPL)?

Answer 1

Từ bài "Tail calls, @tailrec and trampolines" blog:

• Trong Scala 2.8, bạn cũng sẽ có thể sử dụng các @tailrec chú thích mới để có được thông tin về những phương pháp được tối ưu hóa.
  Chú thích này cho phép bạn đánh dấu các phương pháp cụ thể mà bạn hy vọng trình biên dịch sẽ tối ưu hóa.
  Sau đó, bạn sẽ nhận được cảnh báo nếu chúng không được trình biên dịch tối ưu hóa.
• Trong Scala 2.7 hoặc cũ hơn, bạn sẽ cần phải dựa vào kiểm tra thủ công hoặc kiểm tra mã bytecode để tìm hiểu xem phương pháp đã được tối ưu hóa chưa.

Ví dụ:

bạn có thể thêm chú thích @tailrec để bạn có thể chắc chắn rằng những thay đổi của bạn đã làm việc.

import scala.annotation.tailrec 

class Factorial2 { 
    def factorial(n: Int): Int = { 
    @tailrec def factorialAcc(acc: Int, n: Int): Int = { 
     if (n <= 1) acc 
     else factorialAcc(n * acc, n - 1) 
    } 
    factorialAcc(1, n) 
    } 
} 

---

Và nó hoạt động từ REPL (ví dụ từ Scala REPL tips and tricks):

C:\Prog\Scala\tests>scala 
Welcome to Scala version 2.8.0.RC5 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_18). 
Type in expressions to have them evaluated. 
Type :help for more information. 

scala> import scala.annotation.tailrec 
import scala.annotation.tailrec 

scala> class Tails { 
    | @tailrec def boom(x: Int): Int = { 
    | if (x == 0) throw new Exception("boom!") 
    | else boom(x-1)+ 1 
    | } 
    | @tailrec def bang(x: Int): Int = { 
    | if (x == 0) throw new Exception("bang!") 
    | else bang(x-1) 
    | } 
    | } 
<console>:9: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position 
     @tailrec def boom(x: Int): Int = { 
        ^
<console>:13: error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden 
     @tailrec def bang(x: Int): Int = { 
        ^

Answer 2

Trình biên dịch Scala sẽ tự động tối ưu hóa bất kỳ phương pháp đệ quy thực sự nào có đuôi. Nếu bạn chú thích một phương pháp mà bạn tin là đệ quy đuôi với chú thích @tailrec, thì trình biên dịch sẽ cảnh báo bạn nếu phương pháp này thực sự không phải đệ quy đuôi. Điều này làm cho chú thích @tailrec là một ý tưởng hay, cả hai để đảm bảo rằng một phương pháp hiện có thể tối ưu hóa và nó vẫn có thể tối ưu hóa khi nó được sửa đổi.

Lưu ý rằng Scala không xem xét một phương pháp có tính đệ quy đuôi nếu nó có thể bị ghi đè. Vì vậy, phương thức này phải là riêng, cuối cùng, trên một đối tượng (trái ngược với một lớp hoặc đặc điểm), hoặc bên trong một phương thức khác để được tối ưu hóa.

Answer 3

Chú thích là scala.annotation.tailrec. Nó gây ra một lỗi biên dịch nếu phương pháp này không thể được gọi đuôi tối ưu hóa, mà sẽ xảy ra nếu:

1. Cuộc gọi đệ quy không phải là ở vị trí đuôi
2. Phương pháp này có thể được overriden
3. Phương pháp này không phải là cuối cùng (trường hợp đặc biệt của số trước)

Nó được đặt ngay trước def trong định nghĩa phương thức. Nó hoạt động trong REPL.

Ở đây, chúng tôi nhập chú thích và thử đánh dấu phương thức là @tailrec.

scala> import annotation.tailrec 
import annotation.tailrec 

scala> @tailrec def length(as: List[_]): Int = as match { 
    | case Nil => 0 
    | case head :: tail => 1 + length(tail) 
    | } 
<console>:7: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position 
     @tailrec def length(as: List[_]): Int = as match { 
        ^

Rất tiếc!Lời gọi cuối cùng là 1.+(), không phải length()! Hãy tái cấu trúc phương pháp:

scala> def length(as: List[_]): Int = {         
    | @tailrec def length0(as: List[_], tally: Int = 0): Int = as match { 
    |  case Nil   => tally          
    |  case head :: tail => length0(tail, tally + 1)      
    | }                 
    | length0(as) 
    | } 
length: (as: List[_])Int 

Lưu ý rằng length0 là tự động tin vì nó được xác định trong phạm vi của phương pháp khác.