Tail Call

This is an enriched topic in CS241E, but I really didn’t have enough time to study this.

def m() = {
	var i = 0
	var j = 0
	def loop(): Unit = {
		if (i < 10*1000*1000) {
			i = i + 1
			j = j + 1
		}
	}
	loop()
	i+j
}

Since each call to the loop procedure pushes a frame onto the stack, we might expect the stack to grow very large and possibly overflow the memory that is available for it. However, this Scala code runs without running out of stack space no matter how high we increase the iteration count. How is this possible?

See lecture notes 6.

I think there is this similar idea that i saw in Python, ohh where you pass the flag. I think I saw it in computerphile video!! It’s through the JIT Compiler

A procedure call is a tail call if it is the last thing executed in the procedure before the epilogue. Note that this does not necessarily correspond to the physical position of the call within the source code.

Consider the following cases

def factorial(n:Int):Int = { if(n <= 1) { 1 } else { n * factorial(n-1) } }
def sum(n:Int,a:Int):Int = { if(n != 0) { sum(n-1,n+a) } else { a } }

• The call to factorial is NOT a tail call, since after evaluating the call, a multiplication operation must be performed before the epilogue.
  • For a tail call to be valid, the call has to be the very last thing executed before the epilogue of the caller. In the factorial procedure, the last thing that happens before the epilogue will be a multiplication operation.
• The call to sum is a tail call. Even though it is not at the physical end of the code, it is the last thing that happens before the epilogue in that particular branch of the if statement

Tail Call Optimization: If f calls g, and the call is a tail call, the frame and parameter chunk of f can be popped off the stack before calling g.

Without tail call optimization: push $f$, push $g$, pop $g$, pop $f$. With tail call optimization: push $f$, pop $f$, push $g$, pop $g$.