%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 
%%% A P system computing the function n^2
%%% implemented in CLP(BAG)
%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Last revision: December 2002 (G.Rossi)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% P system: 
%   U = {a,b},
%   \mu = *{ *{a,b,...,b | nil_2} | nil_1} (n occurrences of b)
%   R_1: empty
%   R_2:
%       (1) abb -> ((bb)(ab)) 
%       (2) ab  -> b  
%       (3) bb  -> b(b,out)(b,out)
%       (4) b   -> (b,out)\delta
%   ordered (1) > (2) > (3) > (4). 
%
% At the end of the computation, n^2 occurrences 
% of b are present in the outer membrane. All other 
% membranes in it have disappeared. 
% (remember that n^2 = \sum_{i=1}^n (2i -1)) 


% Membrane representation
%
% The current version of CLP(BAG) does not support
% colored multisets. Thus a membrane with label c 
% containing n elements s_1,...,s_n is defined in
% CLP(BAG) as the term m(c,*{s_1,...,s_n}).

%

% The main predicate governing the application of 
% evolution rules

p_interpreter(Membrane,Membrane) :- 
    neg applicable(Membrane).
p_interpreter(MembraneIn,MembraneOut) :-
    rule(MembraneIn,MembraneInt) &
    p_interpreter(MembraneInt,MembraneOut).

applicable(Membrane) :- 
    rule(Membrane,_).

% Auxiliary predicates

% choose(Membrane,Kernel,M_i,M_j) chooses a multiset 
% M_i in Membrane with kernel Kernel and the multiset
% M_j that contains it.

choose(m(K1,*{M_i\R}),Kernel,M_i,m(K1,*{M_i\R})) :-
        M_i = m(Kernel,_).
choose(m(K1,*{M\R}),Kernel,M_i,M_j) :-
        M = m(Km,_) & Km neq Kernel &
        choose(M,Kernel,M_i,M_j).

% replace(A,B,C,D) finds one occurrence of
% B in A and replaces it with C obtaining D.

replace(A,A,C,C).
replace(m(K,*{B\R}),B,C,m(K,*{C\R})):-
        m(K,*{B\R}) neq B.
replace(m(K,*{M\R}),B,C,m(K,*{M1\R})) :-
        M neq B &
        replace(M,B,C,M1).

% replace2(A,B,C1,C2,D) is like replace
% but it replaces B in A with both C1 and C2
% (used to implement the division rule)

replace2(m(K,*{B\R}),B,C1,C2,m(K,*{C1,C2\R})).
replace2(m(K,*{M\R}),B,C1,C2,m(K,*{M1\R})) :-
        M neq B &
        replace2(M,B,C1,C2,M1).

% Evolution rules

% rule 1       
rule(MembrIn,MembrOut) :-
       choose(MembrIn,nil2,M_i,M_j) &
       M_i = m(nil2,*{a,b,b\M_i1}) &
       replace2(MembrIn,M_i,m(nil2,*{b,b\M_i1}),m(nil2,*{a,b\M_i1}),MembrOut)!.

% rule 2
rule(MembrIn,MembrOut) :-
       choose(MembrIn,nil2,M_i,M_j) &
       M_i = m(nil2,*{a,b\M_i1}) &
       replace(MembrIn,M_i,m(nil2,*{b\M_i1}),MembrOut)!.

% rule 3
rule(MembrIn,MembrOut) :-
       choose(MembrIn,nil2,M_i,M_j) &
       M_i = m(nil2,*{b,b\M_i1}) &
       replace(MembrIn,M_i,m(nil2,*{b\M_i1}),MembrInt)! &
       MembrInt = m(K,MembrInt1) &
       replace(MembrIn,M_j,m(K,*{b,b\MembrInt1}),MembrOut)!.

% rule 4
rule(MembrIn,MembrOut) :-
       choose(MembrIn,nil2,M_i,M_j) &
       M_i = m(nil2,*{b\M_i1}) &
       M_j = m(K,*{M_i\MembrInt}) &  %% \delta removes M_i from M_j
       replace(MembrIn,M_j,m(K,*{b\MembrInt}),MembrOut)!.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% A sample goal

% {log}=> p_interpreter( m(nil1,*{ m(nil2,*{a,b,b,b}) }) , MembrOut ).
% MembrOut = m(nil1,*{b,b,b,b,b,b,b,b,b})


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% An alternative implementation, forcing rule ordering:
% add a unique identifier to each rule 
% and modify the definition of p_interpreter
% so to apply rules according to a list of rule identifiers 
% which explicitly states the rule ordering for each membrane.

p_interpreter2(Membrane,Membrane) :- 
    neg applicable(Membrane).
p_interpreter2(MembraneIn,MembraneOut) :-
    (L in {1,2,3,4} & rule(L,MembraneIn,MembraneInt))! &
    p_interpreter2(MembraneInt,MembraneOut).

applicable(Membrane) :- 
    rule(_,Membrane,_).

rule(1,MembrIn,MembrOut) :-
       choose(MembrIn,nil2,M_i,M_j) &
       M_i = m(nil2,*{a,b,b\M_i1}) &
       replace2(MembrIn,M_i,m(nil2,*{b,b\M_i1}),m(nil2,*{a,b\M_i1}),MembrOut)!.

rule(2,MembrIn,MembrOut) :-
       choose(MembrIn,nil2,M_i,M_j) &
       M_i = m(nil2,*{a,b\M_i1}) &
       replace(MembrIn,M_i,m(nil2,*{b\M_i1}),MembrOut)!.

rule(3,MembrIn,MembrOut) :-
       choose(MembrIn,nil2,M_i,M_j) &
       M_i = m(nil2,*{b,b\M_i1}) &
       replace(MembrIn,M_i,m(nil2,*{b\M_i1}),MembrInt)! &
       MembrInt = m(K,MembrInt1) &
       replace(MembrIn,M_j,m(K,*{b,b\MembrInt1}),MembrOut)!.

rule(4,MembrIn,MembrOut) :-
       choose(MembrIn,nil2,M_i,M_j) &
       M_i = m(nil2,*{b\M_i1}) &
       M_j = m(K,*{M_i\MembrInt}) &  %% \delta removes M_i from M_j
       replace(MembrIn,M_j,m(K,*{b\MembrInt}),MembrOut)!.


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

start :- 
   nl & 
   write('A P system computing the function n^2') & nl &
   write('Give the goal: ') & nl &
   write('p_interpreter(m(nil1,*{ m(nil2,*{a,b,...,b}) }),MembrOut).') & nl &
   write('                        or                                ') & nl &
   write('p_interpreter2(m(nil1,*{ m(nil2,*{a,b,...,b}) }),MembrOut).') & nl &
   write('(n occurrences of b) to compute n^2:') & nl & 
   write('the resulting outer membrane MembrOut will contain n^2 occurrences of b') & nl &
   write('e.g.,') & nl & 
   write('   {log}=> p_interpreter( m(nil1,*{ m(nil2,*{a,b,b,b}) }),MembrOut ).') & nl &
   write('   MembrOut = m(nil1,*{b,b,b,b,b,b,b,b,b})') & nl &
   nl.