powered by 
In Prolog schreibt man nicht auf, was der Computer der Reihe nach tun soll, sondern was wahr ist: Fakten über eine Familie und Regeln, was Großeltern, Geschwister und Vorfahren sind. Dann stellt man Fragen, und Prolog sucht die Antworten selbst. Du fragst die Musikerfamilie Bach über fünf Generationen aus, lässt Listen rückwärts rechnen und färbst die Bezirke Berlins mit vier Farben.
Alain Colmerauer (1941–2017), französischer Informatiker, Professor in Marseille. Er wollte, dass ein Computer Fragen auf Französisch versteht und aus Sätzen wie »Katzen töten Mäuse« und »Tom ist eine Katze« selbst schließt, was Tom tut. Dafür schrieb er 1972 mit Philippe Roussel eine Sprache, in der ein Programm aus solchen Aussagen besteht: Prolog, von »programmation en logique«. Wie man logische Aussagen als Programm lesen kann, hatte Robert Kowalski in Edinburgh gezeigt, mit dem er 1971 und 1972 in Marseille zusammenarbeitete.
Das Foto zeigt ihn um 1970 in Montreal, in der Gruppe, mit der er an einem Programm zum Übersetzen zwischen Englisch und Französisch arbeitete; er hält gerade eine Ausgabe seiner Q-Systeme in der Hand, aus denen später Prolog wurde. Noch später baute er Prolog so aus, dass es auch mit Zahlen und Bedingungen rechnet, wie in einem Sudoku, das Prolog nicht durch Ausprobieren löst, sondern indem es unmögliche Zahlen streicht.
Ein Prolog-Programm besteht aus Fakten, die einfach gelten, und Regeln, die sagen, wann etwas gilt. Ein Programm läuft nicht von oben nach unten, sondern man stellt eine Anfrage, und Prolog sucht in den Fakten und Regeln, ob sie stimmt und für welche Werte.
Leg einen Ordner an, hol die Fakten über die Familie Bach und starte SWI-Prolog mit ihnen:
mkdir -p /workspace/prolog cd /workspace/prolog wget https://workspace.hackschule.de/prolog/starter/familie.pl swipl familie.pl
Jetzt wartet Prolog hinter ?- auf eine Anfrage. Sie endet immer mit einem
Punkt:
?- parent(johann_sebastian, wilhelm_friedemann). true. ?- parent(johann_sebastian, X). X = catharina_dorothea ; X = wilhelm_friedemann ; X = carl_philipp_emanuel .
Was klein beginnt, ist ein Name, ein Atom: johann_sebastian. Was groß
beginnt, ist eine Variable: X. Gibt es mehrere Antworten, zeigt
Prolog die erste und wartet: ; holt die nächste, Enter hört auf. Hast du
familie.pl im Editor geändert, lädt make. sie neu; halt. beendet
Prolog.
Jede Zeile parent(johann_ambrosius, johann_sebastian). in familie.pl ist
ein Fakt: Johann Ambrosius ist ein Elternteil von Johann Sebastian. Eine
Anfrage mit einer Variablen fragt, wofür sie gilt, an jeder Stelle:
parent(X, johann_sebastian) fragt nach den Eltern.
Wie viele Antworten gibt Prolog auf ?- parent(X, johann_sebastian)., wenn du nach jeder mit ; nach der nächsten fragst?
In familie.pl fehlen die Kinder von Johann Sebastian und seiner zweiten Frau Anna Magdalena: gottfried_heinrich, elisabeth_juliane_friederica, johann_christoph_friedrich und johann_christian. Trag sie als Fakten ein, für beide Eltern.
Ein Fakt sieht aus wie die anderen in der Datei: parent(anna_magdalena, johann_christian)., mit einem Punkt am Ende.
Vier Kinder, zwei Eltern: acht neue Zeilen. Am besten stehen sie bei den anderen parent-Fakten.
Eine Regel sagt, wann etwas gilt. :- liest man »wenn«, das Komma »und«:
son(S, P) :- parent(P, S), male(S).
»S ist ein Sohn von P, wenn P ein Elternteil von S ist und S männlich.« Eine
Variable gilt in der ganzen Regel: Das S in male(S) ist dasselbe wie
das in parent(P, S).
Schreib drei Regeln in familie.pl: father(F, C), wenn F ein Elternteil von C und männlich ist, mother(M, C) ebenso mit weiblich, und grandparent(G, C), wenn G ein Elternteil eines Elternteils von C ist.
Eine Regel hat einen Kopf und, nach :-, die Bedingungen, durch Komma getrennt: father(F, C) :- parent(F, C), male(F).
Für die Großeltern gibt es dazwischen eine Person, die in beiden Bedingungen vorkommt: grandparent(G, C) :- parent(G, P), parent(P, C).
Jemand schreibt sibling(X, Y) :- parent(P, X), parent(P, Y).: Geschwister haben einen gemeinsamen Elternteil. Was antwortet Prolog auf ?- sibling(johann_sebastian, Y)., wenn man mit ; nach allen Antworten fragt?
Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.
Johann Sebastian hat mit sich selbst einen gemeinsamen Elternteil, sogar
zwei: Für P = johann_ambrosius passt Y = johann_sebastian, und für
P = maria_elisabeth wieder. Jedes Geschwister kommt zweimal, einmal über
den Vater und einmal über die Mutter. Prolog weiß nur, was dasteht, und
nirgends steht, dass niemand sein eigenes Geschwister ist.
Schreib sibling(X, Y), das sagt, ob X und Y Geschwister sind: Sie haben einen gemeinsamen Elternteil und sind nicht dieselbe Person. Halbgeschwister zählen mit.
Die Regel aus der Vorhersage ist fast richtig: parent(P, X), parent(P, Y) findet alle, die einen Elternteil mit X teilen, X selbst eingeschlossen.
Eine dritte Bedingung schließt X selbst aus: X \= Y, verschieden.
Wie findet Prolog die Großeltern von Wilhelm Friedemann? Es nimmt das erste Ziel, die Anfrage, und sucht von oben eine Klausel, deren Kopf dazu passt. Passen heißt: Die beiden lassen sich gleich machen, indem Variablen Werte bekommen. Das heißt Unifikation. Passt eine Regel, treten ihre Bedingungen an die Stelle des Ziels. Könnten weiter unten noch andere Klauseln passen, merkt sich Prolog die Stelle. Scheitert später ein Ziel, geht es zum letzten Merkpunkt zurück und probiert dort die nächste Klausel. Das heißt Backtracking.
Die Merkpunkte sind ein Stack: Prolog geht immer zum zuletzt gemerkten zurück. Darum findet es die Antworten in der Reihenfolge, in der die Fakten in der Datei stehen.
Ein Vorfahr ist ein Elternteil, oder ein Elternteil eines Vorfahren. Diese Regel benutzt sich selbst, wie eine rekursive Funktion. Auf die Reihenfolge kommt es dabei an:
ancestor(A, D) :- ancestor(A, P), parent(P, D). ancestor(A, D) :- parent(A, D).
Was passiert bei ?- ancestor(christoph, X).?
Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.
Für ancestor(christoph, X) nimmt Prolog die erste Klausel, und deren
erstes Ziel ist wieder ancestor(christoph, P): Prolog nimmt die erste
Klausel, und so fort, ohne je bei einem Fakt anzukommen. Jeder Aufruf kommt
auf den Stack, bis der Speicher voll ist. Logisch ist die Regel richtig,
aber Prolog sucht von links nach rechts und von oben nach unten. Erst einen
Schritt gehen, dann weiterfragen: Das endet, weil die Familie endlich ist.
Schreib ancestor(A, D): A ist ein Vorfahr von D, wenn A ein Elternteil von D ist, oder ein Elternteil eines Vorfahren von D, so weit zurück, wie die Familie reicht.
Zwei Klauseln: eine für den einfachen Fall, ancestor(A, D) :- parent(A, D)., und eine für den Weg über eine Generation mehr.
Die zweite geht erst einen Schritt hinunter und fragt dann weiter: ancestor(A, D) :- parent(A, P), ancestor(P, D). So kommt jede Rekursion eine Generation näher an D.
Eine Liste schreibt man [a, b, c]. Prolog sieht sie als Kopf und
Rest: [a | [b, c]], und in einer Regel lässt sich beides auf einmal
herausnehmen, [Kopf | Rest]. Die leere Liste ist []. Schreib die
folgenden Prädikate in eine neue Datei:
cd /workspace/prolog
wget https://workspace.hackschule.de/prolog/starter/listen.pl
Schreib in listen.pl das Prädikat is_in(X, List): X ist ein Element der Liste. Zwei Klauseln: X ist der Kopf der Liste, oder X ist im Rest.
Die erste Klausel ist ein Fakt: is_in(X, [X | _]). Wo zweimal X steht, muss beide Male dasselbe stehen.
Die zweite sieht im Rest nach: is_in(X, [_ | Rest]) :- is_in(X, Rest). Die leere Liste braucht keine Klausel: Dort ist nichts, und Prolog sagt false.
Schreib size(List, N): N ist die Zahl der Elemente der Liste. Die leere Liste hat 0 Elemente, jede andere eines mehr als ihr Rest. Gerechnet wird mit is: N is M + 1.
Ein Fakt für die leere Liste, size([], 0)., und eine Regel für eine Liste mit Kopf und Rest.
Erst die Länge des Rests, dann eins mehr: size([_ | Rest], N) :- size(Rest, M), N is M + 1.
Schreib joined(Xs, Ys, Zs): Zs ist die Liste Xs und dahinter Ys. Hängt man an die leere Liste etwas an, kommt das Angehängte heraus; sonst ist der Kopf von Xs auch der Kopf des Ergebnisses.
Der Fakt: joined([], Ys, Ys). An eine leere Liste angehängt, bleibt Ys, wie es ist.
Die Regel nimmt den Kopf mit: joined([X | Xs], Ys, [X | Zs]) :- joined(Xs, Ys, Zs).
Wie viele Antworten gibt ?- joined(Xs, Ys, [a, b, c]).?
Hier geht es weiter, sobald du deine Antwort oben abgegeben hast.
Vier: [] und [a, b, c], [a] und [b, c], [a, b] und [c],
[a, b, c] und []. joined ist keine Funktion, die aus zwei Listen eine
macht, sondern eine Beziehung zwischen drei Listen. Prolog kann jede Stelle
fragen, die unbekannt ist. Dasselbe gilt für is_in: Mit einer Variablen
an erster Stelle zählt es die Elemente auf.
Jede Landkarte lässt sich mit vier Farben so färben, dass keine zwei Nachbarn dieselbe haben. Bewiesen haben das Kenneth Appel und Wolfgang Haken 1976, als einen der ersten großen Beweise mit Hilfe eines Computers. Hier färbt Prolog die zwölf Bezirke Berlins. Nachbarn sind Bezirke mit einer gemeinsamen Grenze:
| Bezirk | Variable | Nachbarn |
|---|---|---|
| Charlottenburg-Wilmersdorf | Cw |
Mitte, Reinickendorf, Spandau, Steglitz-Zehlendorf, Tempelhof-Schöneberg |
| Friedrichshain-Kreuzberg | Fk |
Lichtenberg, Mitte, Neukölln, Pankow, Tempelhof-Schöneberg, Treptow-Köpenick |
| Lichtenberg | Li |
Friedrichshain-Kreuzberg, Marzahn-Hellersdorf, Pankow, Treptow-Köpenick |
| Marzahn-Hellersdorf | Mh |
Lichtenberg, Treptow-Köpenick |
| Mitte | Mi |
Charlottenburg-Wilmersdorf, Friedrichshain-Kreuzberg, Pankow, Reinickendorf, Tempelhof-Schöneberg |
| Neukölln | Nk |
Friedrichshain-Kreuzberg, Tempelhof-Schöneberg, Treptow-Köpenick |
| Pankow | Pa |
Friedrichshain-Kreuzberg, Lichtenberg, Mitte, Reinickendorf |
| Reinickendorf | Re |
Charlottenburg-Wilmersdorf, Mitte, Pankow, Spandau |
| Spandau | Sp |
Charlottenburg-Wilmersdorf, Reinickendorf, Steglitz-Zehlendorf |
| Steglitz-Zehlendorf | Sz |
Charlottenburg-Wilmersdorf, Spandau, Tempelhof-Schöneberg |
| Tempelhof-Schöneberg | Ts |
Charlottenburg-Wilmersdorf, Friedrichshain-Kreuzberg, Mitte, Neukölln, Steglitz-Zehlendorf |
| Treptow-Köpenick | Tk |
Friedrichshain-Kreuzberg, Lichtenberg, Marzahn-Hellersdorf, Neukölln |
Du beschreibst nur, was gelten soll: Jeder Bezirk hat eine Farbe, und Nachbarn haben verschiedene. Wie man eine Färbung findet, überlegt sich Prolog selbst.
cd /workspace/prolog
wget https://workspace.hackschule.de/prolog/starter/bezirke.pl
Schreib in bezirke.pl die Regel berlin(Cw, Fk, Li, Mh, Mi, Nk, Pa, Re, Sp, Sz, Ts, Tk), eine Variable für jeden Bezirk, wie in der Datei beschrieben. Jeder Bezirk bekommt eine der vier Farben, und keine zwei Nachbarn aus der Tabelle oben haben dieselbe.
Jeder Bezirk bekommt seine Farbe mit colour(Mi). Zwei Nachbarn sind verschieden: Mi \= Pa. 24 Nachbarpaare stehen in der Tabelle.
\= kann erst prüfen, wenn beide Seiten eine Farbe haben. Schreib jede Prüfung direkt hinter das zweite colour ihres Paares: Dann scheitert eine falsche Farbe sofort, statt erst, wenn alle zwölf gefärbt sind.
time(aggregate_all(count, berlin(_, _, _, _, _, _, _, _, _, _, _, _), N)).
nach der Zahl der Färbungen. Achte darauf, wie viele Schlüsse
(»inferences«) Prolog jeweils braucht.
Ein Extra für Schnelle. Wer es auslässt, springt zu Wie geht es weiter?.
Prolog kann nicht nur ausprobieren. Mit library(clpfd) sagt man, welche
Werte eine Variable haben darf und welche Bedingungen gelten, und Prolog
streicht unmögliche Werte, bevor es rät. Ein Sudoku ist dann nur noch seine
Regeln: jede Zelle eine Zahl von 1 bis 9, in jeder Zeile, jeder Spalte und
jedem Block alle verschieden.
cd /workspace/prolog
wget https://workspace.hackschule.de/prolog/starter/sudoku.pl
In sudoku.pl fehlen die Blöcke. Schreib blocks(Zeile1, Zeile2, Zeile3), das in drei Zeilen die drei Blöcke nebeneinander nimmt, die ersten drei Zahlen jeder Zeile, dann die nächsten drei und so weiter, und für jeden Block verlangt, dass seine neun Zahlen verschieden sind.
Ein Fakt für drei leere Zeilen, blocks([], [], [])., und eine Regel, die von jeder Zeile drei Zahlen nimmt: blocks([N1, N2, N3 | Rest1], [N4, N5, N6 | Rest2], [N7, N8, N9 | Rest3]).
Darin verlangt all_distinct([N1, N2, N3, N4, N5, N6, N7, N8, N9]) einen Block ohne doppelte Zahl, und blocks(Rest1, Rest2, Rest3) macht mit den nächsten drei Zahlen weiter.
-->) wird eine Grammatik wie die aus
Grammatiken zu einem Programm, das Sätze prüft und
erzeugt.\+ parent(X, _) gilt, wenn Prolog keinen Beweis findet,
nicht, wenn das Gegenteil bewiesen ist. Wer also nicht in der Datei steht,
hat für Prolog keine Kinder.Programming in Prolog, William F. Clocksin und Christopher S. Mellish, 1981. Das Buch, mit dem eine Generation Prolog gelernt hat, von Fakten und Regeln bis zu Grammatiken.
