4Cut und Not

Bis jetzt wurde das "Pure Prolog" behandelt. Ab diesem Kapitel wird das volle Prolog verwendet, das prozedurale und andere Elemente enthält, die keine direkte Entsprechung in der Logik 1. Ordnung haben. Das wichtigste und grundlegende prozedurale Element ist der Cut. Der Cut wird zur Effizienzsteigerung von Prolog-Programmen, zur Implementierung von höheren Kontrollstrukturen und zur Realisierung einer Prolog-Negation verwendet. Er wirkt auf die prozedurale Ausführung von Prolog Programmen und beeinflusst die deklarative Semantik.

4.1Cut

Beispiel:

min( X, Y, X) :- X =< Y.
min( X, Y, Y) :- X > Y.
?- min( 1, 2, Z).  ⇒  Z = 1 ; no 

Bei Backtracking wird die zweite Klausel versucht, obwohl es keine weiteren Lösungen gibt. Effizienzverlust!

Beispiel:

sort( X, Y) :- 
    permutation( X, Y), 
    ordered( Y).

Bei Backtracking werden weitere (ca. n!/2 Permutationen) versucht, obwohl es keine weiteren (verschiedenen) Lösungen gibt. Effizienzverlust!

Das eingebaute Prädikat Cut '!' verhindert die Suche nach weiteren Lösungen, wenn es sie nicht gibt, oder wenn sie nicht interessieren.

Beispiel:

min( X, Y, X) :- X =< Y, !.
min( X, Y, Y) :- X >= Y.

Erklärung:

1. Sobald der Cut ausgeführt wird, wird die Alternativklausel bei Backtracking nicht mehr berücksichtigt.
   Beispiel:
   sort( X, Y) :- permutation( X, Y), ordered( Y), !.
2. Sobald der Cut ausgeführt wird, wird kein Backtracking links von Cut durchgeführt.

Diese Cuts ändern die Logik des Programms nicht und könnten wieder entfernt werden. Da sie ungefährlich sind, heissen sie auch "green cuts". Ihre Bedeutung liegt in der Effizienzverbesserung bei (deterministischen) Prädikaten durch "Abschneiden" von Ästen des Beweisbaumes, die nicht interessieren.

Der Test in der 2. Klausel von min scheint überflüssig zu sein und wird im folgenden Beispiel weggelassen:

min( X, Y, X) :- X =< Y, !.
min( X, Y, Y).

1. Das Programm ist logisch nicht korrekt, da:
   ?- min( 1, 2, 2)   => yes
   Der Cut wird nicht ausgeführt, da das Goal nicht mit dem Kopf der ersten Klausel unifi-ziert, und die zweite Klausel ergibt Success.
2. Durch Entfernen des Cuts entsteht ein falsches Programm. Dann ist nämlich:
   ?- min( 1, 2, Z)   => Z = 1; Z = 2; no

Die Logik des Programms hat sich verändert und kann nur noch prozedural erklärt werden. Die Klauseln können z.B. nicht vertauscht werden. Der nun vorhandene gefährliche Cut heisst "red cut". Er hat nur eine prozedurale Semantik und darf nicht entfernt werden. Er sollte nach Möglichkeit vermieden werden. Das Programm für min, das in der Allgemeinheit falsch ist, wird in der Praxis doch benutzt. Es ist richtig unter der Einschränkung, dass das dritte Argument von min beim Aufruf nicht instantiiert ist, sondern durch min berechnet wird.

Definitionen:

Parent Klausel:	Klausel, deren Body den Cut enthält.
Parent Goal:	Head der Parent Klausel.
Alternativ­klauseln:	Klauseln mit dem gleichen Head (Funktor + Arität) wie die Parent Klausel.

Beispiel:

a :- b, c, !, d, e. /* Parent Klausel; a ist Parent Goal */
a :- f, g. /* Alternativklausel */

Prozedurale Semantik von Cut:

1. Der Cut ist wirksam, nur wenn er ausgeführt wird. Ein durch den Programmablauf nicht ausgeführter Cut hat keine Bedeutung.
2. Falls der Cut noch nicht ausgeführt wurde, wird in allen Subgoals links vom Cut (b, c) ein normales Backtracking durchgeführt.
3. Der erste Aufruf von Cut (CALL) ergibt Success. Jetzt wird der Cut wirksam und bildet eine Barriere, die nach links nicht überschritten werden kann. In den Goals rechts vom Cut (d, e) wird weiterhin ein normales Backtracking durchgeführt. Sobald aber das erste REDO vom Cut versucht wird, ergeben der Parent Goal und alle Alternativ-klauseln eine Failure.

Beispiel:

