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.

I would rather suggest, for a graph that has meshes in it:

d2 @ dist(V,D1) \ dist(V,D2) <=> D1 =< D2 | true pragma priority(1).

Otherwise you get duplicate dist/2 entries. A further remark would
be, you don’t need priority if you exhaust the search. i.e. if you don’t
need an early stop condition. Downside that you don’t have

the same stop condition, might take longer, or you have anyway a
problem where you need to compute the distance everywhere, and
then the exhaustion might be fine, not a bug, rather a feature.

I agree with your point.

The reason for I using D1 < D2 was because I directly copied the code from the paper at that time. However, if you carefully examine the example program from the CHRrp System, it definitely uses D1 =< D2.

If no priority, the result might be the same, but the performance is bad. This algorithm would degenerate into DFS.

For example,

image

?- e(a,1,b),e(b,10,c),e(a,2,c),e(c,3,d),e(d,4,e),source(a).

The execution logic would be roughly:

  1. d1 fires and produces dist(a,0)

  2. Now suppose dist(a,0) match e(a,1,b) and produce dist(b,1). At that time, the dist(b,1) will be an active constraint, which will continue to match e(b,10,c) and produce dist(c,11), which will continue to match e(c,3,d) and produce dist(d,14) and so on.

    These computations will be meaningless once you backtracks to dist(a,0) and matches e(a,2,c). In other words, c → d → e are duplicate computation. It is no longer the Dijkstra’s algorithm.

However, If the CHR system supports rule priorities, there is no the active constraint concept.

The execution logic would be roughly:

  1. d1 fires and produces dist(a,0)

  2. Now suppose dist(a,0) match e(a,1,b) and produce dist(b,1). At that time, the constraint store has dist(a,0) and dist(b,1), which would be “active”?

    The answer is dist(a,0), because for the rule

    d3 @ dist(V,D), e(V,C,U) ==> dist(U,D+C) pragma priority(D+2).
    

    dist(a,0) has priority D+2 = 0+2 = 2, while dist(b,1) as priority D+2 = 1+2 = 3, 2<3, so dist(a,0) has the higher priority.

    So the next constraint produced will be dist(c,2), which reflects the Dijkstra algorithm behavior.

P.S. I’m no expert on CHR and I’ve never successfully run the CHR^rp system, the above is just some logical reasoning. Correct me if I am wrong.

(Nothing of importance)

What do you mean by “area” argument?

I saw the link you gave is Flood Fill, but we were talking about Dijkstra’s Shortest Path. More precisely, the CHR program I mentioned above is a variant of Dijkstra’s Shortest Path: single source shortest paths in a weighted graph.

I searched that page and there is no mention of flood fill anywhere.

For single source shortest paths problem, Dijkstra’s algorithm does have some flood fill behaviors, but it give you more. It finds the shortest paths from the source node to all other nodes in the graph, producing a shortest-path tree.

The CHR program does not give you specific paths though, it gives you the lowest costs correspond to those paths, and it can be easily modified to produce specific paths (not just costs).

Note that you can flood fill a graph but it will only give you reachability, not the shortest paths (or the lowest costs).

A stopping condition can be provided, but is not required in this example, because it is just a variant of Dijkstra’s algorithm, i.e. single source shortest paths. See Dijkstra's algorithm - Wikipedia

The algorithm exists in many variants. Dijkstra’s original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

The notion of flood fill comes from how a distance map calculation
might spread when deploying a shortest path algorithm.

S = source, this is a single source distance map. Nothing to do
with a distance map that covers every vertex pair.

234567890123456
123456789012345
01###########5E
901234567890#45
890123456789#34
789012345678#23
678901234567#12
567890123456#01
456789012345#90
345678901234#89
234567890123#78
123456789012#67
S1###########56
123456789012345
234567890123456

Example grid from redblobgames website.

I know the Floyd–Warshall, but this thread discusses CHR^rp (CHR with rule priorities), and Dijkstra’s algorithm is a good example of using the CHR^rp system .

There are many ways to compute shortest path, such as Dijkstra, Floyd–Warshall, A*, etc. Each has pros and cons. For instance, Dijkstra often computes single source shortest paths, whereas Floyd-Warshall computes shortest paths between all pairs of vertices.

You can do Floyd–Warshall for your situation, but Dijkstra has its own applicable scenarios. It is not feasible for one algorithm to completely replace another.

Back to the CHR^rp system, because the priority queue behavior in Dijkstra’s algorithm can be elegantly expressed via rule priority in CHR^rp, that’s why I was discussing it here. For other algorithms, they are not within the scope of discussion unless they are relevant to the CHR^rp system.

I needed to explain to you what flood fill is, since you were lost! Nothing
todo with your on or off topic allegations. I am not sure whether you
understood it, since the diagram I showed did show the result of a

single source flood fill, so it showed a selection projection of the
distance map. It didn’t show a distance map for every vertex pair. You
made that up! You tend to jump to conclusions only to boycott a

discussion of CHR^rp. Shame on you! Please see also below:

I don’t know, now its me who is lost. And somebody of your caliber
might help me. Ordinary CHR didn’t perform well here, it was
way behind single source limited distance Dijkstra algorithm:

