[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: rrrs-authors*Subject*: tail-recursion*From*: harrison@sp21.csrd.uiuc.edu (Luddy Harrison)*Date*: Wed, 25 Apr 90 16:37:45 CDT

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

- Prev by Date:
**No Subject** - Next by Date:
**re: tail-recursion** - Prev by thread:
**No Subject** - Next by thread:
**re: tail-recursion** - Index(es):