Satisfying a set of goals in Prolog

Question

In Prolog I often solve a problem by providing a template (a structure containing variables) and then satisfying a set of constraints on it. A trivial example might be:

go(T) :-
    T = [_, _, _],
    member(cat, T),
    member(dog, T),
    member(mouse, T).

And in practice the set of constraints is generated some other way rather than being fixed, and I have to write a recursive predicate to satisfy each constraint in turn:

go(T) :-
    T = [_, _, _],
    findall(A, animal(A), As),
    % satisy member(A, T) for each A in As
    fill_in_animals(T, As)

fill_in_animals(T, []).
fill_in_animals(T, [A|Rest]) :-
    member(A, T),
    fill_in_animals(T, Rest).

Note that my question isn't about list related constraints, and even the parameters to the constraint cannot always be easily generated as a list to be passed to a relatively simple helper predicate as used above. In practice I find the helper is a rather ungainly predicate that I write each time, which:

1. Accepts a template, several parameters to be used for the constraint (and hence for binding the template's variables to useful values), and a variable for indicating which constraint it is up to.
2. Generates a constraint to satisfy in this iteration, applying it to the template.
3. Recursively calls itself so that the remaining constraints can be satisfied.

What I'm looking for is a predicate along the lines of findall, etc, which will satisfy a set of goals, one after the other. Something like:

% satisfyall(:Goal)
% backtracks on Goal but keeps all bindings from each fully satisfied goal.

satisfyall((animal(A), member(A, T)))

The answer I'm looking for does not have to be in this form. In fact there may be a contradiction between backtracking on a goal and maintaining each set of bindings resulting from it.

I hope I've explained my problem so that it's reasonably clear what would help. (If not let me know.) Apologies in advance for the long-winded question!

Update (2 years later)

I'll try it out later today and update my question!

Note that I never said I'd update the question the same day as trying . ;-)

@CapelliC has steered me in the right direction, and I've found a pattern which seems to work pretty well:

?- Gs = [member(red),member(blue)], T = [_,_], foreach(member(G, Gs), call(G, T)).
T = [red, blue] ;
T = [blue, red] ;

Answer 1

You surely know that backtracking will need to undo changes done to work. That's the core of Prolog algorithm, and the source of Prolog power.

It's also a weakness point, when it come to more usual computations, like those necessarily involved with side effects, or loops.

To find the right way to force our rules working along a deterministic path can be difficult, probably because that's not the way Prolog is supposed to work.

Well, now, stopping philosophy rants, let's see what Prolog's gurus have made available to us: SWI-Prolog offers library(aggregate), where you find foreach, that I think does much of what you're after:

?- foreach(animal(X), member(X,L)).
L = [cat, dog, mouse|_G10698] .

Studying such complex builtin could give you some idea for your implementation (use ?- edit(foreach). from console to inspect the source).

Note that it separates Generator and Goal, while in your question they are hopeless united. That's of course needed to be able to backtrack only over the generator part.

BTW, try to understand the tiny example listing in doc page. It's overly complicated by dif/2, but you'll really need to grasp the behaviour of bindings to be able to generalize your recursive predicates.

HTH

Answer 2

The situation you describe in the question is a little different from the signature of the satisfyall/1 predicate you gave. There's no backtracking involved in the fill_in_animals example, at least not with respect to the variables that flow out of go/1. There might be "petit backtracking" in the satisfaction of subgoals, but the overall goal doesn't fail while leaving bindings intact.

A trite, and probably unhelpful solution is to use maplist/2. For instance, your example is easy to achieve this way:

?- length(L, 3), maplist(animal, L).
L = [cat, cat, cat] ;
L = [cat, cat, dog] ;
L = [cat, cat, mouse] ;
L = [cat, dog, cat] ;
...
L = [mouse, mouse, dog] ;
L = [mouse, mouse, mouse].

You could go on to use a materialized database by adding just one predicate:

% just flips the arguments of member/2
memberof(L, A) :- member(A, L).

Then we can use findall/3 to do the work:

?- findall(A, animal(A), Animals), 
   length(L, 3), 
   maplist(memberof(Animals), L).

Animals = [cat, dog, mouse],
L = [cat, cat, cat] ;
Animals = [cat, dog, mouse],
L = [cat, cat, dog] ;
Animals = [cat, dog, mouse],
L = [cat, cat, mouse] ;
...
Animals = [cat, dog, mouse],
L = [mouse, mouse, dog] ;
Animals = [cat, dog, mouse],
L = [mouse, mouse, mouse].

This should make it clear why lambda.pl would help. You wouldn't need the helper predicate, you could simply write:

?- findall(A, animal(A), Animals), 
   length(L, 3), 
   maplist(\Animal^member(Animal, Animals), L).

(untested)

If you are really intent on circumventing the variable binding and unbinding, I think you're going to create a debugging nightmare for yourself, but SWI-Prolog has a global variable facility you can use. I vaguely recall reading somewhere that asserta/retract are insufficient for this task.

The more I think about it, the more it feels to me like there isn't going to be a meaningful implementation of satisfyall/1 that differs substantively from maplist/2, but I'm looking forward to finding out I'm wrong.