10: Cut, Negation

Zu den Aufgaben Folien ansehen Musterlösungen herunterladen

Das Prädikat fail/0

Das Prädikat fail/0 scheitert immer.
Es erzwingt Backtracking und kann zur Ausgabe aller Lösungen eingesetzt werden:

all(L):-
    member(X,L),
    write(X),nl,
    fail.
all(_).
?- all([a,b,c]).
a
b
c
true.

Umgang mit dem Cut

Schattenseiten des Cuts

Der Cut zerstört die Deklarativität von Prolog-Programmen.
Die Interpretation einer Prädikatsdefinition mit roten Cuts ist i.d.R. nur noch unter Berücksichtigung der Reihenfolge der Beweisschritte möglich.
Deshalb: Cut nur einsetzen, wenn ein offensichtlicher Vorteil erzielt werden kann.

Gründe für die Verwendung des Cuts

Beschneiden des Suchraums.
Erzwingen von Determinismus.
Modellierung von Defaults.
Modellierung von Negation.

Der Cut

Der Cut „!“ ist ein eingebautes Prädikat, mit dem Backtracking kontrolliert werden kann.

Der Cut kann folgendes bewirken:

Effizienzsteigerung
Speichereinsparung
Kürzere Programme

Wirkungsweise

Der Cut wird im Rumpf von Regeln eingesetzt und verhindert Backtracking.
Der Top-Down-Beweis des Cut gelingt immer.
Nach dem Passieren eines Cuts in einem Regelrumpf sind
- die Teilziele, die in demselben Regelrumpf vor dem Cut stehen, und
- alle weiteren Klauseln desselben Prädikats, die hinter der Regel stehen,
vom weiteren Backtracking ausgeschlossen.

Grüne und rote Cuts

In der Literatur wird oft zwischen roten und grünen Cuts
unterschieden.

Ein grüner Cut kann aus einem Programm entfernt werden, ohne dass sich die Bedeutung des Programms ändert.
Ein roter Cut kann nicht aus einem Programm entfernt werden, ohne dass sich die Bedeutung des Programms ändert.

max/3 mit grünem, rotem und ohne Cut

ohne Cut:

max(X,Y,Y) :- X =< Y.
max(X,Y,X) :- X>Y.

ineffizient!

?- max(3,5,X).
1 Call: max(3,5,_487) ?
2 Call: 3=<5 ?
2 Exit: 3=<5 ?
1 Exit: max(3,5,5) ?
X = 5 ? ;
1 Redo: max(3,5,5) ?
2 Call: 3>5 ?
2 Fail: 3>5 ?
1 Fail: max(3,5,_487) ?
false.

mit grünem Cut:

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

gut!

?- max(3,5,X).
1 Call: max(3,5,_487) ?
2 Call: 3=<5 ?
2 Exit: 3=<5 ?
1 Exit: max(3,5,5) ?
X = 5 ? ;
false.

mit rotem Cut

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

falsch!

?- max(3,5,3).
true.

Cut: Beschneiden des Suchraums

my_member(H,[H|_]):- !.
my_member(H,[_|T]):- my_member(H,T).
?- my_member(b,[a,b,c]).
true.
?- my_member(d,[a,b,c]).
false.
?- my_member(X,[a,b,c]). X=a.
true.
?- my_member(a,X). X=[a|G_1].
true.

Die Beschneidung des Suchraums führt zu Determinismus.

Beschneidung des Suchraums – delete_first

L2 entsteht durch das Löschen eines Vorkommens von X aus L1.

% delete_once(X,L1,L2)
delete_once(X,[X|L1],L1).
delete_once(X,[H|T1],[H|T2]):-
delete_once(X,T1,T2).
?- delete_once(a,[a,b,c,a,d],L).
L = [b, c, a, d] ;
L = [a, b, c, d] ;
false.

L2 entsteht durch das Löschen des ersten Vorkommens von X aus L1.

% delete_first(X,L1,L2).
delete_first(X,[X|L1],L1):-!.
delete_first(X,[H|T1],[H|T2]):-
delete_first(X,T1,T2).
?- delete_first(a,[a,b,c,a,d],L).
L = [b, c, a, d].

Erzwingung von Determinismus – Fakultät

Lösung nicht deterministisch:

fak(N,R):-
    fak(N,1,R).
fak(0,Acc,Acc).
fak(N,Acc,R):-
    AccNew is N * Acc,
    NNew is N - 1,
    fak(NNew,AccNew,R).

Problem: Prädikat im Backtracking ⇒ Endlosschleife

Verbesserung durch Kontrollabfrage

fak(N,R):-
    fak(N,1,R).
