LbP Theoretische Grundlagen

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Abstrakter Interpreter für Logikprogramm 1.1 Informelle Beschreibung des Verfahrens 1.2 Algorithmus 1.3 Formelle Beschreibung der Interpretation 1.4 Unendlich viele Lösungen 1.5 Welches Ziel ist das nächste? 1.6 Welche Regel wählt man aus?

Abstrakter Interpreter für Logikprogramm

Informelle Beschreibung des Verfahrens

...

Algorithmus

Input

Ein Ziel und ein Programm

Output

Eine Instanz von , d.h. eine logische Konsequenz von , anderenfalls no.

Algorithmus

Initialisiere die Resolvente mit G.

Solange die Resolvente nicht leer ist, tue

• Wähle ein Ziel A aus der Resolvente
  
• Wähle eine (umbenannte) Klausel von P, so dass und mit dem allgemeinsten Unifikator unifiziert werden. (Falls kein solches Ziel und derartige Klausel existieren, verlasse den Zyklus.)
  
• Substituiere durch in der Resolvente.
  
• Wende auf die Resolvente und auf an.
  

Wenn die Resolvente leer ist, gib G aus, ansonsten no.

Beispiel

...

Formelle Beschreibung der Interpretation

...

Unendlich viele Lösungen

Die Lösungen zu einer Frage können auch Variablen sein.

mymember(X,[X|Xs]). mymember(X,[Y|Ys]) :- mymember(X,Ys).

Erwartungsgemäss liefert die variablenfreie Anfrage die Lösung Yes.

mymember(3,[1,2,3,4,5]).

ausführen

Demgegenüber wird bei

mymember(3,X).

ausführen

eine Variable, deren Name bisher noch nicht vorgekommen ist, generiert.

Man könnte nun meinen, dass derartige Fragen wenig sinnvoll sind, so dass Anfragen, die Variablen enthalten, prinzipiell vermeidbar wären. Dies ist jedoch keineswegs zutreffend. In unserem Beispiel fragen wir nach einer Liste, die die Zahl 3 enthält. Die Frage ist durchaus legitim und es ist sofort klar, dass es unendlich viele solche Listen gibt. Einige davon haben die oben angegebene Gestalt, nämlich die Zahl in der Kopfposition. Übrigens erhalten wir das gleiche Resultat, wenn wir das Systemprädikat member/2 verwenden.

Allgemein charakterisieren Lösungen mit Variablen die unendliche Menge aller ihrer variablenfreien Instanzen.

Welches Ziel ist das nächste?

Die Theorie der Logik-basierten Programmierung beantwortet die Frage so: "Es ist völlig gleichgültig, welches Ziel (als Teil der jeweiligen Resolvente) als nächstes reduziert wird. Falls es eine Lösung gibt, wird sie so oder so gefunden."

In einer entsprechenden (Prolog-)Implementation würde man sicher von links nach rechts arbeiten.

Welche Regel wählt man aus?

Natürlich macht die Frage nur Sinn, wenn es mehrere Regeln im Programm gibt, deren Kopf mit dem gewählten Ziel unifiziert werden kann. Das Verfahren arbeitet nichtdeterministisch, was natürlich nicht bedeutet, dass jede Zufallsauswahl zur Lösung führt. Nur das "Erfolgreiche Raten" führt zum Erfolg - s. Orakel aus der Theoretischen Informatik.

Für die Implementation des Verfahrens zur Bestimmung der nächsten zu versuchenden Regel kommt theoretisch nur die Breitensuche in Frage. Tiefensuche, d.h. fortgesetzte Reduktion bis zur leeren Resolvente oder Sackgasse kann in einen Endloszyklus führen.

Aus Effizienzgründen bevorzugt man trotzdem in den meisten Prolog-Implementationen das Tiefe-zuerst-Verfahren und interpretiert nichtanhaltende Berechnung bzw. Abbruch der Berechnung als Fehlschlag. Für die praktische Programmierarbeit bedeutet das allerdings, dass die Reihenfolge, in der die zu einer Prozedur gehörenden Regeln im Programm notiert werden, signifikant ist. Beispielsweise führt

myappend([X|Xs],Ys,[X|Zs]) :- myappend(Xs,Ys,Zs). myappend([ ],Ys,Ys).

myappend(Xs,[c,d],Ys).

ausführen

zum Abbruch der Berechnung durch Speicherüberlauf, wenn das Prädikat myappend wie folgt definiert wurde.

myappend([X|Xs],Ys,[X|Zs]) :- myappend(Xs,Ys,Zs). myappend([ ],Ys,Ys).

Vertauscht man die beiden Zeilen miteinander,

myappend1([ ],Ys,Ys). myappend1([X|Xs],Ys,[X|Zs]) :- myappend1(Xs,Ys,Zs).

so geht obige Anfrage anders aus:

myappend1(Xs,[c,d],Ys).

ausführen