proper tail calls

Anton van Straaten anton at appsolutions.com
Mon Jan 21 11:35:33 PST 2008


Peter Michaux wrote:
> I've been trying to find out how [proper tail calls] are not an 
> optimization. I haven't read anyone else that thinks they are not an 
> optimization but I have read other people refer to them as an 
> optimization. I think that from an application programmers point of 
> view they are an optimization since the same program will run without 
> proper tail calls if the computer has infinite resources.
...
> Following one of those links leads to a wiki and the wiki has the
> following page which discusses proper tail calls as an optimization in
> the language
> 
> http://c2.com/cgi/wiki?TailCallOptimization

There's a distinction between the space efficiency property known as 
"proper tail recursion" and the implementation technique called "tail 
call optimization".  For some discussion of this, see:

http://groups.google.com/group/comp.lang.lisp/msg/0b8eb4a54bff7857

In that post, Will Clinger makes the point that there's a distinction 
between:

"* a syntactic concept (tail calls, aka tail recursion)
  * implementation techniques (tail call optimization, tail merging)
  * space efficiency property (proper tail recursion)"

The abstract of Clinger's original paper[*] about proper tail recursion 
mentions this point:

"Proper tail recursion is not the same as ad hoc tail call optimization 
in stack-based languages. Proper tail recursion often precludes stack 
allocation of variables, but yields a well-defined asymptotic space 
complexity that can be relied upon by portable programs."

Proper tail calls are a property that programmers can rely on in 
languages which offer it.  How that is implemented is not that important 
to an application programmer.  The fact that one can implement proper 
tail recursion, in part, with a technique known as tail-call 
optimization, doesn't make proper tail calls an optimization, any more 
than optimizations in a garbage collector make garbage collection an 
optimization.

Anton

[*] http://citeseer.ist.psu.edu/clinger98proper.html




More information about the Es4-discuss mailing list