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.

VII. Vorwärtsschließen

  1. Zwei grundlegende vorwärtsauswertende Interpretierer
  2. Vorwärtsschließen ohne Nebeneffekte
  3. Erweiterung auf nichtbereichsbeschränkte Fakten und Regeln
  4. Inkrementelles Vorwärtsschließen
  5. Weitere Optimierungen
  6. Vorwärtsausgewertete Regeln als Metainterpretationssprache

1. Zwei grundlegende vorwärtsauswertende Interpretierer

Die Metainterpretierer der Kapitel 5 und 6 implementieren verschiedenen Formen des Rückwartsschließens. In diesem Kapitel wird die Technik der Metainterpretation angewendet, um verschiedene Formen des Vorwärtsschließens zu implementieren.
Zwei Sprachen werden also verwendet:
  • Die umgebende Sprache oder Metasprache PROLOG, um die vorwärtsschließenden Metainterpretierer zu implementieren.
  • Die eingebettete Sprache oder Objektsprache der Fakten und Regeln, womit vorwärts geschlossen wird.
Darstellung der eingebetteten "Vorwärtssprache":
  • Fakten: dargestellt als PROLOG-Fakten, zum Beispiel:
    p. q(a).
  • Regeln: dargestellt in wenn-dann-Form von links nach rechts, zum Beispiel:
    p(X), q(X) ---> r(X).
    Dabei ist ---> ein spezielles zweistelliges Relationssymbol, das in Infixform geschrieben wird. In Präfixform lautet die obige Regel also
    --->( (p(X),q(X)), r(X) ).
    Man beachte, daß diese Regeln aus PROLOG-Sicht ebenfalls als Fakten dargestellt sind. Das Zeichen ---> wird wie folgt deklariert:
    :- op(1200, xfx, --->).
    Man könnte die Regeln auch als PROLOG-Regeln mit dem Zeichen :- darstellen, aber für das Vorwärtsschließen ist die wenn-dann-Form von links nach rechts intuitiver.
