XI. Rückwärtsschließen

Meta- und Objektsprachen
Der Metainterpretierer zum Rückwärtsschließen
Beispiele

In den letzten Kapiteln sind verschiedene vorwärtsschließende Auswerter in der rückwärtsschließenden Programmiersprache PROLOG implementiert worden.

In diesem Kapitel wird untersucht, wie eine Form des Rückwärtsschließens mittels Regeln implementiert werden kann, die vorwärts ausgewertet werden. Dabei geht es nicht um ein Kuriosum, sondern um einen Ansatz zum Rückwärtsschließen, der eine besonders interessante Eigenschaft besitzt.

Rückwärtsschließen

Meta- und Objektsprachen
Der Metainterpretierer zum Rückwärtsschließen
Beispiele

1. Meta- und Objektsprachen

Regeln, die vorwärts ausgewertet werden, sollen also verwendet werden, um andere Regeln rückwärts auzuwerten. Dazu soll ein vorwärtsschließender Auswerter zugrunde liegen, der selber in der Rückwärtssprache PROLOG implementiert ist.

Um etwas Ordnung in diesem Sprachwirrwarr zu schaffen, wollen wir zunächst zwischen den verschiedenen Regelsprachen unterscheiden.

Implementierungs- oder Metasprache:
Regeln: dargestellt mit dem Implikationszeichen --->, dazu: :- op(1200, xfx, --->).

Fakten: dargestellt als PROLOG-Fakten.

Die Metasprache wird mit einem der vorwärtsschließenden Auswerter der letzten Kapitel ausgewertet, der selber in PROLOG implementiert ist. Diese Implementierung in PROLOG bleibt aber zunächst im Hintergrund.

Zur Implementierung der Objektsprache sollen die zwei folgenden Relationssymbole verwendet werden:
anfrage/1 ausgewertet/2
Objektsprache:
Regeln: dargestellt mit dem Implikationszeichen <-, dazu: :- op(1200, xfx, <-).

Fakten: Ein Faktum F wird dargestellt als F <- wahr.

Bemerkungen:

Im Prinzip könnte man die PROLOG-Syntax für die Objektsprache verwenden, d.h. eine Regel als H :- B darstellen. Wo aber in den unten angegebenen Programmen ein Aufruf H <- B steht, kann man nicht H :- B verwenden. Anstelle von H :- B, dessen Aufruf in PROLOG zu einem Fehler führt, verlangt PROLOG die Schreibweise clause(H, B).
Lediglich der Einfachheit halber werden Fakten als Regelm mit wahr als Rumpf dargestellt. Zum Preis eines weiteren Relationssymbols neben <-, anfrage und ausgewertet kann diese Annahme aufgehoben werden.

zum Seitenanfang

1. Meta- und Objektsprachen

Implementierungs- oder Metasprache:
- Regeln: dargestellt mit dem Implikationszeichen --->, dazu: :- op(1200, xfx, --->).
- Fakten: dargestellt als PROLOG-Fakten.
Zur Implementierung der Objektsprache sollen die zwei folgenden Relationssymbole verwendet werden:
anfrage/1 ausgewertet/2
Objektsprache:
Regeln: dargestellt mit dem Implikationszeichen <-, dazu:
:- op(1200, xfx, <-).
Fakten: Ein Faktum F wird dargestellt als F <- wahr.

2. Der Metainterpretierer zum Rückwärtsschließen

Das folgende Programm spezifiziert in der Metasprache einen Auswerter zur rückwärtsschließenden Auswertung der Objektsprache:

100


:op(1200, xfx, --->).
:- dynamic(anfrage/1), dynamic(ausgewertet/1).
:op(1200, xfx, <-).
 
anfrage(A),
A <- Rumpf)              ---> anfrage(Rumpf).
 
anfrage(A),
A <- Rumpf),
ausgewertet(Rumpf)        ---> ausgewertet(A).
 
