Does Scala have an intelligent compiler?

Question

I made a recursive function like

require : L (List[Int]) 

Match pattern L

• Nil => Thread.dumpStack()
• x :: xs => print(x) + function(xs)

 def function(L : List[Int]) { L match { case Nil => Thread.dumpStack() case x :: xs => print(x + " "); function(xs) } } 

val l = (from 1 to 5) .toList // function (l)

So, I think that this function is in the stack frame n times, but it happens once, I think that this function has already found Nil and printed a Thread.dumpStack exception.

Is the scala compiler smart or otherwise?

Answer 1

You observe tail recursion: there is nothing to store from one iteration to the next, so recursion essentially turns into a while loop by the compiler. (So ​​yes, the compiler is smart this way.)

Answer 2

As Rex Kerr noted, this is a Scala compiler that uses tail call optimization. If you want to know what compiles at the end, you can run the compiler with an additional argument:

 scalac -Xprint:tailcalls yourfile.scala 

This will print an intermediate view after the tailcalls compiler tailcalls . (If you want to learn about all the steps, you can also run scalac -Xshow-phases .) For example, at the following input:

 object TailRec { def foo(l : List[Int]) : Unit = l match { case Nil => Thread.dumpStack() case x :: xs => println(x); foo(xs) } } 

The compiler will print (for the foo function):

 def foo(l: List[Int]): Unit = { <synthetic> val _$this: TailRec.type = TailRec.this; _foo(_$this,l){ l match { case immutable.this.Nil => java.this.lang.Thread.dumpStack() case (hd: Int, tl: List[Int])collection.immutable.::[Int]((x @ _), (xs @ _)) => { scala.this.Predef.println(x); _foo(TailRec.this, xs) } } } } 

The _foo(_$this,l) looks like a function definition, but it’s really a label, and the _foo(TailRec.this, xs) “call” _foo(TailRec.this, xs) is actually a jump to that label. In short, the compiler rewrote the recursive call into what the while loop really is.

The compiler will automatically apply optimization when possible. If you want to make sure that the function is overwritten correctly, you can annotate it with @tailrec , and the compiler throws an error if it cannot optimize it.