In diesem Abschnitt werden bereichsbeschränkte und negationsfreie Fakten und Regeln angenommen. Eine negationsfreie Regel heißt bereichsbeschränkt, wenn jede Variable, die im Regelkopf vorkommt, auch im Regelrumpf vorkommt. Analog heißt ein Faktum bereichsbeschränkt, wenn es gar keine Variablen enthält. Variablenfreie Fakten nennt man auch Grundfakten.
Programm P60 wertet die Objektsprache vorwärts aus. Es benutzt die PROLOG-Datenbank zur Speicherung der Faktenmenge und fügt jedes Faktum in die Faktenmenge hinzu, sobald es hergeleitet wird:
60
:- op(1200, xfx, --->). vorwaerts :- (Rumpf ---> Kopf), Rumpf, not Kopf, !, assert(Kopf), vorwaerts. vorwaerts.
Dieses Programm setzt voraus, daß alle Relationssymbole, die in Köpfen von Vorwärtsregeln vorkommen, als dynamisch deklariert werden. Die folgende Sitzung bezieht sich auf Programm P60:
:dynamic(t/2). yes. :- [user]. r(1, 2). r(2, 3). r(3, 1). t(X, Y), t(Y, Z) ---> t(X, Z). r(X, Y) ---> t(X, Y). yes. listing(t/2). yes. :- vorwaerts. yes. :- listing(t/2). t(1, 2). t(2, 3). t(1, 3). t(3, 1). t(2, 1). t(1, 1). t(3, 2). t(2, 2). t(3, 3). yes.
Um die Arbeitsweise des Programms P60 genau zu verstehen, ist es nützlich, nachzuvollziehen, in welchen Fällen welche der beiden Klauseln von vorwaerts verwendet wird und warum die t-Fakten genau in der obigen Reihenfolge hergeleitet worden sind.
Programm P61 ist eine mengenorientierte Version von Programm P60: zunächst werden alle neuen herleitbaren Fakten berechnet, bevor sie in die Datenbank hinzugefügt werden.
61
vorwaerts_menge :- setof(Kopf, Rumpf^( (Rumpf ---> Kopf), Rumpf, not Kopf ), Menge), assert_all(Menge), vorwaerts_menge. vorwaerts_menge. assert_all([]). assert_all([H | T]) :- assert(H), assert_all(T).
Man beachte die existentielle Quantifikation der Variablen Rumpf in der Anfrage des Aufrufes von setof. Sie ist notwendig, damit alle Köpfe ermittelt werden, die sich aus verschiedenen Bindungen der Rümpfe ergeben. Ohne die existentielle Quantifizierung von Rumpf würde der Aufruf von setof nur Bindungen von Kopf für eine einzige Bindung von Rumpf ergeben.
Da assert vom Rücksetzen nicht beeinflußt wird, ist es verlockend, das Vorwärtsschließen mit einer scheitern-getriebenen Schleife wie folgt zu implementieren:
62
% Vorsicht: inkorrektes Programm! vorwaerts :- (Rumpf ---> Kopf), Rumpf, not Kopf, assert(Kopf), fail. vorwaerts.
Die folgende Sitzung zeigt, daß Programm P62 inkorrekt ist:
:- dynamic(t/2). yes. :- [user]. r(1, 2). r(2, 3). r(3, 1). t(X, Y), t(Y, Z) ---> t(X, Z). r(X, Y) ---> t(X, Y). yes. :- vorwaerts. yes. :- t(X, Y). X = 1 Y = 2 More? (;) ; X = 2 Y = 3 More? (;) ; X = 3 Y = 1 yes.
Nicht alle herleitbaren t-Fakten sind generiert worden. Der Grund liegt in der Verwaltung der Rücksetzpunkte in PROLOG. Diese Verwaltung nimmt die neuen Rücksetzpunkte nicht notwendigerweise wahr, die während der Auswertung entstehen können. Das ist hier der Fall: die hinzugefügten t-Fakten können verwendet werden, um mit der ersten Vorwärtsregel neue Fakten zu erzeugen. Da aber das PROLOG-System die neuen Rücksetzpunkte nicht wahrnimmt, geschieht dies nicht.
Hierbei handelt es sich um eine wichtige Eigenschaft von PROLOG, die leicht übersehen werden kann.
Der Zeitbedarf von Metainterpretierer P60 im Falle des Objektprogramms
p(a1). p(a2). . . . p(an). p(X) ---> q(X).
kann wie folgt geschätzt werden: Die Relation p wird beim 1. Mal durchsucht bis zu p(a1), dann ein 2. Mal bis zu p(a2), ..., schließlich zum n. Mal bis zu p(an). Insgesamt werden also 1 + 2 + ... + n = n * (n+1)/2 Fakten mit dem Regelrumpf verglichen, obwohl nur n neue Fakten hergeleitet werden können. Das Verfahren hat quadratischen Aufwand O(n**2) in der Zahl der herleitbaren Fakten.
Die Programme P60 und P61 terminieren natürlich nicht, wenn die Menge der herleitbaren Fakten unendlich ist.
Dies ist der Fall zum Beispiel mit dem folgenden Objektprogramm:
p(a). p(X) ---> p(f(X)). p(X) ---> p(g(X)).
Ein wesentlicher Unterschied zwischen Programm P60 und Programm P61 ist, daß das zweite erschöpfend ist, d.h. jedes herleitbare Faktum wird in endlicher Zeit generiert. Das vorangehende Beispiel zeigt, daß Programm P60 nicht erschöpfend ist: es generiert kein Faktum, in dem das Funktionssymbol g vorkommt.
Eine interessante Eigenschaft der Programme P60 und P61 ist, daß sie immer terminieren, wenn die Menge der herleitbaren Fakten endlich ist, auch dann, wenn das Objektprogramm rekursiv ist. Dies ist zum Beispiel der Fall mit dem Objektprogramm:
r(1, 2). r(2, 3). r(3, 1). t(X, Y), t(Y, Z) ---> t(X, Z). r(X, Y) ---> t(X, Y).
Das Rückwärtsschließen von PROLOG hat diese Terminierungseigenschaft nicht: wird zum Beispiel die Anfrage t(1, V). gegenüber dem vorangehenden Beispiel ausgewertet, dann terminiert die Auswertung nicht, obwohl es nur endlich viele Antworten gibt.
Das folgende Programm ergänzt Programm P61 mit einem "trace":
63
vorwaerts_trace :- setof(Kopf, Rumpf^( (Rumpf ---> Kopf), Rumpf, not Kopf ), Menge), assert_all(Menge), ausgabe(Menge), vorwaerts_trace. vorwaerts_trace. assert_all([]). assert_all([H | T]) :- assert(H), assert_all(T). ausgabe(Menge) :- runde(N), nl, write(N), write(". Runde:"), nl, write_all(Menge). write_all([]). write_all([H | T]) :- write(" "), write(H), nl, write_all(T). :- dynamic(rundenzaehler/1). rundenzaehler(1). runde(N) :- retract( rundenzaehler(N) ), Nplus1 is N + 1, assert( rundenzaehler(Nplus1) ).
Die folgende Sitzung bezieht sich auf Programm P63:
:- dynamic(t/2). yes. :- [user]. r(1, 2). r(2, 3). r(3, 1). t(X, Y), t(Y, Z) ---> t(X, Z). r(X, Y) ---> t(X, Y). yes. :- vorwaerts_trace. 1. Runde: t(1, 2) t(2, 3) t(3, 1) 2. Runde: t(1, 3) t(2, 1) t(3, 2) 3. Runde: t(1, 1) t(2, 2) t(3, 3) yes.

zum Seitenanfang

P60 wertet die Objektsprache vorwärts aus.

Die folgende Sitzung bezieht sich auf Programm P60:

:dynamic(t/2). yes. :- [user]. r(1, 2). r(2, 3). r(3, 1). t(X, Y), t(Y, Z) ---> t(X, Z). r(X, Y) ---> t(X, Y).
P61 ist eine mengenorientierte Version von Programm P60.
Programm P62 implementiert das Vorwärtsschließen mit einer scheitern-getriebenen Schleife. Die folgende Sitzung zeigt, daß P62 inkorrekt ist:
:- dynamic(t/2). yes. :- [user]. r(1, 2). r(2, 3). r(3, 1). t(X, Y), t(Y, Z) ---> t(X, Z). r(X, Y) ---> t(X, Y). yes. :- vorwaerts. yes.
P60 im Falle des Objektprogramms
p(a1). p(a2). . . . p(an). p(X) ---> q(X).

P60 und P61 terminieren natürlich nicht, wenn die Menge der herleitbaren Fakten unendlich ist. Wie z.B.
p(a). p(X) ---> p(f(X)). p(X) ---> p(g(X)).
Der Unterschied zwischen Programm P60 und Programm P61 ist, daß das zweite erschöpfend ist.
Sie terminieren immer wenn sie endlich sind, auch wenn das Objektprogramm rekursiv ist, wie z.B.:
r(1, 2). r(2, 3). r(3, 1). t(X, Y), t(Y, Z) ---> t(X, Z). r(X, Y) ---> t(X, Y).
Das Programm P63 ergänzt Programm P61 mit einem "trace".

2. Vorwärtsschließen ohne Nebeneffekte

