Mutual tail recursion

The example below shows two functions isEven and isOdd calling each other. This is compiled using trampolines where the actual function calls are replaced with constructor TcContinue and the result is returned in TcDone. The constructor TcContinue will have an index indicating which function to call and the arguments for the function. There will be a top-level function in Idris JVM runtime called tailRec which iterates as long as TcContinue object is returned and returns the result when it gets a TcDone object. This basically ensures that the functions don’t call each other and we trade off the heap for the stack to hold the function arguments. This works for any number of functions, not just two, calling each other in tail position.

mutual
  isEven : Nat -> Bool
  isEven Z = True
  isEven (S k) = isOdd k

  isOdd : Nat -> Bool
  isOdd Z = False
  isOdd (S k) = isEven k

Decompiled Java code

In the decompiled code below, the Idris top-level function isOdd simply calls the runtime function tailRec that iterates between mutually recursive functions. $tcOpt$1 determines which tail-call optimized function to call based on the TcContinue constructor id, and the function is passed to tailRec which keeps on calling this function until it encounters TcDone. isEven$tc1 and isOdd$tc2 are the tail-call optimized versions of respective Idris functions where the recursive call is replaced with TcContinue and the result is returned in TcDone.

public static Object isOdd(Object arg$0) {
    return Runtime.tailRec(Main::$tcOpt$1, new TcContinue_1(2, arg$0));
}

public static Object $tcOpt$1(Object $a$0) {
    Object $a$0 = (IdrisObject)$a$0;
    Object arg$0;
    switch ($a$0.getConstructorId()) {
        case 1:
            arg$0 = ((IdrisObject)$a$0).getProperty(0);
            return isEven$tc1(arg$0);
        case 2:
            arg$0 = ((IdrisObject)$a$0).getProperty(0);
            return isOdd$tc2(arg$0);
        default:
            return null;
    }
}

public static Object isEven$tc1(Object arg$0) {
    BigInteger constantCaseExpr0 = (BigInteger)arg$0;
    int hashCodePosition1 = -1;
    switch (constantCaseExpr0.hashCode()) {
        case 0:
            if (constantCaseExpr0.equals(BigInteger.ZERO)) {
                hashCodePosition1 = 0;
            }
        default:
            switch (hashCodePosition1) {
                case 0:
                    return new TcDone(0, 1);
                default:
                    Object e$0 = ((BigInteger)arg$0).subtract(BigInteger.ONE);
                    return new TcContinue_1(2, e$0);
            }
    }
}

public static Object isOdd$tc2(Object arg$0) {
    BigInteger constantCaseExpr0 = (BigInteger)arg$0;
    int hashCodePosition1 = -1;
    switch (constantCaseExpr0.hashCode()) {
        case 0:
            if (constantCaseExpr0.equals(BigInteger.ZERO)) {
                hashCodePosition1 = 0;
            }
        default:
            switch (hashCodePosition1) {
                case 0:
                    return new TcDone(0, 0);
                default:
                    Object e$0 = ((BigInteger)arg$0).subtract(BigInteger.ONE);
                    return new TcContinue_1(1, e$0);
            }
    }
}