Which types of tail recursion does the scala compiler recognize

Question
1

Can the scala compiler detect tail recursion in non-trivial cases?

InteliJ has the nice feature that it shows which function it thinks are tail recursive. But I’ve seem to recall being warned that the analysis that IntelliJ does (or perhaps the scala plug-in) is not 100% accurate, especially in corner cases.

The Common Lisp compiler which I’m most familiar with treats tail calls between local functions as tail-recursion. E.g., if two local functions f1 and f2 call each other and/or the host function in tail position, then they are compiled as tail-calls.

Here is an example of such a function. InteliJ claims it is NOT tail recursive, but in my mind it is. Of course in this simple example, the local functions fEven and fOdd could be eliminated by the programmer.

def fTop(n:Int):Int = {
  def fEven(n:Int):Int = {
    fTop(n/2)
  }
  def fOdd(n:Int):Int = {
    fTop(3*n + 1)
  }
  if (n == 1)
    1
  else if (n%2 == 0)
    fEven(n)
  else
    fOdd(n)
}
2

From experimentation it would seem that, at least by default, scalac does not compile local function calls as tail calls. The first version of the function below java.lang.StackOverflowError.

def parseListContent(chars: List[Char], clause:Clause, clauses:CNF): CNF = {
  def skipSpace(): CNF = {
    parseListContent(chars.dropWhile(whiteSpace.contains(_)), clause, clauses)
  }
  def skipToEOL(): CNF = {
    parseListContent(chars.dropWhile(!endOfLine.contains(_)), clause, clauses)
  }

  def readNumber(): CNF = {
    val (num, tail) = chars.span { c => digits.contains(c) }
    val number = num.mkString.toInt
    if (number == 0)
      parseListContent(tail, Nil, clause.reverse :: clauses)
    else
      parseListContent(tail, number :: clause, clauses)
  }

  chars match {
    case 'p' :: _ |
         'c' :: _ => skipToEOL()
    case c :: _ if digits.contains(c) => readNumber()
    case c :: _ if whiteSpace.contains(c) => skipSpace()
    case Nil if clause.nonEmpty => (clause.reverse :: clauses).reverse
    case Nil => clauses.reverse
  }
}

However, if I inline the local functions skipSpace, skipToEOL, and readNumber, then no such stack overflow occurs.

def parseListContent(chars: List[Char], clause:Clause, clauses:CNF): CNF = {
  chars match {
    case 'p' :: _ |
         'c' :: _ => parseListContent(chars.dropWhile(!endOfLine.contains(_)), clause, clauses)
    case c :: _ if digits.contains(c) => {
      val (num, tail) = chars.span { c => digits.contains(c) }
      val number = num.mkString.toInt
        if (number == 0)
          parseListContent(tail, Nil, clause.reverse :: clauses)
        else
          parseListContent(tail, number :: clause, clauses)
    }
    case c :: _ if whiteSpace.contains(c) => parseListContent(chars.dropWhile(whiteSpace.contains(_)), clause, clauses)
    case Nil if clause.nonEmpty => (clause.reverse :: clauses).reverse
    case Nil => clauses.reverse
  }
}
3

I’ve added a thread on Scala Contributors to discuss questions of implementation. Potentially that discussion makes this one moot?

4

You can add the @tailrec annotation on a method that you think is tail-recursive: the compilation will fail if the compiler doesn’t treat it as tail recursive.

1 Like
5

That’s probably a good habit to get into.

6

Yeah, I strongly recommend using @tailrec any time you expect tail recursion.

But in general – yeah, Scala’s tail-recursion support is pretty simplistic, largely because the underlying JVM doesn’t provide much support. A function can call itself, but that’s about it. There are one or two compiler plugins (such as twotails) to open things up a little, but in general you can’t count on really sophisticated tail-recursion.

(This is a known limitation, and a sometimes frustrating one, but so far nobody’s cracked it.)

7

Does the concept of local function inlining exist in the the compiler. As I understand, one limitation of the JVM is that once functions become too large, the runtime optimizer turns itself off.

8

Hmm. Interesting point. IIRC there is some of that in Scala 2, but inlining becomes a much more significant and predictable feature in Scala 3. (Which adds an inline keyword that forces inlining.) I’m not sure how that interacts with tail recursion, but I could believe that it would sometimes help…

1 Like