Die Interpretierer des vorangehenden Abschnitts speichern hergeleitete Fakten in der Prolog-Datenbank, die sie mit assert verändern. Die Akkumulator-Technik bietet eine Alternative ohne solche Nebeneffekte.
64
:- op(1200, xfx, --->). vorwaerts(HerleitbareFakten) :- vorwaerts([true], HerleitbareFakten). vorwaerts(Fakten, Ergebnis) :- (Rumpf ---> Kopf), auswerten(Rumpf, Fakten), not auswerten(Kopf, Fakten), !, vorwaerts([Kopf|Fakten], Ergebnis). vorwaerts(Fakten, Fakten). auswerten( (A,B), M) :- !, auswerten(A, M), auswerten(B, M). auswerten( A, M) :- member(A, M).
Beim Aufruf ist das Argument von vorwaerts/1 normalerweise eine Variable, die dann an die Liste aller herleitbaren Fakten gebunden wird. Das erste Argument von vorwaerts/2 ist der Akkumulator. Er muß eigentlich mit der Menge aller Fakten des Objektprogramms initialisiert werden. Zur Vereinfachung wurde angenommen, daß die Fakten des Objektprogramms als Regeln der Gestalt true ---> F dargestellt sind. Deshalb konnte als Initialwert einfach [true] verwendet werden...

Die hergeleiteten Fakten werden nicht in der PROLOG-Datenbank gespeichert, sondern in dem Akkumulator. Der Preis dafür ist, daß die Auswertung der Regelrümpfe und -köpfe gegenüber einer Menge von Fakten nun implementiert werden muß. Ansonsten unterscheidet sich das Programm P64 kaum vom Programm P60.


zum Seitenanfang
P64

3. Erweiterung auf nichtbereichsbeschränkte Fakten und Regeln

Betrachten wir das folgende Objektprogramm:
r(a, V). r(W, a). t(X, Y), t(Y, Z) ---> t(X, Z). r(X, Y) ---> t(X, Y).
Man erwartet, daß unter Anwendung der zweiten Regel zunächst t(a, V). t(W, a). und dann unter Anwendung der ersten Regel t(W, V). hergeleitet wird, nämlich aus t(X, Y), t(Y, Z) ---> t(X, Z). W a a V W V
Dies geschieht mit den Interpretierern P60, P61, P63 oder P64 nicht. Der Aufruf not t(W,V) scheitert wegen den Fakten t(a,V) und t(W,a). Das Problem ist, daß dieser Aufruf erzwingt, daß das zuletzt generierte Faktum mit keinem zuvor generierten Faktum unifiziert werden kann. Offenbar ist dies im Falle von nichtbereichsbeschränkten Fakten und Regeln zu stark. Es sollte lediglich sichergestellt werden, daß das zuletzt generierte Faktum keine Instanz eines zuvor generierten Faktum ist.
Der folgende Metainterpretierer leistet dies:
65
vorwaerts :- (Rumpf ---> Kopf), Rumpf, not (faktum(F), instance(Kopf,F)), !, assert(Kopf), vorwaerts. vorwaerts. faktum(F) :- (_ ---> F), clause(F, true).
Die Anfrage clause(F, true) ist für alle PROLOG-Fakten erfolgreich, also nicht nur für diejenigen PROLOG-Fakten, die Fakten des Objektprogramms repräsentieren. Die Anfrage (_ ---> F) schränkt deshalb die Fakten ein auf solche, die mit Regelköpfen des Objektprogramms unifizierbar sind.
Der folgende Metainterpretierer ist eine mengenorientierte Version mit "trace" des Programms P65.
66
vorwaerts_trace :- coverof(Kopf, Rumpf^F^( (Rumpf ---> Kopf), Rumpf, not (faktum(F), instance(Kopf,F)) ), Menge), assert_all(Menge), ausgabe(Menge), vorwaerts_trace. vorwaerts_trace. faktum(F) :- (_ ---> F), clause(F, true). assert_all([]). assert_all([H | T]) :- assert(H), assert_all(T). ausgabe(Menge) :- runde(N), nl, write(N), write(". Runde:"), nl, write_all(Menge). write_all([]). write_all([H | T]) :- write(" "), write(H), nl, write_all(T). :- dynamic(rundenzaehler/1). rundenzaehler(1). runde(N) :- retract( rundenzaehler(N) ), Nplus1 is N + 1, assert( rundenzaehler(Nplus1) ).
Die folgende Sitzung zeigt, wie sich das Programm P66 mit dem oben erwähnten Objektprogramm verhält:
:- dynamic(r/2), dynamic(t/2). yes. :- [user]. r(a, _). r(_, a). t(X, Y), t(Y, Z) ---> t(X, Z). r(X, Y) ---> t(X, Y). yes. :- vorwaerts_trace. 1. Runde: t(a, Y) t(X, a) 2. Runde: t(X, Z) yes.

zum Seitenanfang
P60, P61, P63 oder P64 nicht.

Bei dem Programm P65 ist das zuletzt generierte Faktum keine Instanz eines zuvor generierten Faktum. leistet dies.

Das Programm P66 ist eine mengenorientierte Version mit "trace" des Programms P65.

P66 mit dem oben erwähnten Objektprogramm verhält:
:- dynamic(r/2), dynamic(t/2). yes. :- [user]. r(a, _). r(_, a). t(X, Y), t(Y, Z) ---> t(X, Z). r(X, Y) ---> t(X, Y). yes. :- vorwaerts_trace. 1. Runde: t(a, Y) t(X, a) 2. Runde: t(X, Z) yes.

4. Inkrementelles Vorwärtsschließen

