% Concurrent program according to Shapiro
:- constraints primes/2,integers/3,sift/2,filter/3.

option(guard_simplification,on).
option(type_definition,type(list(X), [ [], [X | list(X)]])).
option(type_declaration,sift(list(int),list(int))).
option(type_declaration,filter(list(int),int,list(int))).
option(mode,sift(+,?)).
option(mode,filter(+,+,?)).

primes(N,Ps) <=> integers(2,N,Ns), sift(Ns,Ps).

integers(F,T,Ns) <=> F > T | Ns=[].
integers(F,T,Ns) <=> F =< T | Ns=[F|Ns1], F1 is F+1, integers(F1,T,Ns1).

sift([P|Ns],Ps) <=> Ps=[P|Ps1], filter(Ns,P,Ns1), sift(Ns1,Ps1).
sift([],Ps) <=> Ps=[].

filter([X|In],P,Out) <=> 0 =\= X mod P | Out=[X|Out1], filter(In,P,Out1).
filter([X|In],P,Out) <=> 0 =:= X mod P | filter(In,P,Out).
filter([],P,Out) <=> Out=[].

go :- go(100000).
go(Count):-
	measure(dobench(Count), true, Utime,Gtime,System),
	write(bench(cprimes_CHR,Count,Utime,Gtime,System)), write('.'),nl,fail.
go(Count):-
	measure(dobenchp(Count), true, Utime,Gtime,System),
	write(bench(cprimes_prolog,Count,Utime,Gtime,System)), write('.'),nl,fail.

dobench(N):-
	primes(N,Ps),fail;true.
dobenchp(N):-
	primesp(N,Ps),fail;true.

primesp(N,Ps) :- integersp(2,N,Ns), siftp(Ns,Ps).

integersp(F,T,[]) :- F > T.
integersp(F,T,Ns) :- F =< T, Ns=[F|Ns1], F1 is F+1, integersp(F1,T,Ns1).

siftp([P|Ns],Ps) :- Ps=[P|Ps1], filterp(Ns,P,Ns1), siftp(Ns1,Ps1).
siftp([],[]).

filterp([X|In],P,Out) :-
	( 0 =\= X mod P ->
	    Out=[X|Out1], filterp(In,P,Out1)
	;
	    filterp(In,P,Out)
	).
	
filterp([],P,[]).