V. Programme als Daten: Metainterpretation

Metainterpretation
Einfache Metainterpretierer
All-Antwort- und Systemprädikate berücksichtigen
Metainterpretierer zur Darstellung von Beweisbäumen für "reines PROLOG"
Behandlung von cut

PROLOG-Hilfsprädikate und -programme

Metainterpretation
Einfache Metainterpretierer
All-Antwort- und Systemprädikate berücksichtigen
Metainterpretierer zur Darstellung von Beweisbäumen für "reines PROLOG"
Behandlung von cut

1. Metainterpretation

In PROLOG sind Fakten und Regeln gewöhnliche Datenstrukturen. Im Ausdruck


p(a, f(b))

kann p sowohl als Relations- als auch als Funktionssymbol angesehen werden. Die Interpretation von p als Relations- oder Funktionssymbol hängt lediglich davon ab, wo der Ausdruck p(a, f(b)) sich im Programm befindet. In


:- p(a, f(a, b)).

q(a) :- p(a, f(a, b)), s(a, b).

p(a, f(a, b)) :- r(a, b), s(a, b).

gilt p als Relationssymbol. In


q(p(a, f(a, b)), c).

q(a, b) :- r(p(a, f(a, b)), c).

gilt p als Funktionssymbol.

Diese Interpretationsmöglichkeiten von identischen Ausdrücken ermöglicht, oder erleichtert zumindest wesentlich, die Bearbeitung von PROLOG-Programmen durch andere PROLOG-Programme.

Ein Metaprogramm ist ein Programm, das andere Programme, Objektprogramme genannt, als Eingabe erhält. Ein Metainterpretierer ist ein Metaprogramm, das Objektprogramme auswertet.

Die Metaprogrammierung und -interpretation sind in der PROLOG-Programmierung verbreitet. Sie erleichtern u.a. die Implementierung von Auswertungsmethoden.

zum Seitenanfang

Metainterpretation

In PROLOG sind Fakten und Regeln gewöhnliche Datenstrukturen. Im Ausdruck

>


p(a, f(b))

kann p sowohl als Relations- als auch als Funktionssymbol angesehen werden. Die Interpretation von p als Relations- oder Funktionssymbol hängt lediglich davon ab, wo der Ausdruck p(a, f(b)) sich im Programm befindet.

Ein Metaprogramm ist ein Programm, das andere Programme, Objektprogramme genannt, als Eingabe erhält. Ein Metainterpretierer ist ein Metaprogramm, das Objektprogramme auswertet.

2. Einfache Metainterpretierer

Der einfachste PROLOG-Metainterpretierer für PROLOG-Programme ist wohl das folgende Programm:

45


demo(X) :- X.

Ein einfacher Metainterpretierer, der jedoch die Auswertung näher spezifiziert, ist:

46


demo(true)    :- !.
demo( (X,Y) ) :- !, demo(X), demo(Y).
demo(X)       :- clause(X, Rumpf), demo(Rumpf).

Bemerkung: In vielen PROLOG-Systemen muß, um das Systemprädikat clause auf Klauseln, d.h. Fakten und Regeln, anwenden zu können, das durch diese Klauseln definierte Relationssymbol als dynamisch deklariert worden sein.

Programm P₄₆ hat den Nachteil, baumrekursiv zu sein. Baumrekursive Programme sind in der Regel weniger effizient als linearrekursive Programme. Zudem verhindert die Baumrekursion die Anwendung der Endrekursion-Optimierung, die in den meisten PROLOG-Systemen durchgeführt wird und linear endrekursive Programme als iterative Prozesse ausführt.

Programm P₄₇ ist ein linear endrekursives Gegenstück zu Programm P₄₆, das allerdings eine etwas andere Anfrage- und Klauseldarstellung voraussetzt als die in PROLOG übliche.

47


:- op(255, xfx, <---).

demo([]).
demo([Atom | Anfragen]) :- (Atom <--- Rumpf),
                           append(Rumpf, Anfragen, NeueAnfragen),
                           demo(NeueAnfragen).

Programm P₄₇ bearbeitet Klauseln der Gestalt:


Kopf <--- Rumpf

