1. Darstellung von Listen in PROLOG

2. Simulation eines nichtdeterministischen Automaten

3. Arithmetik in PROLOG

4 Das Acht-Damen-Problem

5. Backtrackingkontrolle

als [a,b,c,d] geschrieben werden.Die leere Liste wird durch [] bezeichnet.Eine Liste L ist

folgendermaßen definiert:

die Mitgliedschaftsrelation implementieren.Die Relation mitglied(X,L) ist wahr,falls das

Objekt X in der Liste L auftritt,und falsch ansonsten.Die Implementation von mitglied/2

kann auf folgenden Beobachtungen aufgebaut werden: X ist Mitglied von L,wenn:

Dies kann in zwei Klauseln beschrieben werden:

dreistellige Relation programmiert,die als letztes Argument das Ergebnis der Konkatenetion

von zwei ersten Argumenten liefert.So ist zum Beispiel konk([a,b],[c,d],[a,b,c,d]) wahr.

Bei der Definition von konk/2 werden wiederum zwei Fälle unterschieden:

Beispiel:

Das konk-Programm,wie die meisten PROLOG-Programme,kann flexibel auf verschiedene

Arten benutzt werden.Zum Beispiel für das Zerlegen einer Listen in zwei Listen:

programmiert werden.Diese Klausel geht davon aus,daß X Mitglied einer Liste L ist,wenn L

so in zwei Listen zerlegt werden kann,daß die zweite Liste X als Kopf hat.

einer Liste zu suchen.Zum Beispiel können wir Elemente einer Liste,die vor einem bestimmten

Element liegen,und Elemente,die diesem Element folgen,wie folgt finden:

PROLOG simuliert.Der Automat ist in der Abbildung 2.1 dargestellt.

Abbildung 2.1.

des Automaten besteht offensichtlich in einer Implementierung der Übergangsfunktion.

Unser Programm entscheidet,ob das in der Anfrage angegebene Wort vom Automaten

akzeptiert bzw. verworfen wird.Dazu einige Überlegungen:

wie folgt aus:

tiert wird,noch nicht beantwortet.Dies tut eine zweistellige Relation akzeptiert/2.Bei der

Implementierung dieser Relation gehen wir davon aus,daß der Automat ein Wort genau

dann akzeptiert,wenn es einer der folgenden Fälle auftritt:

erzwungen.Auf Anfragen,wie etwa

daran,daß der Ausdruck 1+2 lediglich einen PROLOG-Term darstellt,in dem Objekte 1

und 2 durch den +-Funktor verknüpft sind.Die Auswertung eines Ausdrucks (d.h.das Akti-

vieren der Additionsoperation) ermöglicht der is-Operator.Unter Anwendung des Opera-

tors sieht die obige Anfrage wie folgt aus:

Unser erstes Programm soll die Länge einer gegebener Liste zurückliefern.Dabei ist es

nützlich,zwei Fälle zu unterscheiden:

Das entspricht folgendem Programm:

Teilers.Es wird nach folgenden Regeln berechnet: Seien X und Y ganze Zahlen,deren ggT

zu berechnen ist,dann gilt es:

operatoren gelten in PROLOG folgende Schreibweisen:

(das dritte Argument repräsentiert dabei das Ergebnis):

daß sie sich nicht paarweise bedrohen.Die Lösung wollen wir als unäre Relation

loesung(Stellung) programmieren.

Sie hat also die Gestalt [X1/Y1,X2/Y2,...,X8/Y8],wobei das "/"-Zeichen nicht für Divisions-

operator steht,sondern nur als Trennzeichen verwendet wird(solange kein is-Operator

angewendet ist,wird keine Divisionsoperation hervorgerufen(s.Arithmetik in PROLOG)).

der Form [1/Y1,2/Y2,3/Y3,...,8/Y8] suchen.

werden:

Der erste Fall wird mit dem Fakt

programmiert,der zweite mit

realisiert.

bedroht_nicht(D,D_Liste).Es sind wider zwei Fälle zu unterscheiden:

Das wird wie folgt programmiert:

eines Ziels notwendig ist.Automatisches Backtracking ist ein nützliches Programmierkonzept,

das den Programmierer von der Last befreit,explizites Backtracking vorzunehmen.Manch-

mal ist es aber sinnvoll automatisches Backtracking (aus Effizienzgründen) abzuschalten,um

unerwünschte Folgen des unkontrollierten Backtracking zu verhindern.Dies wird in PROLOG

mit dem "Cut" gemacht.Anwendung des Cut wird mit folgendem einfachem Beispiel

demonstriert.Wir betrachten die Funktion:

Sie kann in Prolog als binäre Relation f(X,Y) implementiert werden:

Angenommen,wir haben in der Anfrage folgendes angegeben:

Bei Berechnung des ersten Ziels wird Y zu 0 instanziiert.Das zweite Ziel 2<0 scheitert,und

damit die gesamte Zielliste.Nach dem Scheitern des Ziels 2<0 werden in PROLOG die

Regeln 2 und 3 versucht,obwohl das sinnlos ist und zu Ineffizienzen führt.In der Abbildung

5.1 wird dies ausführlich gezeigt.

Stelle das Symbol "!" erreicht,so wird kein Backtracking mehr durchgeführt.Wenn wir die

gleiche Zielliste in der Anfrage für die zweite Variante des Programms angeben,werden die

Regeln 2 und 3 wegen Anwendung des Cut nicht versucht,was offensichtlich effizienter ist.

Wir könnten das Programm unter Berücksichtigung der Reihenfolge der Regeln noch verkür-

zen.Dies wird bei einer ökonomischer Formulierung der Regeln erreicht:

Das führt zu einer dritten Version des Programms:

Dieses Programm liefert die gleichen Ergebnisse,ist aber effizienter und kürzer als das ursprüngliche.

des Maximums zweier Zahlen.Ohne Cuts sieht das Programm wie folgt aus:

Die beiden Regeln schließen sich gegenseitig aus,was in der zweiten Version des Programms

genutzt wird:

immer,wohingegen das zweite immer scheitert.

programmieren.Wir werden die Relation wie folgt definieren:

In PROLOG wird dies folgendermaßen geschrieben:

Negation der mathematischen Logik entspricht.