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.
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.
[ July 04, 2008: Message edited by: Garrett Rowe ]
Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter
Joined: Jan 17, 2006
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.
Joined: Jan 17, 2006
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: