prolog negation \+

Question

There are four baskets, and each with a unique color. I write a prolog program to tell the color oder based on some facts and rules. This is the .pl file:

iright(L, R, [L | [R | _]]).
iright(L, R, [_ | Rest]) :- iright(L, R, Rest).
nextto(L, R, List) :- iright(L, R, List).
nextto(L, R, List) :- iright(R, L, List).

myprogram(Data) :-     =(Data, [_,red,_,_]), 
\+nextto(red,blue,Data), % blue is not next to red
iright(red,green,Data), %green is right to red
member(red,Data),
member(blue,Data),
member(green,Data),
member(yellow,Data).

The iright and nextto predicates are correct. My query is myprogram(Data), and I expect the result should be

Data = [yellow,red, green, blue]?
yes

but actually the prompt show that

| ?- myprogram(Data).

no

I know the problem is the negation, but idk how and why. Plz help.

When I use trace.

      1    1  Call: myprogram(_16) ? 
      2    2  Call: \+nextto(red,blue,[_46,red,_50,_52]) ? 
      3    3  Call: nextto(red,blue,[_46,red,_50,_52]) ? 
      4    4  Call: iright(red,blue,[_46,red,_50,_52]) ? 
      5    5  Call: iright(red,blue,[red,_50,_52]) ? 
      5    5  Exit: iright(red,blue,[red,blue,_52]) ? 
      4    4  Exit: iright(red,blue,[_46,red,blue,_52]) ? 
      3    3  Exit: nextto(red,blue,[_46,red,blue,_52]) ? 
      2    2  Fail: \+nextto(red,blue,[_46,red,_50,_52]) ? 
      1    1  Fail: myprogram(_16) ? 

(2 ms) no

Have you tried tracing the execution? Type trace. at the Prolog prompt. — Fred Foo
I think you just stumbled upon a case of floundering. If you want to know more try googling "sldnf floundering". — NotAUser

Sean McSomething Sean McSomething · Accepted Answer · 2012-11-21T00:43:48

If you move the \+nextto(red, blue, Data) to the last line of myprogram, it works.

It's a little unintuitive but you need to think a bit about how Prolog evaluates expressions & what negation really means. Negation means "there's no possible way for this to be true", not "can't be true for a particular set of values". If you strip your program down to simply:

 myprogram(Data) :-
    =(Data, [_,red,_,_]),
    \+nextto(red,blue,Data).

You will still get a No.. This is because, with what you've declared, Data can be [_, red, blue, _] - you see this decision made at Exit: iright(red,blue,[red,blue,_52]). Prolog tries to backtrack, but there's nothing else it can try - you haven't constrained any of the _s to have a particular value yet.

If, OTOH, you put all your nextto, member & iright statements before your negated statement, there's multiple possible solutions (well, two) to try when it gets to the negated expression: Data = [blue,red,green,yellow] and Data = [yellow,red,green,blue]. At this point, when it sees the negation it 'throws away' the 'branch' where red is next to blue, but it's able to backtrack and has a possible world state that makes the negation true. That is to say that:

myprogram(Data) :-
    =(Data, [_,red,_,_]),
    iright(red,green,Data),
    member(red,Data),
    member(blue,Data),
    member(green,Data),
    member(yellow,Data),
    \+nextto(red,blue,Data).

...gives you the desired results.

TL;DR - negation (and cuts, when you get to them) in Prolog are a lot more powerful than you think at first. Make sure you've figured everything else out first before using them.

prolog negation \+

1 Answers