%% Version: 1.0 - Date: 11 June 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 evaluated result; 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 - successor %% % k(F,[G1,..,Gn]) - composition of F and G1,..,Gn %% % pr(F,G) - primitive recursion %% % mu(F) - mu-operator applied to 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 defined 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(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).