[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