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

*To*: Luddy Harrison <harrison@sp21.csrd.uiuc.edu>*Subject*: Re: tail recursion*From*: halstead@crl.dec.com*Date*: Mon, 23 Apr 90 17:16:42 EDT*Cc*: halstead@crl.dec.com, rrrs-authors*In-Reply-To*: Your message of Mon, 23 Apr 90 15:06:14 -0500. <9004232006.AA03672@sp21.csrd.uiuc.edu.>

> Consider my dataflow example again. It may be that in order to > achieve speedup, such a machine uses a quantity of "resources" that is > not O(kX) where X is the consumption of M0. ... Actually, this suggests an interesting idea: I can see a bunch of arguments for limiting the "resource consumption" of any legal Scheme implementation to O(f(X)) where X is the consumption on M0, independent of how long the program runs. This in itself would rule out any implementation (such as the naive, non-tail-recursive one) that uses space of O(Xt), where t is the running time of the program. But is there any reason to rule out O(X log X) space consumption? O(X^2)? O(X^3)? O(2^X)?! If any of these are permissible, do any of them offer any useful flexibility to the designer? -Bert

**References**:**tail recursion***From:*harrison@sp21.csrd.uiuc.edu (Luddy Harrison)

- Prev by Date:
**Re: tail recursion** - Next by Date:
**tail recursion** - Prev by thread:
**tail recursion** - Next by thread:
**Re: tail recursion** - Index(es):