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
-
der Auswertung des Rumpfes
R = A1, ..., An
, gefolgt vom
-
"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:
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 ).
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.
zum Seitenanfang
Rumpf
in der Anfrage des Aufrufes vonsetof
. Sie ist notwendig, damit alle Köpfe ermittelt werden, die sich aus verschiedenen Bindungen der Rümpfe ergeben. Ohne die existentielle Quantifizierung vonRumpf
würde der Aufruf vonsetof
nur Bindungen vonKopf
für eine einzige Bindung vonRumpf
ergeben.