Francis Cheng

Today I'm going to talk about the proposed Proper Tail Calls (PTC) feature and recursion. I'm going to show you how PTC can significantly reduce stack usage for functions with recursive calls in tail position. If you recall, I mentioned in my previous post that Proper Tail Calls is also called Proper Tail Recursion. This is because PTC has a significant effect on certain types of recursive functions. In case you're unfamiliar with recursion, a recursive function is a function that calls itself. For example, we could use a recursive function to calculate the factorial of a number, which means multiplying a number by every integer between that number and zero, as in 3! = 3 x 2 x 1 = 6. Here's an ActionScript function that calculates factorials:

So let's call factorial() with an argument of 3 and walk through the code execution. The parameter num is assigned a value of 3, which means we skip down to the else{} statement because 3 is greater than 1. In the else{} statement, we call factorial() again, but this time with the argument value 2. When the new call happens, the runtime suspends execution of the original call to factorial() and pushes the original call onto the stack because we'll need it later. Next, we walk through the second call to factorial(), but with the value 2. We get similar results, factorial() gets called a third time, but this time with an argument value of 1.

At this point we've not yet returned from any function, so all of these functions are still active and piled onto the stack, with our initial call at the bottom of the stack. With the call to factorial(1), however, we finally enter the if{} statement and simply return the value 1. This means that the call to factorial(1) can be discarded and we emerge back inside the else{} statement in the previous call to the factorial function, factorial(2). This return trip back down the stack is where values are returned and the calculations occur:

Notice that the recursive call to factorial() is not in tail position because the last thing the function does is multiply num by the return value of factorial(num-1). So PTC would not affect the execution of factorial() as it is written above. To get the benefits of PTC, we would need to refactor the code so that the recursive call to factorial() is in tail position. One way to do that would be to use a helper function that handles the recursion:

PTC will apply to factorialIterator() because the recursive call to factorialIterator() is in tail position. The factorialEx() function takes a very different approach in that it uses a counter to track progress so that it doesn't have to fill up the stack with a large number of suspended function calls. A call to factorialEx() sets in motion a series of tail calls that keeps stack usage constant. Stepping through, a call to factorialEx(3) results in a tail call to factorialIterator(), which results in recursive tail calls until the counter is equal to 3. The subTotal parameter stores the running total throughout this process.

The difference between these two techniques is more pronounced if you consider larger factorials. If you want to calculate 40 factorial, the original factorial() function will result in extensive stack usage that will require memory enough to hold 40 deferred function calls. On the other hand, if PTC is added to the language, the factorialEx() function will grow the stack by no more than one function. Currently, however, ActionScript exhibits the same extensive stack-usage behavior for both factorial() and factorialEx().

You may be thinking that 40 or so functions on the stack are not a big deal, and we can't feed numbers to factorial() much bigger than that before we exceed the capacity of the Number type to hold the answer. I agree that this isn't a great example of the benefit of PTC, but it was useful as a simple way to explain the differences between these recursive functions. There are other examples, such as calculating Fibonacci numbers, that better show the benefits of PTC. You could write a non-tail-recursive Fibonacci function that calls itself for every addition operation. There you would run into ActionScript's recursion limit when feeding in numbers that call for more than a thousand calculations. That would mean a thousand suspended functions stored on the stack, which would contrast sharply with a tail-recursive implementation that would grow the stack by exactly one function.

Here are links to some of the materials I used in my research for this post:

• Structure and Interpretation of Computer Programs
• Tail Call Optimization, by Laurence Tratt
• Compilation of Functional Programming Languages using GCC - Tail Calls (pp. 7 - 9), by Andreas Bauer
• Proper tail recursion and space efficiency, by William Clinger
• Proper Tail Calls, ECMAScript 4th Edition proposal

Posted by Francis Cheng at 11:13 AM | Permalink | Comments (5)

One of the things I get to do here at Adobe is help out with the drafting of the ECMAScript Edition 4 (ES4) language specification. Lately, there has been a flurry of discussion on the ES4-discuss list about one of the proposed new features, Proper Tail Calls (a.k.a. Proper Tail Recursion, but I'm going to call it PTC from now on). I thought this might give me a good opportunity to provide some background information about this feature and what it might mean for ActionScript developers in the future.

In case you don't know, ECMAScript is the language standard upon which JavaScript, JScript, ActionScript and many other languages are based. The current version of ECMAScript is the third edition, but a lot of work is going on for the fourth edition. So what I'm discussing here is not currently in ActionScript, but may one day be if PTC makes it into the fourth edition specification.

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.

Posted by Francis Cheng at 9:51 PM | Permalink | Comments (6)