Betrachten wir das Programm P60. Wie die Abschätzung des Zeitbedarfs gezeigt hat, kann es zu redundanten Auswertungen eines Regelrumpfes kommen, die nicht zur Herleitung von neuen Fakten beitragen. Das ist dann der Fall, wenn sich die Auswertung des Regelrumpfes nicht auf wenigstens eines der zuletzt hergeleiteten Fakten bezieht.
Die folgende Sitzung illustriert diese Redundanz:
:- dynamic(p/1). yes. :- [user]. p(a). p(a) ---> p(b). p(a) ---> p(c). p(b), p(d) ---> p(e). yes. :- (Rumpf ---> Kopf), Rumpf, not Kopf, !, assert(Kopf). Rumpf = p(a) Kopf = p(b) yes. :- (Rumpf ---> Kopf), Rumpf, not Kopf, !, assert(Kopf). Rumpf = p(a) Kopf = p(c) yes. :- (Rumpf ---> Kopf), Rumpf. Rumpf = p(a) Kopf = p(b) More? (;) ; Rumpf = p(a) Kopf = p(c) More? (;) ; no (more) solutions.
Die letzte Anfrage zeigt, womit die nächste Runde beginnen würde. Die beiden Regeln mit p(a) im Rumpf werden wieder ausgewertet, obwohl sie nichts neues erzeugen können. Durch den nachfolgenden Test not Kopf, also not p(b) bzw. not p(c), würde dies zwar erkannt, aber die redundante Auswertung des Regelrumpfes wäre dann bereits geschehen.
Es ist sinnvoll, die Herleitungen auf neue Beweise einzuschränken. Das sind solche, die mindestens ein neues Faktum, d. h. zuletzt hergeleitetes Faktum, verwenden. Das Programm P67 leistet dies für bereichsbeschränkte Fakten und Regeln:
67
vorwaerts :- setof(Kopf, Rumpf^( (Rumpf ---> Kopf), Rumpf, not Kopf ), Menge), assert_all(Menge), vorwaerts(Menge). vorwaerts(Inkrement) :- setof(Kopf, Rumpf^( (Rumpf ---> Kopf), neu_beweisbar(Rumpf, Inkrement), not Kopf ), Menge), assert_all(Menge), vorwaerts(Menge). vorwaerts(_). assert_all([]). assert_all([H | T]) :- assert(H), assert_all(T). neu_beweisbar(Ausdruck, Menge) :- conjunct_rest(Fakt, Rest, Ausdruck), member(Fakt, Menge), Rest. conjunct_rest(C, R, (C,R) ). conjunct_rest(C, (X,R), (X,Y,Z)) :- !, conjunct_rest(C, R, (Y,Z)). conjunct_rest(C, R, (R,C) ) :- !. conjunct_rest(C, true, C ).
Das Programm P68 ist die Anpassung von P67 auf Fakten und Regeln, die nicht notwendigerweise bereichsbeschränkt sind:
68
vorwaerts :- coverof(Kopf, Rumpf^F^( Rumpf ---> Kopf), Rumpf, not (faktum(F), instance(Kopf,F)) ), Menge), assert_all(Menge), vorwaerts(Menge). vorwaerts(Inkrement) :- coverof(Kopf, Rumpf^F^( Rumpf ---> Kopf), neu_beweisbar(Rumpf, Inkrement), not (faktum(F), instance(Kopf,F)) ), Menge), assert_all(Menge), vorwaerts(Menge). vorwaerts(_). faktum(F) :- (_ ---> F), clause(F, true). assert_all([]). assert_all([H | T]) :- assert(H), assert_all(T). neu_beweisbar(Ausdruck, Menge) :- conjunct_rest(Fakt, Rest, Ausdruck), member(Fakt, Menge), Rest. conjunct_rest(C, R, (C,R) ). conjunct_rest(C, (X,R), (X,Y,Z)) :- !, conjunct_rest(C, R, (Y,Z)). conjunct_rest(C, R, (R,C) ) :- !. conjunct_rest(C, true, C ).
Die Programme P67 und P68 sind mengenorientiert: bei jedem rekursiven Aufruf werden alle Fakten ermittelt und in die Datenbank hinzugefügt, die unter Verwendung des letzten Inkrements herleitbar sind. Die Frage stellt sich, ob das neue Inkrement notwendigerweise alle herleitbaren Fakten umfassen muß. Das folgende Programm berechnet ein Inkrement von nur einem Faktum.
69
% Vorsicht: inkorrektes Programm! vorwaerts :- (Rumpf ---> Kopf), Rumpf, not Kopf, !, assert(Kopf), vorwaerts(Kopf). vorwaerts. vorwaerts(Fakt) :- (Rumpf ---> Kopf), inkr_auswerten(Rumpf, Fakt), not Kopf, !, assert(Kopf), vorwaerts(Kopf). inkr_auswerten(Ausdr, Fakt) :- conjunct_rest(Fakt, Rest, Ausdr), Rest. conjunct_rest(C, R, (C,R) ). conjunct_rest(C, (X,R), (X,Y,Z)) :- !, conjunct_rest(C, R, (Y,Z)). conjunct_rest(C, R, (R,C) ) :- !. conjunct_rest(C, true, C ).
Die folgende Sitzung bezieht sich auf Programm P69 und zeigt, daß es nicht vollständig ist:
:- dynamic(p/1). yes. :- [user]. true ---> p(a). p(a) ---> p(b). p(a) ---> p(c). p(b) ---> p(d). p(a), p(c), p(d) ---> p(e). yes. :- vorwaerts. no (more) solution. :- findall(p(X), p(X), S). S = [p(a), p(b), p(d)]. yes.
Der Aufruf vorwaerts scheitert, und die Fakten p(c) und p(e) werden nicht generiert.
Die Vollständigkeit kann dadurch hersgetellt werden, daß beide Cuts (in vorwaerts/0 und in vorwaerts/1) beseitigt werden. Die folgende Sitzung zeigt, wie dann die Fakten erzeugt werden:
:- dynamic(p/1). yes. :-user]. true ---> p(a). p(a) ---> p(b). p(a) ---> p(c). p(b) ---> p(d). p(a), p(c), p(d) ---> p(e). yes. :- vorwaerts. vorwaerts p(a) vorwaerts(p(a)) p(b) vorwaerts(p(b)) p(d) vorwaerts(p(d)) Ruecksetzen! Ruecksetzen! p(c) vorwaerts(p(c)) p(e) vorwaerts(p(e)) Ruecksetzen! Ruecksetzen! Ruecksetzen! yes. :- findall(p(X), p(X), S). S = [p(a), p(b), p(d), p(c), p(e)] yes.
Diese Sitzung bezieht sich auf Programm P70, eine Erweiterung des korrigierten Programms P69 (ohne Cuts) mit einem "trace":
70
vorwaerts :- ausgabe(vorwaerts, 0), Rumpf ---> Kopf), Rumpf, not Kopf, assert(Kopf), ausgabe(Kopf, 0), vorwaerts(Kopf,1). vorwaerts. vorwaerts(Fakt, T) :- ausgabe(vorwaerts(Fakt), T), (Rumpf ---> Kopf), inkr_auswerten(Rumpf, Fakt), not Kopf, assert(Kopf), ausgabe(Kopf, T), Tplus1 is T + 1, vorwaerts(Kopf, Tplus1). vorwaerts(_, T) :- ausgabe("Ruecksetzen!", T), fail. inkr_auswerten(Ausdr, Fakt) :- conjunct_rest(Fakt, Rest, Ausdr), Rest. conjunct_rest(C, R, (C,R) ). conjunct_rest(C, (X,R), (X,Y,Z)) :- !, conjunct_rest(C, R, (Y,Z)). conjunct_rest(C, R, (R,C) ) :- !. conjunct_rest(C, true, C ). ausgabe(X, T) :- einruecken(T), write(X), nl. einruecken(0). einruecken(T) :- T > 0, T1 is T - 1, write(" "), einruecken(T1).

