Tail Calls, Tail Recursion, TCO

I'm going to tell a story that I think explains Tail Calls, Tail Recursion and TCO. I might decide to post some code about it, I might not. I don't actually find it necessary. First, a few definitions. If they aren't clear now, the stories should make them so.

• Tail Call - When the last thing a function does is call another function, and then immediately returns the result of that call.
• Tail Recursion - Just a special case of tail call where the function tail called is the same as the caller function. Tail Recursion won't come up again in this post, so if the definition isn't clear, don't worry about it.
• Tail Call Optimization - A compiler technique for avoiding adding an activation record to the stack for a tail call. (However, I don't like the word 'optimization' here. It is more like the correct implementation. More on that later.)

Regular Function Calls

Here, I tell a story about normal function calls, and introduce the theme and characters that will be used throughout the rest of this post.

Imagine that you have the munchies (feel free also, to imagine any reason why you might have the munchies :). Your particular craving at the moment is popcorn. A big bucket of salty, buttery popcorn. Standing next to you is your friend, Mr. Salt. He owns a salt shaker. Standing next to Mr. Salt is his friend Mr. Butter. Mr. Butter owns one of those liquid butter pumping machines that you see at the movie theaters. You don't really care that that happens to be a heart attack in the making. In fact, you don't really care about much of anything right now except the munchies and getting your popcorn :) Standing next to Mr. Butter is his friend Mr. Popper. Mr. Popper has a pop corn popper and a giant bin full of popcorn, and he's more than happy to dish some out.

You turn to Mr. Salt and ask, "like, duuude...I'd really like some salty, buttery, delicious popcorn right now. Could you get it for me? Here's five bucks." You hand him the five dollars.

Mr. Salt says, "Sure, but just give me a second to get some buttery popcorn and I'll put some salt on it for you." He then turns to Mr. Butter and says, "I can haz buttery popcorn? I got 5 bills." Mr. Butter replies, "Oh hai, u can haz. Hold on a sec."

Mr. Butter turns to Mr. Popper and asks him for some popcorn, handing him the 5 bucks. Mr. Popper obliges, and hands Mr. Butter a giant bucket of freshly popped plain popcorn.

Mr. Butter takes the popcorn, puts some butter on it, and hands it to Mr. Salt. Mr. Salt then takes the buttery delicious popcorn from Mr. Butter, puts a pile of salt on it, and hands it to Mr. Hungry Man (that's you).

These are examples of normal function calls, not tail calls. A tail call, once again, is when you make a function call, and have nothing left to do but return the result. But Mr. Butter and Mr. Salt did have work left to do with the result. Mr. Butter had to take the result (the plain popcorn) and apply butter to it. Similarly, Mr. Salt had to take the buttery popcorn and apply salt to it. Mr. Hungry Man had to eat the popcorn. (Mr. Popper didn't actually make a function call at all, he just immediately returned a result. Think 'def seven = 7').

Notice that each person in the chain is like an activation record on the stack, and that they all eventually have to be popped off the stack.

Tail Calls

To demonstrate tail calls, we only need to change the story slightly. You, (Mr. Munch, Mr. Hungry Man, Sir Smokealot) have decided to go on a diet. You ask Mr. Salt for some plain popcorn. He turns to Mr. Butter and asks him for plain popcorn. Mr. Butter turns to Mr. Popper and asks for some plain popcorn.

Here is where we really demonstrate the difference between a regular function call and a tail call.

Mr. Butter takes the popcorn from Mr. Popper and does nothing with it at all except turn around and hand it to Mr. Salt. He doesn't first apply butter to it. And, exactly the same, Mr. Salt takes the plain popcorn from Mr. Butter and turns around and hands it to Mr. Hungry Man. He doesn't put any salt on it.

Those are tail calls. Remember the definition: "When the last thing a function does is call another function, and immediately return the result of that call." The last thing those middle men did was ask someone else to get them something, took that thing from them and gave it to whoever asked them for it.

One important thing to notice here. I haven't talked at all about tail call optimization. Mr. Salt and Mr. Butter are still on the stack. They still take up space on the stack, and they still need to eventually be popped off the stack.

Before I talk about TCO, let's talk about the need for TCO.

The Problem

Imagine simply, that the line of people between you and the popcorn was 1000 dudes long. You still just want some plain popcorn, but have to go through 999 middle men to get it. That's 999 guys on the stack. 999 guys that eventually have to get popped off the stack as well.

Ok, fine. That might work. I guess it depends on how big your stack is.

But now imagine that the line is one million men long! 999999 middle men. 999999 guys on the stack right? WRONG. Stack Fricken Overflow Dood.

In the JVM world, this is what you get. There are of course techniques to avoid it, but you're severely limited on the JVM because it doesn't support tail call optimization (it doesn't have a tailcall byte code).

Tail Call Optimization

Okay. Now is the part where I change the story to describe TCO, and how it works. It's actually very easy.

You turn to Mr. Salt and say, "Can I please have some plain popcorn?" He turns the Mr. Butter and says, "Mr. Hungry Man would like some plain popcorn. Can you please get it for him? I don't really feel like it. In fact, I'm out of here." Mr. Salt then goes home for the day.

Mr. Butter turns to Mr. Popper and says the same thing: "Mr. Hungry Man would like some plain popcorn. Can you please get it for him? I don't really feel like it. In fact, I'm out of here." Mr. Butter than also goes home for the day.

Mr. Popper gets a bucket of popcorn and simply hands it to Mr. Hungry Man.

And that folks, is the end of the story. Case closed!

Ok fine, I guess it deserves at least a little more explanation. Mr. Salt, who knows he has a tail call where he would just take the result and give it to Mr. Hungry Man, can instead just have Mr. Butter give it to him. It makes absolutely no difference (ok a tiny difference that I'll explain later) who hands the popcorn to Mr. Hungry Man, so he might as well leave. In technical terms, Mr. Salt and Mr. Butter going home means they go off the stack. This could be implemented in a few different ways - maybe the top activation record is completely torn off the stack, or maybe it is just modified accordingly. Either way, this strategy saves stack space, and a little computation time too (remember that string of a million gotos that would have happened if the stack didn't overflow, all those instructions are saved).

Conclusion

I'd like to take this time to point out a confusion, or at least a point of contention in language designer circles (academics and non-academics alike). Because the term itself 'TCO' contains 'O' many people view TCO as just that, an optimization, while others view it simply as correct language design and implementation.

I fall into the latter camp. I think it is analogous to garbage collection. I don't think most programmers would consider GC as an optimization, but simply correct implementation. It isn't ok to just run out of heap space because you didn't bother to implement a GC. And so, it isn't ok to run out of stack space just because you didn't bother to correctly implement tail calls.

I believe this post is consistent and self contained and I don't want to spoil it with code, too many technical details, or language specific details. For that reason, I believe a Scala related follow up post is in order. It would explain things like:

• How the Scala compiler can turn tail recursive functions into while loops, and why it can't do so with non-final functions.
• What @tailrec does.
• Mutually recursive functions, trampolining and scala.util.control.TailCalls.

I also think I could extend this story to explain continuations. Maybe someday I'll get the chance to do that as well.

References

• Lambda: the ultimate goto

http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-443.pdf

• Fortress Blog - ObjectOrientedTailRecursion

http://tinyurl.com/yjbgks3

• Rich Dougherty - Tail Calls, Tail Rec, Trampolines

http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html

• John Rose - Tail Calls in the JVM

http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm

• Matthias Felleisen - A Tail-Recursive Machine with Stack Inspection

http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf

• Stack Overflow - @tailrec and non-final methods

http://bit.ly/stacko-tailrec