wobei Kopf ein Atom ist und Rumpf eine Liste von Atomen ist. Fakten werden als solche Klauseln dargestellt, deren Rumpf, oder rechter Teil, die leere Liste ist. Programm P₄₇ wertet Anfragen aus, die die Gestalt von Listen von Atomen haben, wobei die leere Liste als das Atom true interpretiert wird:


:- [user].
t(A, B) <--- [r(A, B)].
t(A, B) <--- [r(A, C), t(C, B)].
r(1, 2) <--- [].
r(2, 3) <--- []. 
r(3, 4) <--- [].

yes.

:-  findall(t(A, B), demo([t(A, B)]), L).
A = A
B = B
L = [t(1,2), t(2,3), t(3,4), t(1,3), t(1,4), t(2,4)]
yes.

:-

Bemerkung: Programm P₄₇ wurde von Sven Panne vorgeschlagen.

zum Seitenanfang

Einfache Metainterpretierer

Der einfachste PROLOG-Metainterpretierer für PROLOG-Programme ist wohl das folgende Programm:

45


demo(X) :- X.

Ein einfacher Metainterpretierer, der jedoch die Auswertung näher spezifiziert, ist:

46


demo(true)    :- !.
demo( (X,Y) ) :- !, demo(X), demo(Y).
demo(X)       :- clause(X, Rumpf), demo(Rumpf).

Bemerkung: In vielen PROLOG-Systemen muß, um das Systemprädikat clause auf Klauseln, d.h. Fakten und Regeln, anwenden zu können, das durch diese Klauseln definierte Relationssymbol als dynamisch deklariert worden sein.

3. All-Antwort- und Systemprädikate berücksichtigen

Die Metainterpretierer P₄₆ und P₄₇ sind unzufriedenstellend, wenn sie auf Objektprogramme angewandt werden, die PROLOG-Systemprädikate oder All-Antwort-Prädikate aufrufen. Das folgende Programm verbessert P₄₆ in diesem Punkt:

48


demo(true)             :- !.
demo( (X,Y) )          :- !, demo(X), demo(Y).
demo(findall(X, Y, Z)) :- !, findall(X, demo(Y), Z).
demo(X^A)              :- !, X^demo(A).
demo(bagof(X, Y, Z))   :- !, bagof(X, demo(Y), Z).
demo(coverof(X, Y, Z)) :- !, coverof(X, demo(Y), Z).
demo(setof(X, Y, Z))   :- !, setof(X, demo(Y), Z).
demo(X)                :- system(X), !, X.
demo(X)                :- clause(X, Rumpf), demo(Rumpf).

zum Seitenanfang

All-Antwort- und Systemprädikate berücksichtigen

Der Metainterpretierer P₄₆ ist unzufriedenstellend, wenn er auf Objektprogramme angewandt wird, die PROLOG-Systemprädikate oder All-Antwort-Prädikate aufrufen. Das folgende Programm verbessert P₄₆ in diesem Punkt:

48


demo(true)             :- !.
demo( (X,Y) )          :- !, demo(X), demo(Y).
demo(findall(X, Y, Z)) :- !, findall(X, demo(Y), Z).
demo(X^A)              :- !, X^demo(A).
demo(bagof(X, Y, Z))   :- !, bagof(X, demo(Y), Z).
demo(coverof(X, Y, Z)) :- !, coverof(X, demo(Y), Z).
demo(setof(X, Y, Z))   :- !, setof(X, demo(Y), Z).
demo(X)                :- system(X), !, X.
demo(X)                :- clause(X, Rumpf), demo(Rumpf).

4. Metainterpretierer zur Darstellung von Beweisbäumen für "reines PROLOG"

Mit "reines PROLOG" bezeichnet man oft das Fragment von PROLOG ohne Negation und ohne nichtlogische Systemprädikate. Für "reine" PROLOG-Programme liefert der folgende Metainterpretierer die Beweisbäume zu den ausgewerteten Anfragen:

49


:- op(120, xfy, <--). 

