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

Re: tail recursion

> 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