© 2001
François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung
angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht oder eine
Veröffentlichung von Kopien oder Übersetzungen) dieses Lehrmaterials
bedarf der Erlaubnis des Autors.
demo(true) :- !.
demo( (X,Y) ) :- !, demo(Y), demo(X).
demo(not X) :- !, not demo(X).
demo(X) :- system(X), !, X.
demo(X) :- clause(X, Rumpf), demo(Rumpf).
system(_ = _).
:- dynamic(spricht_eine_fremdsprache/1), dynamic(fremdsprache/1),
dynamic(spricht/2).
:- [user}.
spricht_eine_fremdsprache(X) :- fremdsprache(S), spricht(X, S).
fremdsprache(S) :- not S = deutsch.
spricht(francois, franzoesisch).
yes.
:- spricht_eine_fremdsprache(X).
no (more) solution.
:- demo(spricht_eine_fremdsprache(X)).
X = francois
yes.
:-
demo(true) :- !.
demo( (X,Y) ) :- !, select(Literal, (X,Y), Rest),
demo(Literal), demo(Rest).
demo(not X) :- !, not demo(X).
demo(X) :- clause(X, Rumpf), demo(Rumpf).
select(Lit, (not L, Ausdr), Rest) :- enthaelt_variablen(L), !,
select(Lit, Ausdr, R),
und(not L, R, Rest).
select(Lit, (Lit, Rest), Rest) :- !.
select(Lit, Lit, true).
und(X, true, X) :- !.
und(X, Y, (X, Y)).
enthaelt_variablen(A) :- term_variables(A, L), not L = [].
:- select(Lit, (p, q, r), Rest).
Lit = p
Rest = q, r
yes.
:- select(Lit, (not p(a), q(X), r(X)), Rest).
X = X
Lit = not p(a)
Rest = q(X), r(X)
yes.
:- select(Lit, (not p(X), q(X), r(X)), Rest).
X = X
Lit = q(X)
Rest = not p(X), r(X)
yes.
:- select(Lit, (not p(X), not q(X)), Rest).
X = X
Lit = not q(X)
Rest = not p(X)
yes.
:-
:- t(1,K). für das folgende Programm:
t und das erste Literal ihres Rumpfes
bearbeitet werden:
< t(1,K) >
< t(1,C'), r(C',K) >
< t(1,C''), t(C'',C'), r(C',K) >
< t(1,C'''), t(C''',C''), t(C'',C'), r(C',K) >
...
T begrenzte Auswertung, mit steigenden
Werte für T. Das folgende Programm begrenzt die Auswertung bis zur
Tiefe T:
:- dynamic(r/2), dynamic(t/2).
yes.
:- [user].
r(1, 2).
r(2, 3).
r(3, 4).
t(A, B) :- t(A, C), t(C, B).
t(A, B) :- r(A, B).
yes.
:- I = 1, setof(t(1,K), demo(t(1,K), I), L).
K = K
I = 1
L = [t(1, 2)]
yes.
:- I = 2, setof(t(1,K), demo(t(1,K), I), L).
K = K
I = 2
L = [t(1, 2), t(1, 3)]
yes.
:- I = 3, setof(t(1,K), demo(t(1,K), I), L).
K = K
I = 3
L = [t(1, 2), t(1, 3), t(1, 4)]
yes.
:- I = 4, setof(t(1,K), demo(t(1,K), I), L).
K = K
I = 4
L = [t(1, 2), t(1, 3), t(1, 4)]
yes.
:- dynamic(r/2), dynamic(t/2).
yes.
:- [user].
r(1, 2).
r(2, 3).
r(3, 4).
t(A, B) :- t(A, C), t(C, B).
t(A, B) :- r(A, B).
yes.
:- iterative_deepening( t(1,K) ).
Tiefe 1
[t(1, 2)]
weiter (ja/nein)? ja.
Tiefe 2
[t(1, 2), t(1, 3)]
weiter (ja/nein)? ja.
Tiefe 3
[t(1, 2), t(1, 3), t(1, 4)]
weiter (ja/nein)? ja.
Tiefe 4
[t(1, 2), t(1, 3), t(1, 4)]
weiter (ja/nein)? nein.
no (more) solution.
:-
demo(A) :- breitensuche([(A :- A)], 0).
breitensuche([], _) :- !.
breitensuche(L1, T) :-
write("Tiefe "), write(T), nl,
loesungen(L1, Geloest, L2), ausgabe(Geloest),
write("weiter (ja/nein)?"), read(Antwort), Antwort == ja,
alle_expandieren(L2, L3), Tplus1 is T + 1, breitensuche(L3, Tplus1).
alle_expandieren(L1, L2) :-
findall((A :- Anfragen),
(member((A :- R), L1), expandieren(R, Anfragen)),
L2).
expandieren((X,Y), Anfragen) :-
!, clause(X, RumpfX), expandieren(Y, AnfragenY),
und_verknuepfen(RumpfX, AnfragenY, Anfragen).
expandieren(X, Anfragen) :- clause(X, Anfragen).
und_verknuepfen(true, X, X ) :- !.
und_verknuepfen(X, true, X ) :- !.
und_verknuepfen((X,Y), Z, (X,YZ)) :- !, und_verknuepfen(Y, Z, YZ).
und_verknuepfen(X, Y, (X, Y)).
loesungen([], [], []).
loesungen([(A :- true)|Rest], [A|Geloest], Ungeloest) :-
!, loesungen(Rest, Geloest, Ungeloest).
loesungen([(A :- R)|Rest], Geloest, [(A :- R)|Ungeloest]) :-
loesungen(Rest, Geloest, Ungeloest).
ausgabe([]).
ausgabe([K|R]) :- write(" "), write(K), nl, ausgabe(R).
ähnlich wie im Programm
P58 implementiert
breitensuche eine Treiberschleife mit einem Argument für die
Auswertungstiefe. Das erste Argument von breitensuche ist eine
Liste von "Begründungen" der Form A :- Anfragen. Dabei ist
A eine Kopie der ursprünglichen Anfrage mit möglicherweise schon
gebundenen Variablen. Die "Begründung" repräsentiert die Information, daß
A bereits auf Anfragen zurückgeführt wurde und jede
Möglichkeit, Anfragen mit Hilfe der Klauseln des Objektprogramms
nach true zu transformieren, eine Lösung für A
ergibt. Das Symbol :- in der "Begründung" wurde aus
Bequemlichkeitsgründen benutzt. Man beachte, daß A auch eine
Konjunktion sein kann.
Das Prädikat loesungen zerlegt eine Liste von solchen
"Begründungen" in die Liste der gelösten, deren Anfragen bereits
true sind, und die Liste der ungelösten.
expandieren berechnet aus einer (atomaren oder konjunktiven)
Anfrage alle Anfragen, die man bilden kann, indem man jedes Atom der
gegebenen Anfrage durch den Rumpf einer passenden Klausel des Objektprogramms
ersetzt. alle_expandieren führt dies für alle Anfragen einer
Liste von "Begründungen" durch. In der Liste, die durch den Aufruf von
findall erzeugt wird, haben die Kopfatome keine gemeinsamen
Variablen. Dies ist ein Nebeneffekt der Variablenumbenennung, oder
standardization apart, die in PROLOG-Systemen eingebaut ist und durch den
Aufruf von expandieren erfolgt.
:- %%% kante verbunden gerade ungerade
dynamic(k/2), dynamic(v/2), dynamic(g/1), dynamic(u/1).
yes.
:- [user].
k(1,2).
k(2,3).
k(3,4).
v(A,B) :- v(A,C), k(C,B).
v(A,B) :- k(A,B).
g(2).
g(4).
u(A) :- k(A,B), g(B).
yes.
:- expandieren( (u(X), v(X,Y)), Anfragen ).
X = X
Y = Y
Anfragen = k(X,B), g(B), v(X,C), k(C,Y) More? (;) ;
X = X
Y = Y
Anfragen = k(X,B), g(B), k(X,Y)
yes.
:- set_flag(output_mode, "QPmV"),
alle_expandieren( [ (v(X,Y) :- v(X,Y)) ], L ).
X = X_g218
Y = Y_g208
L = [v(X_g328, Y_g330) :- (v(X_g328, C_g344), k(C_g344, Y_g330)),
v(X_g368, Y_g370) :- k(X_g368, Y_g370)]
yes.
:- set_flag(output_mode, "QPm"),
L0 = [ (u(X), v(X,Y)) :- (u(X), v(X,Y)) ],
alle_expandieren(L0, L1), alle_expandieren(L1, L2).
L0 = [(u(X), v(X,Y)) :- (u(X), v(X,Y))]
L1 = [(u(X), v(X,Y)) :- (k(X,B), g(B), v(X,C), k(C,Y)),
(u(X), v(X,Y)) :- (k(X,B), g(B), k(X,Y)) ]
L2 = [(u(1), v(1,2)) :- (v(1,C), k(C,1)),
(u(1), v(1,3)) :- (v(1,C), k(C,2)),
(u(1), v(1,4)) :- (v(1,C), k(C,3)),
(u(1), v(1,2)) :- k(1,1),
(u(1), v(1,3)) :- k(1,2),
(u(1), v(1,4)) :- k(1,3),
(u(3), v(3,2)) :- (v(3,C), k(C,1)),
(u(3), v(3,3)) :- (v(3,C), k(C,2)),
(u(3), v(3,4)) :- (v(3,C), k(C,3)),
(u(3), v(3,2)) :- k(3,1),
(u(3), v(3,3)) :- k(3,2),
(u(3), v(3,4)) :- k(3,3),
(u(1), v(1,2)) :- true,
(u(3), v(3,4)) :- true ]
yes.
:- demo(true).
Tiefe 0
true
weiter (ja/nein)? ja.
yes.
:- demo( (u(X), v(X,Y)) ).
Tiefe 0
weiter (ja/nein)? ja.
Tiefe 1
weiter (ja/nein)? ja.
Tiefe 2
u(1), v(1, 2)
u(3), v(3, 4)
weiter (ja/nein)? ja.
Tiefe 3
u(1), v(1, 3)
weiter (ja/nein)? ja.
Tiefe 4
u(1), v(1, 4)
weiter (ja/nein)? ja.
X = X
Y = Y
yes.
Letzte änderung: 18. August 1998
term_variablesist ein Systemprädikat des PROLOG-Systems Eclipse, das die Liste aller ungebundenen Variablen liefert, die in einem Term vorkommen.