Kotlin: ricorsione di coda per le funzioni ricorsive reciprocamente

Question

Supponiamo che scrivo codice come questo:

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)) 
} 

Come raggiungo Kotlin per ottimizzare queste funzioni ricorsive reciprocamente, in modo che possa funzionare main senza lanciare uno StackOverflowError? La parola chiave tailrec funziona per la ricorsione a funzione singola, ma nulla di più complicato. Vedo anche un avviso che non vengono trovate chiamate di coda in cui viene utilizzata la parola chiave tailrec. Forse questo è troppo difficile per i compilatori?

Answer 1

Quello che stai cercando sono "chiamate di coda adeguate". La JVM non supporta quelli, quindi è necessario trampolines.

Una chiamata di coda corretta pulisce la memoria della propria funzione (parametri, variabili locali) prima di saltare (anziché chiamare) alla coda chiamata funzione. In questo modo la coda chiamata funzione può tornare direttamente alla sua funzione chiamante-chiamante. È possibile una infinita ricorsione reciproca. (Nelle lingue funzionali questa è una delle funzionalità più importanti.)

Per consentire chiamate di coda corrette nell'assemblatore, è necessario un comando per passare (goto) a una routine/metodo a cui si fa riferimento tramite puntatore. OOP ha bisogno di chiamate (posizione dei negozi per tornare in pila e poi salti) a una routine/metodo a cui si fa riferimento tramite puntatore.

È possibile emulare le chiamate di coda appropriate con il modello di disegno del trampolino, forse c'è un supporto tramite la libreria. Il trampolino è un ciclo while che chiama una funzione che restituisce un riferimento alla funzione successiva che restituisce un riferimento al successivo ...

Answer 2

da Wikipedia https://en.wikipedia.org/wiki/Tail_call:

una chiamata coda è una subroutine eseguita come azione finale di una procedura. Se una chiamata di coda potrebbe portare alla stessa subroutine chiamato più tardi nella catena di chiamate, la subroutine si dice che sia ricorsiva in coda

Quindi il vostro caso non è una ricorsione di coda per definizione. Questo è quello che dice l'avvertimento.

Attualmente non è possibile che il compilatore lo ottimizzi, soprattutto perché si tratta di una situazione molto rara. Ma non sono sicuro che anche Haskel lo ottimizzi.

Answer 3

Ecco un'implementazione di @ comonad's trampoline suggestion. Funziona!

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)) 
}