Search code examples
prolog

Prolog programm returns false and i cannot see why


My goal is to format the Term exactlyOneIsTrue(ListOfVars) into a regular term. For example, exactlyOneIsTrue([a,b]) would be turned into

or( and( a, not( b)) , and( not( a), b)).

The plan is to go through the original list, perform exactlyOne/3 for each member of the list, by counting through the list in exactlyOneLoop. However for a reason i cannot wrap my head around, when I try it, i just get "false".

exactlyOneLoop(Original,[_X],Counter,Return):-
    exactlyOne(Original,Counter,Return).
exactlyOneLoop(Original,[_,T],Counter,or(Chain,Return)):-
    C is Counter + 1,
    exactlyOne(Original,Counter,Chain),
    exactlyOneLoop(Original,T,C,Return).
    
%Part below works fine.

exactlyOne(List,Position,and(Positive,Chain)):-
    remove_at(Positive,List,Position,Negative),
    chainANDN(Negative,Chain),
    !.
    
chainANDN([X],Y):-
    simplify_expr(not(X),Y).
chainANDN([H|T],and(H1,T1)):-
    simplify_expr(not(H),H1),
    chainANDN(T,T1).
    
element_at(X, [X|_], 1).
element_at(X, [_|T], C) :- 
    C > 1,
    C1 is C - 1,
    element_at(X, T, C1).

remove_at(X, [X|T], 1, T).
remove_at(X, [H|T], C, [H|R]) :- 
    C > 1,
    C1 is C - 1,
    remove_at(X, T, C1, R).

I looked at a number of different Prolog programs working with lists, yet didn't catch any significant difference. I expected a logical formula to be returned.

?- exactlyOneLoop([a,b,c],[a,b,c],1,R).
false.

?- exactlyOneLoop([a,b,c],[c],3,R).
R = and(c, and(not(a), not(b))) ;
false.

Solution

  • To understand why your first query fails it is sufficient to generalize your program a bit. Simply by removing several goals, here shown with a prefix * in front of those goals. Since the resulting program still fails, there must be an error in the remaining visible part.

    ?- exactlyOneLoop([a,b,c],[a,b,c],1,R).
       false, unexpected.    
    
    :- op(950, fy, *).
    
    *_G_0.
        
    exactlyOneLoop(Original,[_X],Counter,Return):-
        * exactlyOne(Original,Counter,Return).
    exactlyOneLoop(Original,[_,T],Counter,or(Chain,Return)):-
        * C is Counter + 1,
        * exactlyOne(Original,Counter,Chain),
        exactlyOneLoop(Original,T,C,Return).
    
    ?- exactlyOneLoop(Xs,Ys,C,R).
       Ys = [_A] % too general, but could be OK
    ;  Ys = [_A,[_B]], R = or(_C,_D), unexpected
    ;  Ys = [_A,[_B,[_C]]], R = or(_D,or(_E,_F)), unexpected
    ;  ... .
    ?- Ys = [_,_,_|_], exactlyOneLoop(Xs,Ys,C,R).
       false, unexpected.
    

    In case the error is not evident, it often helps to ask the most general question which gives now unexpected answers. And there is no solution for a list with three or more elements.

    In case this is not enough, let's dig deeper into the last query! There, we can generalize the program even further!

    exactlyOneLoop(Original,[_X],Counter,Return):-
        * exactlyOne(Original,Counter,Return).
    exactlyOneLoop(Original,[_,T],Counter,or(Chain,Return)):-
        * C is Counter + 1,
        * exactlyOne(Original,Counter,Chain),
        * exactlyOneLoop(Original,T,C,Return).
    
    ?- exactlyOneLoop(Xs,Ys,C,R).
       Ys = [_A]
    ;  Ys = [_A,_B], R = or(_C,_D)
    ;  unexpected.  % missing further answers 
    ?- Ys = [_,_,_|_], exactlyOneLoop(Xs,Ys,C,R).
       false, unexpected.