[mercury-users] Can mercury apply tail call optimization for this piece of code?

[Vladimir Gubarkov]

On Wed, Mar 30, 2011 at 2:40 AM, Peter Wang <novalazy at gmail.com> wrote:

> On 2011-03-29, Vladimir Gubarkov <xonixx at gmail.com> wrote:
> > Hi,
> >
> > I'm experimenting with some optimization options. I know, that mercury
> > supports goal-reodering for optimization, so I thought, that it could
> > optimize next code to tail-recursive, but seems It's not.
> ...
> >
> > :- pred replaceEvenElementList(list(char), list(char)).
> > :- mode replaceEvenElementList(in, out) is det.
> >
> > replaceEvenElementList([A,E|T1],[A,E1|T2]):-
> replaceEvenElementList(T1,T2),
> > E1 = (E='x'->'y'; E).
>
> --optimise-constructor-last-call can do it if you move the construction
> directly after the recursive call.
>
> replaceEvenElementList([], []).
> replaceEvenElementList([A], [A]).
> replaceEvenElementList([A, B0 | L0], L) :-
>    B = (B0 = 'x' -> 'y' ; B0),
>    replaceEvenElementList(L0, L1),
>    L = [A, B | L1].
>

The thing is that --optimise-constructor-last-call can do it also for code:

replaceEvenElementList([], []).
replaceEvenElementList([A], [A]).
replaceEvenElementList([A, B0 | L0], [A, B | L1]) :-
   B = (B0 = 'x' -> 'y' ; B0),
   replaceEvenElementList(L0, L1).

but not for:

replaceEvenElementList([], []).
replaceEvenElementList([A], [A]).
replaceEvenElementList([A, B0 | L0], [A, B | L1]) :-
   replaceEvenElementList(L0, L1),
   B = (B0 = 'x' -> 'y' ; B0).

But I thought that if for mercury this two definitions should be logically
equal (goal order not metters) then it could in theory optimize the second
one to be tail-recursive (ok, with constractor-last-call) either. But it's
not.

How do you think, theoretically is this optimization possible, or maybe it's
incorrect to perform such optimization? Though, I don't see why.



> Peter
> --------------------------------------------------------------------------
> mercury-users mailing list
> Post messages to:       mercury-users at csse.unimelb.edu.au
> Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
> Subscriptions:          mercury-users-request at csse.unimelb.edu.au
> --------------------------------------------------------------------------
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mercurylang.org/archives/users/attachments/20110330/661d20f4/attachment.html>