Claim 2: General tail-recursion is an essential element of a programming language.

By `general' tail-recursion I mean that all calls that occur in `tail' position avoid allocating. Many languages or implementations support `self' tail-recursion in which tail-recursive calls to the same procedure are compiled or interpreted as loops, but fewer support the completely general case of arbitrary mutual tail-recursive procedures acting as a loop.

`Essential' is trickier to justify. There are many arguments for it and one really big argument against it. Might as well play devil's advocate first.

General tail recursion cannot be `essential' in a meaningful way because few programming languages support it and no one is complaining.

That is certainly a true statement, so let's compare a hypothetical language that has two variants, one has no tail recursion, the other supports general tail recursion. The first observation we can make is this: Any program that runs in a language without tail recursion will also run in a language with tail recursion. (That is, if it completes with an answer, both versions would produce the same answer.) The second observation is this: There are programs that run in a tail recursive language that will fail to run in a language without tail recursion. These would obviously be the programs that run out of stack or memory. So the claim that general tail recursion is essential is equivalent to the claim that there exist interesting programs that run in a tail recursive language and fail to run in a language without tail recursion. The devil's advocate position would deny this:

General tail recursion cannot be `essential' because there are no interesting programs that require a general tail-recursive implementation.

It seems unlikely that this is an a priori truth. Even the fact that there exists a class of programs that require general tail-recursion is interesting in itself. There is a slightly weaker argument that gets around this objection without much difficulty:

There are no interesting programs that require a general tail-recursive implementation because there are equivalent programs that do not require a general tail-recursive implementation.

This is also true, but the argument has been critically weakened. The equivalent programs are not, in general, `macro expressible' in the original language. You can turn the self tail-recursion into a loop fairly easily but you cannot make a loop out of mutually tail-recursive procedures without whole-program analysis (that is, an analysis at the level above the scoping of the mutually recursive procedures).

So why doesn't anyone complain about this? Most programming languages require you to write loops using special primitive looping constructs. These languages encourage the programmer to indentify and separate out the iterative and recursive forms. The programmer is trained from very early on to perform the larger analysis needed to identify iterative control flow and rewrite it as a looping construct. It isn't all that difficult, you have to do it anyway, so what's there to complain about?

Continuation passing style.

Continuation passing style is an example of a programming paradigm that can be very difficult to convert into a looping construct. Every CPS function performs a tail-recursive call to another CPS function, and rather than keep nested state on the stack, the state is kept in nested closures. If every function takes exactly one continuation argument, then it isn't too hard to `unravel' the CPS code into an equivalent `direct style' program, but the more complicated CPS code that takes more than one continuation cannot be easily converted to direct style.

There are few loops in continuation passing style. Control is transferred from function to function in a uniform manner and the difference between `iteration' and `recursion' is seen only as a difference in the space complexity of the continuation arguments. The interpreter or compiler must be sure to avoid inessential allocation when transferring control or an otherwise iterative construct would consume an arbitrary amount of memory (or stack).

If you agree with my claim that languages that support continuation-passing-style are more expressive than ones that do not, and that general tail recursion is a necessary prerequisite for continuation-passing-style, then you ought to agree that languages that have general tail recursion are more expressive than ones that do not.

Some more about general tail recursion later.