© Poohchisa Tunsiri / 123RF.com

Logische Programmierung verfolgt einen völlig anderen Ansatz als andere Programmierparadigmen. Hier soll der Compiler selbstständig Schlüsse ziehen, statt die Schritte eines Algorithmus abzuarbeiten.

Was heißt logische Programmierung? Sollte nicht jede Programmiersprache klar und einleuchtend sein, im landläufigen Sinne also logisch? Eine logische Sprache im engeren Sinn wie das im Folgenden exemplarisch vorgestellte Prolog meint allerdings etwas ganz anderes: Eine solche Sprache gründet sich explizit auf die formale Logik, genauer gesagt auf die Prädikatenlogik erster Ordnung. Diese Teildisziplin der Mathematik und der theoretischen Informatik verknüpft formalisierte logische Aussagen anhand streng definierter Schlussregeln. Auf diese Weise will etwa Prolog aus Fakten nach mathematischem Vorbild automatisch Schlussfolgerungen ableiten.

Logische Sprachen bilden eine Unterart des deklarativen Paradigmas, was bedeutet, dass sie nicht beschreiben, mit welchen Schritten ein Ergebnis zu berechnen ist. Sie definieren vielmehr Wissen in Gestalt von Fakten und Regeln und fragen den Compiler nach den Schlussfolgerungen, die er daraus ziehen kann.

In gewisser Weise ähnelt das Programmieren damit dem Anlegen einer Datenbank aus Tatsachen und ihren Verknüpfungen, die sich dann mit Queries abfragen lassen. Entsprechend gibt es in einer solchen Sprache (wie etwa auch in der Datenbanksprache SQL) keine imperativen Sprachmittel wie Schleifen oder If-Then-Else-Konstrukte. Stattdessen besteht ein Prolog-Programm aus der besagten Wissensbasis in Gestalt einer Sammlung von Fakten, zugehörigen Wenn-Dann-Regeln (den sogenannten Klauseln) sowie den Anfragen des Anwenders, die das Programm dann zu beantworten versucht.

Fakten und Regeln

Ein oft genutztes Beispiel für den Aufbau eines Prolog-Programms verwendet einen Stammbaum. Einen Ausschnitt daraus zeigt Abbildung 1. Zu dieser Ahnentafel gilt es nun Fakten in Prolog zu hinterlegen, im einfachsten Fall beispielsweise das Geschlecht der Personen (Listing 1). Jeder Fakt besteht aus einem sogenannten Funktor und einem oder mehreren Argumenten. Als Funktoren dienen hier »maennlich« und »weiblich«, als einziges Argument der Name der Person. Groß- und Kleinschreibung spielt dabei eine Rolle: Fakten- und Regelfunktoren müssen mit einem Kleinbuchstaben beginnen, Variablen starten mit einem Großbuchstaben.

Abbildung 1: Ausschnitt aus dem fiktiven Stammbaum, den die Beispiele verwenden.

weiblich(elisabeth)
weiblich(katrin)
weiblich(marie)
maennlich(thomas)
maennlich(frank)
maennlich(christian)
maennlich(egon)
maennlich(leo)
maennlich(udo)

Als Nächstes gilt es, die Mutter- und Vater-Kind-Beziehungen zu erfassen. Elisabeth ist die Mutter und Thomas der Vater von Frank, Katrin die Mutter von Christian und so weiter. Wie in Listing 2 zu sehen, haben die Fakten in der resultierenden Notation jeweils zwei Argumente. Nun ließe sich schon eine Regel formulieren, die festlegt, ob es sich bei einer der Personen um einen Elternteil einer anderen Person handelt:

elternteil(Elter, Kind) :- vater(Elter, Kind); mutter(Elter, Kind).

Die Großschreibung verweist hier darauf, dass es sich bei »Elter« und »Kind« um Variablen handelt. Das Semikolon am Ende der zweiten Zeile symbolisiert eine Oder-Verknüpfung. Die Kombination aus Doppelpunkt und Minuszeichen, die Regelkopf und Regelrumpf trennt, ist der Regeloperator, der sich als “wenn” lesen lässt. Der Regelkopf enthält das Beweisziel oder Goal. Damit ergibt sich hier als Prosatext der Regel: »Elter« ist ein Elternteil von »Kind«, wenn »Elter« entweder Vater oder Mutter von Kind ist.

