Evolog - Actions and Modularization in Lazy-Grounding Answer Set Programming

Abstract

Answer Set Programming (ASP) ist ein seit Jahrzehnten etablierter Formalismus in der Logikprogrammierung, der insbesondere bei der Modellierung und Lösung NP-schwerer Planungsprobleme Anwendung findet. Effiziente Solver für ASP sind seit über 20 Jahren verfügbar. Aktuelle Trends in ASP befassen sich zunehmend mit der Interaktion mit externen Daten - sowohl zum Lesen und Verarbeiten selbiger, angefangen von Stream Reasoning bis hin zu Interaktionen mit Machine-Learning-Software - als auch zum Ausführen von Aktionen, d.h. der Entwicklung von ASP-Programmen mit Seiteneffekten(side-effects). Das primäre Ziel der vorliegenden Arbeit ist es, eine neue Methode zur Modellierung von Regeln mit Seiteneffekten in ASP Programmen zu entwickeln, die sich leicht in einem ASP-Solver wie dem von Weinzierl et al. entwickelten Lazy-Grounding-Solver Alpha implementieren lässt. Ein weiteres Ziel ist die Entwicklung eines leichtgewichtigen Konzeptes zur Programmmodularisierung, das die zuvor erwähnte Unterstützungvon Aktionen ergänzt. Die Notwendigkeit hierfür begründet sich aus der Tatsache, das Modellieren von Seiteneffekten in einer vollständig deklarativen Sprache zwangsläufig einige Einschränkungen struktureller Natur für Programme mit Aktionen mit sich bringt. Die mit dem Modularisierungskonzept gegebene Möglichkeit, seiteneffekt-freie Unterprogramme als eigenständige Einheiten auszuführen, sollte diese Einschränkungen im Praxiseinsatz ausgleichen. Die resultierende erweiterte Answer-Set-Programming-Sprachewird Evolog genannt. Die formale Semantik von Aktionen wird bezüglich eines Frame, d.h. eines Modells der Seiteneffekte einer Aktion in der Außenwelt in Form einer Interpretationsfunktion für Action-Atome, modelliert. Basierend auf diesem Modell der Außenwelt werden Kriterien definiert, nach denen ein Evolog-Programm (semantisch) gültig ist. Schließlich wird das Konzept eines Evolog-Modells definiert, d.h. eines StableModels eines Evolog-Programms, das konsistent bezüglich einem gegebenen Frame ist. Darüber hinaus wird gezeigt, dass Evolog eine konservative Erweiterung der üblichen Stable-Model-Semantik ist, insofern als jedes reguläre ASP-Programm auch ein gültiges Evolog Programm in allen Frames ist. Die Modularisierung wird basierend auf Alpha’s bestehendem Konzept eines externen Atoms modelliert, d.h. eines Atoms, das eine seiteneffektfreie Funktion abbildet, die in einer beliebigen Programmiersprache (in diesem Fall Java) implementiert ist. Modul-Atome sind definiert als externe Atome, deren Interpretationsfunktion darin besteht, einen ASP-Solver mit einem fixen Programm (der Modul-Implementierung) und den Eingabetermen des externen Atoms als zusätzlichem Input aufzurufen. Um das Schreiben von Code, der Module benutzt, effizienter zu gestalten, wird das (rein syntaktische) Konzept eines Listen-Terms eingeführt. Um die Eignung von Evolog als tatsächliche Programmiersprache zu demonstrieren, wird eineeinfache Kommandozeilenapplikation vorgestellt, die Graphen aus XML-Dateien einliest, 3-Colorings dieser Graphen berechnet und die berechneten Colorings in XML-Dateien serialisiert. Die Applikation wird sowohl in Bezug auf die Bedienbarkeit von Evolog als Implementierungssprache als auch auf die Ausführungsleistung diskutiert. Basierend auf der Demonstration anhand der XML-3-Coloring-App werden mögliche Erweiterungen der Sprache, sowie zukünftige Wege zur Steigerung der Solver-Performance angesprochen.

For decades, Answer Set Programming (ASP) has been an established formalism in logic programming, especially used for NP-hard planning problems, with efficient solvers available for more than 20 years. Current trends in ASP increasingly deal with interaction with external data, both for reading and processing (such as in stream reasoning or even interacting with machine learning software) as well as performing actions, i.e. influencing the state of the outside world. This thesis’ primary concern is exploring a new way of representing actions in a manner suitable for easy implementation in a lazy-grounding ASP solver such as Alpha by Weinzierl et al. Secondary to that, the other goal of this work is to specify and implement a light-weight program modularization concept to go along with the aforementioned action support. The inspiration here is that, since inevitably modelling side-effects in a fully declarative language forces us to impose some restrictions on programs with actions, being able to run action-free subprograms as encapsulated units should alleviate any such strictures in software development. The resulting extended answer set programming language is called Evolog. We define the formal semantics of actions with regards to a frame, i.e. a formalization of the effects of an action in the outside world, that is modelled as an interpretation function for action atoms. Based on this model of the outside world, the notion of what constitutes a (semantically) valid Evolog program is defined. Finally, we define an Evolog Model, i.e. a stable model of an Evolog program that is consistent with a given frame. We further show that Evolog is a conservative extension to traditional ASP in the sense that every regular ASP program is also a valid Evolog program in all frames. Modularization is modelled around Alpha’s existing concept of an external atom, i.e. an atom that models a side-effect free function which is implemented in an arbitrary programming language (Java in this case). We define module atoms as external atoms whose interpretation function is given as calling an ASP solver with a fixed program (the module body) and the input terms of the external atom as additional input. To aid in efficiently writing code around modules, the purely syntactical concept of a list term is introduced. In order to demonstrate Evolog’s suitability as an actual application programming language, a simple command-line application for reading graphs from XML files, calculating 3-colorings of said graphs and serializing calculated colorings to XML files, is showcased and discussed in terms of both ease of development, as well as evaluation performance. Based on our demonstration of the XML-3-coloring application, we formulate possible refinements to the language as well as future paths for improvement in solver performance.