anfrage(A),
(A <- wahr)               ---> ausgewertet(A).
 
anfrage( (Atom, _Rest) )  ---> anfrage(Atom).
 
anfrage( (Atom, Rest) ),
ausgewertet(Atom)         ---> anfrage(Rest).
 
anfrage( (Atom, Rest) ),
ausgewertet(Atom),
ausgewertet(Rest)         ---> ausgewertet( (Atom, Rest) ).

Man beachte, daß wie bei früheren Metainterpretierern die Unifikation in der Objektsprache auf die Unifikation in der Metasprache zurückgeführt ist. In dem Fall vom Programm P₁₀₀ wird diese auf die Unifikation in PROLOG zurückgeführt.

Das Programm P₁₀₀ spezifiziert nicht alle Konjunktionen, die gelten, d.h. die logisch hergeleitet werden könnten. Im allgemeinen sind das ja unendlich viele. Das Programm P₁₀₀ generiert lediglich solche Konjunktionen, die mit dem Rumpf einer Regel (der Objektsprache) unifizieren können. Von solchen Konjunktionen gibt es zu jeder Zeit endlich viele.

Der Auswerter P₁₀₀ muß selber ausgewertet werden. Dazu kann der folgende Auswerter vom Kapitel 7 "Vorwärtsschließen" verwendet werden:

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

zum Seitenanfang

Der Metainterpretierer zum Rückwärtsschließen

Rückwärtsschließende Auswertung der Objektsprache: siehe Progarmm P₁₀₀

Das Programm P100 spezifiziert nicht alle Konjunktionen und muß selber ausgewertet werden. Dazu kann das Programm P₆₆ verwendet werden.

3. Beispiele

Betrachten wir nun ein erstes Objektprogramm:

101


t(X, Y) <- r(X, Y).
t(X, Z) <- t(X, Y), t(Y, Z).
 
r(a, b) <- wahr.
r(b, c) <- wahr.
r(c, a) <- wahr.
r(1, 2) <- wahr.
r(2, 3) <- wahr.
r(3, 4) <- wahr.
r(4, 1) <- wahr.
 
anfrage(t(a, _X)).

Das Programm P₁₀₁ spezifiziert die transitive Hülle t einer binären Relation r.

Man beachte, daß r zwei Zusammenhangskomponenten hat. Die Knoten der einen Zusammenhangskomponente sind Zahlen, die Knoten der anderen sind Buchstaben. Bei einer rückwärtsschließenden Auswertung der Anfrage t(a, X) sollen r-Fakten über Zahlen weder angefragt noch hergeleitet werden.

Die folgende Sitzung bezieht sich auf die Programme P₁₀₀ und P₁₀₁:


:- vorwaerts_trace.

1. Runde:
anfrage(r(a, _X))
anfrage((t(a, Y), t(Y, _X)))
 
2. Runde:
anfrage(wahr)
ausgewertet(r(a, b))
 
3. Runde:
ausgewertet(t(a, b))
 
4. Runde:
anfrage(t(b, _X))
 
5. Runde:
anfrage(r(b, _X))
anfrage((t(b, Y), t(Y, _X)))
 
6. Runde:
ausgewertet(r(b, c))
 
7. Runde:
ausgewertet(t(b, c))
 
8. Runde:
anfrage(t(c, _X))
ausgewertet((t(a, b), t(b, c)))
 
9. Runde:
anfrage(r(c, _X))
anfrage((t(c, Y), t(Y, _X)))
ausgewertet(t(a, c))
 
10. Runde:
ausgewertet(r(c, a))
 
11. Runde:
ausgewertet(t(c, a))
 
12. Runde:
ausgewertet((t(a, c), t(c, a)))
ausgewertet((t(b, c), t(c, a)))
ausgewertet((t(c, a), t(a, b)))
ausgewertet((t(c, a), t(a, c)))
 
