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.

Kategorie: CHR, Prolog

Tags: , ,

Diese Icons verlinken auf Bookmark Dienste bei denen Nutzer neue Inhalte finden und mit anderen teilen können.
  • MisterWong
  • Y!GG
  • Webnews
  • Digg
  • StumbleUpon
  • Reddit
  • Facebook