tail recursion

[jinx (Guillermo J. Rozas)]

    No, of course not.  It's not a semantic property; it's an
    implementation property.  As Jonathan Rees points out, it is a
    concept closely related to garbage collection, the presence of
    which is also an implementation property, not a semantic one.
    Both of these implementation properties have indirect semantic
    consequences, however, in that they make it possible *in practice*
    to write programs in a certain style which some people like;
    without these properties, the execution of programs written in
    that style would make (what is judged to be) inadequately
    effective use of the hardware resources available.  Would they be
    considered important on every imaginable architecture?  Who knows?

I don't agree with you.  You can have semantics at different levels,
depending only on how much magnification you want out of the semantics
microscope.  It should not be hard to write a semantics with explicit
memory management where both of these properties are explicit.  Of
course, the semantics would be (in most ways) much less informative
than the usual semantics that ignores such aspects.

The way that I like to define proper tail recursion is as follows:

An evaluator with explicit control and finite-memory management that
implements "proper tail recursion" can be written for the language.
It can be similar to the one in chapter 5 of SICP, although it does
not have to be written in machine language, but can be written on any
mutually acceptable language, such as Scheme, C, or denotational
semantics.  Call such an implementation (definition) M0.

An implementation M of the language is properly tail-recursive if
there exists a constant K (dependent only on M), such that any program
running on M requires at most K times the amount of storage that the
same program would require to run on M0 (for the same inputs/state,
etc.).

By requiring X storage I mean that if the implementation is given X
units of storage, an out-of-memory condition does not arise during the
execution of the program.

I realize that this definition has implications for the implementation
of environment structure, closures, etc., but that is precisely the
point.

Furthermore, if an implementation has infinite memory, no
out-of-memory conditions can arise, so you can't ever tell whether or
not it is properly tail recursive, but it shouldn't matter either.