Infinite Recursion

http://paulbarry.com/articles/2009/09/02/infinite-recursion

by luccastera • 17 years ago

59 6 17 years ago

amichail• 17 years ago

From: http://stronglytypedblog.blogspot.com/2009/08/scala-tail-rec...

If the recursion is indirect, for example, Scala cannot optimize tail calls, because of the limited JVM instruction set.

Why is that?

jdale27• 17 years ago

Apparently the JVM goto instruction can only jump to an address within the same method:

http://java.sun.com/docs/books/jvms/second_edition/html/Inst...

bigmac• 17 years ago

I think the CLR team was able to learn from some of the JVM's shortcomings; this limitation is one example. .NET IL has the TAIL. instruction prefix that allows tail calls. It can be prepended to any call instruction outside of an exception handling block.

There's also the JMP instruction, which is similar and allows the current method's arguments to be passed to another function, discarding the current stack frame and returning to the current method's caller.

yangyang• 17 years ago

He forgot C! It's not in the language spec, but gcc will optimize tail calls, with -O2 or above.

Periodic• 17 years ago

This had me laughing out loud:

"The same mistake is done on the Computer Language Benchmark Game. There's an Array sorting benchmark where Haskell just blows away even hand-optimized C. The secret is that the benchmark never prints out the contents of the sorted array. The C compiler isn't smart enough to recognize that the array is never actually used anywhere, but Haskell is, and so the entire benchmark basically compiles down to the equivalent of "int main() { return 0; }"."

Infinite Recursion

Related Stories