Package of CHR with dynamic rule priorities?

Help! Pack
,
7

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.