Jekejeke Minlog 0.5: Erstes Erweiterungsmodul

Admin User, erstellt 23. Jul 2012

1 Einleitung

Mit Jekejeke Minlog steht ein erstes Erweiterungsmodul von Jekejeke Prolog zur Verfügung. Das Modul wurde schon in 2011 angedacht konnte aber erst jetzt nach einigen Monaten Entwicklungszeit vollendet werden. Dieses Modul liefert eine Komponente zur Vorwärtsverkettung. Darauf aufbauend liefert das Modul auch einen Chartparser sowie einen Constraintlöser.

2 Vorwärtsverkettung

Beim Jekejeke Minlog handelt es sich nicht um eine einfache Bibliothek von Prolog Prädikaten. Vielmehr erweitert das Modul den Jekejeke Prolog Interpreter um eine zusätzliche Prädikateigenschaft delta/0. Diese Eigenschaft wird dazu benutzt um die normalen Prolog Klauseln von Vorwärtsklauseln zu unterscheiden. Vorwärtsklauseln werden auf spezielle Weise in normale Prolog Klauseln übersetzt sodass sie zur Berechnung von neuen Fakten aus alten Fakten herangezogen werden können.

Fakten können mit dem neuen Prädikat post/1 hinzugefügt werden und die Vorwärtskomponente berechnet dann automatisch den Abschluss. Damit die Vorwärtsverkettung dynamisch innerhalb dem Ablauf von Prologprogrammen benutzen werden kann, werden diese Fakten nur temporär in der Wissensbank gehalten. Dazu werden die Änderungen an der Wissensbank in einer Liste festgehalten und beim Backtracking automatisch rückgängig gemacht. Der in Jekejeke Prolog 0.9.3 eingeführte Mechanismus des sys_unbind/1 Prädikates war uns dabei dienlich.

3 Chartparser

Bei der Integration des Chartparsers stellte sich die Frage ob man einen neuen Operator für die Grammatik Regeln einführen soll. Wir entschieden uns jedoch auch hier auf die Prädikateigenschaft delta/0 zu testen. Eine Schwierigkeit bestand darin dem existierenden DCG Mechanismus des normalen Interpreters zusätzliche Regeln unterzujubeln. Wir entschieden uns für die Einführung einer neuen Direktive advice/1 mit der nachträglich Klauseln am Anfang eines Prädikates hinzugefügt werden können. Das Modul erweitert so den bestehenden DCG Mechanismus.

Der Chartparser verwendet ‚D‘/3 Fakten für Terminale mit Positionsangaben in Anlehnung an den normalen DCG Parser der eine ‚C‘/3 Regel benutzt. Bei der Arbeit am Chartparser haben wir die Vorzüge der asymmetrischen Konjunktion (&)/2 kennengelernt. Diese Konjunktion berechnet neue Fakten nur linksseitig und es genügt das erste Ziel einer Grammatikregel damit auszustatten. Werden nun die Terminale dem Chartparser von rechts nach links und nicht wie üblich von links nach rechts zu gefügt, so entstehen Chartparser die auch semantische Aktionen {}/1 durchführen können und über eine gute Performance verfügen.

4 Constraintlöser

Als weiteren Anwendungsbereich der Vorwärtsverkettung haben wir einen Constraintlösers realisiert der die Constraints in der Wissensbank hält. Dazu mussten wir die Vorwärtsverkettung jedoch zuerst um den Mechanismus des Löschens von Fakten erweitern. Wir liessen uns dabei von der Syntax des Push-Backs in normalen DCG Regeln inspirieren. Im Kopf einer Vorwärtsklausel können nun durch das Komma abgetrennt Fakten angegeben werden die gelöscht werden sollen.

Mit Hilfe des Löschmechanismus kann der Constraintlöser richtige Vereinfachungen an der Wissensbank und somit an den Constraints vornehmen in dem mehrere Constraints durch ein neues Constraint ersetzt werden. Wir sind dann daran gegangen verschiedene Varianten des CLP(FD) auszuprobieren um uns schliesslich für eine Variante mit orientierter Intervallkonsistenz zu entscheiden. Bei dieser Arbeit wurde die Vorwärtsverkettung ein zweites Mal erweitert und die Möglichkeit hinzugefügt, dass eine Vorwärtsklausel einen Abbruch anzeigen kann. Dies ist nützlich wenn Constraints als unlösbar erkannt werden.

5 Ausblick

Eine Vorversion des Chartparsers sowie eine Variante des Constraintlösers konnten wir an der TaCoS 2012 vorstellen. Dort haben wir auch den Bezug zur Minimalen Logik hergestellt die namensgebend für das Modul ist. Als nächstes steht der Abschluss der Tests für das an der TaCoS 2012 aufgeführte Anwendungsgebiet an. Ausserdem werden wohl noch einige Performanceverbesserungen aufscheinen. Eine Evaluationsversion steht unter http://www.jekejeke.ch/ allen Interessenten zum Test zur Verfügung.

Jan Burse
Geschäftsführer