Why won't Scala optimize tail call with try/catch?

Question

In a recent StackOverflow answer, I gave the following recursive code:

def retry[T](n: Int)(fn: => T): T = {
  try {
    fn
  } catch {
    case e if n > 1 =>
      retry(n - 1)(fn)
  }
}

If I add the @tailrec annotation, I get:

Could not optimize @tailrec annotated method retry: it contains a recursive call not in tail position.

I was able to hack a tail-recursive alternative, but I still wonder why this didn't optimize. Why not?

Answer 1

To be tail-recursion optimized, this has to be transformed into something like the following:

def retry[T](n: Int)(fn: => T): T = {
  START:
    try {
      fn
    } catch {
      case e if n > 1 =>
        n = n - 1
        GOTO START
    }
}

When it executes the GOTO to loop, it has to leave to scope of the catch block. But in the original recursive version, the execution of the recursive call is still within the catch block. If the language allows that this could ever potentially change the meaning of the code, then this wouldn't be a valid optimization.

EDIT: From discussion with Rex Kerr in the comments, this is a behaviour-preserving transformation in Scala (but only when there is no finally). So apparently it's just that the Scala compiler doesn't yet recognise that the last call of a catch block where there is no finally is in a tail-call position.

Answer 2

I don't think the list of implemented transformations for putting code in tail-recursive form include traversing exception-handling blocks. These are particularly tricky, even though you can come up with examples (as you have) of where it ought to be legal. (There are many cases that look legal which are not (e.g. if there is a finally block), or require considerably more complex winding/unwinding rules.)

Answer 3

I found this solution elsewhere on SO. Basically, use a return with fn so that if fn returns w/o exception, so will your function. If fn does throw, and the exception meets the condition n > 1, then the exception is ignored and the recursive call happens after the catch block.

@tailrec
def retry[T](n: Int)(fn: => T): T = {
  try {
    return fn
  } catch {
    case e if n > 1 => // fall through to retry below
  }
  retry(n - 1)(fn)
}