demo(true,   true)             :- !.
demo((X,Y), (BeweisX,BeweisY)) :- !, demo(X,BeweisX), demo(Y,BeweisY).
demo(X,     (X <-- BeweisR))    :- clause(X, R), demo(R, BeweisR).

Um verständlich zu sein, müssen Beweisbäume in einer lesbaren Form dargestellt werden. Dies leistet das folgende Programm:

50


darstellen(Baum)             :- darstellen(Baum, 0).
	
darstellen( (X <-- true), E) :- !, einruecken(E), write(X), nl.  
darstellen( (X, Y),       E) :- !, darstellen(X, E),
                                einruecken(E), write("und"), nl, 
                                darstellen(Y, E). 
darstellen( (X <-- Y),    E) :- einruecken(E), write(X), 
                                write(" weil"), nl,
                                Eplus1 is E + 1, darstellen(Y, Eplus1). 
 
einruecken(0) :- !.
einruecken(E) :- write("  "), Eminus1 is E - 1, einruecken(Eminus1).

Die folgende Sitzung bezieht sich auf die Programme P₄₉ und P₅₀:


:- dynamic(kante/2), dynamic(verbunden/2). 

:- [user].
kante(a, b1).
kante(b1, c1).
kante(b1, c2).
kante(a, b2).
kante(b2, c1).
kante(c1, a).

verbunden(X, Y) :- kante(X, Y).
verbunden(X, Y) :- kante(X, Z), verbunden(Z, Y). 

yes.

:- demo(verbunden(a,a), B), darstellen(B).
verbunden(a, a) weil
  kante(a, b1)
  und
  verbunden(b1, a) weil
    kante(b1, c1)
    und
    verbunden(c1, a) weil
      kante(c1, a)

B = verbunden(a, a) <-- 
      (kante(a, b1) <-- true, 
       verbunden(b1, a) <-- 
         (kante(b1, c1) <-- true, 
          verbunden(c1, a) <-- 
            kante(c1, a) <-- true))         More?

Bemerkung: der Wert von B wurde hier zur besseren Verständlichkeit mit Einrückungen versehen, die den Einrückungen bei der Ausgabe von darstellen(B) entsprechen. Das Prolog-System gibt den Wert von B natürlich ohne Einrückungen aus.

zum Seitenanfang

Metainterpretierer zur Darstellung von Beweisbäumen für "reines PROLOG"

Mit "reines PROLOG" bezeichnet man oft das Fragment von PROLOG ohne Negation und ohne nichtlogische Systemprädikate. Für "reine" PROLOG-Programme liefert der folgende Metainterpretierer die Beweisbäume zu den ausgewerteten Anfragen:

49


:- op(120, xfy, <--). 

demo(true,   true)             :- !.
demo((X,Y), (BeweisX,BeweisY)) :- !, demo(X,BeweisX), demo(Y,BeweisY).
demo(X,     (X <-- BeweisR))    :- clause(X, R), demo(R, BeweisR).

5. Behandlung von `cut`

Eine naheliegende Lösung zur Behandlung des Cuts in Objektprogramme ist die folgende Ausarbeitung von Programm P₄₆:

51


demo(true)    :- !.
demo(!)       :- !. 
demo( (X,Y) ) :- !, demo(X), demo(Y).
demo(X)       :- clause(X, Rumpf), demo(Rumpf).

Wie die folgende Sitzung aber zeigt, erfüllt Programm P₅₁ seinen Zweck nicht:


:- dynamic(p/1). 
yes.

:- [user].
p(1).
p(2).
p(3).

yes.

:- p(A), !.
A = 1
yes.

:- demo( (p(A), !) ).
A = 1     More? (;) ;

A = 2     More? (;) ;

A = 3
yes.

:-

Warum? Die zusätzliche Klausel demo(!) :- !. behandelt eigentlich das Cut wie true, d. h. hat nicht den gewünschten Effekt. Die Anfrage


demo( (p(A), !) ).

wird bearbeitet wie


demo(p(A)), demo(!).

d. h. wie


demo(p(A)), demo(true).

d. h. wie


demo(p(A)).

Kein Rücksetzungspunkt wird dadurch beseitigt.

Eine korrekte Behandlung des Cuts in Objektprogrammen erfordert einen etwas raffinierteren Metainterpretierer:

52


demo(X)                :- demo(X, M),  ( M == cut_rueck, !, fail
                                       ; true ).  
		       
		       
demo(_,     M)         :- M == cut_rueck, !, fail.
demo(!,     _). 
demo(!,     cut_rueck) :- !. 
demo(true,  _)         :- !.
demo((X,Y), M)         :- !, demo(X, M),    ( M == cut_rueck, !
                                            ; demo(Y, M) ).
demo(X,     M)         :- clause(X, Rumpf), 
                          demo(Rumpf, M),   ( M == cut_rueck, !, fail
                                            ; true ).

Zum Verständnis mag es helfen, die folgende Sitzung nachzuvollziehen, die sich auf Programm P₅₂ bezieht:


:- dynamic(p/1). 
yes.

:- [user].
   p(1).
   p(2).
   p(3).

yes.

:- demo( (p(A),!), M ).

A = 1
M = M     More? (;) ;

A = 1
M = cut_rueck     More? (;) ;

A = 2
M = M     More? (;) ;

A = 2
M = cut_rueck     More? (;) ;

A = 3
M = M     More? (;) ;

A = 3
M = cut_rueck
yes.


:- demo( (p(A),!) ).

A = 1     More? (;) ;

no (more) solution.

Die folgende Sitzung zeigt das korrekte Verhalten in einem komplizierteren Fall:


:- dynamic(p/1), dynamic(q/1), 
   dynamic(r/1), dynamic(s/1), dynamic(t/1).
yes.

:- [user].
   p(Z) :- q(Z).
   p(Z) :- t(Z).
   
   q(Z) :- r(Z), !.
   q(Z) :- s(Z).
   
   r(1).
   r(2).
   
   s(3).
   s(4).
   
   t(a).
   t(b).

yes.

:- demo( p(Z) ).

Z = 1     More? (;) ;

Z = a     More? (;) ;

Z = b
yes.

Bemerkungen:

In demo/1 sowie in der ersten und letzten Klausel von demo/2 wird !,fail statt not verwendet, um ein unerwünschtes Rücksetzen über die Disjunktion zu vermeiden. Man überprüfe, warum die folgende Definition von demo/1 nicht das Gewünschte leisten würde:
demo(X) :- demo(X,M), M \== cut_rueck.

zum Seitenanfang

Behandlung von `cut` (1)

Eine naheliegende Lösung zur Behandlung des Cuts in Objektprogramme ist Programm P₅₁ (als Ausarbeitung von Programm P₄₆).

Wie die folgende Sitzung aber zeigt, erfüllt Programm P₅₁ seinen Zweck nicht:


:- dynamic(p/1). 
yes.

:- [user].
p(1).
p(2).
p(3).

yes.

:- p(A), !.
A = 1
yes.

:- demo( (p(A), !) ).
A = 1     More? (;) ;

A = 2     More? (;) ;

A = 3
yes.

:-

Behandlung von `cut (2)`

Warum? Die zusätzliche Klausel demo(!) :- !. behandelt eigentlich das Cut wie true, d. h. hat nicht den gewünschten Effekt. Die Anfrage


demo( (p(A), !) ).

wird bearbeitet wie


demo(p(A)), demo(!).

d. h. wie


demo(p(A)), demo(true).

d. h. wie


demo(p(A)).

Kein Rücksetzungspunkt wird dadurch beseitigt.

V. Programme als Daten: Metainterpretation

PROLOG-Hilfsprädikate und -programme

1. Metainterpretation

Metainterpretation

2. Einfache Metainterpretierer

Einfache Metainterpretierer

3. All-Antwort- und Systemprädikate berücksichtigen

All-Antwort- und Systemprädikate berücksichtigen

4. Metainterpretierer zur Darstellung von Beweisbäumen für "reines PROLOG"

Metainterpretierer zur Darstellung von Beweisbäumen für "reines PROLOG"

5. Behandlung von cut

Behandlung von cut (1)

Behandlung von cut (2)

5. Behandlung von `cut`

Behandlung von `cut` (1)

Behandlung von `cut (2)`