[mercury-users] Re: GC and tail calls (was: Many data elements using Mercury on Cygwin?)

[Fergus Henderson]

On 07-Feb-2003, Douglas Auclair <dauclair at msn.com> wrote:
> >If adjusting the stack size does make the problem go away, then you might 
> >be able to eliminate the problem completely by rewriting your main loop(s) 
> >to be tail recursive, so that they do not consume stack space proportional 
> >to the size of the input.
> 
> If one does some source-to-source transformations, my code is 
> tail-recursive.  Translation:  I do tail-calls, but not necessarily 
> tail-recursive-calls; is the compiler smart enough to optimize tail calls?  

I'm not sure exactly what you mean.  Do you mean you have tail calls
that are indirectly recursive, e.g.

	p :- ..., q.

	q :- ..., p.

?

If that's what you mean, then the answer depends on the compilation grade.
In the low-level C grades (e.g. asm*), and in the .NET grade (`il'),
yes, the compiler will optimize tail calls to other procedures,
so examples like the one above will consume constant stack space.

But in the high-level C grades (e.g. hlc*), no, currently only
direct tail recursion is optimized.

> Is there a way ON CYGWIN to profile the code so I can see if I'm doing tail 
> calls and that the compiler's picking that up?

In 0.11.0, there is a Mercury compiler option `--warn-non-tail-recursion'
which will warn about recursive calls which are not tail calls.
This will issue warnings for cases such as

	p :- ..., p, ...

However, it won't catch indirect non-tail recursion, e.g.

	p :- ..., q, ...
	q :- ..., p, ...

Otherwise, well, it's always possible to examine the generated code.
In the low-level C grades you can examine the generated C code and look
for occurrences of "MR_call" or "MR_tailcall" to see which calls have
been optimized into tail calls.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------