[clean-list] Memory usage in recursion

Fergus Henderson fjh@cs.mu.oz.au
Wed, 22 Nov 2000 01:09:09 +1100


On 21-Nov-2000, F.S.A.Zuurbier@inter.nl.net <F.S.A.Zuurbier@inter.nl.net> wrote:
> Jerzy wrote:
> =============
> > Clean and other functional programming languages would not be
> > useful if this problem had not been solved. Indeed, it has been
> > solved. So called tail-recursion can usually (if not always) by
> > compiled in such a way that a stack-frame is not needed. 
>
> Not always. (And not only because the compilers of, say, C++ are lousy). 
> In Prolog or other Logic Programming Languages the calls often must 
> leave something on the "trail" in order to enable the backtracking. 
> So, even the tail calls may overflow internal data structures, unless 
> the user is conscious and "cuts" the backtrack points. 

Actually for Prolog code that creates choice points, Prolog
implementations can't do tail call optimization.  They can
only do tail call optimization in the determinate case.
Typically this is done by a run-time check at the point
of the tail call.  For example, if you have

	p(...) :-
		q(...),
		r(...),
		p(...).

then code for the tail call to `p' must check whether `q' or `r'
created any choice points; if so, it is not safe to eliminate p's
stack frame, since it may be needed again on backtracking.

BTW, as a matter of Prolog programming style, it is generally better
to use first-argument clause indexing to avoid creating choice points
in the first place, rather than creating choice points and then using
cuts to prune them away.

> Check the Prolog-like Mercury language. I have not tried, but I
> would not be surprised if ithas a much nicer way to avoid stack
> allocation for tail calls. Not explicit cuts, but a way of knowing
> that backtracking is not needed in the context at hand, namely mode
> analysis.

Yes, actually it is Mercury's determinism analysis (which of course
relies on the mode analysis) that allows us to do tail calls in
situations like the example above, provided that `q' and `r' have at
most one solution.

We also have a `--checked-nondet-tailcalls' option on our compiler,
which is for cases where the code *might* create choice points but
rarely does so.  In that case, we generate code similar to what
Prolog compilers do, with a dynamic check.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.