%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 
%%% A naive interpreter for the Gamma language
%%% (actually, an approximation of the Gamma language, 
%%% using sets instead of multisets)
%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Last revision: December 2002 (G.Rossi)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%% The Gamma interpreter 

gamma(Rule,Input,Input) :- 
    naf applicable(Rule,Input).
gamma(Rule,Input,Output) :-
    rule(Rule,Input,Intermediate) &
    gamma(Rule,Intermediate,Output).

applicable(Rule,Input) :- 
    rule(Rule,Input,_).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%% Sample application %%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Generating the set of all the prime numbers smaller
%%% than a given integer N
%%%
%%% primes_gamma(N,S): 
%%% true if S is the set of all the prime numbers smaller than N
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

primes_gamma(N,S) :- 
    R = {X : X in int(2,N)} &
    gamma(rule1,R,S)!.

rule(rule1,{X,Y\Z},{X\Z}) :- 
    X neq Y & Y nin Z & 
    Rmdr is Y mod X & Rmdr = 0.

% Sample goal:
%
% {log}=> primes_gamma(15,S).
% S = {2,3,5,7,11,13}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% start predicate
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

start :- 
   nl &
   write('Generating the set of all the prime numbers smaller ') & nl &
   write('than a given integer N ') & nl & nl &
   write('Give the goal primes_gamma(N,S): ') & nl &
   write('S is the set of all the prime numbers smaller than N').

%:-start.