stadt( baden). 
klein( baden).
stadt( london).
gross( london).
stadt( basel).
klein( basel).
stadt( paris).
gross( paris).
gross_stadt( S) :- 
    stadt( S), gross( S).
gross_stadt( rom).
?- gross_stadt( S).  ⇒  S = london; S = paris; S = rom; no

Änderungen im Programm - Ersetzung der jeweiligen Klauseln durch die folgenden:

/* 1 */
stadt( baden) :- !.
?- gross_stadt( S). 
 ⇒  S = rom; no

/* 2 */
stadt( basel) :- !.
?- gross_stadt( S). 
 ⇒  S =  london; S = rom; no

/* 3 */
gross_stadt( S) :- !, 
    stadt( S), gross( S).
?- gross_stadt( S). 
 ⇒  S =  london; S = paris; no

/* 4 */
gross_stadt( S) :- 
    stadt( S), !, gross( S).
?- gross_stadt( S). 
 ⇒  no

/* 5 */
gross_stadt( S) :- 
    stadt( S), gross( S), !.
?- gross_stadt( S). 
 ⇒  S =  london; no

Probleme mit Cut am Beispiel einer Klassifikation:

n( X, N) = N ist die Anzahl Eltern von X. Eva und Adam haben 0, alle anderen 2 Eltern.

n1( adam, 0).
n1( eva, 0).
n1( _, 2).
?- n1( adam, N). 
 ⇒  N = 0; N = 2 /* FALSCH */ 

n2( adam, 0) :- !.
n2( eva, 0) :- !.
n2( _, 2).
?- n2( adam, 2). 
 ⇒  yes /* FALSCH */ 

n3( adam, N) :- !, N = 0.
n3( eva, N) :- !, N = 0.
n3( _, 2).
?- n3( X, N). 
 ⇒  X = adam, N = 0; no /* FALSCH */ 

n4( adam, 0).
n4( eva, 0).
n4( X, 2) :- X \= adam, X \= eva.
?- n4( X, 2). 
 ⇒  no /* "FALSCH", siehe n5 */ 

n5( adam, 0).
n5( eva, 0).
n5( X, 2) :- 
    X \== adam, 
    X \== eva.
    /* richtig, aber unschön */ 
?- n5( X, 2). 
 ⇒  X = X

Bei der Verwendung vom Cut zur Klassifikation, wird meistens der Modus des Aufrufs vereinbart, z.B. n( X, N) wird nur verwendet, wenn X instantiiert und N nicht instantiiert ist. Dann ist die Variante n2( X, N) richtig und käme zum Einsatz. Das eingebaute Prädikat var(X) ist in solchen Problemen oft nützlich.

If-Then-Else

Mit Cut können höhere Kontrollstrukturen implementiert werden, z.B. if-then-else.

Beabsichtigte Bedeutung:

a = if b1 then a1
    else if b2 then a2
    else a0.

Implementierung mit Cut:

a :- b1, !, a1.
a :- b2, !, a2.
a :- a0.

Implementierung mit den Operatoren -> und ; (vordefiniert durch Prolog):

a :- (b1 -> a1
    ; b2 -> a2
    ; a0).

4.2Not

Beispiel:

giftig( X) :- 
    pilz( X), rot( X).
pilz( fliegenpilz).
rot( fliegenpilz).
pilz( steinpilz).
essbar( X) :- 
    giftig( X), !, fail.
essbar( X).

fail ist ein eingebautes Prädikat, das immer Failure ergibt. "!, fail" heisst auch die Cut / fail - Kombination.

1. Wenn X giftig ist (giftig( X) liefert Success), dann wird fail ausgeführt und liefert Failure. Wegen des ausgeführten Cuts wird die zweite Klausel nicht versucht, und das Prädikat essbar( X) liefert Failure.
2. Wenn X nicht giftig ist (giftig( X) liefert Failure), dann wird durch Backtracking die zweite Klausel versucht und das Prädikat essbar( X) liefert Success.

essbar( X) ist also eine Art Negation von giftig( X). Diese Technik der "Negation" wird allgemein verwendet. Es gibt das vordefinierte Prädikat 'not' der Arität 1 (not ist auch ein Präfix-Operator), das folgendermassen definiert werden könnte:

not( P) :- call( P), !, fail. /* analog wird not P definiert */
not( P).

call( P) ist ein vordefiniertes Prädikat. Die Variable P kann dynamisch an einen beliebigen Term T gebunden werden. Die Lösung von call( P) ist dann gleichbedeutend mit der Lösung von T.

Unter Verwendung von not ist:

/* Eingebauter Operator not: */
essbar( X) :- not giftig( X).

/* Eingebautes Prädikat not: */
essbar( X) :- not (giftig( X)).

Es gilt allgemein:

