On Mon, 2005-10-03 at 15:09 +0200, Thomas Fischbacher wrote:
> On Mon, 3 Oct 2005, skaller wrote:
> 
> > > I hope that one day functional language compilers will
> > > do that optimization for you - convert a
> > > non-tail-recursive code into a tail-recursive one. Do
> > > you know of some progress in that direction?
> > 
> > Isn't that just CPS? 
> 
> He presumably wanted to see a different thing, e.g. 
> automatically transforming

I know. But his comment 'that's different' is inadequate.
CPS transforms code so there are no function calls at all,
(procedural form), or, in functional form, every function
contains exactly one call which is always in tail position.

So it certainly does what is required. Therefore the
question is nonsense. The real question is more like
asking if it is possible to transform a routine
using O(n^k) store into one using O(n^j) store, where j < k.

It is always possible to eliminate recursion: for example,
a recursive descent of a simple tree can always be replaced by a using
an iterator .. of course the iterator will have to retain
a list of parent nodes to allow the traversal, so eliminating
the 'recursion' does not save any storage.



-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net