Tail Calls vs memoization

[Pho Tek]

With regards to the fibonacci function as discussed here, can I characterized memoization as an optimization to overcome the JVM's lack of support for Tail call optimization ? I'm a bit hazy on both concepts. Perhaps someone can elaborate.

Thanks

Pho

[Garrett Rowe]

Someone may correct me on this, but I believe memoization, and tail call optimization are orthogonal concepts.

Memoization is an optimization that allows the runtime to compute the result of a function only once. In a referentially transparent function (or method), subsequent calls to the same function with the same arguments will always yield the same result. Therefore once the result is computed, all other invocations of the function with equal arguments can be replaced with the previously computed result.

Tail call optimization on the other hand, is a "trick" that minimizes the size of the call stack. If the return value of a method is a call to another method, the current stack frame can be reused.

The Scala compiler can optimize tail recursion where the last call of a nonoverrideable method recalls the same method with different arguments. I believe instead of swapping stack frames as in normal tail call optimization, the compiler unrolls this type of tail recursion into a loop.

Tail recursive calls to overridable (non final, top level methods) methods are not tail call optimized. Tail calls to other methods are also not tail call optimized. Both of these situations theoretically could be optimized to run in constant stack space, but the JVM is not able to do that.

Here is an example of a fib function that can be optimized by the Scala compiler.

def fib(num : Int) : Int = {
   def fibtc(a : Int)(b : Int)(count : Int) : Int = {
      if (count <= 0) {
         b
      } else {
         fibtc(a + b)(a)(count - 1)
      }
   }
   fibtc(1)(0)(num)
}

[ July 04, 2008: Message edited by: Garrett Rowe ]

[Garrett Rowe]

There is a memoization library for Scala in the Scalaz library written by Tony Morris. One of the examples with the distribution is a fib function using memoization.

[Garrett Rowe]

After some experimentation, I see that tail-recursive methods declared in objects are also tail call optimized. Presumably because objects cannot be subclassed so methods declared in them are implicitly final. For example, this overflows the call stack:

class StackOverflow {
 
   def overflowStack(i: Int): Unit = {
      if (i % 10e6 == 0) println("overflowStack(" + i + ")")
      overflowStack(i + 1)
   }
 
}
 
object StackOverflowMain {
 
   def main(args: Array[String]) = {
      val so = new StackOverflow
      so.overflowStack(1)
   }
}

But this results in an infinite loop:

object StackOverflow {
 
   def overflowStack(i: Int): Unit = {
      if (i % 10e6 == 0) println("overflowStack(" + i + ")")
      overflowStack(i + 1)
   }
      
   def main(args: Array[String]) = {
      overflowStack(1)
   }
 
}

This also results in an infinite loop:

class StackOverflow2 {
 
   final def overflowStack(i: Int): Unit = {
      if (i % 10e6 == 0) println("overflowStack(" + i + ")")
      overflowStack(i + 1)
   }
 
}
 
object StackOverflowMain {
 
   def main(args: Array[String]) = {
      val so2 = new StackOverflow2
      so2.overflowStack(1)
   }
}

[Marc Peabody]

infinite loop = tail call optimization in the above code examples. Without tail call optimization, the stack would eventually get too large and throw an exception.

For further proof, using the following tweak to purposefully throw a RuntimeException so we can see the stacktrace result:

    if (i % 10e6 == 0){
      println("overflowStack(" + i + ")")
      throw new RuntimeException
    }    

and the result:

Exception in thread "main" java.lang.RuntimeException
overflowStack(10000000)
at cool.StackOverflow.overflowStack(StackOverflow2.scala:7)
at cool.StackOverflow2$.main(StackOverflow2.scala:16)
at cool.StackOverflow2.main(StackOverflow2.scala)    

Here, only a single call to overflowStack() is shown in the stacktrace even though it was on recursion call #10000000.

I could have sworn I had seen something like this in POJ (Plain Old Java) in the past as well but my quick little tests couldn't confirm it.
[ July 07, 2008: Message edited by: Marc Peabody ]

[Garrett Rowe]

Marc Peabody: I could have sworn I had seen something like this in POJ (Plain Old Java) in the past as well but my quick little tests couldn't confirm it.

I don't think the Sun compiler does this kind of optimization, but I believe there is an IBM java compiler that can.

[Marc Peabody]

Originally posted by Garrett Rowe:
I don't think the Sun compiler does this kind of optimization, but I believe there is an IBM java compiler that can.

That would explain it. I've used RAD a lot in the past.

[Gabriel Claramunt]

I would love to see tail call optimization added to the jvm!