voriges Kapitel | Startseite | Inhalt | nächstes Kapitel

© 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.


VI. Metainterpretation zur Steuerung der Auswertung

  1. Letztes Literal auswählen
  2. Selektionsfunktion
  3. Fortschreitende Tiefensuche
  4. Breitensuche
  5. Verfolgung der Auswertung (trace)
Die Metainterpretation ermöglicht, PROLOG-Programme in einer Weise auszuwerten, die von der herkömmlichen PROLOG-Auswertung abweicht.

P53 wertet Objektprogramme so aus, daß Konjunktionen von rechts nach links ausgewertet werden
Die folgende Sitzung bezieht sich auf Programm P53:
:- 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. :-
Die folgende Sitzung bezieht sich auf Programm P55:
:- 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. :-

3. Fortschreitende Tiefensuche

Die herkömmliche Auswertung der Anfrage terminiert nicht, weil stets zunächst die erste Klausel für 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) > ...
Die fortschreitende Tiefensuche (iterative deepening) bezeichnet eine bis zu einer Auswertungstiefe T begrenzte Auswertung, mit steigenden Werte für T. Das folgende Programm begrenzt die Auswertung bis zur Tiefe T:
Die folgende Sitzung bezieht sich auf Programm P57:
:- 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.
Die folgende Sitzung bezieht sich auf Programm P58:
:- 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. :-

zum Seitenanfang

4. Breitensuche

ä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.

Die folgende Sitzung bezieht sich auf Programm P59:
:- %%% 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.

zum Seitenanfang
P59
Die folgende Sitzung bezieht sich auf Programm P59:
:- %%% 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.
voriges Kapitel | Startseite | Inhalt | nächstes Kapitel

Letzte änderung: 18. August 1998

Valid 
	     XHTML 1.0!