Residual goals for CHR

[bakaq]

I'm looking into implementing Constraint Handling Rules in Scryer as a module, and I think it can be done with just term_expansion/2, goal_expansion/2 and bb_b_put/2, but there is one part that I'm not sure how to implement, and that is the "residual goals" (not sure if this is the right term in this context).

I know Scryer has some way to do it, because it has residual goals with attributed variables, but in the little I have delved into it, it seems that it's very attached to the toplevel. Is there a general way of doing residual goals that I'm not aware of or is it necessary to modify the toplevel to make it possible to do this in a new module? If there isn't a general way to do residual goals, should we add a way to do this?

[UWN]

CHRs are not really constraints, but something close. They need an explicit notion of a store. And thus they do not enjoy the same algebraic properties as constraint systems do. Also, it seems that interest in them has waned. The current implementation in SWI is incompatible with occurs-check unification being activated at the same time. So this would not be an easy port.

There are definitely more grateful tasks to consider.

[bakaq]

I know that implementing CHR is kind of pointless and low priority, but for me this seems like something that would be very fun to implement and it's just out of my comfort zone. Making stupid pointless things is one of the best ways to learn, and I may stumble on some deeper more fundamental errors while implementing them (like #2063 and #2065 when improving dif/2, #2037 and #2042 while implementing phrase_from_stream/2, #2059 while implementing constrained.pl, and #2217 while implementing when/2).

My plan was to make "the stupidest possible implementation" just as a learning experience and maybe as a decent base to optimize later. No smart algorithms, just bruteforcing the pattern matching to make it work for simple cases.

I believe you that there are better directions to channel my enthusiasm into. Last time you pointed me to dif/2 and that was very productive. I read most of the open issues here on Scryer trying to find something that I could actually do, and that's why I implemented when/2 recently. Most of the issues involve the low level details of the engine that I'm trying to get into for months. I'm currently reading the WAM book and making a toy implementation just to learn how it works so that I can help more in the low level Rust parts of Scryer.

For now though the parts that are most accessible to me are the "high level" Prolog only parts and attributed variables, which have the benefit that they could be ported to other compatible enough systems without much difficulty (I know that Trealla has adopted my improved dif/2 implementation verbatim for example) and therefore are improvements not only to Scryer but to Prolog in general. What in your opinion would be some good higher priority tasks for me to focus on?

[triska]

Every module that attaches attributes to variables can describe residual goals as a relation between an attributed variable and a list of goals, described with the DCG nonterminal attribute_goals//1 defined in that module.

If this nonterminal is present in a module where attributes of a variable stem from, then, when residual goals are needed, it is automatically invoked with the variable as argument. The nonterminal must describe a list of goals that, when called, cause equivalent attributes to be present on that variable. Also, it should remove the attributes it has translated to such goals.

For example, in library(dif), it is defined as:

attribute_goals(X) -->
    { get_atts(X, +dif(Goals)) },
    gather_dif_goals(X, Goals),
    { put_atts(X, -dif(_)) }.

The interface to relate terms to residual goals is copy_term/3, which is automatically invoked by the toplevel. It is copy_term/3 that calls attribute_goals//1 if it is present. For example:

?- dif(X, Y), copy_term(X-Y, X-Y, Gs).
   Gs = [dif:dif(X,Y)], ... .

[bakaq]

Yes, I know about this. However, as far as I know (I don't know much about CHR, correct me if I'm wrong @haijinSk), you can have residual goals without variables there. Imagine the leq/2 constraint that I've seen many examples:

reflexivity   leq(X,X) <=> true.
antisymmetry  leq(X,Y), leq(Y,X) <=> X = Y.
idempotence   leq(X,Y) \ leq(X,Y) <=> true.
transitivity  leq(X,Y), leq(Y,Z) ==> leq(X,Z).

With just these rules, there is nothing that says that leq(1, 2) is true, but as I understand it these constraints would still work like this:

-? leq(1, 2), leq(2, 3).
   leq(1,2), leq(2,3), leq(1, 3).

There are no variables to attribute here, so I think this can't use the existing attribute_goals//1 system.

[triska]

In short, what you see here is not the Prolog code that is actually running when you try the example, because these sample definitions are only Prolog facts.

You can define goal expansions to expand these facts to any Prolog clauses you want. These clauses can introduce variables and attach attributes as you need them. The residual goals can omit any variable that is not needed.

[bakaq]

You can define goal expansions to expand these facts to any Prolog clauses you want. These clauses can introduce variables and attach attributes as you need them. The residual goals can omit any variable that is not needed.

Ooohhh, this is really smart. I believe I could make a dummy variable that is otherwise useless just to have attributes so that residual goals can be shown, right?

Yeah, it does work! Look:

%% Contents of residual.pl
:- module(residual, []).

:- use_module(library(atts)).
:- use_module(library(dcgs)).

:- attribute test_attr/1.

user:goal_expansion(test, (
    residual:put_atts(X, test_attr(test_residual(2,2,3))),
    % Needed to avoid a singleton variable warning.
    % Is there a better way of doing this?
    _ = X 
)).

attribute_goals(Var) -->
    { get_atts(Var, test_attr(T)) },
    [T],
    { put_atts(Var, -test_attr(_)) }.
%% End of contents of residual.pl

?- use_module(residual).
   true.
?- test.
   test_residual(1,2,3). % Wow, no variables, yet an residual goal.

Thank you very much.

[triska]

You are welcome! Now that CHR is almost done, may I suggest you also look into CLP(Q)? That would be an awesome component, and a working CLP(Q) implementation would make Scryer the first freely available Prolog system that has one!

[bakaq]

Now that CHR is almost done

It's not almost done, I haven't even started. I just wanted to confirm we have all the parts I think are needed for a very basic implementation.

may I suggest you also look into CLP(Q)?

I REALLY wanted a CLP(Q) or CLP(R) implementation, I miss this kind of functionality a lot. I never used the interface so I don't know how it works or how it should work, but I started doing something in this direction a few months ago. I was making predicates to reason about unions of intervals with open and closed borders, which I think is the basis of a numeric real/rational constraint system (like what I think Prolog IV has). From what I know CLP(Q/R) from something like SICStus is more for solving linear constraints in a more symbolic way, and I really don't know how to even start there.

a working CLP(Q) implementation would make Scryer the first freely available Prolog system that has one!

Doesn't SWI also has an implementation of CLP(Q/R)? Or that one doesn't count to you for some reason?

[triska]

As far as I know, other implementations are not correct, an example of a correctness issue is SWI-Prolog/issues#94. It would be great to have a correct implementation in a freely available Prolog system.

[lortabac]

What's the status of this project? I'm very interested in having a CHR implementation for Scryer.

[bakaq]

Completely useless at the moment. I hadn't had much time to work on Prolog related stuff lately and this is included in that. I do intend to get back to it eventually, but I don't know when. I also don't want to prevent anyone doing another CHR implementation for Scryer just because I said I started doing one, more implementations would be good. If you can't wait and you have the time and interest you could try to implement it.