Prolog-Grundzüge 7: Cut-Operator

July 21, 2009 at 5:49 pm 1 comment


Das Prolog-System sucht stets nach allen möglichen Lösungen für eine Anfrage und liefert diese nacheinander als Ergebnis. Manchmal möchte man das aber gar nicht. Stattdessen ist man mit dem erstbesten Ergebnis vollkommen zufrieden.

Nehmen wir ein selbstgebautes IF-THEN-ELSE-Konstrukt als Beispiel. Eine erste Implementation könnte so aussehen:

if_then_else(P, Q, R) :- P, Q ; R.

Wenn die Bedingung Q wahr ist, wird die Then-Regel Q aktiviert. Wenn Q nicht wahr ist, greift die zweite Definition von “if_then_else” und es wird die Else-Regel R aktiviert. (Wir erinnern uns: Komma bedeutet “und”, Semikolon bedeutet “oder”).

Wenn man die if_then_else-Regel so aktiviert, dass die Else-Bedingung aktiviert wird, ist das Ergebnis erwartungskonform.

if_then_else(false, write('then'), write('else')).

gibt “else” aus und hat “true” als Ergebnis.

Anders sieht es aus, wenn wir “true” als Bedingung übergeben.

if_then_else(true, write('then'), write('else')).

schreibt zuerst “then” und hat “true” als Ergebnis. Aber als nächstes wird “else” ausgegeben und wieder “true” geliefert. Nanu? Was ist denn da los?

Die Ursache ist das Auswertungsverfahren, dass Prolog einsetzt. Zuerst wird geprüft, ob P gilt. Wenn das der Fall ist, wird Q ausgewertet. Und danach wird R auch noch ausgewertet – weil nichts dagegen spricht.

Prolog unterscheidet sich hier von dem, was die meisten anderen Programmiersprachen machen. Die meisten Programmiersprachen brechen die Auswertung eines Ausdrucks ab, wenn die weitere Auswertung das Ergebnis nicht mehr ändern kann. Mit dieser Auswertungsregel bräuchte man R nicht mehr auswerten. Die if_then_else-Regel ist durch den ersten Teil der Oder-Klausel bereits “true”.

Um mit dieser Problematik umzugehen, bietet Prolog den Cut-Operator “!”. Der Cut-Operator setzt eine Grenzlinie, über die Prolog bei der Auswertung einer Regel nicht zurück darf (das sogenannte Backtracking wird eingeschränkt). Mit Hilfe des Cut-Operators sieht unsere if_then_else-Regel so aus:

if_then_else(P, Q, R) :- P, !, Q ; R.

und jetzt verhält sich die Regel auch erwartungskonform.

if_then_else(true, write('then'), write('else')).

schreibt zuerst “then” und hat “true” als Ergebnis und mehr passiert nicht.

Anmerkung: Man hätte den Cut-Operator auch noch eine Position weiter nach hinten schreiben können, also hinter Q.

Prinzipiell gibt es zwei Anwendungsbereiche für den Cut-Operator: Logik und Performance. Wir haben den Cut-Operator angewendet, weil unser Programm sonst nicht richtig funktioniert. Manchmal wendet man den Cut-Operator auch an, um aus Performancegründen unnötige Auswertungen zu unterbinden.

Und leider ist der Cut-Operator nicht-trivial. Mit meinen bisherigen Prolog-Kenntnissen kann ich häufig nicht auf Anhieb sagen, ob und wo genau ein Cut-Operator notwendig ist. Ich sehe erst beim Ausprobieren meiner Regeln, dass sie nicht richtig funktionieren – das zeigt sich häufig in Form von Endlosrekursion. Aber vielleicht wird man da mit der Zeit geübter.

Auf jeden Fall muss man für die Anwendung des Cut-Operators ziemlich genau wissen, wie Prolog die Regeln auswertet. Und das finde ich etwas skurril. Schließlich ist Prolog mit dem Anspruch angetreten, dass man sich um die Algorithmik nicht mehr kümmern muss und seine Logik nur noch spezifiziert. Insgesamt hat Prolog da auch Beeindruckendes zu bieten. Aber der Cut-Operator passt da nicht so gut ins Bild. Immerhin habe ich den Cut-Operator in meinen Beispielprogrammen bisher nur selten benötigt.

Entry filed under: 1. Tags: .

Prolog-Grundzüge 6: Fail Prolog-Grundzüge 8: Datenbasis

1 Comment Add your own

  • 1. Gerold Egger  |  December 23, 2009 at 4:40 pm

    Danke!! – Ein kurzes und verständliches Beispiel.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed



%d bloggers like this: