Posts tagged ‘Prolog’

Prolog-Grundzüge 5: Rekursion

In Prolog gibt es keine Schleifenkonstrukte wie FOR oder WHILE im klassischen Sinne. Stattdessen wird Rekursion verwendet. Häufig trifft man Rekursion in Prolog im Zusammenhang mit Listen an.

Wollen wir beispielsweise alle Elemente einer Liste ausgeben, so können wir dies durch folgende Regeln erreichen:

schreibe_liste([]).
schreibe_liste([H|T] :- write(H), write(','), schreibe_liste(T).

Diese Definition liest sich so: Wenn wir eine leere Liste haben, schreiben wir nichts. Ansonsten schreiben wir das erste Element, gefolgt von einem Zeilenumbruch “nl” und schreiben den Rest der Liste.

Durch die Definition von “schreibe_liste([])” haben wir die Abbruchbedingung für die Rekursion definiert. Hätte man diese Definition weggelassen, würde die Ausgabe immer noch korrekt erfolgen, “schreibe_liste” würde aber immer “false” liefern – weil die rekursive Regelanwendung irgendwann bei der leeren Liste ankommen würde, die sich nicht weiter aufsplitten lässt. Bei anderen Definitionen kann das Weglassen der Abbruchregel leicht zu Endlosrekursionen führen.

July 21, 2009 at 4:47 pm Leave a comment

Prolog-Grundzüge 4: Pattern Matching

Eine weiteres sehr nützliches Prolog-Feature ist das Pattern-Matching. In den meisten Programmiersprachen wird zur Auswahl einer Funktion oder Prozedur nur der Name herangezogen, bei Java und Konsorten auch noch die Anzahl und der statische Typ der Parameter. Bei Prolog wird außerdem die Form der Argumente herangezogen.

So kann man in einer Regeldefinition z.B. den Split-Operator für Listen (den wir im letzten Blogeintrag kennen gelernt haben) verwenden und sowas schreiben:

liste([H,T], H, T) :- true. 

tut dasselbe wie die Regel “liste” aus dem letzten Blogeintrag. Dort war “liste” definiert als:

liste(EineListe, H, T) :- [H|T] = EineListe.

Wir werden beim Thema Rekursion sehen, dass es hier nicht nur darum geht, Regeln etwas kürzer aufschreiben zu können. Das Pattern-Matching ist letztlich die Voraussetzung dafür, dass sich Rekursion in Prolog überhaupt elegant benutzen lässt.

Und über das Pattern-Matching kann man benannte Parameter realisieren, ohne dass Prolog dieses Konzept direkt unterstützt:

fuelle_liste([Wert], mit:1, mal:Wert) :- !.
fuelle_liste(Liste, mit:Anzahl, mal:Wert) :- AnzahlRed is Anzahl - 1, fuelle_liste(Liste2, mit:AnzahlRed, mal:Wert), Liste = [Wert|Liste2].

So kann man jetzt die Abfrage sprechend formulieren:

?- fuelle_liste(Liste, mit:4, mal:a).

Liefert “[a, a, a, a]”. Hier sieht man außerdem eine Besonderheit von Prolog. Wenn man Berechnungen durchführt, darf man diese nicht mit = auf eine Variable zuweisen. Stattdessen muss man is verwenden. Das Ausrufezeichen ! ist übrigens der Cut-Operator. Aber um den kümmern wir uns später.

Noch eine Schmankerl zum Schluss: Regeln die immer “true” liefern, unterscheiden sich nicht von Fakten, so dass wir die Regel “liste” noch etwas kürzer schreiben können:

liste([H,T], H, T). 

July 20, 2009 at 8:09 pm Leave a comment

Prolog-Grundzüge 3: Listen

Eine Liste schreibt man in Prolog kommasepariert und umgeben von eckigen Klammern auf: [a,b,c] definiert eine Liste aus dem Symbolen a, b und c. Mit dem Pipezeichen | kann man eine Liste zerlegen – in das erste Element und den Rest. Man kann z.B. schreiben:

liste(EineListe, H, T) :- [H|T] = EineListe.

H und T sind in Prolog übliche Variablennamen, wenn es um das Aufsplitten von Listen geht. H steht für “Head” und T für “Tail”. Die Regel “liste” können wir vielfälig verwenden:

?- liste([a,b,c], H, T).

liefert “H=a, T=[b,c]”.

Wir können so auch feststellen, wie eine Liste aufgesplittet wird, die nur ein Element hat

?- liste([a], H, T).

liefert “H=a, T=[]”. Eine einelementige Liste besteht also aus dem Element und der leeren Liste.

Und wie sieht es mit der leeren Liste aus?

?- liste([], H, T).

liefert “false”. Die leere Liste lässt sich nicht weiter aufsplitten. Damit lässt sich die Regel nicht erfolgreich anwenden und das quittiert das Prolog-System mit “false”.

Wie wir schon im ersten Blogeintrag gesehen haben, kann man viele Regeln auch umgekehrt anwenden. Mit der Regel “liste” können wir nicht nur Listen zerlegen, wir können auch Listen damit zusammenbauen.

?- liste(L, a, [b,c]).

liefert “L=[a,b,c]”.

July 20, 2009 at 5:12 pm 1 comment

Prolog-Grundzüge 2: Das Prolog-System

Nachdem wir im letzten Prolog-Blogeintrag gesehen haben, wie man in Prolog prinzipiell Fakten und Regeln definiert, geht es in diesem Post um die grundsätzliche Handhabung von Prolog-Systemen. Ich verwende SWI-Prolog, das es für Linux, Mac und Windows gibt.

Grundsätzlich definiert man in Prolog Fakten und Regeln in Dateien – wie Quellcode in anderen Programmiersprachen auch. Prolog-Quelltextdateien enden auf .pl oder .pro (wenn man Verwechselungen mit Perl vermeiden will). Quelltextdateien lädt man in das Prolog-System, dass man im Fall von SWI-Prolog mit “swipl” startet – häufig ist auch auch der Shortcut “pl” definiert. Am einfachsten lädt man seine Dateien mit:

['meine_prolog_datei.pro'].

Wichtig ist, dass man den Punkt nicht vergisst. Das Prolog-System lädt die Datei ein und compiliert diese in eine interne Zwischenrepräsentation. Erwartet uns der Prompt “?-” und wir können interaktiv Abfragen auf den Fakten und Regeln definieren. Im vorigen Blogpost haben wir Fakten und Regeln für Benutzer und Gruppen definiert. Wir können jetzt z.B. fragen

?- gruppe(admin, stefan).

und erhalten als Antwort “true”. (“?-” gibt man nicht mit ein; das bezeichnet nur den Prompt).

Häufig liefern Regeln nicht nur ein Ergebnis, vor allem dann, wenn man in der Abfrage mit Variablen arbeitet.

?- gruppe(X, stefan).

liefert erst “X=admin” und dann “X=user”. Bei SWI-Prolog bekommt man zunächst nur “X=admin” angezeigt und wenn man dann “n” (für Next) eingibt “X=user”.

Wir werden bei einem späteren Blogpost noch sehen, dass man die strikte Unterscheidung zwischen Fakten und Regeln auf der einen und Abfragen auf der anderen Seite aufweichen kann. Man kann auch Abfragen in Quelltext-Dateien definiert und man kann auch mit dem Prolog-Prompt Fakten und Regeln definiert.

July 20, 2009 at 4:35 pm Leave a comment

Prolog-Grundzüge 1: Fakten und Regeln

Nachdem ich das Terminplaner-Beispiel bereits in Java, Groovy, Lisp und Groovy programmiert habe, hatte ich mir als nächstes Prolog (PROgramming in LOGic) vorgenommen. Und da Sebastian bereits gesagt hat, dass er den Prolog-Code nicht versteht, habe ich entschieden, diese Mini-Einführung zu schreiben.

Prolog ist eine sogenannte deklarative Programmiersprache. Man deklariert lediglich Fakten und Regeln auf diesen Fakten und das Prolog-System kümmert sich um die Algorithmen. Sowas wie If-Konstrukte oder Schleifen der klassischen Form gibt es in Prolog nicht.

In Prolog schreibt man Fakten so ähnlich auf wie sonst Funktionsaufrufe:

benutzer(stefan).
benutzer(mika).

bedeutet beispielsweise, dass stefan ein Benutzer ist. stefan muss hier nicht als String angegeben werden. Es ist ein Symbol (ein Konzept, dass es auch in Lisp gibt). Symbole werden dadurch von Variablen unterschieden, dass sie klein geschrieben werden und Variablen mit einem Großbuchstaben oder Unterstrich beginnen.

Führen wir zu den Benutzern noch Benutzergruppen ein:

gruppe(admin, stefan).
gruppe(admin, mika).

Damit können wir bereits ein paar drollige Dinge machen. Trivialerweise können wir abfragen, ob stefan der Gruppe admin angehört: gruppe(admin, stefan) liefert true. Interessanter wird es, wenn wir Stefans Gruppe wissen möchten: gruppe(X, stefan) liefert X=admin. Und das funktioniert auch mit Mengen: gruppe(admin, Y) liefert Y=stefan und Y=mika. Und es funktioniert sogar die Kombination gruppe(X, Y). Das Prolog-Laufzeitsystem sucht alle Belegungen für X und Y, die definiert wurden, also X=admin, Y=stefan und X=admin, Y=mika.

Hier sieht man einen wichtigen Unterschiede zu klassischen Programmiersprachen: Parameter für Regeln haben keine vordefinierte Richtung. In der Gruppe Regel konnten wir die beiden Parameter sowohl als Ein- wie auch als Ausgabeparameter verwenden. Das reduziert die Menge der notwendigen Regeln/Funktionen.

Jetzt können wir eine Regel selbe_gruppe einführen, die prüft, ob sich zwei Benutzer in derselben Gruppe befinden.

selbe_gruppe(Benutzer1, Benutzer2) :- gruppe(Gruppe, Benutzer1), gruppe(Gruppe, Benutzer2), Benutzer1 \= Benutzer2. 

Das Komma bedeutet hier soviel wie Und.

Und dann können wir fragen, ob Stefan und Mika zur selben Gruppe gehören.

?- selbe_gruppe(stefan, mika). 

und Prolog liefert uns erwartungsgemäß true.

In der Abfrage kann man auch selbst wieder Variablen verwenden:

?- gruppe(X, stefan).

liefert admin.

Und das waren auch schon die allerersten Grundzüge von Prolog. Soweit, so einfach. Wie man damit einen Terminplaner schreiben soll, ist erstmal noch hochgradig unklar. Als nächstes werde ich daher einen Blog-Eintrag zu Rekursion in Prolog schreiben.

July 15, 2009 at 7:33 pm 2 comments

Terminplaner in Prolog

Ich habe meine Prolog-Kenntnisse aufgefrischt und dazu das Terminplaner-Beispiel in Prolog implementiert. Die geringe Anzahl Lines of Code (LoC) der Prolog-Lösung finde ich ziemlich beeindruckend. Ich habe die Größe der Lösung in den verschiedenen Programmiersprachen mal gegenüber gestellt (LoC: ohne Leerzeichen und Kommentare).

Sprache LoC LoC Tests
Java 187 109
Groovy 155 79
Ruby 141 90
Lisp (CLOS) 63 77
Prolog 34 93

LoC ist sicher kein besonders gutes Maß, um die Mächtigkeit einer Programmiersprache zu bewerten. Wenn man allerdings nur 34 Zeilen braucht, wo man sonst 150-200 Zeilen braucht, finde ich das schon ziemlich denkanstößig.

Der Code steht unter github bereit: http://github.com/stefanroock/Terminplaner/tree/master (Achtung: Die Python-Lösung funktioniert noch nicht).

July 13, 2009 at 7:30 pm 5 comments

Newer Posts