zum Seitenanfang
P67 P68 P69 P70
P69 nicht vollständig ist:
:- dynamic(p/1). yes. :- [user]. true ---> p(a). p(a) ---> p(b). p(a) ---> p(c). p(b) ---> p(d). p(a), p(c), p(d) ---> p(e). yes. :- vorwaerts. no (more) solution. :- findall(p(X), p(X), S). S = [p(a), p(b), p(d)]. yes.

5. Weitere Optimierungen

Betrachten wir das Programm P67 zur inkrementellen vorwärtsschließenden Auswertung von bereichsbeschränkten Fakten und Regeln.
Bei jedem rekursiven Aufruf, d.h. bei jeder Auswertungsrunde, wird für jeden Regelrumpf überprüft, ob er dank des Inkrements die Herleitung eines neuen Fakts ermöglicht. Jede Runde benötigt also eine Zeit, die proportional zu der Größe der Regelmenge ist, also ca. proportional zu der Größe des Objektprogramms.
Es wäre wünschenswert, nur auf die Regeln zuzugreifen, in deren Rumpf ein Atom vorkommt, das mit einem Element des Inkrements unifiziert. Der Zeitbedarf für eine Runde wäre dann proportional zur Größe des Inkrements.
Betrachten wir eine Regel: (*) p(X,Y), q(Y,Z), r(Z,T) ---> s(X,T).

Wenn ein Faktum p(X,Y) existiert, dann gilt auch die spezialisierte Regel:

q(Y,Z), r(Z,T) ---> s(X,T).

Diese Wenn-dann-Beziehung läßt sich wieder durch eine Regel ausdrücken:

(**) p(X,Y) ---> ( q(Y,Z), r(Z,T) ---> s(X,T) ).

Es ergibt also einen Sinn, die Regel (*) durch folgende drei Inkrementregeln zu ersetzen:

p(X,Y) ---> ( q(Y,Z), r(Z,T) ---> s(X,T) ). q(Y,Z) ---> ( p(X,Y), r(Z,T) ---> s(X,T) ). r(Z,T) ---> ( p(X,Y), q(Y,Z) ---> s(X,T) ).

Die Herleitung des Faktums q(a,b) würde dann zur Generierung der folgenden spezialisierten Regel führen:

p(X,a), r(b,T) ---> s(X,T)

Man kann sich leicht davon vergewissern, daß eine spezialisierte Regel, die in dieser Weise aus einem Grundfaktum und einer Inkrementregel gewonnen wird, die zu einer bereichsbeschränkten Regel gehört, ebenfalls bereichsbeschränkt ist.

