Kotlin: Tail đệ quy cho các chức năng hai bên đệ quy

Question

Giả sử tôi viết code như thế này:

tailrec fun odd(n: Int): Boolean = 
     if (n == 0) false 
     else even(n - 1) 

tailrec fun even(n: Int): Boolean = 
     if (n == 0) true 
     else odd(n - 1) 

fun main(args:Array<String>) { 
    // :(java.lang.StackOverflowError 
    System.out.println(even(99999)) 
} 

Làm thế nào để tôi nhận được Kotlin để tối ưu hóa các chức năng này đôi bên cùng có đệ quy, vì vậy mà tôi có thể chạy mà không cần main ném một StackOverflowError? Từ khóa tailrec hoạt động cho đệ quy hàm đơn, nhưng không có gì phức tạp hơn. Tôi cũng thấy một cảnh báo rằng không có cuộc gọi đuôi nào được tìm thấy khi từ khóa tailrec được sử dụng. Có lẽ đây là quá khó khăn cho trình biên dịch?

Answer 1

Điều bạn đang tìm kiếm là "cuộc gọi đuôi thích hợp". JVM không hỗ trợ chúng, vì vậy bạn cần trampolines.

Cuộc gọi đuôi thích hợp dọn sạch bộ nhớ của chức năng riêng của nó (tham số, biến cục bộ) trước khi nhảy (thay vì gọi) đến đuôi được gọi là hàm. Bằng cách đó, đuôi được gọi là hàm có thể quay trở lại trực tiếp đến hàm người gọi của nó. Sự đệ quy lẫn nhau vô hạn là có thể. (Trong các ngôn ngữ chức năng, đây là một trong những tính năng quan trọng nhất.)

Để cho phép các cuộc gọi đuôi thích hợp trong assembly, bạn cần một lệnh để nhảy (goto) đến một thường trình/phương thức được gọi thông qua con trỏ. OOP cần các cuộc gọi (lưu trữ vị trí để nhảy trở lại trên stack và sau đó nhảy) đến một thói quen/phương pháp được gọi thông qua con trỏ.

Bạn có thể mô phỏng các cuộc gọi đuôi thích hợp với mẫu thiết kế tấm bạt lò xo, có thể có một số hỗ trợ qua thư viện. Tấm bạt lò xo là vòng lặp trong khi gọi một hàm trả về tham chiếu đến hàm tiếp theo, trả về tham chiếu đến hàm kế tiếp ...

Answer 2

By wikipedia https://en.wikipedia.org/wiki/Tail_call:

một cuộc gọi đuôi là lời kêu gọi chương trình con thực hiện như các hành động cuối cùng của một thủ tục. Nếu cuộc gọi đuôi có thể dẫn đến cùng một chương trình con được gọi lại sau trong chuỗi cuộc gọi, chương trình con được gọi là đệ quy đuôi

Vì vậy, trường hợp của bạn không phải là đệ quy đuôi theo định nghĩa. Đó không phải là lời cảnh báo.

Hiện tại không có cách nào trình biên dịch sẽ tối ưu hóa điều đó, chủ yếu là do đó là một tình huống rất hiếm. Nhưng tôi không chắc chắn rằng ngay cả Haskel tối ưu hóa mà đi.

Answer 3

Đây là việc thực hiện của @ comonad trampoline suggestion. Nó hoạt động!

import kotlin.reflect.KFunction 

typealias Result = Pair<KFunction<*>?, Any?> 
typealias Func = KFunction<Result> 

tailrec fun trampoline(f: Func, arg: Any?): Any? { 
    val (f2,arg2) = f.call(arg) 
    @Suppress("UNCHECKED_CAST") 
    return if (f2 == null) arg2 
     else trampoline(f2 as Func, arg2) 
} 

fun odd(n: Int): Result = 
     if (n == 0) null to false 
     else ::even to n-1 

fun even(n: Int): Result = 
     if (n == 0) null to true 
     else ::odd to n-1 

fun main(args:Array<String>) { 
    System.out.println(trampoline(::even, 9999999)) 
}