Prolog
Aus Wikibooks
Dieses Buch steht im Regal Programmierung.
[Bearbeiten] Zusammenfassung des Projekts
- Zielgruppe: Studenten
- Projektumfang:
- Themenbeschreibung:
- Lernziele: Das Erlernen deklarativer Programmiersprachen am Beispiel von Prolog.
- Abgrenzung zu anderen Wikibooks:
- Richtlinien für Co-Autoren:
- Aufbau des Buches:
Inhaltsverzeichnis |
In Erstellung AndreasPrang 21:52, 26. Jun 2005 (UTC)
[Bearbeiten] Vorwort
Prolog (programming in logic) ist die Bezeichnung für eine Programmiersprache, welche es ermöglicht nichtlineare Programmierung zu betreiben. Dieses Buch soll dazu dienen, die Syntax der Programmiersprache kennen zu lernen und in komplexen Anwendungen einzusetzen. Neueinsteigern wird empfohlen, die ersten Kapitel zu lesen und den Rest, als Nachschlagewerk zu nutzen. Hierfür werden im Laufe der Kapitel einige Beispiele erarbeitet. Das Buch richtet sich speziell an Schüler der Gymnasialen Oberstufe und Studenten der Richtung Theoretische & Praktische Informatik. Ich erhebe den Anspruch, dass es nach dem Lesen des Buches möglich sein sollte rekursive Algorithmen selbstständig erstellen zu können. Hierfür sollte sich ein jeder Leser mit einer Entwicklungsumgebung vertraut machen. Diese wird für Mac OS X, Linux und Windows Systeme im Laufe des ersten Kapitels in Kürze erläutert werden.
[Bearbeiten] Installation
[Bearbeiten] Mac OS X
Die Installation unter Mac OS X ist mittels zweier Umgebungen möglich. Hier wäre zunächst die grafische Lösung zu nennen, welche in der aktuellen Version jedoch keine Textausgabe ermöglicht (darauf werde ich später eingehen). Weitere Informationen hierzu sind unter http://xgp.sourceforge.net/ zu finden.
Die zweite Entwicklungsumgebung, kommandozeilenbasierend ohne GUI (Graphic User Interface) ist unter http://www.swi-prolog.org/dl-stable.html zu finden. Für die Installation sind jedoch zusätzlich DarwinPorts und X11 notwendig. Hierfür sollten die im Link angegebenen Installationshinweise befolgt werden.
Es wird empfohlen die Windowsversion zu nutzen, da ausschließlich diese über eine grafischen Debugger verfügt.
[Bearbeiten] Linux
An dieser Stelle möchte ich aufgrund der verschiedenen Versionen lediglich auf die z.Z. gängigste Distribution eingehen, SuSE Linux. Hierfür muss das auf http://www.swi-prolog.org/dl-stable.html verfügbare RPM heruntergeladen und installiert werden. Anschließend sollte ein Plug-in für Emacs heruntergeladen und installiert werden. Auch diese Version beinhaltet keinen Debugger mit grafischer Oberfläche. Ein weiteres Prolog-System ist GNU Prolog, das auf http://pauillac.inria.fr/~diaz/gnu-prolog z.B. als RPM oder im Quelltext runtergeladen werden kann.
[Bearbeiten] Windows
SWI-Prolog für Windows wird als Grundlage für alle in diesem Buch gezeigten Beispiele genutzt. Für die Installation nutzen Sie bitte die aktuellen Quellen auf http://www.swi-prolog.org/dl-stable.html.
[Bearbeiten] Einführung
Prolog-Programme bestehen aus einer Datenbasis, die Fakten und Regeln umfasst. Der Benutzer formuliert Anfragen an diese Datenbasis. Der Prolog-Interpreter benutzt die Fakten und Regeln, um systematisch eine Antwort zu finden.
[Bearbeiten] Ein Beispiel für eine Daten-Basis
Eine Prolog Daten-Basis bezeichnet den Quelltext eines Programmes, welcher in der betreffenden Quelldatei gespeichert ist. Hier ein Beispiel für eine Daten-Basis:
Bsp.:1, UE01.pl
% Daten - Basis. mensch(gregor). mensch(stefan).
Erstellen Sie diese Daten-Basis mit einem Text-Editor und speichern Sie diese unter dem Namen ue01.pl. Jetzt koennen sie die Daten-Basis in Prolog laden:
?- consult(ue01). - laedt die Daten-Basis % ue01 compiled 0.00 sec, 904 bytes Yes
Jetzt können wir Anfragen an die Daten-Basis stellen: Z.B. können wir alle Menschen in der Daten-Basis ausgeben lassen. Beachten Sie, dass die Ausgabe nach jedem Fund anhält, bis Sie "r" (redo) drücken.
? - mensch(Name). Name = gregor; Name = stefan; No.
[Bearbeiten] Prädikate
Prädikate in Prolog bezeichnen im einfachsten Fall fest stehende Argumente. So zeigt uns folgendes Beispiel, wie ein in der Prolog-Datenbasis existierendes Argument abgefragt wird:
Bsp.: 2
wohnt_in(schneider, hauptstrasse). wohnt_in(schmidt, hauptstrasse). wohnt_in(meier, hauptstrasse). wohnt_in(mueller, dorfstrasse). wohnt_in(petram, dorfstrasse). wohnt_in(kringel, bahnhofstrasse). wohnt_in(fischer, bahnhofstrasse).
Diese Datenbasis beschreibt Fakten durch das Prädikat wohnt_in(<Familie>, <Strasse>) wohnt_in/2. Die Bezeichnung wohnt_in/2 beschreibt die Existenz eines solchen Prädikats mit zwei Variablen. Bei einer Abfrage wie
?- wohnt_in(schmidt,Strasse).
geht Prolog die Daten-Basis (DB) durch und sucht nach passenden Fakten innerhalb des Prädikats wohnt_in/2. Wir bekommen die Antwort:
Strasse = hauptstrasse; No. ?-
Sie sollten sich durch das No. am Ende nicht verwundern lassen. SWI-Prolog gibt zunächst immer eine Lösung aus. Nach der Eingabe von ; oder n wird die nächste Lösung angegeben, welche durch die gegebene DB erfüllt wird. Da keine weitere Lösung existiert, gibt der Compiler ein No. zurück und terminiert die Ausführung.
Prädikate können komplexer aufgebaut werden, woraus sich Abhängigkeitsbeziehungen ergeben, welche Prolog durch systematisches Durchgehen zu beweisen versucht. So haben wir nachstehendes Beispiel, welches die Bewohner einer Strasse und wer Nachbar von wem ist beschreibt. Es wird erfragt, ob sich Bewohner schmidt und mueller über einen anderen Nachbarn kennen.
Bsp.: 3
% DB: % Prädikate: ist_nachbar_von(<Nachbar1>,<Nachbar2>). wohnt_in(<Bewohner>,<Strasse>). ist_Nachbar_von(schmidt,meier). ist_Nachbar_von(meier,mueller). /* Anfrage: */ ?- ist_Nachbar_von(schmidt, Nachbar2), ist_Nachbar_von(Nachbar2,mueller). Nachbar2 = meier Yes.
Somit ist das gegebene Prädikat bewiesen.
Wir haben in diesem Beispiel zwei neue Elemente der Syntax kennengelernt. Das Prozentzeichen "%" wird für das Auskommentieren von Textelementen genutzt. Es dient der Auskommentierung der restlichen Zeile. Eine andere Form der Auskommentierrung ist /* ... */. Hierbei wird der Bereich von /* bis zum am Ende stehenden */ auskommentiert.
Syntax: Sehen Sie nun noch einmal bewußt auf die Groß- und Kleinschreibung der Anfrage. Ihnen sollte nun aufgefallen sein, dass die Namen der Nachbarn jeweils klein geschrieben sind. Dies ist eine der Prolog-Syntaxregeln. Fakten und Prädikate beginnen mit Kleinbuchstaben. Variablen beginnen mit Großbuchstaben
[Bearbeiten] Variablen
Entgegen anderen, allgemein bekannten Programmiersprachen (Java, C, Pascal, Visual Basic) ist es in Prolog nicht notwendig, Variablen zu deklarieren. Diese werden durch das Zuweisen von Werten initialisiert. Prolog erkennt Variablen, wie bereits erwähnt, anhand des ersten, groß geschriebenen Buchstabens. Die Zuweisung von Werten erfolgt nach den Regeln des folgenden Beispiels:
Bsp.: 4
Variable1 = 'Text'. % Der Variable Variable1 wird ein Text zugewiesen. Variable2 = 2. % Der Variable Variable2 wird ein Integer - Wert zugewiesen.
Wie in den beiden Variablenzuweisungen erkennbar, wird jede fertige Syntaxzeile mit einem Punkt beendet.
[Bearbeiten] Vergleichsoperatoren
Der Vergleich zweier Variablen ist in Prolog mittels zweier Operatoren möglich.
==
Ersterer (==) prüft, ob der in den Variablen enthaltene Text übereinstimmt. Hier ein Beispiel:
%DB: text_ist_gleich(Variable1, Variable2) :- Variable1 == Variable2.
%Anfrage: ?- text_ist_gleich(text,text). Yes.
=:=
Der zweite Vergleichsoperator (=:=) ist für den Vergleich von Zahlwerten zu benutzen. Siehe:
%DB: zahlen_sind_gleich(Variable1, Variable2) :- Variable1 =:= Variable2.
%Anfrage: ?- zahlen_sind_gleich(1024,1024). Yes.
\=
Um die Ungleichheit zweier Variablen zu prüfen, ist der Ungleichoperator (\=) verfügbar. Er liefert bei Ungleichheit der Variablen ein Yes. zurück.
%DB: zahlen_sind_ungleich(Variable1, Variable2) :- Variable1 \= Variable2.
%Anfrage: ?- zahlen_sind_ungleich(1024,4711). Yes.
[Bearbeiten] Rechnen mit Variablen
Das Rechnen mit Variablen ist entgegen Java ähnlichen Programmiersprachen anders gestaltet. Im kommenden Beispiel werden wir ein Prädikat schreiben, welches das Quadrat einer Zahl zurückliefert.
Bsp.: 5
%DB: quadrat_von(Zahl,Quadrat_der_Zahl):-Quadrat_der_Zahl is(Zahl*Zahl).
Anfrage: quadrat_von(4,Ergebnis). % quadrat_von(4,Ergebnis) :- Ergebnis is (4 * 4). Ergebnis = 16. Yes.
Wir sehen, dass das Rechnen mit Variablen mit einem Prefix-Operator ermöglicht wird. Wir erhalten bei diesem Ergebnis ein Yes., da wir kein zweites Ergebnis erwarten und somit statt <n> <Enter> gedrückt haben.
Syntax: Mit diesem Beispiel wurde der gilt wenn Operator eingeführt. Wie eingangs beschrieben, ist Prolog eine Programmiersprache, welche versucht eingegebene Anfragen zu beweisen. Daher gilt an dieser Stelle: quadrat_von/2 gilt, wenn Quadrat_der_Zahl is(Zahl*Zahl) gilt. Da die Variable Zahl bereits durch die eingegebene Anfrage an eine feste Zahl gebunden wurde, ist Quadrat_der_Zahl is(Zahl*Zahl) ein Fakt und gilt somit. Ein einfacheres Beispiel verdeutlicht dies:
Bsp. 6
%DB: weiblich(helene). ist_Elternteil_von(helene,stefan). ist_Mutter(Mutter) :- weiblich(Mutter), ist_Elternteil_von(Mutter,_).
%Anfrage: ist_Mutter(helene). Yes.
Syntax: Ein Unterstrich wird für anonyme Variablen verwendet. Dies bedeutet, dass es sich hierbei um eine Variable handelt, welche einen beliebigen Wert zugewiesen bekommt. Anonyme Variablen werden nicht ausgegeben!
Achtung! Sollten sich in einem Prädikat zwei dieser anonymen Variablen befinden, sind diese nicht gleichzusetzen. Es handelt sich um zwei verschiedene Variablen, welche nicht weiter genutzt werden können.
[Bearbeiten] Verknüpfungen
[Bearbeiten] Und
Wie zu sehen ist, sind in der DB des vorangehenden Beispiels (Bsp. 6) die Fakten, dass helene weiblich ist und Mutter von Stefan gespeichert. Anhand des Prädikates ist_Mutter wird überprüft, ob es eine weibliche Person gibt, welche gleichzeitig Elternteil eines Kindes ist.
Syntax: In diesem Beispiel haben wir die Und - Verknüpfung kennengelernt. Diese wird mit einem Komma zwischen den Prädikaten realisiert.
[Bearbeiten] Oder
Oder-Verknüpfungen werden in Prolog durch ein Semikolon dargestellt. Für die nächsten Anfragebeispiele nutzen wir die folgende DB:
Bsp.: 7
%DB:
hat_gestohlen(markus).
hat_gestohlen(stefan).
hat_gestohlen(christine).
hat_randaliert(markus).
hat_randaliert(christine).
hat_sich_entschuldigt(stefan).
% Prädikate:
wird_gesucht(Name) :-
hat_gestohlen(Name);
hat_randaliert(Name).
ist_frei(Name) :-
(
hat_gestohlen(Name);
hat_randaliert(Name)
),
hat_sich_entschuldigt(Name).
Bsp.: 7a
Anfrage: wird_gesucht(Name). Name = markus; Name = stefan; Name = christine; Name = markus; Name = christine; No.
Anhand dieser Ausgabe wird die Art der Beweisführung Prologs erkennbar. Prolog durchsucht die DB chronologisch von oben nach unten und versucht die Anfrage mittels findbarer Fakten zu beweisen. Da markus mit zwei Delikten in der DB aufgeführt ist und die Frage gestellt wurde, wer gestohlen oder randaliert hat, wird er in der Ausgabe zweifach aufgeführt, da Prolog die Frage wird_gesucht mit hat_gestohlen und hat_randaliert beweisen kann. Prolog verwendet bei der Suche nach Fakten für die Beweisführung das Prinzip der Tiefensuche.
[Bearbeiten] Und - Oder
(DB siehe Bsp.:7)
Bsp.: 7b
Anfrage: ist_frei(Name). Name = stefan; No.
Wie im Prädikat ist_frei (siehe Bsp.:7) sichtbar, ist die komplexe Verknüpfung von und & oder Verknüpfungen mittels Klammern erfolgreich. Es werden nach den Regeln der Mathematik zunächst die Argumente in der Klammer beachtet.
Mit dem bis hierher gewonnenen Wissen sollten Sie nun bereits einige kleine Programme schreiben können.
[Bearbeiten] Übungen
[Bearbeiten] Übung 1
Formuliere für die folgende DB mit dem Prädikat kind(<Elternteil>,<Kind>):
kind(hanna,sabine). kind(hanna,peter). kind(robert,sabine). kind(robert,peter). kind(peter,jana). kind(peter,christine). kind(claudia,jana). kind(claudia,christine). kind(claudia,jutta). kind(jana,jakob). weiblich(claudia). weiblich(jana). weiblich(christine). weiblich(jutta). weiblich(sabine). weiblich(hanna). maennlich(peter). maennlich(robert). maennlich(jakob).
die folgenden Anfragen:
a) Welche Schwestern hat Jana? (keine Halbschwestern!)
b) Welche Tanten hat Christine?
c) Welche Nichten hat Sabine?
d) Wer hat Geschwister? (auch Halbgeschwister!)
Gib jeweils die Anfrage und Antwort in Prolog an!
[Bearbeiten] Übung 2
Formuliere eine Prolog-Regel (Prädikat) für die Verwandtschaftsbeziehung eines Neffen: (neffe( X, Y), was bedeutet: Y ist Neffe von X) Nutze hierfür die DB der Übung 1. Die Schwester oder der Bruder von X, dessen Kind Neffe von X ist, soll dabei eine leibliche Schwester bzw. ein leiblicher Bruder (keine Halbgeschwister) sein!
Formuliere desweiteren folgende Anfragen:
a) Hat Claudia einen Neffen?
b) Wer hat einen Neffen?
c) Wessen Neffe ist Jakob?
Gib jeweils die Anfrage und Antwort in Prolog an!
[Bearbeiten] Komplexe Problemlösungen
[Bearbeiten] Schleifen & Prolog - Arbeitsbäume
Schleifen, wie man sie aus anderen Programmiersprachen kennt, sind in Prolog nicht vorgesehen. Es ist jedoch möglich, eine Schleife mit einfachen Mitteln zu erstellen. Hierzu ein kleines Beispiel:
Bsp.: 8
% DB: schleife :- schleife.
Diese Regel, besagt, dass schleife gilt, wenn schleife gilt. Dies klingt auf den ersten Blick, so alleinstehend, recht unlogisch und ist es eigentlich auch, da in diesem Fall keine Abbruchbedingung gegeben ist. Aus diesem Grund sehen wir uns eine Schleife mit Abbruchbedingung an.
Bps.: 9
%DB:
quadrat_von(Zahl) :-
Zahl =:= 16.
quadrat_von(Zahl) :-
Quadrat is (Zahl * Zahl),
quadrat_von(Quadrat).
Wir sehen uns zunächst an, was bei der Anfrage quadrat_von(16). geschieht. Prolog prüft die erste Regel namens quadrat_von/1. Diese gilt, wenn die übergebene Variable dem Wert 16 entspricht. Es ist zu beachten, dass der Vergleichsoperator =:= ausschließlich für Zahlenwerte funktioniert und == für Textvergleiche. Da der übergebene Variablenwert dem Vergleichswert entspricht, ist die Beweisführung beendet und Prolog endet mit "Yes.
Nun überprüfen wir den den Aufruf: quadrat_von(2). Hierbei wissen wir, dass die Beweisführung mittels des ersten Prädikats fehlschlagen wird, da der Inhalt der Variable Zahl gleich 2 ist und dementsprechend nicht 16 entspricht. Als nächstes versucht Prolog die Beweisführung mittels des zweiten Prädikats. Wir wissen, dass die Variable Zahl noch immer den Wert 2 beinhaltet. Es wird eine neue Variable Quadrat erstellt, welcher das rechnerische Ergebnis von (Zahl * Zahl) zugewiesen wird. Somit ist der Inhalt von Quadrat 4. Da hinter der eben beschriebenen Zeile ein Komma (Und) steht, wird diese ebenfalls beachtet. Das Prädikat quadrat_von/1 mit dem Variablenwert 4 wird aufgerufen. Sollte diese beweisbar sein, ist auch unser Aufruf bewiesen, da dieser genau dann gilt. Abermals wird die Bedingung des ersten Prädikats nicht erfüllt und Prolog bedient sich des zweiten. Sie sehen, wir befinden und im zweiten Umlauf der Schleife. Im zweiten Prädikat wird erneut das Quadrat der Zahl (jetzt 4) gebildet und quadrat_von/1 ruft sich mit dem neuen Wert selbst auf. Da die nun übergebene Zahl 16 ist, besteht das erste Prädikat die Abbruchbedingung (ist erfüllt) und Prolog liefert uns ein Yes. zurück.
Anhand des Baumes der nebenanstehenden Grafik ist die Art der Suche wiedererkennbar. Prolog prüft stets von oben nach unten und von links nach rechts.
Probieren Sie beschriebenes Beispiel aus und überprüfen es ebenfalls mit quadrat_von(4). und quadrat_von(3) aus. Sie werden feststellen, dass ersteres beweisbar ist und zweiteres nicht.
[Bearbeiten] Listen
Bisher sprach ich stets über Prädikate mit einzelnen Variablen. Zur Verwaltung einer Vielzahl von Variablen ist es in Prolog möglich Listen zu nutzen. Ich werde diese anhand von Sortieralgorithmen einführen.
[Bearbeiten] Rekursion
Rekursionen sind den Schleifen gleichzusetzen. Sie haben lediglich den kleinen Unterschied inne, ein großes Problem in viele kleine zu zerlegen, und schließlich ein kleinstes Teilproblem zu finden, welches lösbar ist. Dieses kleinste Problem stellt den Rekursionsabbruch dar.
[Bearbeiten] Übungen
[Bearbeiten] Übung 3
Gegeben sei folgende Prolog-Datenbasis:
ist_Nachbar_von(schneider, schmidt). ist_Nachbar_von(schmidt, schneider). ist_Nachbar_von(meier, schmidt). ist_Nachbar_von(schmidt, meier). ist_Nachbar_von(meier, mueller). ist_Nachbar_von(mueller, meier). ist_Nachbar_von(mueller, petram). ist_Nachbar_von(petram, mueller). ist_Nachbar_von(petram, kringel). ist_Nachbar_von(kringel, petram). wohnt_in(schneider, hauptstrasse). wohnt_in(schmidt, hauptstrasse). wohnt_in(meier, hauptstrasse). wohnt_in(mueller, dorfstrasse). wohnt_in(petram, dorfstrasse). wohnt_in(kringel, bahnhofstrasse). wohnt_in(fischer, bahnhofstrasse).
und das Prädikat
sind_bekannt(X,Y) :- wohnt_in(X, _strasse), wohnt_in(Y, _strasse). sind_bekannt(X,Y) :- ist_Nachbar_von(X,Y).
Es sei die folgende Anfrage gegeben:
?- sind_bekannt(kringel, fischer).
a) Gib zu dieser Anfrage den vollständigen Prolog-Abarbeitungsbaum inklusive aller erfolgreichen und fehlschlagenden Pfade an.
b) Markiere in a) alle Pfade, die zum Beweisbaum der Anfrage gehören, also alle Pfade, die zur Erfüllung der Anfrage führen.
[Bearbeiten] Ergebnisse der Übungen
Sollten sie schönere Lösungen (funktionierende) finden, können sie diese gern an dieser Stelle einfügen.
[Bearbeiten] Übung 1
[Bearbeiten] Aufgabe 1
a)
?- kind(Mutter,jana), kind(Mutter,Geschwister), kind(Vater,jana), kind(Vater,Geschwister), weiblich(Mutter), maennlich(Vater), weiblich(Geschwister), Geschwister\==jana.
Mutter = claudia Geschwister = christine Vater = peter; No.
b)
?- kind(Elternteil, christine), kind(Grosselternteil, Elternteil), kind(Grosselternteil, Tante), weiblich(Tante).
Elternteil = peter Grosselternteil = hanna Tante = sabine ; Elternteil = peter Grosselternteil = robert Tante = sabine ; No.
c)
?- kind(Elternteil, sabine), kind(Elternteil,Geschwister), kind(Geschwister, Nichte), weiblich(Nichte). Elternteil = hanna Geschwister = peter Nichte = jana ; Elternteil = hanna Geschwister = peter Nichte = christine ; Elternteil = robert Geschwister = peter Nichte = jana ; Elternteil = robert Geschwister = peter Nichte = christine ;
d)
?- kind(Elternteil, Geschwister1), kind(Elternteil, Geschwister2), Geschwister1\==Geschwister2.
Elternteil = hanna Geschwister1 = sabine Geschwister2 = peter ; Elternteil = hanna Geschwister1 = peter Geschwister2 = sabine ; Elternteil = robert Geschwister1 = sabine Geschwister2 = peter ; Elternteil = robert Geschwister1 = peter Geschwister2 = sabine ; Elternteil = peter Geschwister1 = jana Geschwister2 = christine ; Elternteil = peter Geschwister1 = christine Geschwister2 = jana ; Elternteil = claudia Geschwister1 = jana Geschwister2 = christine ; Elternteil = claudia Geschwister1 = jana Geschwister2 = jutta ; Elternteil = claudia Geschwister1 = christine Geschwister2 = jana ; Elternteil = claudia Geschwister1 = christine Geschwister2 = jutta ; Elternteil = claudia Geschwister1 = jutta Geschwister2 = jana ; Elternteil = claudia Geschwister1 = jutta Geschwister2 = christine ; No.
[Bearbeiten] Aufgabe 2
Regeln:
elternteil(KindA,ElternteilA):- kind(ElternteilA,KindA).
vollgeschwister(KindA,KindB):- elternteil(KindA,ElternteilA),weiblich(ElternteilA), elternteil(KindA,ElternteilB),maennlich(ElternteilB), elternteil(KindB,ElternteilA) elternteil(KindB,ElternteilB) KindA\==KindB.
neffe(Mensch1,Neffe):- vollgeschwister(Mensch1,Mensch2), kind(Mensch2,Neffe), maennlich(Neffe).
Antworten:
a)
?- neffe(claudia,A). No.
b)
?- neffe(A,B). A = christine B = jakob ; No.
c)
?- neffe(A,jakob). A = christine ; No.