Do you say CHR^rp would perform better? How would you do day
21 with dynamic priorities? My guess you can speed it up with
CHR^rp straight away. The only problem is, just the same way I

am not a frequent user of ordinary CHR, I am also pretty new to CHR^rp!
The challenge for day 21 would be to have dynamic priorities, but also
to limit them. Since day 21 poses a limit on the number of steps.

I’m not sure what you are arguing about.

Your original reply in this thread were about:

  1. You pointed that the CHR program should use =< instead of <.

    I agreed with your point and explained why I chose < at that time.

  2. You pointed that “don’t need priority if you exhaust the search”

    I disagreed with your point and I’ve already explained the reason in this reply.

    What do you think of my explanation? I didn’t get any feedback.

Afterward, you brought up the “area” argument, Flood Fill, “DFS, and BFS have the same effort”, etc. (You have deleted those replies [8,10,11] though, I’m not sure whether they are still valid?)

Do you still believe that, in the Dijkstra algorithm example, priority is not needed if the search is exhausted? Or you just want to suggest a new shortest path algorithm, which is better than Dijkstra algorithm and does not require priority?

I have no idea about your point.

Could you provide an overview of the topic you would like to discuss?


The reason I mentioned “shortest paths between all pairs of vertices” is because in your previous reply, you assumed that I didn’t know Floyd-Warshall algorithm, so I had to tell you the main difference between Dijkstra and Floyd-Warshall.

However, after I wrote about the Floyd-Warshall, you edited the previous response and removed the Floyd–Warshall related information. This led to some abruptness in my response.

I do not boycott discussions of CHR^rp, but the discussions must be related to CHR or CHR^rp.

So please provide an overview of the topic you would like to discuss.

For the CHR program in the original post, YES. CHR^rp will perform better than the current CHR in SWI-Prolog, because it is essentially Dijkstra’s algorithm instead of naive DFS. I’ve explained it before.

I didn’t do Advent of code, so I don’t know day 21.

No, but I believe you can find it on the Internet.

It’s absolutely possible. Just restrict the starting set and ending set.

Maybe you didn’t pay attention where this came from?
It came from another thread, where I tried your code, but
ended up with =< instead of <:

Because it didn’t produce the correct result with ‘<’. With
‘=<’ it produces the correct result. Does this clear your mind?
Or are you still confused? With ‘=<’ it produces the correct result:

Now the next step would be to transform the above code from
CHR to CHR^rp, and see how it performs.

Edit 30.12.2023
I even gave credit to this thread in the other thread. By placing
a link. SWI-Prolog discourse automatically places a backlink,
which you find in the first post of this thread:

I was relying on this backlink. But maybe I should have placed
this backlink in my post and not rely on this automatic feature
of SWI-Prolog discourse. Seems I have caused a lot

of stress and made people psychotic.

There are many posts in the forum. You should not assume I’ve read all the posts. Especially a title like Advent of code. Again, you should not assume I must do Advent of code.

As I mentioned before, regarding the issue of < and =<, I agree with your point and I’ve also informed you about where this < actually comes from. See https://lirias.kuleuven.be/retrieve/303147

image

Are the < and =< all the points you want to discuss?

If it is, we can stop this discussion.

If not, you must provide an overview of the topic you would like to discuss.

Why I have to pay attention to the backlinks?

If you want to provide some background information, you should place the link explicitly in the reply under this thread, rather than relying on the backlinks feature of SWI-Prolog discourse.

Even if you provided an explicit link under this thread, you should not assume that I must track it. Some posts (like Advent of code 2023) are very long. You should first provide an overview of the topic you would like to discuss. No way I can read such a long post to extract the points you want to discuss.

Your are lucky that I am very patient. I can repeat it a 3rd time.

Nope, you posit absurd nonsense. I wrote already twice:

BTW: But my patience with your harassement has now an end:

I have flagged your last 3 posts and wrote “Person plays the fool.”.
It seems all you want to do is run in circles. Either you don’t understand
english or you simply ignore what I write, I even posted the full CHR code.

If you are not interested, why don’t you just keep quiet?
There are other people in this forum who might help. I nowhere
addressed @chansey97 exclusively. Whats wrong with you?

I have changed it into:

1 Like

OK. That’s great, but it just repeats my original post.

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


  1. You were challenging me.

    So I had to give you responses.

    I have explained in detail why priority is needed with Dijkstra’s algorithm.

    But unfortunately I didn’t get normal feedback but some weird responses, such as “area” argument, Flood Fill, “DFS, and BFS have the same effort”, A*, “Dijkstra’s algorithm is like Schrödingers Cat”, “I guess you have never heard of the Floyd–Warshall algorithm ?”, etc. (Most of these have been deleted or edited by you.)

    I really don’t know what you want to express.

    That’s why I asked you to provide an overview of the topic you would like to discuss!

  2. You must understand that this is MY THREAD.

    If some people’s discussions deviate from the original topic or introduce incorrect conclusions, I would have the right to provide response and steer the discussion back in the right direction.

    You can create your own thread and write down your ideas in that post. People who are interested will naturally go to your thread and discuss your ideas.