Why return in getOrElse makes tail recursion not possible?

Question

I am confused by following code: the code is artificial, but still I think it is tail recursive. The compiler does not agree and produces 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 the code above making tail recusion not possible? Why is the compiler telling me:

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

A similar code (with return inside of 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 inlining 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, code with slightly modified map is rejected by the compiler and produces the 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

It happens because the return in your first snippet is a non-local one (it's nested inside a lambda). Scala uses exceptions to compile non-local return expressions, so the code gets transformed 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)
}

To 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 last point is that recursive calls are not tail calls when wrapped in try/catch blocks. Basically, this contrieved example:

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

Is akin to this, which is obviously not tail-recursive:

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

There are certain particular cases where you can optimize this (down to two stack frames, if not one), but there doesn't seem to exist an universal rule to apply to this kind of situation.

Also, the return expression in this snippet, is not a non-local return, which is why 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)
}

The above works because, in Scala, return e is an expression, not a statement. Its type is Nothing, though, which is a subtype of everything, including Unit => X, which is the type required by map's param. The evaluation though is pretty simple, e is returned from the enclosing function before map is even executed (arguments are evaluated before the method call, obviously). It may be confusing because you'd expect map(return e) to be parsed/interpreted as map(_ => return e), but it's not.

Answer 2

This is almost surely a bug with the compiler, or a partially implemented feature.

It most likely has to do with the implementation of return in an expression in Scala. Non-local return statements are implemented using exceptions, so that when the return is called, a NonLocalReturnException is thrown, and the whole expression is wrapped in a try-catch. I bet x => return x is converted to a nested expression, which, when wrapped in a try-catch, is confusing the compiler when determining if it can use @tailrec. I would go so far as to say that using @tailrec in conjunction with non-local return should be avoided.

Read more about the implementation of return in Scala in this blog post or in this question.