Testcase for ciaopp

26 May 2003

      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).

Roberto Bagnara

tags (0)

participants (1)