LbP Cut

Wiki-Quelltext dieser Seite.

== Beeinflussung der eingebauten Suchstrategie ==

===(Grüner und roter) Cut===
Der ''Cut'', geschrieben als <tt>!</tt>, 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 <tt>P</tt> und
 P :- K1, K2, K3.
 P :- Q1, Q2, !, Q3, Q4.
 P :- R1, R2.

# Die dritte Klausel kommt nach Ausführung des Cuts nicht mehr zum Einsatz.
# Für <tt>Q1</tt>, <tt>Q2</tt> wird keine (ggf. vorhandene) Alternative benutzt, nachdem der Cut ausgeführt wurde.
# 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)
<code>
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).
</code>
<run>mymerge1([2,6,12,234],[3,6,24,123,150,290],Ls).</run>

Es ist klar, dass <tt>mymerge1</tt> 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 <tt>mymerge1</tt> abschneiden, ''nachdem'' der Test absolviert wurde. Dies gilt für die ersten drei Klauseln. Dann sieht das Prädikat <tt>mymerge1</tt> folgendermassen aus.

Beispiel: Zusammenführen zweier geordneter Teillisten (grüner Cut)
<code>
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) :- !.
</code>
<run>mymerge2([2,6,12,234],[3,6,24,123,150,290],Ls).</run>

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 <tt>mymerge1</tt> findet ein Backtrack statt. Dies ist bei <tt>mymerge2</tt> nicht der Fall.

Wir illustrieren die Verwendung eines roten Cuts. 
Beispiel: Minimum zweier Zahlen (zunächst ohne Cut)
<code>
minimum1(X,Y,X) :- X=<Y.
minimum1(X,Y,Y).
</code>
<run>minimum1(2,3,M).</run>

Beispiel: Minimum zweier Zahlen (roter Cut)
<code>
minimum2(X,Y,Z) :- X=<Y, !, X=Z.
minimum2(X,Y,Y).
</code>
<run>minimum2(2,3,M).</run>

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

<run>findall(M,minimum1(2,3,M),Ms).</run>
Ausserdem würde auch <tt>minimum1(2,3,3)</tt> als richtig angesehen werden. Probieren Sie es oben aus!
Der Cut in <tt>minimum2</tt> verhindert dies.

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

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 <tt>not</tt> benutzt. (Bei dem hier verwendeten Prolog und vielen anderen ist <tt>not</tt> 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 <tt>not</tt>
<code>
not(X) :- X, !, fail.
not(X).
</code>
<run>not(3<2).</run>
<run>not(3>2).</run>

Insgesamt sollte man vorsichtig sein im Umgang mit <tt>not</tt>. 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 <tt>ungleich</tt>
<code>ungleich(X,X) :- !, fail.
ungleich(X,Y).
</code>
<run>ungleich(2,2).</run>

===<tt>repeat/0</tt>===
<tt>repeat</tt> 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 <tt>fail</tt> wird Backtracking veranlasst. Dies ist aber nur dann sinnvoll, wenn Nebenwirkungen stattfinden, wie beispielsweise bei <tt>write/1</tt>.
<code>
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.
</code>
<run>mytab(3).</run>                            

Failure-driven-loops, die <tt>repeat</tt> verwenden, heißen repeat-loops. Das Prädikat <tt>repeat</tt> wird folgendermassen definiert.
<code>
myrepeat.
myrepeat :- myrepeat.
</code>

Ein <tt>fail</tt>, das die Rückkehr zu <tt>myrepeat</tt> erzwingt, sorgt für unendlich viele Backtracks, denn <tt>myrepeat</tt> passt immer wieder. Davon kann man sich durch die Analyse der Berechnung des Beweisziels überzeugen.
<run>myrepeat, fail.</run>
Stellen Sie einen Unterschied fest, wenn Sie statt <tt>myrepeat</tt> das Systemprädikat <tt>repeat</tt> verwenden?
<run>repeat, fail.</run>