Es handelt sich um eine Implementierung eines Unifikationskalüls in der Sprache von Prolog
mittels Java. Der Interpreter ist 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. |