Ausgewählter Nerdkram von Informatikstudenten der Uni Ulm

Using Prolog as an incremental CHR constraint store

The work with Constraint Handling Rules (CHR) has many advantages. One of them is the so called online property: It’s possible to execute your CHR program by giving some constraints in a first query, wait for the result (or not!) and add further constraints later at any time. So a CHR program normally does not terminate but rather halts if it can’t execute any rule with the constraints currently in the constraint store. And so it simply waits for new constraints. That’s why it is called incremental constraint store.

Working with Prolog as the host language, you will detect that it doesn’t work in this way: Once you entered your query of maybe multiple constraints, Prolog plays the constraint handler and applies your rules until it’s no longer possible. And stop. While the resulting constraint store is printed, you neither can add any new constraint nor manipulate this constraint store in any way. So the big advantage of the online property, which is recited mechanically in every CHR lesson, gets lost.

I’ve written Jon Sneyers, one of the developers of the K.U.Leuven CHR System used by SWI-Prolog, if he knows a way to use Prolog as an incremental CHR constraint store. And the solution is as simple as short: Because Prolog uses backtracking, it will turn to the point before the query was executed once all rules have been applied. That’s why it can not be used as an incremental constraint store without a simple trick: By writing an own prompt which takes the queries, we can prevent Prolog to backtrack. So the main idea is the following:

main :- prompt.

prompt :- write('[CHRstore] ?- '),

This will result in a loop which produces a self-defined prompt to get new queries without forgetting the old ones. But this very basic example has some disadvantages: First you can’t stop the loop. And second there is no way to show the current constraint store once you have added a new query. So we will modify the Prolog rules a little bit:

main :- prompt.

prompt :- write('[CHRstore] ?- '),

callq(show_constraints) :- writeln('[CHRstore] Stored constraints:'),
callq(stop_store) :- writeln('[CHRstore] Stopped.').
callq(Query) :- call(Query),

By adding a callq predicate we can provide two special queries: show_constraints and stop_store. While the latter one will break our prompt loop, the show_constraints calls the built-in chr_show_store/1 predicate to print the constraint store of the module Mod. To get the current module you can either add a fact at the top, use some built-in predicates or something else.

I’ve wrapped up these snippets in a little Prolog module, which can additionally handle multiple modules too.

Benjamin Erb [] studiert seit 2006 Medieninformatik und interessiert sich insbesondere für Java, Web-Technologien, Ubiquitous Computing, Cloud Computing, verteilte Systeme und Informationsdesign.

Raimar Wagner studiert seit 2005 Informatik mit Anwendungsfach Medizin und interessiert sich für C++ stl, boost & Qt Programmierung, Scientific Visualization, Computer Vision und parallele Rechenkonzepte.

David Langer studiert seit 2006 Medieninformatik und interessiert sich für Web-Entwicklung, jQuery, Business Process Management und Java.

Sebastian Schimmel studiert seit 2006 Informatik mit Anwendungsfach Medizin und interessiert sich für hardwarenahe Aspekte, Robotik, webOs, C/C++ und UNIX/Linux.

Timo Müller studiert seit 2006 Medieninformatik. Er interessiert sich allen voran für Mobile and Ubiquitous Computing, systemnahe Enwticklung und verteilte Systeme, sowie Computer Vision.

Achim Strauß studiert seit 2006 Medieninformatik. Seine Interessen liegen in Themen der Mensch-Computer Interaktion sowie Webentwicklung und UNIX/Linux.

Tobias Schlecht studiert seit 2006 Medieninformatik und interessiert sich vor allem für Software Engineering, Model Driven Architecture, Requirements Engineering, Usability Engineering, Web-Technologien, UML2 und Java.

Fabian Groh studiert seit 2006 Medieninformatik. Seine Interessengebiete sind Computer Graphics, Computer Vision, Computational Photography sowie Ubiquitos Computing.

Matthias Matousek studiert seit 2007 Medieninformatik und interessiert sich besonders für Skriptsprachen, Echtzeitsysteme und Kommunikation.

Michael Müller [] studiert seit 2009 Medieninformatik. Er interessiert sich vor allem für Web-Technologien, Ubiquitous Computing, User-Interfaces, UNIX und Creative Coding.

Falco Nogatz [] studiert seit 2010 Informatik mit Anwendungsfach Mathematik. Er interessiert sich für Web-Technologien, Programmierparadigmen und theoretische Grundlagen.


Februar 2015
« Mrz