14

Suppose I write code like this:

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

How do I get Kotlin to optimize these mutually recursive functions, so that I can run main without throwing a StackOverflowError? The tailrec keyword works for single-function recursion, but nothing more complicated. I also see a warning that no tail-calls are found where the tailrec keyword is used. Perhaps this is too hard for compilers?

Improve this question
2
  • You can add a feature request to youtrack.jetbrains.com for the feature of "mutual tail recursion", that is the best bet if you want it added to Kotlin. Also search there first, in case it is already requested or planned. Commented Mar 1, 2016 at 12:25
  • 1
    I created a Kotlin issue here: youtrack.jetbrains.com/issue/KT-11307 Commented Mar 5, 2016 at 16:51

3 Answers 3

Reset to default
10

What you are looking for are "proper tail calls". The JVM does not support those, so you need trampolines.

A proper tail call cleans up the memory of its own function (parameters, local variables) before jumping (instead of calling) to the tail called function. That way the tail called function can return directly to its caller-caller-function. Infinite mutual recursion is possible. (In functional languages this is one of the most important features.)

To allow proper tail calls in assembler you would need a command to jump (goto) to a routine/method that is referred to via pointer. OOP needs calls (stores location to jump back to on the stack and then jumps) to a routine/method that is referred to via pointer.

You can emulate proper tail calls with the trampoline design pattern, maybe there is some support via library. The trampoline is a while loop that calls a function which returns a reference to the next function which returns a reference to the next...

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Cool, it sounds like we could support this in the JVM by writing a trampoline method which calls method references with given arguments. The even and odd functions should be modified to return method references plus the next argument. We make the first call by calling the trampoline method with a reference to the even function and argument 99999.
4

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

a tail call is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive

So your case is not a tail recursion by definition. That't what the warning says.

Currently there is no way compiler will optimise that, mostly because it is a very rare situation. But I am not sure that even Haskel optimises that away.

Improve this answer

5 Comments

From the same page (slightly edited): "functional languages [like Kotlin] that target the JVM [tend to] implement direct [or self] tail recursion, but not mutual tail recursion." I can assure you that Haskell supports mutual tail recursion.
It does? Cool! I thought so, just because it is Haskell, it would. Thanks for the tip.
Could you clarify further? In the even/odd example, the final action of both even and off is a subroutine call, and we see that the same subroutine is called later in the call chain. Therefore by the definition both functions are tail-recursive.
The relevant Wiki section is here: en.wikipedia.org/wiki/Mutual_recursion#Computer_functions
"Proper Tail Calls" (like in Haskell) are not an optimization; they are a needed guarantee to allow infinite recursion on which the Haskell run time system depends on. (Imagine the first command tail-calls a function given via parameter, which is the second command with its parameter pointing to the third.) Inlining of a function would be an optimization.
4

Here is an implementation of @comonad's trampoline suggestion. It works!

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))
}
Improve this answer

1 Comment

This is neat. Though applying args is not what I intended... Could you implement sth with the following idea? interface PTC<A> { Object run(); static PTC<A> <A>of(Supplier<A> run){...}; static PTC<A> <A>flatten(Supplier<PTC<A>> run){...}; final PTC<B> flatMap(Function<A,PTC<B>> f){PTC<A>self=this;return ()->{return f(trampoline(self))};}; static A trampoline(PTC<A> w){return loop(w);};static A trampoline(A x){return loop(x);};private static A loop(Object wx){while(wx instanceof PTC){wx=((PTC)wx).run();} return wx;};}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.