I recently wanted to calculate some binomial coefficients in Erlang, and so needed an implementation of the factorial function. No problem. The factorial function is the canonical illustration of how to define a recursive function in Erlang. It goes something like this:
fac(0) -> 1; fac(N) -> N * fac(N-1).
I have to confess that definition has always bothered me because it is not tail recursive. And it only takes one more line to write a tail recursive version, just the way God intended:
fac1(N) -> fac1(N,1). fac1(0,R) -> R; fac1(N,R) -> fac1(N-1, N*R).
The advantage of fac1 over fac is that fac1 operates in constant space, while fac requires space linear in N. For large N one has to wonder whether fac's chain of deferred multiplications will overflow the stack. But is this really a problem? Just how large a value of N is required to overflow the stack? I decided to try to find out.
I ran some test cases: fac(1000), fac(10000), fac(50000). No stack overflow yet, but I could see it might get old waiting for the enormous answers to be computed and displayed. I decided to switch gears. To avoid suffering through monster integers, I modified the test. Rather than testing with fac, I settled on using the structurally similar function sum:
sum(0) -> 0; sum(N) -> N + sum(N-1).
Just for grins, I decided to try the same thing in a couple of other languages. Here is sum in Clojure:
(defn sum [n] (if (= n 0) 0 (+ n (sum (- n 1)))))
And here it is in Haskell, where I changed the spelling to summ to avoid a name collision with a Prelude function called sum:
summ 0 = 0 summ n = n + summ (n-1)
I was surprised by the results of my tests.
Just to build up the suspense, I'll pause to describe the test machine. It's a Dell T105, quad-core AMD Opteron, 8GB of ram, running Ubuntu Intrepid. Clojure is revision 1173, running on top of Java 1.6.0_10. Haskell is ghci 6.10.1, and Erlang is R12B-5.
On to the results. First up is Clojure:
user=> (sum 10000) 50005000 user=> (sum 20000) 200010000 user=> (sum 30000) 450015000 user=> (sum 40000) java.lang.StackOverflowError (NO_SOURCE_FILE:0)
The stack overflow is just the sort of thing that makes me prefer fac1 over fac. Let's see what happens in Haskell.
*Main> summ 10000 50005000 *Main> summ 30000 450015000 *Main> summ 40000 800020000 *Main> summ 50000 1250025000 *Main> summ 75000 2812537500 *Main> summ 100000 5000050000 *Main> summ 150000 11250075000 *Main> summ 175000 *** Exception: stack overflow
Haskell, or rather ghci, did roughly four times better. It's probably worth pointing out that this is not really a comparison of the languages so much as a comparison of how the language implementations handle one very specific detail.
Here I need to point out that I am quite aware than both the Clojure and Haskell examples could be (and normally ought to be) modified so as not to blow the stack. My purpose here is to see what it takes to blow the stack. I want to blow the stack.
Time to see how the Erlang virtual machine fares. I stuck the sum function in a module called fac. No matter.
Eshell V5.6.5 (abort with ^G) 1> fac:sum(1000). 500500 2> fac:sum(10000). 50005000 3> fac:sum(50000). 1250025000 4> fac:sum(100000). 5000050000 5> fac:sum(200000). 20000100000 6> fac:sum(500000). 125000250000 7> fac:sum(1000000). 500000500000 8> fac:sum(5000000). 12500002500000 9> fac:sum(10000000). 50000005000000 10> fac:sum(50000000). 1250000025000000 11> fac:sum(100000000). 5000000050000000 12> fac:sum(200000000). 20000000100000000
At that point I went for broke, and tried to compute sum(1000000000). Maybe it would have worked eventually, but I killed it. My machine had gone nearly non-responsive, and I could hear my hard drive thrashing. Those disk sounds incline me to guess that when Erlang ran out of stack space, it moved the computation into virtual memory and soldiered on. Whatever the actual means, N=200,000,000 is pretty impressive. That's three orders of magnitude better than ghci or the jvm. Kudos to the authors of the Erlang virtual machine.
One final thought. In spite of what I saw here, I'll still go with the tail recursive version of the factorial function. It better satisfies my sense of aesthetics. But it's nice to know I don't have to.