Das folgende Programm P71 konvertiert zunächst alle Regeln aus dem üblichen "Benutzerformat" in Inkrementregeln, die bei der Generierung eines neuen Fakts die zugehörigen spezialisierten Regeln berechnen. Um die Regeln im "Benutzerformat" von den Inkrementregeln zu unterscheiden, werden die letzteren mit dem Implikationszeichen ===> dargestellt.
71
:- op(1200, xfx, --->), dynamic(---> /2), op(1200, xfx, ===>), dynamic(===> /2). vorwaerts :- coverof(Konv, R^K^( retract(R ---> K), konvertieren((R ---> K), Konv), not vorhandenes_faktum(Konv) ), Menge), assert_all(Menge), atome(Menge, Atome), vorwaerts(Atome). vorwaerts(Inkrement) :- coverof(Konv, Fakt^RegelOderAtom^V^( member(Fakt, Inkrement), (Fakt ===> RegelOderAtom), vereinfachen(RegelOderAtom, V), konvertieren(V, Konv), not vorhandenes_faktum(Konv) ), Menge), assert_all(Menge), atome(Menge, NeuesInkrement), vorwaerts(NeuesInkrement). vorwaerts(_). assert_all([]). assert_all([H | T]) :- assert(H), assert_all(T). %%% Vereinfachen und Konvertieren von Regeln vereinfachen((R ---> K), V) :- !, vereinfachen_konj(R, VR), V = (VR ---> K). vereinfachen( A, A). vereinfachen_konj((A,B), V) :- !, vereinfachen_konj(A, VA), vereinfachen_konj(B, VB), und_verknuepfen(VA, VB, V). vereinfachen_konj(A, V) :- vereinfachen_atom(A, V). vereinfachen_atom(A, true) :- A. vereinfachen_atom(A, A) :- not A. konvertieren( ((X,Y) ---> K), Konv) :- !, conjunct_rest(A, R, (X,Y)), Konv = (A ===> (R ---> K)). konvertieren( (true ---> K), Konv) :- !, Konv = K. konvertieren( (A ---> K), Konv) :- !, Konv = (A ===> K). konvertieren( Atom, Atom). %%% Hilfsprozeduren conjunct_rest(C, R, (C,R) ). conjunct_rest(C, (X,R), (X,Y,Z)) :- !, conjunct_rest(C, R, (Y,Z)). conjunct_rest(C, R, (R,C) ) :- !. conjunct_rest(C, true, C ). und_verknuepfen(true, X, X ) :- !. und_verknuepfen(X, true, X ) :- !. und_verknuepfen(X, Y, (X,Y) ). vorhandenes_faktum(F) :- atomare_formel(F), F. atome(Menge, Atome) :- findall(A, (member(A,Menge), atomare_formel(A)), Atome). atomare_formel(X) :- not X = (_ ===> _). % reicht hier aus
Alle initialen Regeln werden aus dem Benutzerformat in Fakten bzw. Inkrementregeln konvertiert. Die dabei entstandenen Fakten bilden die erste Inkrementmenge zum Auslösen der Inkrementregeln.

Die spezialisierte Regel, die durch das Auslösen einer Inkrementregel entsteht, wird in zwei Schritten aus dem "Benutzerformat" umgewandelt. Im ersten Schritt wird ihr Rumpf von den Atomen bereinigt, die bereits hergeleitet wurden (vereinfachen). Im zweiten Schritt werden aus der bereinigten Regel Fakten bzw. Inkrementregeln erzeugt (konvertieren).

Die folgende Sitzung bezieht sich auf eine (hier nicht angegebene) Version von Programm P71 mit einem "trace":
:- dynamic(p/1). :- [user]. true ---> p(a). true ---> p(b). p(a), p(b) ---> p(c). p(a), p(b), p(c) ---> p(d). p(a), p(d) ---> p(e). yes. :- vorwaerts. 0. Runde: p(a) p(b) p(a) ===> (p(b) ---> p(c)) p(b) ===> (p(a) ---> p(c)) p(a) ===> (p(b), p(c) ---> p(d)) p(b) ===> (p(a), p(c) ---> p(d)) p(c) ===> (p(a), p(b) ---> p(d)) p(a) ===> (p(d) ---> p(e)) p(d) ===> (p(a) ---> p(e)) 1. Runde: p(c) p(c) ===> p(d) p(d) ===> p(e) 2. Runde: p(d) 3. Runde: p(e) yes.
Die Art von Optimierung, die in diesem Abschnitt behandelt wird, kommt an die Grenze des Möglichen in PROLOG. Die Mechanismen zum Zugriff auf die PROLOG-Datenbank sind vorgegeben und können vom Programmierer nicht verbessert werden. Für Relationen, die als dynamisch deklariert sind, werden effiziente Zugriffe nicht in gleichem Maße unterstützt wie für andere Relationen. Aus diesem Grund erweisen sich "Optimierungen" oft als weniger effizient, als man gedacht hätte. Auch die Implementierung effizienter Datenstrukturen ist in PROLOG nur beschränkt möglich.
Für die schnelle Überprüfung von Entwürfen, die nach ihrer Erprobung in anderen Programmiersprachen implementiert werden, ist PROLOG jedoch eine sehr passende und bequeme Programmiersprache. Diese Vorgehensweise nennt man "rapid prototyping".

zum Seitenanfang
P67 zur inkrementellen vorwärtsschließenden Auswertung von bereichsbeschränkten Fakten und Regeln.
Betrachten wir eine Regel: (*) p(X,Y), q(Y,Z), r(Z,T) ---> s(X,T).

Wenn ein Faktum p(X,Y) existiert, dann gilt auch die spezialisierte Regel:

q(Y,Z), r(Z,T) ---> s(X,T).

Diese Wenn-dann-Beziehung läßt sich wieder durch eine Regel ausdrücken:

(**) p(X,Y) ---> ( q(Y,Z), r(Z,T) ---> s(X,T) ).

Es ergibt also einen Sinn, die Regel (*) durch folgende drei Inkrementregeln zu ersetzen:

p(X,Y) ---> ( q(Y,Z), r(Z,T) ---> s(X,T) ). q(Y,Z) ---> ( p(X,Y), r(Z,T) ---> s(X,T) ). r(Z,T) ---> ( p(X,Y), q(Y,Z) ---> s(X,T) ).

Die Herleitung des Faktums q(a,b) würde dann zur Generierung der folgenden spezialisierten Regel führen:

p(X,a), r(b,T) ---> s(X,T)

P71 konvertiert zunächst alle Regeln aus dem üblichen "Benutzerformat" in Inkrementregeln, die bei der Generierung eines neuen Fakts die zugehörigen spezialisierten Regeln berechnen.

