What is really a tail call

Question
1

I was surprised to find that there was no compiler error nor intelliJ error for the following function definition. In the tail position I am calling the function recur but its first argument is reduced which is a different type than m. Thus the value of Z is different. Isn’t that really a different function?

      @scala.annotation.tailrec
      def recur[Z](m:M[Z],maybe:Option[B],f:Z=>B): B = {
        if (pairable.singleton(m))
          maybe match {
            case None => f(pairable.head(m))
            case Some(b) => combOp(f(pairable.head(m)), b)
          }
        else {
          val (pairs: M[(B, B)], leftover) = pairable.paired(m,f)
          val reduced: M[B] = pairable.map(pairs, { case (a, b) => combOp(a, b) })
          val last: Option[B] = (maybe, leftover) match {
            case (Some(b), Some(leftover)) => Some(combOp(leftover, b))
            case (None, Some(_)) => leftover
            case (Some(_), None) => maybe
            case (None, None) => None
          }
          recur(reduced,last,id) // is this really a tail call, reduced is NO of type M[Z]
        }
      }
2

I would guess that, due to erasure, it’s still effectively the same type for recursion purposes. (No idea whether that’s appropriate or not, but it doesn’t entirely astonish me…)

3

It’s the same def, and that is what counts.

4

On a JVM level generics don’t exist. They exist only as a metadata in .class files, but I think that metadata is not even required to be correct. Scala’s generics don’t map 1:1 to Java generics metadata, but JVM still accepts .class files generated by Scala compiler.

Specilization partially reverses type erasure and then it does matter which type you recur on:

import scala.annotation.tailrec

object Xxx {
  @tailrec
  def recursive[@specialized A](a: A): Unit = {
    recursive(5)
  }
}

gives compilation error:

could not optimize @tailrec annotated method recursive: it is called recursively with different specialized type arguments

5

Note that @tailrec does not assume any abstract/formal definition of tail recursion. The doc bluntly states:

A method annotation which verifies that the method will be compiled with tail call optimization.

It codifies an assumption about the behavior of the current compiler implementation.

Regarding an abstract notion of tail recursion, looking at more or less formal definitions, both @jimka’s and @tarsa’s examples look clearly tail-recursive to me. The type binding shouldn’t make a difference, and if the compiler happens to produce different code variants for a function and thus cannot optimize, that’s an implementation detail, not a property of the function.

1 Like
6

The [inferred] type argument passed for Z in the recursive call is different in the same way the value arguments passed for m, maybe, and f are different. From a language point of view types are passed around in the same way as values, but they appear in different syntactic positions so you can never mix them up. It also turns out they’re unnecessary at runtime so we discard them, but this is an implementation detail.

7

Maybe my understanding is wrong but I thought tailcall in Scala, lacking support from the jvm, was simply compiled as variable reassignment and jump to the top of the function. In my case, the call to recur in tail position cannot be compiled as such because the variables would be of different type.

8

There’s different type bindings to the “common”, unconstrained type Z, which likely manifests as Object in the generated bytecode.