Automatically backtrack over solutions for unbound constrained variable at the end of a query?

Help!
1

I have a simple constraint that I’ve built (code at bottom) noun/2 that says "X must be a noun". To test, the only noun in the world is “rock” and the only atom that is a rock is rock1:

?- noun("rock", X), X = rock1.
X = rock1.

?- noun("rock", X), X = rock2.
false.

If I want to find all X that meet the constraint I can use the resolveConstraints/1 predicate I wrote (code at bottom) to do that:

?- noun("rock", X), resolveConstraints(X).
X = rock1.

But I really want the system to automatically call resolveConstraints(X) if the constrained variable is left unbound at the end of the query. Right now, the system behavior appears to be to print the constraints:

?- noun("rock", X).
noun(rock,$VAR(X)).

Is there a way to change the behavior to what I want?

Here’s the code for my “constraint system”:

:- module(noun, [resolveConstraints/1, noun/2]).

attr_unify_hook(AttValue, VarValue) :-
    nonvar(VarValue) ->
        nounEval(AttValue, VarValue)
        ;
        fail.

noun(TypeName, X) :-
    var(X),
    put_attr(X, noun, TypeName).

nounEval("rock", rock1).

attribute_goals(X) -->
        { get_attr(X, noun, TypeName) },
        [noun(TypeName, X)].
    
% Backtrack over all values of Variable that meet the constraints
resolveConstraints(Variable) :-
    get_attrs(Variable, AttVars),
    recurseAtt(AttVars, Variable, [], Terms),
    comma_list(Conjunction, Terms),
    del_attrs(Variable),
    Conjunction.

recurseAtt([], _, ValueIn, ValueIn) :- !.
recurseAtt(Att, Variable, ValueIn, ValueOut) :-
    Att = att(Module, Value, More),
    atomic_list_concat([Module, 'Eval'], PredicateName),
    compound_name_arguments(Term, PredicateName, [Value, Variable]),
    recurseAtt(More, Variable, [Term | ValueIn], ValueOut).
2

As a quick remark, most constraint libraries provide a predicate labeling, often taking as first argument a list of variables for which to find concrete values and as second argument an option list that describes how the search process is to be done. The general scheme is that you create variables, add constraints to them and, when you need concrete values, call labeling/2 (this auto-links to the clp(fd) version).

What labeling/2 does depends a lot on the nature of the constraints. Roughly it will search for those variables that it thinks will propagate best and will try to fill these variables with the most promising concrete values. Binding a variable will either cause failure (backtracking) or cause the domain of other variables to be reduced. This process continues until all variables have a concrete value (or no answer is possible).

3

Thanks for the pointer, that is definitely what I was trying to do with my resolveContraints/1 predicate. I remembered having seen something like it before but I couldn’t remember the terminology for it (labeling) to search for it.

I was hoping to use this constraint library transparently in queries, which is why I was looking for a way to have the labeling happen automatically if there were free variables. Meaning, have the following:

?- noun("rock", X).

be able to be implemented with “plain old Prolog” or constraints, invisibly to the user. But to do that, I need the system to call labelling for free variables at the end of a query automatically.

Is there a way to hook whatever system is printing out the contraints for free variables and have it call the labeling predicate instead?

4

Maybe attribute_goals (+Var) // is what you want?
https://www.swi-prolog.org/pldoc/man?section=attvar-hooks

You can see how it’s done by doing a search through the various libraries that use attributed variables, such as library(dif) and library(when).

There’s also attvars_residuals in boot/attvar.pl.

(I’ll probably delete this posting when @jan gives a more definitive answer.)

1 Like
5

You are right. attribute_goals (+Var) // is the right interface. Its task is to examine the existing attributes and generate a goal that reinstantiates these attributes. To make it useful for the toplevel the generated goal must be simplified as much as possible.

As is, the toplevel never tries to label the remaining constraints. I think that would also be a dubious action. Using the above it can produce a good human readable description of the current constraints on the remaining variables.

6

This may be the right interface but I don’t think it does what the OP requested, i.e.," Automatically backtrack over solutions for unbound constrained variable", i.e., the returned goal(s) aren’t executed since:

which I think is appropriate. The top level should be passive in the sense that it only outputs the bindings of the variables as a result of executing the query. So IMO labeling should be done explicitly by the application.

In this particular example, perhaps renaming resolveConstraints to find or some such, would make it appear a little less clumsy, e.g.,

?- noun("rock", X), find(X).
X = rock1.

and is consistent with the conventional “apply test, then generate” constraint paradigm, e.g.,

?- freeze(X, X mod 2 =:= 0), between(0,5,X).
X = 0 ;
X = 2 ;
X = 4 ;
false.

Also note that if it can be determined that there is only one possible binding for X when the constraint is applied, it can (should?) be unified with that value at that time and no constraint is required. However, since the OP is interested in backtracking over solutions, that’s probably not the case here.

Just my 2¢.

2 Likes
7

I certainly don’t know enough about the constraints world to argue for labeling residual constraints in general, I’m sure there are good reasons not to do that.

In the prototype I’m sketching out (which i’m not sure I would call a “CLP Proper”, more like code that is using those mechanisms) I know that the only thing to do with a free variable at the end is to label it to get the answers and there aren’t any solver options to configure. It’s just an extra step that would be required. Kind of like if Prolog made you type report(X) on every remaining free variable in a (non-constraint) query to get the answers. Certainly doable, but a bit annoying.

I’ll try a different approach: Is there a hook or mechanism that the top-level uses to print out the list of residual constraints that I might use to do something like this?

8

The top level doesn’t output free variables, so I don’t think that advances your cause:

?- var(Y), F=f(X).
F = f(X).

The two hooks that the top level uses that I’m aware of if attribute_goals (which you already use) and project_attributes. The latter enables constraints on non-query variables to be projected back to query variables so they’re visible in the output. I suppose you could use one of these hooks to bind actual values to the variables but I’m not sure how the top level would react to this sudden change in binding. Perhaps the bigger issue is whether non-determinism would work in these circumstances, i.e., could you backtrack into one of these hooks to generate other bindings.

About the only advice I could offer is try it, but I’m pretty sure this is outside the scope of their intended design and there’s probably no guarantee this will continue to work (if it does indeed work) into the future.

Another possible issue is that attribute_goals is intended to support copy_term/3 so it could be called from other than the top level. This would suggest using attribute_goals to bind variables would break this predicate since no one would expect copy_term to do any binding.

9

Yeah, I was hoping more that the code that uses attribute_goals to print out residual constraints at the top level was somehow replaceable.