mutter(elisabeth, frank)
mutter(katrin, christian)
mutter(katrin, egon)
mutter(katrin, marie)
mutter(marie, leo)
vater(thomas, frank)
vater(frank, christian)
vater(frank, egon)
vater(frank, marie)
vater(udo, leo)

Abfragen

Nach ein paar kleinen Vorarbeiten könnte man nun schon erste Abfragen an die aus den Fakten aufgebaute Knowledge Base stellen. Um das praktisch auszuprobieren, gilt es, vorab Prolog zu installieren. Im Beispiel verwenden wir GNU Prolog, das Sie aus den Repositories der verwendeten Distribution oder von der Projektwebseite http://www.gprolog.org beziehen. Auf Letzterer gibt es allerdings für Linux nur die Quellen, keine Pakete.

Im zweiten Schritt legen Sie ein Textfile namens »demo.pl« an, das alle obigen Fakten und Regeln enthält, allerdings pro Zeile mit einem Punkt abgeschlossen und so umgeordnet, dass Fakten mit identischen Argumenten untereinander stehen. Der Prolog-Compiler würde sich andernfalls über discontinuous arguments beschweren und die beanstandeten Zeilen ignorieren.

Sieht das Ganze so aus wie in Listing 3, starten Sie den Compiler am besten aus dem Verzeichnis heraus, das das Demo-File enthält, mit dem Kommando »gprolog –consult-file demo.pl«. Es öffnet sich ein Terminalfenster, das bestätigt, dass GNU Prolog die Datei eingelesen und kompiliert hat.

maennlich(egon).
maennlich(thomas).
maennlich(frank).
maennlich(christian).
maennlich(leo).
maennlich(udo).
weiblich(marie).
weiblich(katrin).
weiblich(elisabeth).
mutter(elisabeth,frank).
mutter(katrin,christian).
mutter(katrin,egon).
mutter(katrin,marie).
mutter(marie,leo).
vater(thomas,frank).
vater(frank,christian).
vater(frank,egon).
vater(frank,marie).
vater(udo,leo).
elternteil(Elter,Kind) :- (vater(Elter,Kind); mutter(Elter,Kind)).

Hinter dem Prompt»?-« können Sie in diesem Terminalfenster nun interaktiv Abfragen formulieren. So gibt zum Beispiel »weiblich(elisabeth).« die Antwort »yes« zurück, das Postulat ist also wahr. Verwenden Sie eine groß geschriebene Variable wie »X«, kann der Interpreter alle dazu passenden wahren Aussagen auflisten. Ein Beispiel wäre »maennlich(X)«, was zunächst »egon« erbringt.

Danach tippen Sie das Semikolon als Zeichen für die Oder-Funktion ein und erhalten auf diese Weise noch »thomas«, »frank«, »christian«, »leo« und »udo«. Auf ähnliche Weise fragen Sie die Kinder von Katrin mit »elternteil(katrin,X).« ab (Abbildung 2).

Abbildung 2: Wer sind Katrins Kinder? Eine Abfrage listet sie auf.

Die Verwandtschaftsregeln lassen sich beliebig ausbauen. Die Regel für die Großeltern könnte beispielsweise so aussehen wie in der ersten Zeile von Listing 4. »X« gehört zu den Großeltern von »Z«, wenn »X« ein Kind von »Y« und »Y« ein Kind von »Z« ist.

