ECMAScript 4 is the next-generation version of JavaScript that has the backing of platform providers as diverse and Microsoft, Adobe, and Mozilla. Much like Scala, ECMAScript combines object-oriented and functional features, but provides backwards compatibility with existing JavaScript code, and provides a choice of dynamic or static typing.

The latest version of ECMAScript 4 is currently being developed, and one of the new features proposed for the language is support for tail recursion. This feature may at first appear to be of interest to language implementers, but Adobe's Francis Cheng explains in a series of blog posts why tail recursion may matter to developers as well. In Proper Tail Calls, a definition, Cheng defines tail recursion from a developer's perspective:

The essence of PTC (proper tail calls) 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 ... will store the function in a special area of memory called the stack... 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... 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... 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...

Chen explains in other posts that tail call support can make several programming techniques more efficient. But code refactoring is often required in order to gain that benefit. For instance, Cheng points out that tail call support in the runtime can reduce the amount of stack space required for recursive functions, if such functions are written in a certain way:

function factorial (num:int): Number {
	if (num <= 1) {
		return 1;
	}
	else {
		return num * factorial(num-1);
	}
}

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:

function factorialEx (num:int):Number {
	return factorialIterator(1, 1, num); 
}

function factorialIterator(counter:int, subTotal:Number, maxCount:int) {
	if (counter == maxCount) {
		return subTotal * counter;
	}
	else {
		return factorialIterator (counter + 1,
					  subTotal * counter,
					  maxCount)
	}
}

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.

Chen also explains how tail call support can lead to efficient implementations of state machines in a functional programming style.

What do you think of the proposed tail call support for ECMAScript 4?