[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
tail-recursion
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