[mercury-users] list.merge is not tail recursive

Michael Day mikeday at yeslogic.com
Thu Jan 21 10:51:47 AEDT 2010


Following up on the stack overflow bug I just reported that affects 
list.sort, it seems that the cause of the problem is that list.merge is 
not tail recursive:

list.merge([], [], []).
list.merge([A | As], [], [A | As]).
list.merge([], [B | Bs], [B | Bs]).
list.merge([A | As], [B | Bs], [C | Cs]) :-
     ( compare(>, A, B) ->
         C = B,
         list.merge([A | As], Bs, Cs)
         % If compare((=), A, B), take A first.
         C = A,
         list.merge(As, [B | Bs], Cs)

As a result it overflows the stack when merging long lists. 
Unfortunately even the --optimise-constructor-last-call option has no 
effect on this code (in rotd-2008-01-30), due to the way it is written!

Here is a rewritten version that works as the optimisation applies and 
makes it tail recursive to use constant stack space:

:- func my_merge(list(T), list(T)) = list(T).

my_merge([], []) = [].
my_merge([A|As], []) = [A|As].
my_merge([], [B|Bs]) = [B|Bs].
my_merge([A|As], [B|Bs]) =
     ( if compare('>', A, B) then
         [B|my_merge([A|As], Bs)]
     else % if A =< B then
         [A|my_merge(As, [B|Bs])]

This also works:

my_merge([A|As], [B|Bs]) = Cs :-
     ( if compare('>', A, B) then
         Cs = [B|my_merge([A|As], Bs)]
     else % if A =< B then
         Cs = [A|my_merge(As, [B|Bs])]

But this fails:

my_merge([A|As], [B|Bs]) = [C|Cs] :-
     ( if compare('>', A, B) then
         C = B,
         Cs = my_merge([A|As], Bs)
     else % if A =< B then
         C = A,
         Cs = my_merge(As, [B|Bs])

It would be nice if the constructor last call optimisation was 
sufficiently general to handle this case. (And is the standard library 
compiled with this optimisation?)

Either way, the list.merge and list.sort functions need to be changed!

Best regards,


Print XML with Prince!
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

More information about the users mailing list