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

[Chris King]

On Tue, Mar 29, 2011 at 3:47 PM, Vladimir Gubarkov <xonixx at gmail.com> wrote:
> replaceEvenElementList([A,E|T1],[A,E1|T2]):- replaceEvenElementList(T1,T2),
> E1 = (E='x'->'y'; E).

The call to replaceEvenElementList() is not in tail position there, as
the constructor call occurs after the call to replaceEvenElementList.
This would not be tail-call optimized in most other languages (but see
the note below).  You would need to maintain an accumulator which
collects the results as they are produced, and then reverse it (since
they will be accumulated in reverse order).

Mercury *can* do accumulator introduction (--introduce-accumulators),
but only if your accumulation function is associative (e.g. + or
list.append).  Even in this case, although replacing [|] with
list.append will allow Mercury to introduce accumulators, it will
result in performance issues as you will be appending to the end of
the list.  You can get around this by using list.append to append
items to the end and reversing the result, but that's getting more
complicated than just introducing accumulators manually in the first
place.

Note: I believe Prolog can in fact optimize this, due to its use of
logic variables.  The cons cell can be created first, and then the
tail filled in later.  Mercury does not have this capability.

- Chris
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------