Kotlin: recursión de queue para funciones mutuamente recursivas

Supongamos que escribo un código como este:

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

¿Cómo hago para que Kotlin optimice estas funciones mutuamente recursivas, de modo que pueda ejecutar main sin lanzar StackOverflowError? La palabra key tailrec funciona para la recursión de una sola function, pero nada más complicado. También veo una advertencia de que no se encuentran llamadas tailrec las que se tailrec palabra key tailrec . Tal vez esto es demasiado difícil para los comstackdores?

Lo que estás buscando son "llamadas de queue adecuadas". La JVM no es compatible con eso, por lo que necesita trampolines .

Una llamada de queue apropiada limpia la memory de su propia function (parameters, variables locales) antes de saltar (en lugar de llamar) a la queue llamada function. De esta forma, la queue llamada function puede regresar directamente a su function llamador-llamador. Recursión mutua infinita es posible. (En lenguajes funcionales esta es una de las características más importantes).

Para permitir llamadas de queue adecuadas en el ensamblador, necesitaría un command para saltar (ir a) a una rutina / método al que se hace reference mediante un puntero. OOP necesita llamadas (almacena la location para saltar a la stack y luego salta) a una rutina / método al que se hace reference mediante un puntero.

Puede emular las llamadas de queue adecuadas con el patrón de layout de trampolín, quizás haya algún tipo de soporte a través de la biblioteca. El trampolín es un ciclo while que llama a una function que devuelve una reference a la siguiente function que devuelve una reference al siguiente …

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

una llamada de queue es una llamada de subrutina realizada como la acción final de un procedimiento. Si una llamada de queue puede dar lugar a que se vuelva a llamar a la misma subrutina más adelante en la cadena de llamada, se dice que la subrutina es recursiva de queue

Entonces su caso no es una recursion de queue por definición. Eso es lo que dice la advertencia.

Actualmente no hay forma de que el comstackdor optimice eso, principalmente porque es una situación muy rara. Pero no estoy seguro de que incluso Haskel lo optimice.

Aquí hay una implementación de la sugerencia de trampolín de @ comonad. ¡Funciona!

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