Package of CHR with dynamic rule priorities?

Recently I have read some papers about CHR(Constraint Handling Rules). It is indeed a very powerful language (especially for expressing algorithm’s intent) and in most cases the refined operational semantics is sufficient.

However, I am not satisfied. I want more (I’m greedy, sorry).

Is there a CHR package that supports Constraint Handling Rules with dynamic rule priorities in swi-prolog (or other prolog systems I could try)?

For example, Dijkstra’s Shortest Path can be written in 3 lines if it supports dynamic rule priorities.

d1 @ source(V) ==> dist(V,0) pragma priority(1).
d2 @ dist(V,D1) \ dist(V,D2) <=> D1 < D2 | true pragma priority(1).
d3 @ dist(V,D), e(V,C,U) ==> dist(U,D+C) pragma priority(D+2).

The pragma priority(D+2) schedules the rule applications first that deal with shorter distances, which saves us from having to manually maintain a priority queue (e.g. heap).

I am extremely looking forward to try this language in swi-prolog.

Thanks.

I eventually found the source code of CHRrp system (see The CHR-rp System).

The good news is that it still compiles fine (with some minor changes) in the current SWI-Prolog. The bad news is it doesn’t seem to support dynamic priority?

For example,

%% dijkstra.chr
:- chr_constraint source(+), e(+,+,+), dist(+,+).

source(V) ==> dist(V,0) pragma priority(1).
dist(V,D1) \ dist(V,D2) <=> D1 < D2 | true pragma priority(1).
dist(V,D), e(V,C,U) ==> DC is D + C, dist(U,DC) pragma priority(D+2).
?- consult(["c.pl "]).
true.

?- main(dijkstra).
database:constraint(dist/2,[+,+],[any,any]),
database:constraint(e/3,[+,+,+],[any,any,any]),
database:constraint(source/1,[+],[any]),
database:constraint_index(dist/2,[1],1,2),
database:constraint_index(e/3,[1],2,2),
database:constraint_index(dist/2,[],0,1),
database:constraint_index(e/3,[],2,1),
database:constraint_index(source/1,[],1,1),
database:join_order(3,k(2),[k(1)]),
database:join_order(3,k(1),[k(2)]),
database:join_order(2,k(1),[r(1)]),
database:join_order(2,r(1),[k(1)]),
database:join_order(1,k(1),[]),
database:max_occurrence(e/3,2,1),
database:max_occurrence(dist/2,2,1),
database:max_occurrence(dist/2,1,2),
database:max_occurrence(source/1,1,1),
database:nb_constraint_indexes(e/3,2),
database:nb_constraint_indexes(dist/2,2),
database:nb_constraint_indexes(source/1,1),
database:nb_rules(3),
database:no_check_activation_call(3),
database:no_check_activation_call(2),
database:no_check_activation_call(1),
database:occurrence(e/3,3,k(2),2,1),
database:occurrence(dist/2,3,k(1),2,1),
database:occurrence(dist/2,2,k(1),1,2),
database:occurrence(dist/2,2,r(1),1,1),
database:occurrence(source/1,1,k(1),1,1),
database:rule(3,no,$VAR(_A)+2,[dist($VAR(_B),$VAR(_A)),e($VAR(_B),$VAR(_C),$VAR(_D))],[],[],[$VAR(_E)is$VAR(_A)+ $VAR(_C),dist($VAR(_D),$VAR(_E))]),
database:rule(2,no,1,[dist($VAR(_F),$VAR(_G))],[dist($VAR(_F),$VAR(_H))],[$VAR(_G)< $VAR(_H)],[true]),
database:rule(1,no,1,[source($VAR(_I))],[],[],[dist($VAR(_I),0)]),
schedule_depth(3,k(2),1),
schedule_depth(3,k(1),0),
suspension:fix_suspension_layout,
suspension:uses_history(source/1),
suspension:uses_history(dist/2),
suspension:uses_history(e/3) . <---- There is a choice point, but I don't know what it means. I press `.` .

