How are Prolog and CHR supposed to interact?

Constraints and backtracking iteration, cuts, term copying or tabling do not go well together. Some combinations work. It requires quite detailed knowledge of the specific constraint library to understand what you can use and what not. Meta predicates that do not fall in any of these categories are fine. Notably call/N and maplist/N. Some of the issues:

  • backtracking
    The constraint representations are all subject to backtracking. Notably forall/2 does not work. foreach/2 does, but is subject to some semantic ambiguity as well.
  • cuts
    Including \+/1, if->then;else, etc may prune the search space in ways that are not anticipated. Notably because some goal may be logically false, but succeeds with pending constraints. You are ok if you label before the commit.
  • term copying
    May seem safe as it also copies the constraints, but for CHR, the constraints are elsewhere and in general copying a variable with constraints may copy a huge constraint network and upset the sometimes complex and fragile assumptions on the constraints by some constraint library. Your millage may vary …
    -tabling
    SWI-Prolog’s tabling does not support it at all now. That is likely to change at some points. Tabling too copies thiough, so the issues around copying typically apply.
1 Like

I should add my say, since I’ve probably written way more CHR code than is ever reasonable, so I know a few things. find_chr_constraint is linear in the size of the store. CHR rules are vastly more efficient, as they will go directly to the constraint being searched and can use hash-searching, if they have the write type and mode declarations. If you were to profile (SWI feature) a program that creates constraints, you will see that all the CHR is just compiled into Prolog predicates and you will see them in your profile report. If you got the listing of these generated predicates, you could see when they are doing linear searches and when they are hash lookups. (ints are hashed, and most other things are not.)

Since CHR compiled is just SWI code, involving attributed variables, when clauses, and not much else, backtracking works brilliantly. Cuts are fine if you know what cuts do. Beware of working with non-grounded variables in non-logical ways (e.g. using ==), but in my experience CHR doesn’t compile non-ground efficiently anyway, so I tend to use ground terms whenever possible.

The exception is query constraints. If a bunch of rules establish constraint objects, If I know the keys, I can extract values with

my_result(Key, Value) \ get_my_result(Key, Var)  <=> Var = Value.

I can likewise write a set of rules to retrieve a collection of result objects, getting a list.

I would not ever copy terms that involve CHR managed variables. If performance is an issue, I would study CHR’s type/mode declarations, and profile and optimize. Eventually, if you want high performance, you would recode into straight Prolog because there’s no question there’s a 10x overhead for using the CHR formalism for simple things. That said, for complex things, it can do things that are hard to fathom without it.

3 Likes