Intersult: Intersult Prolog

Es handelt sich um eine Maschine zur logischen Inferenz mittels Unifikationskalül, die durch die Sprache Prolog betrieben wird. Der Interpreter ist in Java implementiert und Bestandtail von Intersult Artificial Intelligence.

Hintergrund#

Prolog ist ein symbolischer Automat zur Problemlösung. Wie Lisp verarbeitet der Prozessor ebenfalls Listen, implementiert aber zusätzlich Backtracking. Backtracking bedeutet in diesem Zusammenhang, dass der Prozessor nicht Befehle für symbolische Namen versteht, sondern diese auch rückwirkend ersetzen kann.

Man kann sich Prolog wie eine Tiefensuche im Lösungsraum einer symbolischen Gleichung vorstellen. Zusätzlich gibt es einen Mechanismus, um das Backtracking zu brechen. Mit onceenter und onceleave kann ein logischer Zweig markiert werden, der nur einmal durchlaufen wird. Mit call(X) kann ein Parameter evaluiert werden.

Das eigentliche Ausführen eines Terms besteht in der sogenannten Unifikation. Die Art der Programmverarbeitung wird daher auch als Unifikationskalül bezeichnet. Terme werden immer genau dann weiter evaluiert, wenn die Parameter mit dem aufgerufenen Muster übereinstimmen. Man sagt auch, zwei Variablen werden unifziert. Als Ergebnis stimmen die Variablen entweder überein, dann werden die folgenden Elemente ebenfalls evaluiert. Oder die Variablen sind unterschiedlich, dann wird Backtracking ausgeführt, also zu den übergeordneten, aufrufenden Termen zurück gegangen.

In Prolog entstehen Ausführungszweige auf zwei Arten:

Gleichnamige Terme: Es können mehrere Terme mit demselben Namen vorhanden sein. Diese werden dann in der festgelegten Reihenfolge evaluiert.
Parameter: Wenn Parameter durch mehrere Terme ersetzt werden können, werden diese der Reihe nach durchprobiert.

Sprache#

Die Sprache Prolog besteht im Kern aus Termen vom Typ:

name(param, ...) [:- ref(ref-param, ...), ...].

Symbol	Bedeutung
name	Legt den Namen eines Terms fest, der in einem anderen Term mit "ref" referenziert werden kann.
param	Formalparameter der in der Definition des Terms als lokale Variable durch "ref-param" referenziert werden kann. Der Parameter wird während der Evaluierung innerhalb der Definition ersetzt und kann auch selbst wieder als "param" verwendet werden oder evaluiert werden.
ref	Referenziert einen anderen Term.
ref-param	Ein Aktualparameter zur Referenz eines Formalparameters "param", der durch eine Referenz des Terms mittels "ref" belegt wird. Bei jeder Evaluation des Terms kann "param" einen anderen Wert liefern.

Boolesche Logik#

Die übliche Logik nach Boole wird bereits durch Terme abgebildet:

