HSG

Aktuelle Seite: HSG/Fächer/Informatik/Prolog

Zitat aus G.Röhner, Informatik mit Prolog, S.30:

So wirkt der Cut

Der Prolog-Interpreter arbeitet nach einem festen Verfahren, das auf Resolution, Backtracking und Unifikation aufbaut. Auf dieses Verfahren kann man keinen Einfluss nehmen, aber man kann die Lösungssuche von Prolog steuern. Erstens durch Anordnung von Fakten und Regeln im Programm, weil die verwendete Resolution die Wissensbasis sequentiell durchsucht und Teilziele von links nach rechts bearbeitet. Zweitens durch Beeinflussung des Backtracking. Backtracking lässt sich mit dem fail-Prädikat erzwingen und mit dem cut-Prädikat verhindern.
Der Cut ist ein nullstelliges Prädikat, das stets erfüllt ist und wie fast alle anderen Systemprädikate deterministisch ist, also nicht reerfüllt werden kann. Den Cut schreibt man mit dem Ausrufezeichen„!". Er wird verwendet, um Zweige des Suchbaums abzuschneiden. Das reduziert die Suchdauer und führt zu effizienteren Programmen. Schneidet man Zweige ab, die keine Lösungen enthalten, so spricht man von grünen Cuts, bei Zweigen mit Lösungen von roten Cuts. Letztere sollte man vermeiden!
Nehmen wir an, zur Erfüllung eines Ziels wird das Prädikat p, zu dem es zwei Klauseln gibt, aufgerufen. 
p:- q1,!, q2.
p:- q3.
Der Cut wird erreicht, wenn das Teilziel q1 erfüllt werden kann. Das Teilziel "!" wird stets erfüllt. Es hat als Seiteneffekt die Wirkung, dass es Prolog auf alle Entscheidungen seit dem Aufruf von p festlegt, d. h. dass kein Backtracking mehr im Ziel q1 sowie in der zweiten p-Regel stattfindet, wohl aber im Ziel q2. Der Cut wirkt also lokal und global:
Die lokale Wirkung bezieht sich auf die Klausel, in der er vorkommt. Er schneidet im Beweisbaum alle noch nicht untersuchten Zweige ab, die im aktuellen Knoten links vom Cut liegen. Die globale Wirkung bezieht sich auf das Prädikat, in der er vorkommt. Die Knoten aller nachfolgenden Klauseln zum selben Prädikat werden abgeschnitten.

Aufgabe

Sagen Sie zu 
p(1).
p(2).
p(3).
die Antworten auf folgende Anfragen voraus: 
?-p(X).
?-p(X),p(Y).
?-p(X),!,p(Y).
Was verändert sich, wenn p(2) durch p(2):-!. ersetzt wird?

Beispiel

Im folgenden Beispiel zu globalen Variablen wird eine nicht existierende Variable neu geschaffen und belegt. Da die zweite Regel den Fall behandelt, dass die Variable existiert, wird die neu geschaffene Variable gleich wieder entfernt und erneut neu geschaffen. 
% Variable 'Var' existiert nicht, wird neu geschaffen und belegt
belege(Var,Wert):-not(variable(Var,_)),assert(variable(Var,Wert)).
% Alle Variablen 'Var' werden entfernt. Variable 'Var' wird neu geschaffen und belegt.
belege(Var,Wert):-retract(variable(Var,_)),assert(variable(Var,Wert)).
Der Cut verhindert dieses Verhalten. 
% Variable 'Var' existiert nicht, wird neu geschaffen und belegt
belege(Var,Wert):-not(variable(Var,_)),assert(variable(Var,Wert)),!.
% Alle Variablen 'Var' werden entfernt. Variable 'Var' wird neu geschaffen und belegt.
belege(Var,Wert):-retract(variable(Var,_)),assert(variable(Var,Wert)).