Direkt zum Inhalt | Direkt zur Navigation

Sektionen
Benutzerspezifische Werkzeuge
Sie sind hier: Startseite Willkommen Professuren Ordentliche Professuren Theoretische Informatik Lehrveranstaltungen Sommersemester 2013 Theoretische Informatik II Downloads Prolog-Programm zur Auswertung mu-rekursiver Ausdruecke

Prolog-Programm zur Auswertung mu-rekursiver Ausdruecke

Ein in Prolog geschriebenes Programm zur Auswertung mu-rekursiver Ausdrücke, Autor: Jens Otten. Benötigt zur Ausführung ein Prolog-System, z.B. SWI Prolog (http://www.swi-prolog.org/).

murek.pl — text/x-perl, 2Kb

Dateiinhalt

%% 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).
Artikelaktionen
Auf einen Blick
Lehrform diverse Formen
Empfohlen ab FS 0
Voraussetzungen Erfolgreiche Teilnahme an Theoretische Informatik I ist sehr zu empfehlen.
Benotet Ja
Punkte gesamt 6
davon praktisch 0
Sprache deutsch
Fremdhörer zugelassen? Nein
Teilgebiete Theoretische Informatik(2000), Wahlfrei(7000)
Studiengang Bachelor
Belegung via PULS