Prolog - Unterschiede zwischen Rot- und Grünschnitt

Question

Ich fing an, Prolog zu lernen, und wollte das Ganze klarer machen. Ich habe gelesen, dass "grüner Schnitt nicht deklarative Bedeutung des Programms ändert, während roter Schnitt tut". Aber, die Bedeutung des Programms ist nicht wirklich rein deklarativ (nur aus der Tatsache, dass Prolog tatsächlich für alle Optionen Backtracks). Hier

ein Beispiel:

p(1). 
p(2) :- !. 
p(3). 

es gesagt wurde, dass es sich dabei grün geschnitten. Aber wenn ich laufe dies:

p(X), X =:= 3. 

ich bekommen „true“ ohne Schnitt, und „falsch“ mit einem Schnitt. also, was vermisse ich?

Vielen Dank im Voraus.

Answer 1

Der Schnitt ist sehr geradlinig operativ zu interpretieren, oder wenn Sie es vorziehen, prozedural. Da jedoch die Mehrheit der Literatur zu den Themen Logikprogrammierung und Prolog eine Tendenz zu der deklarativen Bedeutung von Prolog-Programmen hat (aus guten Gründen), ergeben sich Schwierigkeiten bei der Erklärung des Schnitts. Ein Versuch, dies zu korrigieren, besteht darin, Schnitte abhängig von ihren Auswirkungen zu "färben".

Hier ist mein Versuch, alles noch weniger klar zu machen.

Die operative Bedeutung des Schnittes

1. Von SWI-Prolog's reference manual. „Alles Wahl Punkte verwerfen, da der Eingabe des Prädikats erstellt, in dem der Schnitt Mit anderen Worten erscheint, verpflichten, in dem die Klausel der Schnitt erscheint und verwerfen Auswahlpunkte, die durch Ziele links neben dem Schnitt in der aktuellen Klausel erstellt wurden. "

2. Von "The Art of Prolog" by Sterling and Shapiro. "Ziel erfolgreich und verpflichtet Prolog zu allen getroffenen Entscheidungen, da das übergeordnete Ziel mit dem Kopf der Klausel vereinigt wurde der Schnitt in auftritt [Hervorhebungen nicht meins] Obwohl diese Definition abgeschlossen ist und präzise, ​​seine Auswirkungen und Auswirkungen sind nicht immer intuitiv klar oder offensichtlich. "

3. Von "The Craft of Prolog" by O'Keefe. „[Der Schnitt], um den Stapel der Wahl Punkte beschneidet zurück, wo es war, als das Prädikat, das lexikalisch den Schnitt enthält genannt wurde Ein anderer Weg, dies zu sagen ist, dass der Schnitt gelingt und begeht Prolog zu alle Entscheidungen genannt wurde [wieder, die Betonung nicht meins]“

ich schlage vor, Sie in den Abschnitten über den Schnitt und seine Verwendungen zumindest aus den beiden Bücher gelesen oben zitierten, da das übergeordnete Ziel gemacht. Es wird Ihnen auf jeden Fall helfen zu verstehen, was eigentlich vor sich geht.

Eine häufige Diskussion ist der Unterschied zwischen dem Finden von Lösungen vs. Antworten und Beweisen. Wir (Benutzer, Programmierer) wollen normalerweise Antworten. Das Ergebnis der Auswertung von Prolog-Prädikaten ist Lösungen. Prolog sucht jedoch nach Proofs.

Um Ihr Beispiel zu nehmen. Sie haben die Datenbank p(1). p(2). p(3).. Sie wollen jetzt Prolog fragen: „Gibt es eine p(X) so dass X =:= 3,

?- p(X), X =:= 3. 
X = 3. 

Sie erhalten eine einzige Lösung, X = 3 Sie auch eine Antwort auf Ihre Frage bekommen. Ja, es ist so ein p(X) und X 3, und es gibt eindeutig keine Antworten mehr.

(die Abfrage ?- p(X), X =:= 2. versuchen. ist es identisch zur ursprünglichen Abfrage verhalten?)

Ihr Beweisbaum kann (in einer Art und Weise) gesehen werden, indem die Abfrage Tracing:

?- trace(p/1), trace(=:=). 
%   p/1: [call,redo,exit,fail] 
%   (=:=)/2: [call,redo,exit,fail] 
true. 

[debug] ?- p(X), X =:= 3. 
T Call: (7) p(_G1004) 
T Exit: (7) p(1) 
T Call: (7) 1=:=3 
T Fail: (7) 1=:=3 
T Redo: (7) p(_G1004) 
T Exit: (7) p(2) 
T Call: (7) 2=:=3 
T Fail: (7) 2=:=3 
T Redo: (7) p(_G1004) 
T Exit: (7) p(3) 
T Call: (7) 3=:=3 
T Exit: (7) 3=:=3 
X = 3. 

Grundsätzlich ist jede der Klauseln p/1 wird versucht, wiederum. Die ersten beiden ergeben keinen Beweis, da das zweite Teilziel der Konjunktion versagt. Die Suche nach einem Beweis wird jedes Mal ab dem letzten Auswahlpunkt fortgesetzt (der nächste Satz von p/1). Der letzte kann nachgewiesen werden, und Sie erhalten eine Lösung und eine Antwort auf Ihre Anfrage.

Jetzt fügen Sie einen Schnitt in den Körper des zweiten Satzes von p/1: p(1). p(2) :- !. p(3).. Sie sagen Prolog (in Bezug auf Definition 3. von oben), "wenn die Suche nach einem Beweis den zweiten Satz von p/1 erreicht, den einen, der sein Argument mit 2 vereinheitlicht, den Stapel der Wahlpunkte auf den Punkt abschneidet, wo er war, als p/1 war namens." Wenn p/1 aufgerufen wurde, gab es keine Auswahlpunkte. Wenn also X =:= 3 fehlschlägt, ist die Suche nach einem Beweis abgeschlossen, die Verbindung kann nicht bewiesen werden, es gibt keine Lösungen, und Sie erhalten keine Antworten.

(Versuchen Sie, die Abfrage ?- p(X), X =:= 2.. Ist es identisch mit der gleichen Abfrage, wenn Sie nicht den Schnitt haben?)

Nun zu den Farben ..... Im Rahmen der Verbindung p(X), X =:= 3., diese schnitt eine Lösung und einen Beweis ab. Du hast die Antwort, die du erwartet hast, nicht bekommen. Dieser Schnitt ist rot.

Es wäre schön, wenn wir Prolog sagen könnten, dass wir einen Schnitt entweder grün oder rot (oder grün oder grün oder rot oder blau) meinen, aber Prolog erlaubt uns das nicht. Die "Farbe" ist eine Folge der beabsichtigten Bedeutung des Programms (der Absicht des Programmierers) und der operativen (prozeduralen) Auswirkungen des Schnitts.

Aber wirklich, versuchen Sie, ein Buch zu bekommen und lesen Sie den Abschnitt über Schnitte. Oder sogar zwei Bücher.