grosseltern(X,Z) :- (elternteil(X,Y), elternteil(Y,Z)).
vorfahr(X,Y)     :- elternteil(X,Y).
vorfahr(X,Y)     :- (elternteil(X,Z), elternteil(Z,Y).
vorfahr(X,Y)     :- (elternteil(X,Z), elternteil(Z,S), elternteil(S,Z)).

Eine Abfrage »grosseltern(X,egon)« fördert dann »thomas« und »elisabeth« zutage, weil ein Elternteil von »egon« (»frank«) zugleich als Kind in einer »elternteil«-Regel auftaucht (bei »thomas« und »elisabeth«).

Man kann das noch allgemeiner formulieren und Regeln dafür einführen, wer als Vorfahr gelten soll (Listing 4, Zeilen 2 bis 4). Demnach gelten als Vorfahren die Eltern, die Eltern der Eltern (Großeltern) und die Eltern der Eltern der Eltern (Urgroßeltern). Das ließe sich beliebig fortsetzen. Eine entsprechende Abfrage nach den Vorfahren von Leo zeigt Abbildung 3.

Abbildung 3: Die Vorfahren von Leo.

Auf diese Weise ließen sich Brüder und Schwestern, Onkel und Tanten, Nichten und Neffen in Regeln ausdrücken, kurz: alle möglichen Verwandtschaftsbeziehungen. Die Regeln lassen sich zu Regelnetzwerken verknüpfen, die schnell so komplex ausfallen, dass man sie manuell nicht mehr auswerten kann. Auch die Datengrundlage, hier der Stammbaum, könnte sehr viel umfangreicher ausfallen und Tausende von Personen umfassen.

Selbstverständlich sind Verwandtschaftsverhältnisse nur ein beliebiges Beispiel. Um noch ein anderes herauszugreifen, nehmen wir die Reiseplanung. Dazu könnten wir als Fakt zunächst erfassen, welches Bundesland an welches andere grenzt. Listing 5 beschränkt sich der Einfachheit halber auf zwei Nachbarschaftsbeziehungen (erste zwei Zeilen). Danach ließe sich eine Reiseregel so definieren wie in der letzten Zeile.

Fragen Sie nun »reise(bayern, niedersachsen).« an, bejaht Prolog das, weil es über »thueringen« eine Route dorthin gibt. »reise(thueringen, saarland)« endet dagegen mit einem »no«, weil das Saarland in der Faktenbasis bislang gar nicht vorkommt.

benachbart(bayern,thueringen).
benachbart(thueringen,niedersachsen).
reise(A,C) :- (benachbart(A,B),benachbart(B,C)).

Fazit

Die knappen Beispiele demonstrieren, dass die logische Programmierung einen vollkommen anderen Weg einschlägt als andere Programmierparadigmen. Hier geht es nicht darum, durch das Programm vorgegebene Schritte (einen Algorithmus) präzise abzuarbeiten, um so schließlich zu einem Ergebnis zu gelangen. Stattdessen definiert man die Fakten und Regeln eines Wissensgebiets, und das Programm berechnet durch logisches Schließen aus diesen Axiomen Antworten auf die Fragen des Nutzers.

Dieser Ansatz stammt aus frühen Forschungen zur künstlichen Intelligenz, speziell zu Expertensystemen, für die Prolog auch häufig verwendet wurde. Zunächst hatte man versucht, allgemeine Problemlöser zu konstruieren (General Problem Solver), die unabhängig vom konkreten Gegenstand logische Schlüsse ziehen sollten. Dieses Vorhaben scheiterte jedoch, und so kamen die Forscher zu Systemen, die stattdessen mit dem Wissen einer speziellen Domäne umgehen, das sie detailliert erfassen.

So könnte ein medizinisches Expertensystem beispielsweise aus Symptomen Diagnosen ableiten oder ein botanisches respektive zoologisches aus den Merkmalen von Pflanzen oder Tieren die Art, der sie angehören. Aus Messwerten in einem komplexen industriellen Prozess könnte man darauf schließen, wie man ihn beeinflussen muss, um ein ideales Ergebnis zu erhalten.

Weitere Anwendungen finden sich beispielsweise in der Analyse chemischer Verbindungen, in der geologischen Erkundung, bei Erdbebenvorhersagen und auch im militärischen Bereich. Dafür wird Prolog auch heute noch eingesetzt. So war etwa ein Teil der Software von IBMs KI-System Watson in Prolog geschrieben. Es wurde durch seinen Sieg gegen zwei menschliche Rekord-Champions in der US-TV-Quizshow “Jeopardy!” berühmt.

Im Unterschied zu KI-Anwendungen mit maschinellem Lernen auf der Grundlage neuronaler Netze können Expertensysteme übrigens zumeist erklären, wie und warum sie zu ihren Ergebnissen kommen. (jlu)