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?

Posted in Technology | Tags TCO, Javascript, Scala, Haskell, FunctionalProgramming, Python, TailCallOptimization, Ruby, Java, Erlang, Clojure

Comments

1.

Just some minor nitpicks: it is true that the Ruby *Language* Specification doesn't enforce TCO, but it also doesn't *forbid* it. YARV, for example, has TCO, it's just not enabled by default. The same applies to Python: the Language Specification doesn't have TCO, but AFAIK PyPy *does* have TCO. Haskell has lazy evaluation and call-by-need semantics. Since you aren't doing anything with your forever function, it will never get evaluated. You have to enforce strict evaluation, by e.g. printing it out. (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; }".)

# Posted By Jörg W Mittag on Wednesday, September 2 2009 at 3:31 PM

2.

@Jörg W Mittag - TCO is a language feature, not an implementation optimization. If recursive code might overflow the stack and it might not, then code can't depend on it, and recursion is best used quite sparingly.

# Posted By Peter Burns on Thursday, September 3 2009 at 7:39 PM

3.

The Parrot VM also supports explicit tailcalls, so any language written on it can (theoretically) take advantage of them.

$ cat tc.pir
.sub main :main
.tailcall 'main' ()
.end
$ parrot tc.pir #runs forever

# Posted By Christoph Otto on Thursday, September 3 2009 at 10:02 PM

4.

TCO isn't just about self-calling. I think the following is expected to run forever in scheme (forgive my poor scheme) but has no equivalent in Clojure, hence Clojure doesn't really have TCO (which it freely admits).

(define (foo) (bar))
(define (bar) (foo))
(foo)

# Posted By Dave on Thursday, September 3 2009 at 10:56 PM

5.

Tail call in Scala is a bit similar to the Clojure one, as described by Dave. The JVM has none, so it has to be emulated. As described in Oderskys book "Programming In Scala", Chap 8.9 Tail recursion, at the end it describes the limits: Scala too only tail calls if the calling function calls itself.
(And I'm rather angry about that. The request for tail call recursion in JVMs is in the request list for many years now.)

I'm very impressed by your Haskell findings. I knew these guys are cool, but THAT cool?

# Posted By Falko on Friday, September 4 2009 at 4:20 AM

6.

You forgot about F#. It has TCO as well.

# Posted By Vitaliy on Friday, September 4 2009 at 8:10 AM

7.

See http://www.lua.org/pil/6.3.html

# Posted By Jasper Van der Jeugt on Friday, September 4 2009 at 9:07 AM

8.

@Dave

Clojure supports mutual recursion via another function called trampoline. This will overflow:

(declare bar)

(defn foo [n]
(if (pos? n)
(bar (dec n))
:done-foo))

(defn bar [n]
(if (pos? n)
(foo (dec n))
:done-bar))

(foo 1000000)
-> java.lang.StackOverflowError

To convert to a trampoline, simply return closures over your tail
calls, rather than direct calls. This is as simple as prepending #

(declare bar)

(defn foo [n]
(if (pos? n)
#(bar (dec n))
:done-foo))

(defn bar [n]
(if (pos? n)
#(foo (dec n))
:done-bar))

Then make the top-level call via trampoline:
(trampoline foo 1000000)
-> :done-foo

# Posted By Paul Barry on Tuesday, September 8 2009 at 10:24 AM

9.

@Jörg W Mittag

But shouldn't calling the forever function from ghci force evaluation, since ghci needs to print the result?

# Posted By Paul Barry on Tuesday, September 8 2009 at 10:26 AM

Comments Disabled