LbP Cut

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Beeinflussung der eingebauten Suchstrategie 1.1 (Grüner und roter) Cut 1.2 Cut-fail-Kombination und not 1.3 repeat/0

Beeinflussung der eingebauten Suchstrategie

(Grüner und roter) Cut

Der Cut, geschrieben als !, gibt uns die Möglichkeit, in die eingebaute Prolog-Suchstrategie einzugreifen, indem man bestimmte Teilsuchbäume abzuschneidet (cut = abschneiden). Dies kann zur Folge haben, dass dadurch Lösungen, die ohne Cut gefunden werden würden, entfallen. In einem solchen Fall spricht man von einem roten Cut.

Häufig will man Programme dadurch effizienter machen, dass erfolglose Suchwege verboten werden. Wenn auf dennoch die Lösungsmenge und die deklarative Semantik des Programms nicht verändert werden, spricht man von einem grünen Cut. Optisch gibt es zwischen den "verschiedenfarbigen" Cuts keinen Unterschied.

Ein Cut verändert also in jedem Falle die prozedurale Semantik eines Prolog-Programms.

Verallgemeinert gilt für ein Prädikat mit dem Regelkopf P und

P :- K1, K2, K3.
P :- Q1, Q2, !, Q3, Q4.
P :- R1, R2.

1. Die dritte Klausel kommt nach Ausführung des Cuts nicht mehr zum Einsatz.
2. Für Q1, Q2 wird keine (ggf. vorhandene) Alternative benutzt, nachdem der Cut ausgeführt wurde.
3. Q3 und Q4 stehen nach dem Cut und sind von dessen Wirkung unbetroffen, d.h. es kann Backtracking veranlasst werden.

Beispiel: Zusammenführen zweier geordneter Teillisten (zunächst ohne Cut)

mymerge1([X|Xs],[Y|Ys],[X,Y|Zs]) :- X=:=Y, mymerge1(Xs,Ys,Zs). mymerge1([X|Xs],[Y|Ys],[X|Zs]) :- X<Y, mymerge1(Xs,[Y|Ys],Zs). mymerge1([X|Xs],[Y|Ys],[Y|Zs]) :- X>Y, mymerge1([X|Xs],Ys,Zs). mymerge1(Xs,[],Xs). mymerge1([],Ys,Ys).

mymerge1([2,6,12,234],[3,6,24,123,150,290],Ls).

ausführen

Es ist klar, dass mymerge1 für zwei geordnete Listen eine deterministische Operation ist. D.h., wenn entschieden ist, welcher der drei Fälle (=,<,>) zutrifft, gibt es keine Möglichkeit, durch ein späteres Backtrack weitere Lösungen zu finden. Wir können also alle Alternativen von mymerge1 abschneiden, nachdem der Test absolviert wurde. Dies gilt für die ersten drei Klauseln. Dann sieht das Prädikat mymerge1 folgendermassen aus.

Beispiel: Zusammenführen zweier geordneter Teillisten (grüner Cut)

mymerge2([X|Xs],[Y|Ys],[X,Y|Zs]):- X=:=Y, !, mymerge2(Xs,Ys,Zs). mymerge2([X|Xs],[Y|Ys],[X|Zs]):- X<Y, !, mymerge2(Xs,[Y|Ys],Zs). mymerge2([X|Xs],[Y|Ys],[Y|Zs]):- X>Y, !, mymerge2([X|Xs],Ys,Zs). mymerge2(Xs,[],Xs) :- !. mymerge2([],Ys,Ys) :- !.

mymerge2([2,6,12,234],[3,6,24,123,150,290],Ls).

ausführen

Das Ergebnis ist in beiden Fällen das Gleiche, es wird also keine Lösung "weggeschnitten". Die (deskriptive) Semantik des Programms wird im Beispiel durch den Cut nicht beeinflusst. Einen Unterschied in der Abarbeitung erkennt man in einem entsprechenden trace: Bei mymerge1 findet ein Backtrack statt. Dies ist bei mymerge2 nicht der Fall.

Wir illustrieren die Verwendung eines roten Cuts. Beispiel: Minimum zweier Zahlen (zunächst ohne Cut)

minimum1(X,Y,X) :- X=<Y. minimum1(X,Y,Y).

minimum1(2,3,M).

ausführen

Beispiel: Minimum zweier Zahlen (roter Cut)

minimum2(X,Y,Z) :- X=<Y, !, X=Z. minimum2(X,Y,Y).

minimum2(2,3,M).

ausführen

Ohne den Cut würde es bei erzwungener Fortsetzung der Suche von Lösungen zu einem Fehler kommen:

findall(M,minimum1(2,3,M),Ms).

ausführen

Ausserdem würde auch minimum1(2,3,3) als richtig angesehen werden. Probieren Sie es oben aus! Der Cut in minimum2 verhindert dies.

Cut-fail-Kombination und not

Ein Cut kann auf der rechten Seite einer Klausel durchaus alleine stehen, so wie dies bei mymerge2 der Fall ist. Was bedeutet es, wenn man nach dem Cut ein nicht beweisbarer Term folgt, z.B. 3>4, oder einfach fail, also ..., !, fail.?

Dies bewirkt, dass die Suche nicht fortgesetzt wird. Es können beide Cut-Arten vorkommen. Die cut-fail-Kombination wird beispielsweise zur Definition des Metaprädikats not benutzt. (Bei dem hier verwendeten Prolog und vielen anderen ist not eingebaut, aber es ist dennoch interessant darüber nachzudenken, wie es arbeitet. Und dies geschieht am besten dadurch, dass man es mit "Bordmitteln" implementiert.)

Beispiel: Definition von not

not(X) :- X, !, fail. not(X).

not(3<2).

ausführen

not(3>2).

ausführen

Insgesamt sollte man vorsichtig sein im Umgang mit not. Da es ein Prädikat ist, das ein anderes Prädikat benutzt, also ein sog. Metaprädikat, verstösst Prolog damit gegen den Prädikatenkalkül erster Stufe (PK 1). Auf (gefährliche) Konsequenzen gehen wir hier nicht näher ein.

Beispiel: Definition von ungleich

ungleich(X,X) :- !, fail. ungleich(X,Y).

ungleich(2,2).

ausführen

repeat/0

repeat ist ein Sprachelement, das in der imperativen Programmierung fest verankert ist. Ohne die genaue Syntax zu kennen, verbindet es unsere Vorstellung mit Zyklus, insbesondere mit einer Schleife, deren Durchlaufzahl beim Aufruf unbekannt ist.

In Prolog kann man derartige Schleifen als sog. failure-driven-loops erzeugen. Durch Anhängen von fail wird Backtracking veranlasst. Dies ist aber nur dann sinnvoll, wenn Nebenwirkungen stattfinden, wie beispielsweise bei write/1.

between(A,B,A) :- A =< B. between(A,B,C) :- A < B, A1 is A+1, between(A1,B,C). mytab(N) :- between(1,N,I), write(/), fail.

mytab(3).

ausführen

Failure-driven-loops, die repeat verwenden, heißen repeat-loops. Das Prädikat repeat wird folgendermassen definiert.

myrepeat. myrepeat :- myrepeat.

Ein fail, das die Rückkehr zu myrepeat erzwingt, sorgt für unendlich viele Backtracks, denn myrepeat passt immer wieder. Davon kann man sich durch die Analyse der Berechnung des Beweisziels überzeugen.

myrepeat, fail.

ausführen

Stellen Sie einen Unterschied fest, wenn Sie statt myrepeat das Systemprädikat repeat verwenden?

repeat, fail.

ausführen