13. Runde:
ausgewertet(t(a, a))
ausgewertet(t(b, a))
ausgewertet(t(c, b))
ausgewertet(t(c, c))
 
14. Runde:
ausgewertet((t(a, b), t(b, a)))
ausgewertet((t(a, c), t(c, b)))
ausgewertet((t(a, c), t(c, c)))
ausgewertet((t(a, a), t(a, b)))
ausgewertet((t(a, a), t(a, c)))
ausgewertet((t(a, a), t(a, a)))
ausgewertet((t(b, c), t(c, b)))
ausgewertet((t(b, c), t(c, c)))
ausgewertet((t(b, a), t(a, b)))
ausgewertet((t(b, a), t(a, c)))
ausgewertet((t(b, a), t(a, a)))
ausgewertet((t(c, a), t(a, a)))
ausgewertet((t(c, b), t(b, c)))
ausgewertet((t(c, b), t(b, a)))
ausgewertet((t(c, c), t(c, a)))
ausgewertet((t(c, c), t(c, b)))
ausgewertet((t(c, c), t(c, c)))
 
15. Runde:
ausgewertet(t(b, b))
 
16. Runde:
ausgewertet((t(a, b), t(b, b)))
ausgewertet((t(b, b), t(b, c)))
ausgewertet((t(b, b), t(b, a)))
ausgewertet((t(b, b), t(b, b)))
ausgewertet((t(c, b), t(b, b)))
 
yes.
 
:- setof(t(a, Y), ausgewertet(t(a, Y)), Set).
Y = Y
Set = [t(a, a), t(a, b), t(a, c)]
yes.

Mit dem Auswerter P₁₀₀ terminiert das Rückwärtsschließen aus der Anfrage t(a, X) bezüglich der mit <- geschriebenen objektsprachlichen Regeln des Programms P₁₀₁. Die Rückwärtsauswertung in PROLOG im gleichen Fall würde aber nicht terminieren.

Mit dem Auswerter P₁₀₀ terminiert die Auswertung allerdings auch nicht immer. Das folgende Programm ist ein Fall von Nicht-Terminierung:

102


r(X) <- r(f(X)).
r(a) <- wahr.
 
anfrage(r(b)).

Die folgende Sitzung bezieht sich auf die Programme P₁₀₀ und P₁₀₂:


:- vorwaerts_trace.
1. Runde:
anfrage(r(f(b)))
 
2. Runde:
anfrage(r(f(f(b))))
 
3. Runde:
anfrage(r(f(f(f(b)))))
 
4. Runde:
anfrage(r(f(f(f(f(b))))))
 
5. Runde:
anfrage(r(f(f(f(f(f(b)))))))
 
6. Runde:
anfrage(r(f(f(f(f(f(f(b))))))))
 
7. Runde:
anfrage(r(f(f(f(f(f(f(f(b)))))))))
 
8. Runde:
anfrage(r(f(f(f(f(f(f(f(f(b))))))))))
 
.
.
.

Der Grund für die Terminierung im Falle vom P₁₀₁ liegt zum einen in der Verwaltung der Anfrage als Relation - oder Menge -, zum anderen in der Verwendung des All-Antwort-Prädikats coverof im Auswerter P₆₆ anstatt von z. B. findall oder setof. Das Systemprädikat coverof sorgt dafür, daß keine Anfrage A generiert wird, wenn eine andere Anfrage B bereits generiert wurde, die allgemeiner als A ist.

Im Falle vom P₁₀₂ hilft dies nicht: durch die immer tiefere Schachtelung der in den Anfragen vorkommenden Grundterme ist keine neue Anfrage weniger allgemein als eine zuvor generierte Anfrage.

Die PROLOG-Auswertung beruht auf linearen Resolutionsbeweisen (siehe Kapitel 2 "Prinzipien der Auswertung von PROLOG-Programmen"), die keinen Vergleich von Anfragen durchführt. Aus diesem Grund terminiert die PROLOG-Auswertung eines Programmes wie P₁₀₁ nicht.