?- consult("dijkstra.pl").
true.

?- source(1), e(1,3,2),e(2,8,4),e(1,5,3),e(3,2,4),e(2,1,3), check_activation, show_store.
dist(1,0)
e(1,3,2)
e(2,8,4)
e(1,5,3)
e(3,2,4)
e(2,1,3)
source(1)
true.

It only produced one dist(1,0) constraint. Maybe I missed something?

Using the same approach, the leq.chr can work normally.

%% leq.chr
:- chr_constraint leq/2.

leq(X,X) <=> true pragma priority(1).
leq(X,Y), leq(Y,X) <=> X = Y pragma priority(1).
leq(X,Y) \ leq(X,Y) <=> true pragma priority(1).
leq(X,Y), leq(Y,Z) ==> leq(X,Z) pragma priority(2).
?- leq(1,2),leq(2,3),leq(3,4), check_activation, show_store.
leq(1,4)
leq(2,4)
leq(3,4)
leq(1,3)
leq(2,3)
leq(1,2)
true.

Unless I’m mistaken, priority doesn’t matter for leq as defined above?

Normally CHR will try rules in listed order but for most rule sets even this doesn’t matter. It’s usually a good idea to code so that order of rule selection is irrelevant although it can be convenient to have simplifying rules happen before complicating rules, to reduce algorithm complexity.

In this example, yes.

But in general, rule priority is important, when a suspended constraint be triggered.

Note that constraint store should be seen as a set (instead of ordered list, or something like that), there is no any semantics to determine which constraint should be triggered first.

For example,

Consider that we want to check whether two graphs, G1 and G2 are equal. We do this by removing those edges that are common to both graphs. If there are still edges after reaching a fixed point, then the graphs are different.We represent the edges of graph G1 and G2 by the edge constraints e1/2 and e2/2 respectively. This gives us the following program

s1 @ e1(X,Y) \ e1(X,Y) <=> true pragma priority(1).
s2 @ e2(X,Y) \ e2(X,Y) <=> true pragma priority(1).
rc @ e1(X,Y), e2(X,Y) <=> true pragma priority(2).

Edges obey set semantics, as implemented by the rules s1 and s2.
The rule rc (remove common) removes those edges that appear
both in graph G1 and in graph G2 Now consider the query:

?- e1(X,X), e2(X,Y), e2(Y,X), X = Y.

When executing this query using the refined operational semantics, ignoring the rule priorities, the X = Y built-in constraint causes the sequential activation of all three CHR constraints. If the e1/2 constraint is activated before any of the e2/2 constraints, then rule rc fires before the s2 rule is tried, which results in a final constraint store containing the e2(X,X) constraint which erroneously indicates that the graphs are different.

using rule priorities, the set semantics rules will always be tried before the lower priority rule rc and when the highest priority fireable rule instance is one of priority 2 (or less), then there will be no two syntactically equal e1/2 or e2/2 constraints.

The above example can be implemented correctly using the refined semantics, but this leads to inefficient and unreadable code:

s1@ e1(X,Y) \ e1(X,Y) <=> true.
s2@ e2(X,Y) \ e2(X,Y) <=> true.
s3 @ e1(_,_), e1(X,Y) \ e1(X,Y) <=> true.
s4 @ e1(_,_), e2(X,Y) \ e2(X,Y) <=> true.
s5 @ e2(_,_), e1(X,Y) \ e1(X,Y) <=> true.
s6 @ e2(_,_), e2(X,Y) \ e2(X,Y) <=> true.

PS. The above contents are just about static priorities. The dijkstra’s shortest path uses dynamic priorities, which is more advanced.

This all sounds right. I will note that in practice in the Leuven compiler, rule priority is defined by the lexical ordering of rules. To implement Dijkstra’s algorithm I would have to introduce another constraint and probably two rules that establish reduction order dynamically.