tail-recursion

[harrison@sp21.csrd.uiuc.edu (Luddy Harrison)]

If it should be decided to speak of tail-recursion in the standard,
allow me, as a consumer of the standard, to recommend Guy's
definition.  First, it is quite easy to test: an example like Kent's
can be run, and the fact that it loops forever will be very convincing
evidence of proper tail-recursion.  Moreover, Guy's definition gives a
infinitude of such examples.

Second, it seems quite a bit easier to prove of an implementation than
the M0 test.  I must only be able to speak of identical states,
whatever they might be in my implementation, and then characterize the
evaluator when it encounters identical states along a chain of
tail-recursive calls.

Third, it is independent of issues other than proper tail-recursion.
The M0 test has the bad property that if I pass it, and then change my
representation of hashtables, I might fail it (for a reason that has
nothing to do with tail-recursion).

Kent's proposed characterization (p1 => ... => pn is no more
consumptive of storage than p1 => pn) has a similar effect, but is
slightly weaker than Guy's test, as it does not require infinite
looping the way Guy's test does.

-Luddy