%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 
%%% A naive interpreter for the Gamma language
%%% (using multisets)
%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Last revision: December 2002 (G.Rossi)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%% The Gamma interpreter 

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

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%% Sample applications %%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 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) :- 
    int_to_bag(int(2,N),R) &
    gamma(rule1,R,S)!.

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

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Computing N!
%%%
%%% factorial_gamma(N,F): 
%%% true if F is the factorial of the number N
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

factorial_gamma(N,F) :- 
    int_to_bag(int(1,N),R) &
    gamma(rule2,R,S) &
    S = *{F}.

rule(rule2,*{X,Y\Z},*{V\Z}) :- 
    V is X * Y.

% Sample goal:
%
% {log}=> factorial_gamma(20,F).
% F = 2432902008176640000


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Counting the number of occurrences of element a in a multiset
%%%
%%% no_of_a(M,N): 
%%% true if N is the number of 'a' in multiset M
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

no_of_a(M1,N) :-
     gamma(rule7,M1,M2) &
     msize(M2,N)!.

rule(rule7,*{X\R},R) :- X neq a.

% Sample goal:
%
% {log}=> no_of_a(*{a,b,a,b,a},N).
% N = 3
% Another solution?  (y/n)y
% no

% Sample goal:
%
% {log}=> no_of_a(*{a,b,X},N).
% N = 2,  X = a
% Another solution?  (y/n)y
% N = 1, Constraint:[X neq a]
% Another solution?  (y/n)y
% no


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Chemical reaction - generating molecules of water
%%%
%%% chemical1(C,W): 
%%% true if C is a multiset containing atoms of hydrogen h and oxygen o
%%% and W are the related molecules of water w
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

chemical1(C,W) :-
     gamma(rule5,C,W).

rule(rule5,*{h,h,o\Z},*{w\Z}).

% Sample goal:
%
% {log}=> chemical1(*{o,o,h,h,h,o,h,h,h},W).
% W = *{w,w,w}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Chemical reaction - filtering water
%%%
%%% chemical2(S,W): 
%%% true if S is a substance (i.e., a multiset of its component molecules)
%%% and W are the remainig molecules of water *{h,h,o}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

chemical2(S,W) :-
     gamma(rule6,S,W).

rule(rule6,*{X\W},W) :- X neq *{h,h,o}.

% Sample goal:
%
% {log}=> chemical2(*{*{si,o,o},*{h,h,o},*{h,h,o},*{h,h,o},*{o,si,o}},Water).
% Water = *{*{h,h,o},*{h,h,o},*{h,h,o}}.


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

start :- 
   consult_lib &
   nl & nl &
   write('A naive interpreter for the Gamma language.') & nl &
   write('You can give the goals: ') & nl &
   write(' - primes_gamma(N,S): ') & nl & 
   write('   true if S is the set of all the prime numbers smaller than N ') & nl &
   write(' - factorial_gamma(N,F): ') & nl & 
   write('   true if F is the factorial of the number N ') & nl &
   write(' - no_of_a(M,N): ') & nl &
   write('   true if N is the number of ''a'' in multiset M ') & nl &
   write(' - chemical1(C,W): ') & nl & 
   write('   true if C is a multiset containing atoms of hydrogen h and oxygen o ') & nl &
   write('   and W are the related molecules of water w ') & nl &
   write(' - chemical2(S,W): ') & nl & 
   write('   true if S is a substance (i.e., a multiset of its component molecules) ') & nl &
   write('   and W are the remainig molecules of water *{h,h,o} ') & nl &
   nl.