VI. Metainterpretation zur Steuerung der Auswertung
- Letztes Literal auswählen
- Selektionsfunktion
- Fortschreitende Tiefensuche
- Breitensuche
- Verfolgung der Auswertung (trace)
© 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_variables
ist ein Systemprädikat des PROLOG-Systems Eclipse, das die Liste aller ungebundenen Variablen liefert, die in einem Term vorkommen.