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?

If (n > 1) - really? Not n > 0 or n >= 1? And what happens if n == 1 (== 0)? — user unknown, Nov 22 '11 at 22:39
@user unknown - Obviously you pass in the number of tries total, not the number of retries. — Rex Kerr, Nov 23 '11 at 04:55

Ben · Accepted Answer · 2011-11-23T22:00:57.497

10

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.

edited Nov 23 '11 at 22:00

answered Nov 22 '11 at 23:32

Ben

68,572
20
126
174

Too much speculation, too much of which is wrong. The bytecode is not the problem. Bytecode doesn't even understand catch blocks, only a target for exceptions within a try block. Specs for exception handling don't impact _this_ transformation; just try rewriting it as a while loop! – Rex Kerr Nov 23 '11 at 05:05
@Rex I'm happy to be corrected by someone who knows more about Java bytecode, but I did phrase it as a guess. I'm not sure I understand your last remark though. The tail-recursion transformation is about automatically rewriting code into something like a while loop, and the tail recursion taking place in a catch block clearly does inhibit the compiler from doing this. Either that's just a feature that hasn't been implemented, or the specs for exception handling **do** impact this transformation. Or did I misunderstand you? – Ben Nov 23 '11 at 05:48
1

It's a feature which has not been implemented. There is no case where behavior would differ if you moved the jump outside of the catch block (as long as the logic was correct) in _this_ case. The equivalent iterative code is `var i = n; while(true) { try { return(fn) } catch { case e if i>1 => i -= 1; } }`. – Rex Kerr Nov 23 '11 at 15:02

score 7 · Answer 2 · answered Nov 22 '11 at 20:34

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

score 3 · Answer 3 · answered Dec 15 '16 at 17:18

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

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

3 Answers3

Linked