Prolog Ausdruck	Bedeutung
true.	Ein Ausdruck als reines Symbol ohne Parameter oder Regel führt immer zum Fortsetzen des Backtracking.
equals(X, X).	Ein Ausdruck mit zwei identischen Parametern führt zu einem Ersetzen dieser Parameter. Falls dies Möglich ist, wird die Evaluierung fortgesetzt, andernfalls Backtracking durchgeführt.
fail :- equals(x, y).	Backtracking kann dadurch herbeigeführt werden, indem equals mit zwei unterschiedlichen Parametern referenziert wird.
if(X, Y, Z) :- once(test(X, R)), case(R, Y, Z).	Der Term "test" wird einmal ausgeführt, anschließend der Term "case" mit der entstandenen Entscheidung.
test(X, true) :- call(X).	Der als Parameter X übergebene Term wird ausgeführt, wenn der zweite Parameter mit true unifiziert wird.
test(X, fail).	Der zweite Zweig des Terms "test" führt den Parameter X nicht aus, wenn der zweite Parameter mit fail unifiziert wird.
case(true, X, Y) :- call(X).	Der erste Zweig vom Term "case" führt X aus, wenn der erste Parameter auf true unifiziert.
case(fail, X, Y) :- call(Y).	Der zweite Zweig vom Term "case" führt Y aus, wenn der erste Parameter auf fail unifiziert.
not(X) :- if(X, fail, true).	Der Term "not" kehrt den Wahrheitswert vom Parameter X um, indem er den Term "if" aufruft und den Wahrheitswert umgekehrt zurückgibt.
or(X, Y) :- call(X).	Der erste Zweig des Terms "or", der den Parameter X ausführt.
or(X, Y) :- call(Y).	Der zweite Zweig des Terms "or", der den Parameter Y ausführt. Der zweite Zweig wird also auch bei fail von Parameter X durch Backtracking ausgeführt.
and(X, Y) :- call(X), call(Y).	Der Term "and" führt direkt Parameter X und dann Parameter Y aus. Führt X zu fail, wird Y nicht ausgeführt.
once(X) :- onceenter, call(X), onceleave.	Der Term "once" ist eine Abkürzung für onceenter und onceleave, indem der den Parameter X genau einmal ausführt.
repeat.	Der erste Zweig vom Term "repeat" wird immer ausgeführt.
repeat :- repeat.	Der zweite Zweig des Terms "repeat" ruft sich einfach wieder selbst auf. Das ist die einfachste Art der Rekursion in Prolog. Beim Aufrufen von "repeat" muss natürlich dafür gesorgt werden, dass die Wiederholung irgendwo abgebrochen wird.

Java Interface#

Zunächst kann man einen Prolog-Interpreter durch die Klasse com.intersult.ai.prolog.Prolog instantiieren:

Prolog prolog = new Prolog();

Diesen kann man durch die Methode "consult" neue Terme hinzufügen:

prolog.consult("append([], L, L).");
prolog.consult("append([H | T], L, [H | R]) :- append(T, L, R).");

Hier wird der Term "append" implementiert mit den drei Parametern T, L und R, sodass T = L | R gilt. T ist also das Aneinanderfügen der Listen L und R.

Schließlich kann man einen Term ausführen und das Ergebnis anzeigen, indem wir die Frage stellen, welchen Term X erhält man, wenn man 1, 2 und 3, 4 zusammensetzt:

System.out.println(prolog.run("append([1, 2], [3, 4], X)"));

Ergebnis: Erwartungsgemäß fügt der Prozessor die beiden Listen 1, 2 und 3, 4 zusammen zu 1, 2, 3, 4.

Dies war nun keine logische Leistung, sondern ein imperativer Ablauf, wie es gewöhnliche Java-Programme auch machen. Doch nun machen wir es umgekehrt und fragen, welchen Term X muss man 4, 5, 6 voranstellen, um 1, 2, 3, 4, 5, 6 zu erhalten.

Term result = prolog.run("append(X, [4, 5, 6], [1, 2, 3, 4, 5, 6])");
System.out.println(result.get(0));

Ergebnis: Die Evaluierung von "append" führt zu einer logischen Leistung, indem die Inferenz die einzige Lösung 1, 2, 3 für X findet, sodass das es zusammengesetzt mit 4, 5, 6 zum Ergebnis 1, 2, 3, 4, 5, 6 führt.

Fazit#

Man erkennt, dass jeder Parameter sowohl als Eingabe als auch Ausgabe verwendet werden kann. Und zwar ohne dass jede Variante von Ein- und Ausgabe eigens implementiert werden müsste. Logische Aussagen werden analytisch definiert, sodass der Prozessor eine Inferenz vornehmen kann.

Damit unterscheidet sich Prolog deutlich von den sogenannten imperativen Maschinen, die immer nur einen Befehl (daher imperativ) entgegennehmen und dann einen logischen Zug ausführen.