not P => Success,  wenn P => Failure
not P => Failure,   wenn P => Success.

Diese Definition der "Negation" heisst "Negation by Failure".

Beachte:

?- essbar(fliegenpilz).  ⇒  no
?- essbar(steinpilz).  ⇒  yes
?- essbar(X).  ⇒  no /* Cut wurde ausgeführt */

Es wurde nicht der essbare Steinpilz gefunden! Die Negation kann nur als ein Test mit instantiierten Variablen verwendet werden; nicht instantiierte Variablen werden nicht gebunden. Wenn pilz (fliegenpilz) aus der Prolog Datenbank entfernt wird, dann:

?- essbar(X)  ⇒  yes /* X = _97 */

Semantik

Negation by Failure (not P) hat intuitiv die Bedeutung von ¬ P, entspricht aber nicht ganz der klassischen Negation in der Logik. Um dies zu verstehen, muss die deklarative (logische) Semantik der Prolog-Programme präzisiert werden. Bis jetzt wurden Prolog-Programmklauseln als "wahre" Aussagen betrachten. Der Wahrheitswert (true oder false) einer Aussage ist jedoch relativ und kann eigentlich beliebig gesetzt werden. Die Zuordnung von Wahrheitswerten zu Aussagen heisst Interpretation. Es gibt Aussagen, die immer wahr sind, z.B.:

A ∨ ¬ A
A ⇒ A
[A ∧ A⇒ B)] ⇒ B (Modus Ponens)

Sie heissen gültige Aussagen. Es gibt auch Aussagen, die immer den Wert false ergeben (z.B. A ∧ ¬ A); sie heissen widersprüchliche Aussagen.

Annahme: Ein Prolog-Programm besteht aus den Klauseln P1, P2, ..., Pn. Diese Klauseln können einen beliebigen Wahrheitswert haben. Wenn nun ein Goal G bewiesen wird ("yes"), dann ist die Aussage

P1 ∧ P2 ∧ . . .∧ Pn ⇒ G

gültig (hat immer den Wahrheitswert true). Dies kann auch folgendermassen ausgedrückt werden: Wenn den Klauseln P1, P2, ..., Pn der Wahrheitswert true zugeordnet wird, und der Goal G bewiesen wird, dann hat auch er garantiert den Wahrheitswert true. Die Programmklauseln spielen also die Rolle von Axiomen bei der Ableitung von Goals.

Beispiel: Programm 1:

a.
?- a.  ⇒  yes /* Logik: "a ⇒ a" ist gültig */
?- b.  ⇒  no  /* Logik: der Wahrheitswert von b kann beliebig sein*/

Wenn die Frage ?- G mit "no" beantwortet wird, so tendiert der Programmierer zur Interpretation "G ist immer false", resp. "¬ G ist immer true". Diese Interpretation steht jedoch nicht im Einklang mit der Logik, die in diesem Fall keine Aussage über den Wahrheitswert von G machen kann, da G eigentlich nichts mit den Programmklauseln zu tun hat (s. Beispiel: Programm 1).

Die Betrachtungsweise des Prolog-Programmierers wäre richtig, wenn man festlegen würde, dass nur solche Interpretationen berücksichtigt werden, die den Programmklauseln den Wahrheitswert true und allen anderen Aussagen, die nicht im Programm sind und sich nicht herleiten lassen den Wert false zuordnen. Diese Vereinbarung heisst "Closed World Assumption (CWA)". Es wird angenommen, dass das Prolog-Programm genau alle wahre Grundaussagen repräsentiert. Falls eine Aussage nicht im Programm ist, oder nicht abgeleitet werden kann, so wird sie als falsch (false) betrachtet.

Beispiel: Programm 2 (Der Fakt b wurde zum Programm 1 zugefügt):

b.
?- a.  ⇒  yes /* Logik: "a ∧ b ⇒ a" ist gültig */
?- b.  ⇒  yes /* Logik: "a ∧ b ⇒ b" ist gültig */

Durch die Zunahme des Faktes b hat sich die Gültigkeit von b in der Prolog-Interpretation völlig geändert. Prolog ist nicht monoton. Dies ist in der klassischen Logik nicht möglich: Durch die Zunahme neuer Fakten werden die vorher abgeleiteten Fakten nicht beeinflusst (Monotonie der Logik).

Die Negation in Prolog sollte nur als Test benutzt werden! Auch wenn die Negation in Prolog Success ergibt, werden dadurch keine Variablen instantiiert! 'Not ' ist nicht backtrackable.

Beispiel:

?- X = 1, X \= 2  ⇒  yes  /* Logik: true */
?- X \= 2, X = 1  ⇒  no   
/* X = 2 => Success, 
also X \= 2 => Failure.
Logik: true */