%% Version:  1.0  -  Date: 7 May 2007  -  File: murek.pl
%%
%% Purpose: Evaluating mu-Recursive Expressions
%%
%% Author:  Jens Otten
%%
%% Usage:   rek(E,X,Y).
%%          % where E is a mu-recursive expression, X is a list
%%          % of arguments and Y is the result returned; the
%%          % expression E is made up of the following terms:
%%          % (N,K are natural numbers; F,G are mu-expressions)
%%          %  c(N,K)          - constant K for N arguments
%%          %  p(N,K)          - returns K-th of N arguments
%%          %  s(K)            - successor of K
%%          %  k(F,[G1,..,Gn]) - composition of F and G1,..,Gn
%%          %  pr(F,G)         - primitive recursion
%%          %  mu(F)           - mu-operator applied on F
%%          %  mu(F,G)         - G is limit for mu-operator on F
%%          %
%%          % Example: [murek].
%%          %          rek( pr(p(1,1),k(s,[p(3,3)])), [3,5], Y).
%%          %          rek(add,[3,5],Y).  % add is defined below
%%          %
%%          % Loads program and evaluates the given mu-recursive
%%          % expression, e.g. the sum of 3 and 5 is returned
%%
%% License: GPL

%% These are some examples of mu-recursive expressions; once
%% they are defnined they can be used within other expressions

rek(add,[A,B],Y) :- rek( pr(p(1,1),k(s,[p(3,3)])) ,[A,B],Y).
rek(mul,[A,B],Y) :- rek( pr(c(1,0),k(add,[p(3,1),p(3,3)])) ,[A,B],Y).
rek(p,[A],Y)     :- rek( pr(c(0,0),p(2,1)),[A],Y).  % predecessor
rek(mi,[A,B],Y)  :- rek( pr(p(1,1),k(p,[p(3,3)])), [A,B],Y).  % minus
rek(fakul,[A],Y) :- rek( pr(c(0,1),k(mul,[k(s,[p(2,1)]),p(2,2)])), [A],Y).
rek(div,[A,B],Y) :- rek( k(k(mi,[pr(c(1,1),k(add,[p(3,3),k(mi,[k(add,[p(3,2),
    c(3,2)]),k(mul,[p(3,1),p(3,3)])])])),c(2,1)]),[p(2,2),p(2,1)]), [A,B],Y).
rek(dv2,[A,B],Y) :- rek( mu(k(mi,[k(add,[p(3,1),c(3,1)]),k(mul,[p(3,2),k(add,
    [p(3,3),c(3,1)])])]),p(2,1)), [A,B], Y).  % div using limited mu-operator

%% Do not change anything below this line except you know
%% what you are actually doing ...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
rek(c(N,K),X,K)  :- length(X,N).
rek(p(N,K),X,Y)  :- length(X,N), append(X1,[Y|_],X), length([Y|X1],K).
rek(s,[X],Y)     :- Y is X+1.
rek(k(F,G),X,Y)  :- kom(G,X,YG), rek(F,YG,Y).
rek(pr(F,_),X,Y) :- append(X1,[0],X), rek(F,X1,Y).
rek(pr(F,G),X,Y) :- append(X1,[Z],X), Z>0, Z1 is Z-1, append(X1,[Z1],X2),
                    rek(pr(F,G),X2,Y1), append(X2,[Y1],X3), rek(G,X3,Y).
rek(mu(F),X,Y)   :- min(F,X,[0],!,Y).
rek(mu(F,G),X,Y) :- rek(G,X,T), min(F,X,[0],T,Y).
kom([],_,[]).
kom([G1|G],X,[Y1|Y]) :- rek(G1,X,Y1), kom(G,X,Y).
min(F,X,[Z],_,Z) :- append(X,[Z],X1), rek(F,X1,0), !.
min(F,X,[Z],T,Y) :- Z=T -> Y is Z+1 ; Z1 is Z+1, min(F,X,[Z1],T,Y).