Why does returning getOrElse make tail recursion impossible?

Question

I am confused by the following code: the code is artificial, but still I think it is recursive. The compiler does not agree and generates an error message:

@annotation.tailrec def listSize(l : Seq[Any], s: Int = 0): Int = { if (l.isEmpty) { None.getOrElse( return s ) } listSize(l.tail, s + 1) } 

How is code that does tail recovery impossible? Why does the compiler tell me:

failed to optimize @tailrec annotated listSize method: it contains a recursive call not in tail position

Similar code (with return inside map ) compiles fine:

 @annotation.tailrec def listSize(l : Seq[Any], s: Int = 0): Int = { if (l.isEmpty) { Some(()).map( return s ) } listSize(l.tail, s + 1) } 

Even the code obtained by embedding None.isEmpty compiles fine:

 @annotation.tailrec def listSize(l : Seq[Any], s: Int = 0): Int = { if (l.isEmpty) { if (None.isEmpty) { return s } else None.get } listSize(l.tail, s + 1) } 

On the other hand, a code with a slightly modified map rejected by the compiler and causes an error:

 @annotation.tailrec def listSize(l : Seq[Any], s: Int = 0): Int = { if (l.isEmpty) { Some(()).map( x => return s ) } listSize(l.tail, s + 1) } 

Answer 1

This is because return in your first fragment is non-local (it is nested inside lambda). Scala uses exceptions to compile non-local return , so the code is converted by the compiler from this:

 @annotation.tailrec def listSize(l : Seq[Any], s: Int = 0): Int = { if (l.isEmpty) { None.getOrElse( return s ) } listSize(l.tail, s + 1) } 

Something similar to this (compile with scalac -Xprint:tailcalls ):

 def listSize2(l : Seq[Any], s: Int = 0): Int = { val key = new Object try { if (l.isEmpty) { None.getOrElse { throw new scala.runtime.NonLocalReturnControl(key, 0) } } listSize2(l.tail, s + 1) } catch { case e: scala.runtime.NonLocalReturnControl[Int @unchecked] => if (e.key == key) e.value else throw e } } 

The latter indicates that recursive calls are not tail calls when they are wrapped in try / catch blocks. Basically, this example:

 def self(a: Int): Int = { try { self(a) } catch { case e: Exception => 0 } } 

This is related, which is obviously not tail recursive:

 def self(a: Int): Int = { if (self(a)) { // ... } else { // ... } } 

There are certain special cases where you can optimize this (up to two stack frames, if not one), but there does not seem to be a universal rule to apply to this situation.

In addition, the return expression in this fragment is not a non-local return , so the function can be optimized:

 @annotation.tailrec def listSize(l : Seq[Any], s: Int = 0): Int = { if (l.isEmpty) { // `return` happens _before_ map `is` called. Some(()).map( return s ) } listSize(l.tail, s + 1) } 

This works because in Scala, return e is an expression, not an operator. Its type is Nothing , although it is a subtype of everything, including Unit => X , which is the type required by the map parameter. The evaluation is quite simple: e returned from the closing function before map even executed (the arguments are evaluated before the method is called, obviously). This can be confusing because you expect map(return e) be parsed / interpreted as map(_ => return e) , but it is not.

Answer 2

This is almost certainly a compiler error or a partially implemented function.

This is most likely due to the implementation of return in an expression in Scala. Nonlocal return are implemented using exceptions, so when return is NonLocalReturnException , a NonLocalReturnException and the whole expression is enclosed in a try-catch . I put that x => return x converted to a nested expression that, when completed in try-catch confuses the compiler to determine if it can use @tailrec . I would go so far as to say that you should avoid using @tailrec in combination with non-local return .

Learn more about implementing Scala's return in this on the blog or this question.

Answer 3

return always aborts recursion calls. You should change the code to something like this:

 @tailrec def listSize(l : Seq[Any], s: Int = 0): Int = { l match { case Nil => s case head :: tail => listSize(tail, s + 1) } } 

Answer 4

I can’t try it now, but will this fix the problem?

 @annotation.tailrec def listSize(l : Seq[Any], s: Int = 0): Int = { if (l.isEmpty) { None.getOrElse( return s ) } else { listSize(l.tail, s + 1) } } 

Using if-else instead of a simple if ensures that the if always returns something.