fak(0,Acc,Acc).
fak(N,Acc,R):-
    N > 0,
    AccNew is N * Acc,
    NNew is N - 1,
    fak(NNew,AccNew,R).
?- fak(5,X). X=120;
false.

Determinismus durch Cut:

fak(N,R):-
    fak(N,1,R).
fak(0,Acc,Acc):-!.
fak(N,Acc,R):-
    AccNew is N * Acc,
    NNew is N - 1,
    fak(NNew,AccNew,R).
?- fak(5,X). X=120.

neg(A):-
    A,
    !,fail.
neg(_).

hund(snoopy).
hund(pluto).
katze(garfield).
?- neg(katze(pluto)).
true.
?- \+ katze(pluto).
true.
?- neg(katze(X)).
false.
?- \+ katze(X).
false.

Negation als „negation as failure“

Negation wird in Prolog durch eine Cut-FailKombination realisiert („negation as failure“)

Z. 2: Wenn der Ausdruck A bewiesen werden kann,

Z. 3: sorgt die Cut-Fail-Kombination dafür, dass der der Beweis von neg(A) scheitert. Der Cut hinter A und vor fail verhindert, dass die zweite Klausel von neg(A) für eine beweisbare Aussage A herangezogen werden kann.

Z. 4: Greift die erste Klausel nicht, ist A nicht beweisbar und die Negation von A ist wahr.

Das Negationsprädikat ist in Prolog als PräfixOperator + vordefiniert.

Vorsicht: Enthält eine Aussage Variablen und gibt es eine Variablenbelegung, die die Aussage wahr macht, ist die Negation der Aussage falsch.

if-then-else

ifthenelse(If,Then,_):-
    If,
    Then.
ifthenelse(If,_,Else):-
    \+ If,
    Else.

Drei Aussagen If, Then und Else erfüllen die
if-then-else-Relation, wenn

Z. 6-8: entweder If und Then beweisbar sind oder

Z. 9-11: If nicht beweisbar und Else beweisbar ist.

Beispiel: max/3 mit ifthenelse/3:

max(X,Y,Z):- ifthenelse(X=<Y,Y=Z,X=Z).

Wenn X kleiner oder gleich Y ist, so ist Y das Maximum von X und Y.
Wenn X nicht kleiner oder gleich Y ist, so ist X das Maximum von X und Y.

Probleme mit cut-fail Definition der Negation

neg(A):-
     A,
     !,fail.
neg(_).
ledigerStudent(X):-
     neg(verheiratet(X)),
     student(X).
student(peter).
verheiratet(klaus).
?- ledigerStudent(peter).
true.
?- ledigerStudent(klaus).
false.
?- ledigerStudent(X).
false.

Z. 6-8: X ist lediger Student, wenn X
nicht verheiratet ist und wenn
X Student ist.

„Negation as failure“ ist keine logische Negation. Daher kann das Prädikat ledigerStudent/1 in dieser Form nicht zur Generierung aller ledigen Studenten eingesetzt werden.
Sehen Sie einen einfachen Weg, das Prädikat zu verbessern?

cut-fail und default

mit cut-fail direkt

can_fly(X):-
    penguin(X),
    !, fail.
can_fly(X):- bird(X).
bird(X):- penguin(X).
bird(X):- eagle(X).
penguin(tweety).
eagle(klaus).

schlecht!

?- can_fly(tweety).
false.
?- can_fly(klaus).
true.
?- can_fly(popeye).
false.
?- can_fly(X).
false.

mit Negation (Version 1)

can_fly(X):-
    neg(penguin(X)),
    bird(X).
bird(X):- penguin(X).
bird(X):- eagle(X).
penguin(tweety).
eagle(klaus).

ebenso schlecht!

?- can_fly(tweety).
false.
?- can_fly(klaus).
true.
?- can_fly(popeye).
false.
?- can_fly(X).
false.

mit Negation (Version 2)

can_fly(X):-
    bird(X),
    neg(penguin(X)).
bird(X):- penguin(X).
bird(X):- eagle(X).
penguin(tweety).
eagle(klaus).

gut!

?- can_fly(tweety).
false.
?- can_fly(klaus).
true.
?- can_fly(popeye).
false.
?- can_fly(X). X=klaus.
true.

Zusammenfassung

Wir haben das Prädikat fail/0 kennengelernt, das immer scheitert.
Wir haben den Cut kennengelernt und gesehen, wie man Negation in Prolog als „negation as failure“ definieren kann.
Wir haben gelernt zwischen roten und grünen Cuts zu unterscheiden.
Wichtig: Cuts zerstören die Deklarativität von Prologprogrammen und sollten daher mit Bedacht eingesetzt werden.
Keywords: „negation as failure“, roter und grüner Cut, Cut-Fail-Kombination