Package of CHR with dynamic rule priorities?

[chansey97]

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.

[chansey97]

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.

[abaljeu]

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.

[chansey97]

@abaljeu

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

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.

[abaljeu]

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.

[j4n_bur53]

@chansey97

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

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.

[chansey97]

@j4n_bur53

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.

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.

@j4n_bur53

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.

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

For example,

?- 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.

[chansey97]

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.

[chansey97]

@j4n_bur53

If you check Wikipedia, the pseudo code also describes flood fill:

Dijkstra’s algorithm - Pseudocode
Dijkstra's algorithm - Wikipedia

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

@j4n_bur53

If you use this code below, it does flood fill. CHR produces all solutions:

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).

@j4n_bur53

How do you implement a stopping condition? Or does priorized-CHR offer
a special query to ask for the first solution given a destination? You even
didn’t model destination/1 only source/1.

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.

[chansey97]

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.

[chansey97]

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?

---

@j4n_bur53

It didn’t show a distance map for every vertex pair. You
made that up!

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.

@j4n_bur53

You tend to jump to conclusions only to boycott a

discussion of CHR^rp. Shame on you!

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.

@j4n_bur53

Do you say CHR^rp would perform better?

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.

@j4n_bur53

How would you do day
21 with dynamic priorities?

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

@j4n_bur53

Do you have some code for Dijkstra algorithm with a source and a destination?

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

@j4n_bur53

Its actually possible for the Floyd-Warshall algorithm to provide a source and
a destination.

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

[chansey97]

@j4n_bur53

Maybe you didn’t pay attention where this came from?

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.

@j4n_bur53

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:

Here the result for the tester 11x11 from the part 1 description:

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

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.

[chansey97]

@j4n_bur53

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:

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.

[j4n_bur53]

(Nothing of importance)

[chansey97]

@j4n_bur53

@j4n_bur53

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

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)?

---

@j4n_bur53

If you are not interested, why don’t you just keep quiet?

1. You were challenging me.

   @j4n_bur53

   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.

   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.

[chansey97]

We’re talking about Dijksta’s algorithm (at least shortest path problem), right?

Why are you suddenly discussing Flood Fill?

@chansey97

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?

[chansey97]

@j4n_bur53

Because producing a shortest-path tree is a form of flood fill.

OK.

Does the “area” argument still hold? i.e. the effort of Dijkstra and DFS are the same, when producing a shortest-path tree?

[chansey97]

@j4n_bur53

I didn’t apply the argument to a tree, this here is a mesh its not a
proper tree. Its a mesh because there are different paths with
same length reaching the same goals respectively subgoals, different

This is where your digression begins.

1. You didn’t answer my question directly.

2. You gave me many unrelated information.

   @j4n_bur53

   I didn’t apply the argument to a tree, this here is a mesh its not a
   proper tree.

   @j4n_bur53

   Its a mesh because there are different paths with
   same length reaching the same goals respectively subgoals, different

   combination of edges might lead to identical vertices

   I never said “apply the argument to a tree”, the surprising things “tree” and “mesh” were introduced by you, which makes me overwhelmed. For the shortest path problem, we usually discuss directed graphs or undirected graphs.

   I don’t know why you suddenly introduce meshes? We are talking about graph, right?

   @j4n_bur53

   The numbers are just the single source distance modulo 10.

   I don’t know what is single source distance modulo 10. No any explanation.

   You provide a lot of information and images, but without any precise context.

   @j4n_bur53

   One has also to distinguish between flooding a whole area without
   having a “stop condition” from having a “stop condition”. The website
   calls it “early exit”. Both can be constructed via Dijkstra algorithm:

   It sounds like the flood fill you’re talking about (assuming it would produce a shortest path tree) still requires Dijkstra, right?

   The critical question is: if you do the same thing, but using DFS instead of Dijkstra, are their algorithmic complexity the same? Have you compared the two?

[chansey97]

I think we can stop the discussion.

[j4n_bur53]

There was never any sort of discussion, only various attempt to discredit me.
I hope you had fun! Even “scientific truth” didn’t stand your mocking. LoL
Shame on you! You even made fun of my visualization explanation:

@chansey97

@j4n_bur53

The numbers are just the single source distance modulo 10.

I don’t know what is single source distance modulo 10.

Also because of your irrational behaviour you missed the oportunity
of working on day 21 of AoC 2023. Nevermind, the forum has other people,
and I am not repelled by your behaviour in doing it myself. I only wasted

an awful amount of time with explaining some trivialities.