[gclist] tail recursion requires gc

[William D Clinger]

I did not mean to appear to have the intention of intending
to suggest that anything short of fully general tail recursion
in C would fail to make C more useful as a target language.
My message was an attempt to refute the idea that tail-recursion
is unrelated to garbage collection, and therefore off-topic for
this mailing list.

Richard O'Keefe suggested that I was using "fully general tail
recursion" to mean "those tail calls that require garbage
collection".  Not so.  By "fully general tail recursion" I
mean that all syntactically tail-recursive calls execute
without allocating any space for a new continuation.

"Syntactically tail-recursive" is statically decidable.  "Tail
calls that require garbage collection" is not statically
decidable, nor is the notion of a "tail call that does not
require garbage collection".  "Syntactically self-tail-recursive"
is statically decidable, but is too specialized to allow C's
native calling conventions to be used by properly tail-recursive
compilers for other languages.  (Besides, a conventional
stack-based compiler for C cannot safely compile all
syntactically self-tail-recursive calls without allocating new
stack.)

To use C as a target for properly tail-recursive compilers,
we need some widely available C compiler such as gcc or lcc
to guarantee that some usefully large but syntactically
decidable subset of the syntactically tail-recursive calls
will execute without allocating space for a new continuation.

Wilson, Henderson, O'Keefe, and probably others have identified
appropriate subsets, so it is just a matter of modifying gcc to
make the guarantee.  I'm all for it.

William Clinger