Prolog oder die unendlichen Weiten der Logik

Wissensverwaltung und Schlüsse ziehen sind Standardprobleme der Künstlichen Intelligenz, die in der heutigen IT-Welt Furore macht. Schon vor Jahrzehnten führten diese Probleme zur Entwicklung einer Programmiersprache, die so ganz anders zu sein scheint: Prolog.

Sprachen Hans Nikolaus Beck  –  28 Kommentare

(Bild: pixabay / CC0 Creative Commons)

Diese Sprache ist nicht nur ein Spielzeug abgehobener Theoretiker, sie gewinnt gerade angesichts von Big Data und Künstlicher Intelligenz an Bedeutung. Trekkies wissen es: nicht nur, dass es in der Zukunft kein Geld und keine Krankheiten mehr gibt, in Gene Roddenberrys Zukunftsvision muss niemand mehr programmieren. Mr. Data beschreibt dem Computer sein Problem. Wir Programmierer der Jetzt-Zeit müssen uns stattdessen mit Algorithmen und Datenstrukturen befassen. Schritt für Schritt geben wir der Maschine vor, was diese zu tun hat. Verteilte Speicherung von Big-Data-Wolken bringen zwar mehr Komfort. Aber der Mainstream-Programmierer lebt in prozeduralen Sprachen der von-Neumann-Welt, die da sagt "tue dies", dann "tue das".

Prolog ermöglicht es, schon heute ein bisschen Mr. Data zu sein. Der Prolog-Programmierer definiert Fakten, gibt logische Regeln vor und stellt Fragen. Ein Prolog-Programm laufen zu lassen bedeutet nichts anderes, als eine Antwort auf eine Frage logisch abzuleiten. Was so banal klingt, birgt eine mächtige Programmiersprache in sich.

Der erste Kontakt: Suche nach Antworten

Nehmen wir an, wir wollen ein kleines Kartenspiel ähnlich Siebzehn und Vier entwickeln. Eine dafür sinnvolle Wissensbasis könnte sein:

card(herz, 10, 10).
card(herz, bube, 11).
card(herz, dame, 12).
card(herz, koenig, 13).
card(herz, ass, 14).
win(dame, bube).
win(koenig, dame).
win(ass, koenig).

Diese Ausdrücke sind Fakten. Sie sagen: zu einer Karte gehören die Elemente herz, bube und die Zahl 11. card() ist ein sogenannter Funktor, und steht für ein Prädikat oder eine Relation. win(dame, bube) entspräche der Prädikatsaussage dame gewinnt oder sticht gegen bube. Was diese Argumente des Funktors bedeuten (nämlich Kartenfarbe, Kartenname und Punktwert) ist aus logischer Sicht zunächst irrelevant.

Die Kleinschreibweise zeigt Prolog an, dass es sich um feste Symbole handelt. Im Prolog-Kontext spricht man von Atomen. Eine Frage-Sitzung mit SWI-Prolog könnte sich mit diesen Fakten wie in Abbildung 1 gestalten.

Abbildung 1: Eine einfache Prolog Sitzung

Auf die erste Frage ?- card(herz, bube, 11). antwortet Prolog true, also "wahr". Das angefragte Prädikat ist in der Wissenbasis enthalten, also ein Fakt und somit wahr. ?- card(caro, bube, 11). würde das System entsprechend mit false beantworten.

Interessanter sind aber Variablen, in Prolog groß geschrieben. In der zweiten Frage ist mit Point eine solche Variable enthalten. Sie bedeutet: welchen Punktwert hat die Karte Herz-Dame? Prolog versucht, eine Belegung oder Instanzierung der Point-Variable zu finden, so dass der Ausdruck einem bekannten Fakt entspricht. Bei Erfolg wird die Instanzierung ausgegeben. Der gesuchte Punktwert ist hier 12. In Prolog geht es also immer um die Frage, ob ein Ausdruck (in Prolog Term genannt) auf bekannte Fakten zurückgeführt werden kann.

Regeln

Fakten allein würden aber nicht weiterhelfen. Regeln erlauben, logisch aus bekannten Fakten neue Antworten zu bestimmen. Für unser Spiel brauchen wir beispielsweise auch Gewinnregeln. In Siebzehn und Vier ist das Ziel, nur so viele Karten zu ziehen, dass die Summe der Punkte 21 erreicht. Zumindest soll man so dicht wie möglich an 21 herankommen. Angenommen, wir hätten diese Distanz zu 21 für jeden Spieler bereits berechnet. Mit

% Distance1 ist Abstand zu 21 für Spieler 1
% Distance2 ist Abstand zu 21 für Spieler 2
% letztes Argument ist die Spielernummer
winner(Distance1, Distance2, 1) :-
Distance1 < Distance2.
winner(Distance1, Distance2, 2) :-
Distance1 > Distance2.

beschreiben wir Prolog: winner(....,1) ist wahr, wenn Distance1 < Distance2 wahr ist.

Regeln haben allgemein die Struktur A :- B1, B2, B3. A, der sogenannte Regelkopf, ist zutreffend, wenn B1 UND B2, UND B3 wahr sind. Die Bs, auch Klauseln genannt, formen den Regelrumpf und können selbst wieder Fakten oder Regeln sein. In dieser Weise lassen sich logische Strukturen eines Problems leicht formulieren.

Nimmt man Prädikate als Relationen, kann man auch Transitivität ausdrücken:

winAlso(X,Y) :-
win(X, dame),
win(dame, Y).

Bedeutet: Wenn eine Karte X die Dame schlägt, diese aber eine andere Karte Y, so schlägt X auch Y (siehe Abbildung 2). Auch dies ist nur logische Struktur, bisher war nichts Prozedurales nötig. Das ist praktisch, wenn man erst einmal die Struktur seines Problems verstehen will.

Abbildung 2: Abfrage eines transitiven Sachverhalts