Die mit Programm P₁₀₀ implementierte rückwärtsschließende Auswertungsmethode terminiert immer, wenn das Objektprogramm weder Negation noch Funktionssymbole enthält. Erweiterungen des Ansatzes zur Behandlung der Negation sind vorgeschlagen worden. Bisher ist kein Ansatz bekannt, der gute Terminierungseigenschaften hätte, wenn das Objektprogramm Funktionssymbole enthält. Die Terminierung in diesem letzten Fall kann prinzipiell nicht garantiert werden, weil mit rückwärts ausgewerteten, negationsfreien Regeln und Fakten, in denen Funktionssymbole vorkommen, eine Turingmaschine simuliert werden kann.

zum Seitenanfang

Beispiele (1)

Betrachten wir nun ein erstes Objektprogramm: P₁₀₁

Die folgende Sitzung bezieht sich auf die Programme P₁₀₀ und P₁₀₁:


:- vorwaerts_trace.
 
1. Runde:
anfrage(r(a, _X))
anfrage((t(a, Y), t(Y, _X)))
 
2. Runde:
anfrage(wahr)
ausgewertet(r(a, b))
 
3. Runde:
ausgewertet(t(a, b))
 
4. Runde:
anfrage(t(b, _X))

Beispiele (2)


5. Runde:
anfrage(r(b, _X))
anfrage((t(b, Y), t(Y, _X)))
 
6. Runde:
ausgewertet(r(b, c))
 
7. Runde:
ausgewertet(t(b, c))
 
8. Runde:
anfrage(t(c, _X))
ausgewertet((t(a, b), t(b, c)))
 
9. Runde:
anfrage(r(c, _X))
anfrage((t(c, Y), t(Y, _X)))
ausgewertet(t(a, c))

Beispiele (3)


10. Runde:
ausgewertet(r(c, a))
 
11. Runde:
ausgewertet(t(c, a))
 
12. Runde:
ausgewertet((t(a, c), t(c, a)))
ausgewertet((t(b, c), t(c, a)))
ausgewertet((t(c, a), t(a, b)))
ausgewertet((t(c, a), t(a, c)))
 
13. Runde:
ausgewertet(t(a, a))
ausgewertet(t(b, a))
ausgewertet(t(c, b))
ausgewertet(t(c, c))

Beispiele (4)


14. Runde:
ausgewertet((t(a, b), t(b, a)))
ausgewertet((t(a, c), t(c, b)))
ausgewertet((t(a, c), t(c, c)))
ausgewertet((t(a, a), t(a, b)))
ausgewertet((t(a, a), t(a, c)))
ausgewertet((t(a, a), t(a, a)))
ausgewertet((t(b, c), t(c, b)))
ausgewertet((t(b, c), t(c, c)))
ausgewertet((t(b, a), t(a, b)))
ausgewertet((t(b, a), t(a, c)))
ausgewertet((t(b, a), t(a, a)))
ausgewertet((t(c, a), t(a, a)))
ausgewertet((t(c, b), t(b, c)))
ausgewertet((t(c, b), t(b, a)))
ausgewertet((t(c, c), t(c, a)))
ausgewertet((t(c, c), t(c, b)))
ausgewertet((t(c, c), t(c, c)))

Beispiele (5)


15. Runde:
ausgewertet(t(b, b))
 
16. Runde:
ausgewertet((t(a, b), t(b, b)))
ausgewertet((t(b, b), t(b, c)))
ausgewertet((t(b, b), t(b, a)))
ausgewertet((t(b, b), t(b, b)))
ausgewertet((t(c, b), t(b, b)))
 
yes.
 
:- setof(t(a, Y), ausgewertet(t(a, Y)), Set).
Y = Y
Set = [t(a, a), t(a, b), t(a, c)]
yes.