Dear all, here is the small mergesort program for which ciaopp V0.8#17 (as installed on clip) seems to go away, both in the computation of upper and lower complexity bounds. If you have a version of ciaopp that can analyze it, please let us know the complexity analysis results. Of course, it would be great if we could have a version of ciaopp installed on our machines: too often we wonder "which complexity would be obtained with ciaopp for this program?" We can handle beta or even alpha versions... anything, provided it breathes ;-) Cheers Roberto P.S. Same thing applies to ciaoc: as soon as you have a version with the recent memory management fixes, just let us know. -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it :- module(msort, [msort/2], [assertions]). :- entry msort(A,B) : (list(A, num), var(B), ground(A)). % % msort.pl Nai-Wei Lin November, 1991 % % This program performs the mergesort on a list of integers. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %:- mode(divide/3,[+,-,-]). %:- measure(divide/3,[length,length,length]). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% divide([],[],[]). divide([X],[X],[]). divide([X1,X2|L],[X1|L1],[X2|L2]) :- divide(L,L1,L2). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %:- mode(merge/3,[+,+,-]). %:- measure(merge/3,[length,length,length]). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% merge(L,[],L). merge([],L,L) :- L \== []. merge([X1|L1],[X2|L2],[X1|L]) :- X1 >= X2, merge(L1,[X2|L2],L). merge([X1|L1],[X2|L2],[X2|L]) :- X1 < X2, merge([X1|L1],L2,L). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %:- mode(msort/2,[+,-]). %:- measure(msort/2,[length,length]). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% msort([],[]). msort([X],[X]). msort([X1,X2|L],R) :- divide([X1,X2|L],L1,L2), msort(L1,R1), msort(L2,R2), merge(R1,R2,R).