Infinite Recursion
September 2, 2009
A few days ago I posted an article on Tail Call Optimization. One really quick way to determine if any language/VM/interpreter performs Tail Call Optimization (TCO) is to write a function that calls itself, in other words, creating an infinitely recursive function. If the function just runs forever and doesn't return, the interpreter is doing TCO, otherwise you will get some sort of stack overflow error. So I decided to test a variety of languages to see what happens when you write an infinitely recursive function. First up is ruby:
def forever
forever
end
forever
It was no surprise to me that running this results in this error:
run.rb:2:in `forever': stack level too deep (SystemStackError)
from run.rb:2:in `forever'
from run.rb:5
Ruby doesn't have TCO, I knew that. Next up, Python:
def forever(): forever()
forever()
This has a similar result, but the stack track is a little more revealing:
Traceback (most recent call last):
File "run.py", line 3, in <module>
forever()
File "run.py", line 1, in forever
def forever(): forever()
File "run.py", line 1, in forever
def forever(): forever()
...
File "run.py", line 1, in forever
def forever(): forever()
File "run.py", line 1, in forever
def forever(): forever()
RuntimeError: maximum recursion depth exceeded
This shows pretty clearly what is going on, the stack frames are pilling up and eventually it gets to the point where the Python interpreter says enough is enough. Interestingly enough, this mailing list thread shows that it's completely feasible to add TCO to Python and Guido just doesn't want to add it.
JavaScript is no surprise either, but we can write our infinitely recursive function with an interesting little twist:
(function(){ arguments.callee() })()
Yes that's right, it's an anonymous recursive function! Running this with SpiderMonkey results in InternalError: too much recursion. So how about Java:
class Run {
public static void main(String[] args) {
Run run = new Run();
run.forever();
}
public void forever() {
forever();
}
}
The stack trace for this one looks a bit like the Python one, we see a stack frame for each iteration:
Exception in thread "main" java.lang.StackOverflowError
at Run.forever(Run.java:8)
at Run.forever(Run.java:8)
at Run.forever(Run.java:8)
at Run.forever(Run.java:8)
...
So that means no TCO on the JVM. So Scala doesn't have TCO, right?
def forever : Unit = forever
forever
Wrong. This one runs forever. Scala does TCO with some bytecode tricks which Nick Wiedenbrueck explains really well in this blog post.
Clojure is a functional Lisp saddled with the problem of no-TCO on the JVM, but it gets around it in a slightly different way than Scala. If you write a tail recursive function like this:
(defn forever [] (forever))
You will get a java.lang.StackOverflowError just as you do in Java. Instead, Clojure provides a language level feature to do recursion:
(defn forever [] (recur))
Calling recur in the function makes it call the function again. recur also checks that it is in the tail recursive position, which ends up being an interesting feature because you have to explicitly say "I expect this to do TCO". In other languages that do it transparently, you might think TCO is happening, but it might not be and you won't find out until you get a stack overflow error. Also, this construct allows us to have recursive anonymous functions:
((fn [] (recur)))
Erlang, being a function language, has TCO as well:
-module(run).
-compile(export_all).
forever() ->
forever().
Now one thing all of these functional languages that have TCO; Scala, Clojure and Erlang, all have in common is that while the infinitely recursive function runs, it essentially does nothing, but it will peg your CPU utilization to nearly 100%. This next language, Haskell, being the mother of all functional langauges, of course has TCO. Here's the function:
forever = forever
Yes, that's a function. And if you call it with forever, it just sits there and runs forever. But here's the crazy thing, it uses no CPU. My guess is that it has to do with lazy evaluation, but I'm not sure. Any ideas?
