Francis Cheng

Today I'll start with a definition of PTC, and I'll follow up over the next few days with examples and further thoughts. You can find the ES4 proper tail calls proposal at the ecmascript.org website. I should warn you, though, that the proposals are geared more toward language implementors than users, so don't worry too much if you don't understand all the terminology they use. I'll try in this blog to translate what some of these proposals mean for ActionScript developers.

Speaking of writing geared toward computer scientists, the best definition of PTC I've come across is from a journal article by William Clinger at Northeastern University titled "Proper Tail Recursion and Space Efficiency". In that paper, he talks about the essence of PTC, which I'll paraphrase in terms of ActionScript below. I have to admit that much of the article is over my head, but he writes clearly so I learned a lot from reading the sections that I could wrap my brain around. He has the article posted on his website if you're interested in further reading (http://www.ccs.neu.edu/home/will/papers.html).

According to Professor Clinger, the essence of PTC is that it provides a new way to return from a function. Namely, instead of returning a value, you can call any other function as the last thing you do. Such a function call is said to be in tail position, or to make things easier you can just refer to the call as a "tail call". This may not seem like a big deal, but it does add a new twist to the life cycle of a function.

Consider a typical ActionScript function:

function foo () {
   trace("hello");
}

The foo() function will exist in memory from the time that you call it to the time that it returns from that call. The runtime (I'm going to use the word "runtime" instead of "Flash Player" or "Virtual Machine") will store the function in a special area of memory called the stack. As the name implies, a stack is organized as a last-in first-out stack, like a deck of playing cards that grows and shrinks as you add, use, and discard cards from the top of the deck. Notice in our example that we call another function, trace(), from the body of foo(). This means that foo() remains in memory while the trace() function runs. In terms of the stack, the runtime stores trace() on top of foo(). This is not a big issue in our little example, but what if it turns out that trace() calls another function, and that function calls another function, and so on. Pretty soon your stack starts getting pretty big. In fact, sometimes your stack can get too large and you get a stack overflow error.

PTC changes this behavior if the function call is in tail position. Instead of keeping foo() in the stack and placing trace() on top of it, foo() is discarded and trace() takes its place. This seems like a sensible thing to do because foo() doesn't do anything after the call to trace(), so why keep it around in memory? (Some argue that keeping it around is really helpful for debugging, but we'll talk about that another day.) And if there's a tail call in trace(), that call replaces trace() in the stack and so on. Instead of an ever-growing stack, you get a stack that may not grow at all, which will make a stack overflow exception much less likely.

PTC's ability to increase stack-use efficiency leads some people to call this feature Tail Call Optimization (TCO). However, the motivation section of the ES4 proposal for PTC states:

"Proper tail calls are not an optimization, but an aspect of the semantics of the space usage of the language."

I hope that Professor Clinger's insight into the essence of PTC helps you see this as more than just a mere optimization. If you don't, it may be because I did a poor job of paraphrasing him, so I would encourage you to read his article. Over the next few days I'll post new entries that delve more deeply into PTC. Specifically, I'll devote separate posts to recursion and how PTC is useful for programming with finite state machines.