Why doesn't this Prolog rule work?

Question

I'm trying to implement a findall predicate in Prolog (yes I know it's built in, this is for an assignment).

It is written as follows:

my_findall(N,P,Pred,L) :- Pred, not(new(N,P)), !, assert(new(N,P)), my_findall(N1,P1,Pred,L1), L=[N,P,L1], retract(new(N,P)).
my_findall(_,_,_,  []).

For some reason it only gives me the first solution and stops there, as if the second call to my_findall fails. As I understand, the backtracking mechanism should go over all the possible options, which should include all the options for calling Pred(N,P), so even though the second call should fail on the first try (first option tried for Pred has already been asserted), it should try all the other options first before giving up and going to my_findall((,),_, []).

If that's not how it works, is there a way to force this kind of behavior without completely rewriting the solution?

Answer 1

Your Pred contains unbound variables. When in first iteration you call Pred, these variables are bound to first possible values. In your recursive step, Pred already has bound variables and they cannot change values. So... this solution will not work.

Trace from SWI-Prolog (I had to rename new/2 to item/2 for some reasons):

First level (calling: my_findall(A,B,member(p(A,B), [p(1,2), p(3,4)]), L). ).

   Call: (7) my_findall(_G819, _G820, member(p(_G819, _G820), [p(1, 2), p(3, 4)]), _G840) ? creep
   Call: (8) lists:member(p(_G819, _G820), [p(1, 2), p(3, 4)]) ? creep
   Exit: (8) lists:member(p(1, 2), [p(1, 2), p(3, 4)]) ? creep

We got p(A,B) = p(1,2). At this point A is bound to 1, B is bound to 2.

^  Call: (8) not(item(1, 2)) ? creep
   Call: (9) item(1, 2) ? creep
   Fail: (9) item(1, 2) ? creep
^  Exit: (8) not(item(1, 2)) ? creep

Ok, there is no item(1,2) in the database.

^  Call: (8) assert(item(1, 2)) ? creep
^  Exit: (8) assert(item(1, 2)) ? creep

Now item(1,2) is true. Recursive call:

   Call: (8) my_findall(_L215, _L216, member(p(1, 2), [p(1, 2), p(3, 4)]), _L199) ? creep

Let's get another solution do Pred:

   Call: (9) lists:member(p(1, 2), [p(1, 2), p(3, 4)]) ? creep
                          ^^^^^^^

See the underlined piece?

For this technique to work you probably should copy Pred, recursively changing N and P into new variables. For every iteration you have to "create" new pair of N and P. Check copy_term/2 (http://www.swi-prolog.org/pldoc/doc_for?object=copy_term%2f2).