Paul Barry

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


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()


This has a similar result, but the stack track is a little more revealing:

Traceback (most recent call last):
  File "", line 3, in <module>
  File "", line 1, in forever
    def forever(): forever()
  File "", line 1, in forever
    def forever(): forever()
  File "", line 1, in forever
    def forever(): forever()
  File "", 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();
  public void 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(
	at Run.forever(
	at Run.forever(
	at Run.forever(

So that means no TCO on the JVM. So Scala doesn’t have TCO, right?

def forever : Unit = 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:



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?

Tail Call Optimization

August 30, 2009

Tail-Call Optimization (a.k.a Tail Recursion) is a technique often used in functional programming languages that promotes the use of recursion rather than imperative loops to perform iterative calculations. When I say imperative loops, I mean using a local variable that you change the value of as you calculate each step of the iteration. A generic term for this kind of variable is an accumulator, because it accumulates the new value at each step of the iteration.

Let’s say you are hoping to become the next mega millionare and you want to know your odds of winning. Most lotteries consist of something like pick 5 numbers between 1 and 50. Each number can only come up once in the drawing and if you get all 5 numbers right, you win. The order isn’t significant, you just need to get the 5 numbers.

Here’s a JavaScript function written in an imperative style to get your odds:

function odds(n, p) {
  var acc = 1
  for(var i = 0; i < n; i++) {
    acc *= (n - i) / (p - i)
  return acc

The parameters are n, the number of numbers you have to pick and p is the upper limit of all possible numbers to choose from. So the odds for the “pick 5 of 50” are 4.71974173573222e-7. That’s expressed in decimal in scientific notation. To get the more traditional looking “1 in whatever” number, you simply take the inverse, 1/4.71974173573222e-7, which is 1 in 2,118,760.

The mega millions actually has a twist to it with the powerball. You pick 5 numbers of of 56 and then 1 number out of 46. A number that comes up in the first 5 can come up as the powerball. So that means the mega millions odds are 1/(odds(5,56) * odds(1,46)), which is 1 in 175,711,536.

One problem with our function is that it uses a mutable local variable and mutable local variables are evil. Some functional languages, such as Clojure, Haskell and Erlang, don’t even allow you to use mutable local variables. So how can we do it without the accumulator? The answer is recursion:

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)

This is a pretty elegant implementation of the function because it mirrors how you might think of the problem. This still works great but it breaks down if we try to calculate the odds of much larger numbers. For example, if you try to calculate the odds of picking 10,000 numbers out of 100,000 numbers with odds(10000, 100000), you will some kind of stack overflow / too much recursion error, depending on your interpreter.

The reason for this becomes clear when you walk through how the interpreter calculates the value. When you say odds(5, 56), the return value is (5/56) * odds(4, 55). The interpreter cannot evaluate this expression until odds(4, 55) is calculated. So the series of expressions that get evaluated are:

odds(5, 56)
(5/56) * odds(4, 55)
(5/56) * (4/55) * odds(3, 54)
(5/56) * (4/55) * (3/54) * odds(2, 53)
(5/56) * (4/55) * (3/54) * (2/53) * odds(1, 52)
(5/56) * (4/55) * (3/54) * (2/53) * (1/52) * odds(0, 51)
(5/56) * (4/55) * (3/54) * (2/53) * (1/52) * 1

As you can see, the lines get wider as the recursive calls build up. This is representative of how the interpreter works. As each recursive call is added, memory is temporarily used up. Once there are no more recursive calls, it can start evaluating the expressions and freeing up the memory. This works fine, but if you are performing the calculation on a large number that generates more recursive calls than the interpreter can hold in memory, then boom goes the dynamite. Most interpreters push each recursive call onto a stack, so when the stack runs out of memory, you get a Stack Overflow error.

So how can we possibly do calculations like this recursively? The answer to that is tail-call optimization. In order to do this, we are going to have to bring back the accumulator, but in this case, it’s not going to be a mutable local variable, instead it will be a parameter to the function. Since we don’t want callers of our function to have to pass in the initial value of the accumulator, we will define two functions, one “public” and the other “private”:

  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
  odds = function(n, p) {
    return odds1(n, p, 1)

JavaScript doesn’t really have a public/private mechanism, but we can use closures to accomplish the same thing. First this is an anonymous function that we create and then call immediately after we create it. This just gives us a local scope. If we didn’t have this outer wrapping function, all variables would be global. Then we define a function and assign it to a local variable called odds1. Next we define a function and assign it to a global variable odds. The function odds is “closed over” the variable odds1, which means that it can reference that variable, even when the odds function is called outside the context it is defined in, even though the odds1 variable will not be directly available from that context. To test this out, simply try to print the value of odds and then odds1 from outside of this outer function. The interpreter will say odds is a function but it will say odds1 is undefined, which means odds1 is effectively private.

So when someone calls our function odds, it calls odds1 with an initial value of 1 for the accumulator and then returns that value. Since JavaScript does not have tail-call optimization, that is what actually happens. odds waits for the value of odds1 to be calculated and then returns that value once it gets one. If you look at odds1, it does the same thing, returning the value from a recursive call to itself. And since JavaScript does not have tail-call optimization, this still results in some sort of stack overflow with large enough values for n.

What a tail-call optimized language does is realize that the statement return odds1(n, p, 1) is saying call the function odds1 with the arguments n, p and 1 and then return value. What the language can do is have the odds function return immediately and tell the caller to call odds1 with the arguments n, p and 1 in order to get the value. The important distinction between these two is that the call to odds is eliminated from the call stack before odds1 is called.

The way I think of it is tail-call optimization almost like an HTTP redirect. The call to odds is simply redirected to odds1. Once odds has issued a redirect, it’s out of the equation. Without tail-call optimization, the call to odds has to make a call to odds1. While the call it odds1 is being processed, both odds and the original caller are waiting for the response. If the chain of calls becomes to long, the call stack overflows.

This same idea can be applied to the recursive calls within odds1 itself. When odds(5, 56) is called, it will in turn call odds1(5, 56, 1). In odds1, the last thing it will do is call itself recursively, but this time the parameters will be odds1(4, 55, (5/56)). A function that returns a recursive call to itself as the last thing it does is said to be tail-recursive. Our original recursive odds function was not tail-recursive, because it needed to multiple the value of the recursive call by a value after the recursive call returned.

Since odds1 is tail-recursive, the call to odds1(5, 56, 1) can just say call odds1(4, 55, (5/56)) instead and take itself off the call stack. The series of calls looks like this:

odds(5, 56))
odds1(5, 56, 1)
odds1(4, 55, 5/56)
odds1(3, 54, 1/154)
odds1(2, 53, 1/2772)
odds1(1, 52, 1/73458)
odds1(0, 51, 1/3819816)

The value of the accumulator in each of these calls is the result of the multiplication of the previous value and the current n divided by the current p. As you can see here, the width of the expression doesn’t increase for each iteration (well, except a little bit for the width of the accumulator value). If the interpreter actually evaluates the expressions this way there is no way to cause a stack overflow error. You can evaluate any of these expressions independently from the others, assuming you make odds1 public.

To see this in action, you will have to use a language with an interpreter that does tail-call optimization. Erlang is one such language. First let’s write a non-tail-recursive implementation of the odds function:



odds(0, _) -> 1;
odds(N, P) -> (N / P) * odds(N - 1, P - 1).

Now we can see that our function works using the Erlang interactive shell:

$ erlc lotto.erl
$ erl
Erlang R13B01 (erts-5.7.2) [source] [smp:2:2] [rq:2] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.2  (abort with ^G)
1> lotto:odds(5,56).
2> 1/(lotto:odds(5,56) * lotto:odds(1,46)).

So it turns out that you have to work really hard to get the Erlang VM to blow the stack on a non-tail-recursive call, but I managed to get an error eheap_alloc: Cannot allocate 1140328500 bytes of memory (of type "old_heap"). by trying to evaluate lotto:odds(100000000, 1000000000).. Let’s re-write the function to be tail-recursive:



odds(N, P) -> odds(N, P, 1).

odds(0, _, Acc) -> Acc;
odds(N, P, Acc) -> odds(N - 1, P - 1, (N / P) * Acc).

You can see that Erlang gives us a couple of language features to make this a little cleaner than the JavaScript function. First, functions with different arities are completely different functions. Arity is the number of arguments to a function. So here we have two functions, odds/2 and odds/3.

Also, pattern matching is used to distinguish the two cases. The odds/3 function has two cases, one where N is 0 and the other to handle all other cases.

Lastly, the export directive at the top says that we only want the odds/2 function to be public, so the odds/3 function is private to this module.

With this definition of the odds function, if we try to evaluate lotto:odds(100000000, 1000000000)., it will complete, although it will take some time. The original recursive odds function takes O(n) time and O(n) space, which means the amount of time and the amount of space it takes to evaluate the function increases linearly for larger values of n. Due to tail-call optimization, the function still takes O(n) time, but takes O(1) space, which means the amount of time it takes to evaluate the function still increases linearly with larger values for n increases, but the function always operates in a constant amount of space, regardless of the size of n.

So to summarize, tail-call optimization is a technique that is performed by the compiler/interpreter, usually transparently, to make tail-recursive functions operate in constant space. This is a necessary optimization in order to be able to use recursive functions to perform iterative calculations as opposed to imperative functions that use mutable local variables.

Programming Clojure

June 28, 2009
Programming Clojure

A few weeks ago I received my printed copy of Programming Clojure by Stuart Halloway in the mail. I had been a technical reviewer of the book so I was excited to see it finally in print. In case you haven’t heard of it yet, Clojure is a programming language designed by Rich Hickey, a Lisp dialect, that runs on the Java Virtual Machine and is designed support concurrent programming.

Clojure has excellent documentation and Rich has posted several great videos of talks he has given that cover the rational for Clojure as well as an introduction into the major concepts. I highly recommend that you watch those videos if you haven’t already because Rich does a great job explaining why concurrency is hard using the typical Object-Oriented model that we program in today and how the features of Clojure support a better model for concurrency. Whether you are programming in Java, C#, Erlang, Haskell, Python, Ruby, etc., you will probably be able to learn something from these talks, and plus Rich is just an interesting guy to listen to.

So after all that, you might be saying why do we need a book about Clojure? The answer is that although the documentation is good, it can be a little intimidating when first learning Clojure. For programmers with little or no Lisp or functional programming experience, figuring out how to do basic things the idiomatic way in Clojure can be a daunting task. Stuart’s book does an excellent job filling this gap.

The book covers all the major feature of Clojure and is very up-to-date. As a reviewer I got to see the evolution of this book from revision to revision and it was amazing to me to see how much work Stuart put in. Chapters were often completely re-written to keep up with changes in the language that occurred before it stabilized in a 1.0 release. I think the final product greatly benefited from that work and is an excellent resource for learning Clojure. I encourage you to pick up a copy today.

Posted in Technology | Topics Clojure | 2 Comments

Is Clojure An Acceptable Lisp?

February 5, 2009

Almost two years ago now, Steve Yegge post an article articulating his problems with Lisp. He finished up the article with:

There is no acceptable Lisp

This is a problem. It’s not a little teeny one, either. The Lisp communities (yeah, there are a bunch) are going to have to realize that if Lisp is ever going to be massively successful, it needs an overhaul. Or maybe a revolution. Contrary to what some might tell you, it doesn’t need a committee, and it doesn’t need a bunch of money. Linux proved exactly the opposite. Lisp needs a benevolent dictator. Lisp needs to ditch the name “Lisp”, since it scares people. And Lisp needs to learn from the lessons of the 45 years of languages that have followed it.

Sounds a lot like Clojure. Do you agree?

Posted in Technology | Topics Clojure, Lisp | 4 Comments

Testing in a statically-typed language

December 19, 2008

One of the many “fringe” languages that has been on my radar for some time now is Haskell. Haskell has what looks to be a pretty good book available online and a local book club forming, which presents a great opportunity to study it. What is interesting to me about Haskell is that it is a statically-typed language, like Java, not a dynamically-typed language like Lisp, Ruby, Python, JavaScript, etc. I have really become fond of dynamic typing while programming in Ruby, but I always like studying languages that challenge your fundamental beliefs about programming.

Incidentally, this is one of the reasons I have been really interested in Clojure. It challenges the validity of object-oriented project in a very serious way. In Clojure, you don’t define new classes, instead your program is simply comprised of functions that takes input, possibly call other functions, and return values. Studying functional languages helps you to see the benefits and weaknesses of object-oriented programming. Read more about this idea of studying programming in Glenn Vanderburg’s article about Koans.

So anyway, back to Haskell, and the paradigm here that is worth studying is static typing versus dynamic typing. I must admit, after moving from Java (a statically-typed language) to Ruby (a dynamically-typed language), I’m currently a big fan of dynamically-typed languages. So I’m trying to keep an open mind in studying this, but this passage from Chapter 2 of Real World Haskell I have to object to:

Programs written in dynamically typed languages require large suites of tests to give some assurance that simple type errors cannot occur. Test suites cannot offer complete coverage: some common tasks, such as refactoring a program to make it more modular, can introduce new type errors that a test suite may not expose.

In Haskell, the compiler proves the absence of type errors for us: a Haskell program that compiles will not suffer from type errors when it runs. Refactoring is usually a matter of moving code around, then recompiling and tidying up a few times until the compiler gives us the “all clear”.

One thing I learned when moving from Java to Ruby is that developers often rely on the compiler as a false sense of security. The notion that you can refactor a bunch of code, get it to the point where it compiles and then feel that your code works is dangerous. You code can still contain all sorts of runtime and logic errors, therefore if you want to have any degree of certainty that your code is free of bugs, you need to have some sort of test suite, regardless of if you are using a dynamic and statically typed language.

I’ve also heard the argument made that statically-typed languages allow you to write less tests, but I have also not found this to be the case. Most syntax and type errors will be found with the same tests you use to test the logic of the program. In other words, you don’t have to write one suite of tests to check for syntax errors, one for type checking and another for testing the logic of your program.

So the moral of the story is that regardless of whether you are writing your code in a statically or dynamically typed language, you still have to TATFT.