Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does @tailrec work

Tags:

scala

I have used and read about @tailrec annotation to have a tail recursive method. I have gone through many links that explains it. For example it only works when for self-calling functions and shouldnot be overriden etc.

Everywhere it is mentioned that the compiler optimizes. But what magic/concept does the compiler do to make it tail recursive. For a simple function below, what does the compiler do:

@tailrec def fact(acc: Int, n: Int): Int = {
  if (n <= 1) acc
  else fact(n * acc, n - 1)
}
fact(1,10)

I mean does it convert it into a loop where it repeatedly calls it and then returns the final value? Is there any link to paper which explains it

like image 506
Jatin Avatar asked Jun 26 '13 11:06

Jatin


1 Answers

In addition to my comment on your question (repasting the code here):

  var acc = 1 
  var n = 10
start: 
  if (n <= 1) return acc 
  else { 
    acc = n * acc
    n = n - 1
    goto start
  }

I tried compiling the fact method with a recent build I just happened to have and with scalac -Xprint:all and somehow the compiler emitted an icode file. So this really illustrates how it optimizes the tail call:

  // methods
  def fact(acc: Int (INT), n: Int (INT)): Int {
  locals: value acc, value n, value _$this
  startBlock: 1
  blocks: [1,2,3,4,5]

  1: 
    2   JUMP 2

  2: // huynhjl's comment: IF condition is here
    3   LOAD_LOCAL(value n)
    3   CONSTANT(1)
    3   CJUMP (INT)LE ? 3 : 4

  3: // huynhjl's comment: first branch of IF, will return acc
    3   LOAD_LOCAL(value acc)
    3   JUMP 5

  5: 
    2   RETURN(INT)

  4: // huynhjl's comment: else branch of IF, update acc and n and jump back
    4   LOAD_LOCAL(value n)
    4   LOAD_LOCAL(value acc)
    4   CALL_PRIMITIVE(Arithmetic(MUL,INT))
    4   LOAD_LOCAL(value n)
    4   CONSTANT(1)
    4   CALL_PRIMITIVE(Arithmetic(SUB,INT))
    4   STORE_LOCAL(value n)
    4   STORE_LOCAL(value acc)
    4   JUMP 2

  }
like image 107
huynhjl Avatar answered Oct 06 '22 00:10

huynhjl