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

I have the feeling the compiler can't decide wether or not your method is tail recursive because of the return statement, probably he's being defensive and telling you that the recursion is not guaranteed. — Ende Neu, Mar 02 '15 at 10:28

Ionuț G. Stan · Accepted Answer · 2015-03-05T17:06:44.037

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.

Could you perhaps explain in more detail how is `map( return s )` processed? I had some strange feeling about it before, but still I do not get exactly what it does - why is compiler accepting it, and how does it match expected map signature, which should be Unit => X? — Suma, Mar 04 '15 at 08:47

score 2 · Answer 2 · edited May 23 '17 at 12:12

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.

score 0 · Answer 3 · answered Mar 02 '15 at 10:52

0

return always breaks recursion calls. You should change you code into 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)
  }  
}

answered Mar 02 '15 at 10:52

Mariusz Nosiński

1,308
9
10

In your own example you can replace `case Nil => s` with `case Nil => return s` and the function will still be compiled as tail recursive? – Suma Mar 02 '15 at 11:00
Yes, because for tail recursion last call should be `return` or `next call the same function`. In your code , `return` isn't in the last step. Your `return` is alternative for val assigment and then (in the next step) is eventually recursive call. – Mariusz Nosiński Mar 02 '15 at 11:15
I am afraid I still do not see the reason. :( How is `return` in `getOrElse` different from return in e.g. `Some(()).map( return s )`, or in the `getOrElse` which is inlined? Also, are there some links listing the requirements you mentioned: " last call should be return or next call the same function"? – Suma Mar 02 '15 at 12:14
I have added some more examples. What is the difference between the two `map` variants? Why `map( return s )` compiles and `map( x => return s )` does not? – Suma Mar 02 '15 at 12:19

score -1 · Answer 4 · answered Mar 02 '15 at 12:21

-1

I can't try it out right 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 just if will insure the if statement always return something.

answered Mar 02 '15 at 12:21

Tobber

7,211
8
33
56

I have tried it and this is rejected by the compiler as well. – Suma Mar 02 '15 at 12:24

Why return in getOrElse makes tail recursion not possible?

4 Answers4