Please review my first CHR program

Help!
1

I’ve provided this answer to a Stack Overflow question using CHR, but it’s my first time writing a CHR program, so I’m pretty sure I’m doing some things the hard way and formatting the code badly. If any of you have experience with CHR, I would greatly appreciate your notes on how to improve the code. (I tried to join the CHR mailing list but it does not appear to have received either of my submissions).

One thing about CHR that confuses me a little is how one would take the result of running a CHR query and turn it back into (say) Prolog terms that could be further processed by Prolog. Is there a way to do that?

1 Like
2

It looks pretty good!

I noticed that you had to manually adjust the input data to not duplicate the project number where it repeats (i.e project 4). Since the project number isn’t that important to the problem, you can dynamically keep track of seen project numbers, and create a new project number when you see it again.
e.g.

project_seen_b4 @ seen_project(N,Count), project(N,Ps,Cs) <=> succ(Count,Count2), project(N-Count2,Ps,Cs), seen_project(N,Count2).
never_seen @ project(N,Ps,Cs) <=> .... , seen_project(N,1).

Note, your solution doesn’t find all possible solutions, for example:

project(1,[jane,claire],[brian, stephan]),
project(2,[jane,emma],[stephan, jones]).

is solvable, but not by your posted code. Solution left as an exercise to the reader!

You can query the CHR constraint database and convert to prolog terms using find_chr_constraint/1

e.g.

?- main, find_chr_constraint(parent(X,emma)).

will bind X to jane.

HTH.
Ian.

3

For comparison, my version written in CHR.

:- use_module(library(chr)).

:- chr_constraint child_of/2, candidate_parents/2, grouping/2.

project(N,Ps,Cs) :-
     grouping(Ps,Cs),
     project_children(N,Ps,Cs),!.

project_children(N,Ps,[C|Cs]) :-
     candidate_parents(C,Ps),
     project_children(N,Ps,Cs).
project_children(_N,_Ps,[]).

% if a child has two possible sets of mothers, mother must be in the intersection
intersect_parents @ candidate_parents(C,P1) , candidate_parents(C,P2) <=> intersection(P1,P2,P3), candidate_parents(C,P3).

% clean defunct constraints
dups @ child_of(X,Y) \ child_of(X,Y) <=> true.
trash @ grouping([],[]) <=> true.

% grouping with 1 element
single_match @ grouping([P],[C]), candidate_parents(C,_) <=> child_of(C,P).

% single candidate for a childs mother
single_parent @ candidate_parents(C,[P]) <=> child_of(C,P).

% remove child/parent combination from other groupings.
remove_from_groups @ child_of(C,P) \ grouping(Ps,Cs) <=> memberchk(C,Cs), memberchk(P,Ps) | selectchk(C,Cs,NCs), selectchk(P,Ps,NPs), grouping(NPs,NCs).

% Tests.

test1 :-
    project(1,[jane,claire],[brian,stephan]),
    project(2,[claire,jane],[emma,william]),
    project(3,[jane,claire],[william,james]),
    project(4,[jane,sophia,claire],[brian,james,isabelle]),
    project(4,[claire],[brian]),
    project(5,[jane],[emma]).

test2 :-
    project(1,[jane,claire],[brian,stephan]),
    project(2,[claire,jane],[emma,william]),
    project(3,[jane,claire],[william,james]),
    project(4,[jane,sophia,claire],[brian,james,isabelle]),
    project(4,[claire],[brian]),
    project(5,[jane],[emma]),
    project(7,[sally,sandy],[grace,miriam]).

test3 :-
    project(1,[jane,claire],[brian, stephan]),
    project(2,[jane,emma],[stephan, jones]).

P.S. My code is probably badly formatted also :smiley:

4

Thanks, Ian! My code solved the proposed problem at Stack Overflow; I had a sense that it might not be totally correct but I obviously didn’t give it enough thought. I spent a while thinking about your proposed case without seeing the solution. I really appreciate seeing your solution!

I hope someday a style guide for CHR comes about so we can figure out how to format this stuff…

5

For what it’s worth, I’ve decided my preferred format is like this:

c(A,B)
, d(e, f)
\ e(g, h)
<=> test(A)
| prolog_code(here).

If your rules are short, I don’t object to one-lining them.