Programm P71 mit einem "trace":
:- dynamic(p/1). :- [user]. true ---> p(a). true ---> p(b). p(a), p(b) ---> p(c). p(a), p(b), p(c) ---> p(d). p(a), p(d) ---> p(e). yes. :- vorwaerts.

6. Vorwärtsausgewertete Regeln als Metainterpretationssprache

In den vorangehenden Kapiteln 5 "Programme als Daten: Metainterpretation" und 6 "Metainterpretation zur Steuerung der Auswertung" ist die Regelsprache PROLOG, die ihre Regeln rückwärts auswertet, verwendet worden, um verschiedene Formen des Rückwärtsschließens zu implementieren.

In den vorangehenden Abschnitten 1 bis 5 dieses Kapitels ist die Sprache PROLOG, die ihre Regeln rückwärts auswertet, benutzt worden, um verschiedene Formen des Vorwärtsschließens zu implementieren.

In diesem Abschnitt wird untersucht, wie verschiedene Formen des Vorwärtsschließens in einer Sprache von vorwärtsausgewerteten Regeln implementiert werden können.

Die vorwärtsschließende Auswertung einer Regel A1, ..., An ---> K besteht in
  1. der Auswertung des Rumpfes R = A1, ..., An, gefolgt vom
  2. "Schließen" des Kopfes K.
Also in der Sprache von vorwärts ausgewerteten Regeln: (R ---> K), R ---> K wobei hier die Variablen ähnlich wie in PROLOG verwendet werden.
Diese Metaregel illustriert das Prinzip. Sie ist aber nicht korrekt, weil sie ihren rekursiven Aufruf nicht ausschließt, was zur Nichtterminierung führt. Eine korrekte Implementierung verlangt, zwischen Meta- und Objektsprache zu unterscheiden. Dazu verwenden wir hier die folgenden zwei Implikationszeichen: ---> für die Metasprache.      Deklariert mit :- op(1200, xfx, --->).
===> für die Objektsprache.    Deklariert mit :- op(1200, xfx, ===>).
Der grundlegende mittels vorwärtsausgewerteten Regeln implementierte vorwärtsschließende Metainterpretierer lautet also:
72
(R ===> K), R ---> K.
Dieser Metainterpretierer P72 kann selber u.a. mit dem Metainterpretierer P60 ausgewertet werden. Die folgende Sitzung wertet P72 mit P63 aus, das P60 mit einem "trace"erweitert:
:- dynamic(t/2). yes. :- [user]. r(1, 2). r(2, 3). r(3, 1). t(X, Y), t(Y, Z) ===> t(X, Z). r(X, Y) ===> t(X, Y). yes. :- vorwaerts_trace. 1. Runde: t(1, 2) t(2, 3) t(3, 1) 2. Runde: t(1, 3) t(2, 1) t(3, 2) 3. Runde: t(1, 1) t(2, 2) t(3, 3) yes.
Wie kann man eine inkrementelle Auswertung der Objektregeln, d.h. der ===>-Regeln, sicherstellen? Reicht es aus, den Metainterpretierer P72 selber inkrementell, z. B. mit P67 auszuwerten?

Das ist nicht der Fall, weil der Metainterpretierer P72: (R ===> K), R ---> K. keinen Zugriff auf die Rumpfatome der Objektregel R ===> K bietet. Die inkrementelle Auswertung der Objektregeln muß also in der Metasprache spezifiziert werden.

Eine erster Ansatz besteht darin, dem Interpretierer der Metasprache Zugriff für eine inkrementelle Auswertung auf Objektebene wie folgt zu geben:
73
(A, R ===> K), A ---> (R ===> K). (A ===> K), A ---> K.
Ein zweiter Ansatz besteht darin, die inkrementelle Auswertung der Objektsprache direkt in der Metasprache zu spezifizieren:
74
:- op(1200, xfx, --->), op(1200, xfx, ===>). :- dynamic(===> / 2), dynamic(fakt/1), dynamic(auswerten/2), dynamic(ausgewertet/1). (Rumpf ===> _) ---> auswerten(Rumpf, Rumpf). (Rumpf ===> Kopf), ausgewertet(Rumpf) ---> fakt(Kopf). auswerten(true, Ausdr) ---> ausgewertet(Ausdr). auswerten(Konj, Ausdr), conjunct_rest(F, Rest, Konj), fakt(F) ---> auswerten(Rest, Ausdr). %%% Dazu die schon mehrfach benutzte PROLOG-Definition: conjunct_rest(C, R, (C,R) ). conjunct_rest(C, (X,R), (X,Y,Z)) :- !, conjunct_rest(C, R, (Y,Z)). conjunct_rest(C, R, (R,C) ) :- !. conjunct_rest(C, true, C ).
Ähnlich wie in der Programmierung in PROLOG bedient man sich hier einer Metasprache, die aus den Relationssymbolen fakt, auswerten und ausgewertet besteht.
Die folgende Sitzung bezieht sich auf die Programme P74 und P60:
:- [user]. fakt( r(1,2) ). fakt( r(2,3) ). fakt( r(3,1) ). t(X, Y), t(Y, Z) ===> t(X, Z). r(X, Y) ===> t(X, Y). yes. :- vorwaerts. yes. :- listing(fakt/1). fakt( r(1,2) ). fakt( r(2,3) ). fakt( r(3,1) ). fakt( t(1,2) ). fakt( t(2,3) ). fakt( t(3,1) ). fakt( t(1,3) ). fakt( t(2,1) ). fakt( t(1,1) ). fakt( t(3,2) ). fakt( t(2,2) ). fakt( t(3,3) ). yes.
Das folgende Programm ergänzt P74 mit einem "trace":
75
:- op(1200, xfx, --->), op(1200, xfx, ===>). :- dynamic(===> / 2), dynamic(fakt/1), dynamic(auswerten/2), dynamic(ausgewertet/1). (Rumpf ===> Kopf), ausgewertet(Rumpf), schreiben(fakt(Kopf)) ---> fakt(Kopf). (Rumpf ===> _), schreiben(auswerten(Rumpf, Rumpf)) ---> auswerten(Rumpf, Rumpf). auswerten(true, Ausdr), schreiben(ausgewertet(Ausdr)) ---> ausgewertet(Ausdr). auswerten(Konj, Ausdr), conjunct_rest(F, Rest, Konj), fakt(F), schreiben(auswerten(Rest, Ausdr)) ---> auswerten(Rest, Ausdr). %%% Dazu die schon mehrfach benutzte PROLOG-Definition: conjunct_rest(C, R, (C,R) ). conjunct_rest(C, (X,R), (X,Y,Z)) :- !, conjunct_rest(C, R, (Y,Z)). conjunct_rest(C, R, (R,C) ) :- !. conjunct_rest(C, true, C ). %%% Sowie die PROLOG-Definition eines "Systempraedikats": schreiben(X) :- write(X), nl.
Die folgende Sitzung bezieht sich auf die Programme P75 und P60:
:- [user]. fakt( r(1,2) ). fakt( r(2,1) ). t(X, Y), t(Y, Z) ===> t(X, Z). r(X, Y) ===> t(X, Y). yes. :- vorwaerts. auswerten((t(X, Y), t(Y, Z)), (t(X, Y), t(Y, Z))) auswerten(r(X, Y), r(X, Y)) ausgewertet(r(1, 2)) ausgewertet(r(2, 1)) fakt(t(1, 2)) fakt(t(2, 1)) auswerten(t(2, Z), (t(1, 2), t(2, Z))) auswerten(t(X, 1), (t(X, 1), t(1, 2))) auswerten(t(1, Z), (t(2, 1), t(1, Z))) auswerten(t(X, 2), (t(X, 2), t(2, 1))) ausgewertet((t(1, 2), t(2, 1))) ausgewertet((t(2, 1), t(1, 2))) ausgewertet((t(2, 1), t(1, 2))) ausgewertet((t(1, 2), t(2, 1))) fakt(t(1, 1)) fakt(t(2, 2)) ausgewertet((t(1, 1), t(1, 2))) ausgewertet((t(2, 1), t(1, 1))) ausgewertet((t(1, 2), t(2, 2))) ausgewertet((t(2, 2), t(2, 1))) auswerten(t(1, Z), (t(1, 1), t(1, Z))) auswerten(t(X, 1), (t(X, 1), t(1, 1))) auswerten(t(2, Z), (t(2, 2), t(2, Z))) auswerten(t(X, 2), (t(X, 2), t(2, 2))) fakt(t(1, 2)) fakt(t(2, 1)) fakt(t(1, 2)) fakt(t(2, 1)) ausgewertet((t(1, 1), t(1, 2))) ausgewertet((t(1, 1), t(1, 1))) ausgewertet((t(2, 1), t(1, 1))) ausgewertet((t(1, 1), t(1, 1))) ausgewertet((t(2, 2), t(2, 1))) ausgewertet((t(2, 2), t(2, 2))) ausgewertet((t(1, 2), t(2, 2))) ausgewertet((t(2, 2), t(2, 2))) fakt(t(1, 1)) fakt(t(2, 2)) yes.
Bemerkungen:
  1. Der Aufruf von "Systemprädikaten" wie schreiben im Rumpf von vorwärtsausgewerteten Regeln stört die Auswertung nicht.
  2. Die wiederholte Generierung von Fakten wie etwa fakt( t(1,2) ) kommt daher, daß diese Fakten mehrere, unterschiedliche Beweise haben.
  3. In der letzten Regel von Programm P75 kann anstelle von element_rest eine Auswahlfunktion verwendet werden.

zum Seitenanfang
P72 P73 P74 P75
Die folgende Sitzung bezieht sich auf die Programme P74 und P60:
:- [user]. fakt( r(1,2) ). fakt( r(2,3) ). fakt( r(3,1) ). t(X, Y), t(Y, Z) ===> t(X, Z). r(X, Y) ===> t(X, Y). yes.
P75 und P60:
:- [user]. fakt( r(1,2) ). fakt( r(2,1) ). t(X, Y), t(Y, Z) ===> t(X, Z). r(X, Y) ===> t(X, Y). yes. :- vorwaerts. auswerten((t(X, Y), t(Y, Z)), (t(X, Y), t(Y, Z))) auswerten(r(X, Y), r(X, Y)) ausgewertet(r(1, 2)) ausgewertet(r(2, 1))

Vorwärtsausgewertete Regeln als Metainterpretationssprache (5)

fakt(t(1, 2)) fakt(t(2, 1)) fakt(t(1, 2)) fakt(t(2, 1)) ausgewertet((t(1, 1), t(1, 2))) ausgewertet((t(1, 1), t(1, 1))) ausgewertet((t(2, 1), t(1, 1))) ausgewertet((t(1, 1), t(1, 1))) ausgewertet((t(2, 2), t(2, 1))) ausgewertet((t(2, 2), t(2, 2))) ausgewertet((t(1, 2), t(2, 2))) ausgewertet((t(2, 2), t(2, 2))) fakt(t(1, 1)) fakt(t(2, 2)) yes.
voriges Kapitel | Startseite | Inhalt | nächstes Kapitel

Letzte Änderung: 18. August 1998

Valid XHTML 1.0!