Search code examples
prologswi-prolog

Forward chaining in Prolog, problem with multiple rules

in my previous question's best answer, I found a good example of forward chaining in Prolog. I have modified it a bit, but there is a problem with the last rule I tried to define (path). It doesn't work. With the current facts, I should be able to derive the path([a,b,c,d,e]), but it doesn't work.

Forward code:

:- op(1100, xfx, if).
:- op(1000, xfy, and).
:- op(900, xfy, or).
:- dynamic rule/1.                                                       

forward(Facts) :-
    fixed_point(nil, [true], Facts).                % Start with the base with only true

fixed_point(Base, Base, Base) :- !.                 % Reached a fixpoint
fixed_point(_, Base, Facts) :-                      % Base =/= Facts => not a fixpoint
    setof(Fact, derived(Fact, Base), NewFacts),     % Derive new facts
    ord_union(NewFacts, Base, NewBase),             % Add new facts to base
    fixed_point(Base, NewBase, Facts).              % Repeat with new base

derived(Fact, Base) :-                              
    rule(Fact if Condition),                        % Match a rule
    satisfy(Base, Condition).                       % Verify if condition is satisfied given base

satisfy(Base, Condition) :-
    Condition =.. [and, Elem|Bag],!,
    member(Elem, Base),                                     
    (   Bag = []
    ->  true
    ;   NewAtom =.. [and|Bag],       
        satisfy(Base, NewAtom)).
satisfy(Base, Condition) :-
    Condition =.. [or, Elem|Bag],!,
    (   member(Elem, Base)
    ->  true
    ;   (   Bag = []
        ->  false
        ;   NewAtom =.. [or|Bag],       
            satisfy(Base, NewAtom))).
satisfy(Base, Condition) :-
    member(Condition, Base),!.
satisfy(_, true):-!.
satisfy(_, false):-!,fail.

Here are rules and facts:

rule(eats_flies(fritz) if true).
rule(croaks(fritz)     if true).
rule(eats_flies(frotz) if true). % ADDED IN EDIT
rule(croaks(frotz)     if true). % ADDED IN EDIT
rule(sings(tweety)     if true).
rule(chips(tweety)     if true).
rule(has_wings(tweety) if true).
rule(croaks(krogr)    if true).
rule(chips(kroger)     if true).
rule(canary(X)         if and(sings(X),chips(X),has_wings(X))).
rule(frog(X)           if and(croaks(X),eats_flies(X))).
rule(green(X)          if frog(X)).
rule(yellow(X)         if canary(X)).
rule(node(a) if true).
rule(node(b) if true).
rule(node(c) if true).
rule(node(d) if true).
rule(node(e) if true).
rule(connected(a,b) if true).
rule(connected(b,c) if true).
rule(connected(c,d) if true).
rule(connected(d,e) if true).
rule(funny(c,d) if true).
rule(wonderful(X,Y) if or(nice(X,Y),funny(X,Y))).
rule(connected(X,Z) if and(connected(X,Y),connected(Y,Z))).
rule(path([Node|[]]) if node(Node)).
rule(path([Node, NextNode|Nodes]) if and(connected(Node, NextNode),path([NextNode|Nodes]))).

Critical rules:

rule(path([Node|[]]) if node(Node)).
rule(path([Node, NextNode|Nodes]) if and(connected(Node, NextNode),path([NextNode|Nodes]))).

What I get as output of the forward:

?- forward(A).
A = [true,canary(tweety),chips(kroger),chips(tweety),croaks(fritz),croaks(krogr),eats_flies(fritz),frog(fritz),green(fritz),has_wings(tweety),node(a),node(b),node(c),node(d),node(e),path([a]),sings(tweety),yellow(tweety),connected(a,b),connected(a,c),connected(b,c),connected(c,d),connected(d,e),funny(c,d),wonderful(c,d)].

EDIT:

Testing the code I found out that another problem is that if I add similar rules, such as:

rule(eats_flies(fritz) if true).
rule(croaks(fritz)     if true).
rule(eats_flies(frotz) if true).
rule(croaks(frotz)     if true).

The forward will only find that fritz is a frog, but not frotz.

Solution

  • Some problems in your code are:

    • Inappropriate use of operator univ (=..), just use unification (=). See why: 
      ?- (p and q and r) =.. [and,G|Gs], N =.. [and|Gs].
G = p,                        % <== this is the first goal of the condition
Gs = [(q and r)],
N = and((q and r)).           % <== this IS NOT a valid conjunction of the remaining goals

?- (p and q and r) = (G and Gs).
G = p,                        % <== this is the first goal of the condition
Gs =  (q and r).              % <== this IS a valid conjunction of the remaining goals
    • Do not use cut in satisfy(Base, Condition) :- member(Condition, Base), !., as this prevents predicate member/2 backtracking to find alternative answers (e.g., frog(fritz) and frog(frotz)).
    • As initially Base is the set [true], there is no need for the clause satisfy(_, true) :- !.. Note that true is already naturally satisfied by clause satisfy(Base, Condition) :- member(Condition, Base).
    • In Prolog, you only need to declare what is true, so there is no need for the clause satisfy(_, false):- !, fail..

    Taking into account all these observations, a correct code is as follows:

    :- op(1100, xfx, if).
:- op(1000, xfy, and).
:- op(900, xfy, or).
:- dynamic rule/1.

forward(Facts) :-
    fixed_point(nil, [true], Facts).                % Start with the base with only true

fixed_point(Base, Base, Base) :- !.                 % Reached a fixpoint
fixed_point(_, Base, Facts) :-                      % Base =/= Facts => not a fixpoint
    setof(Fact, derived(Fact, Base), NewFacts),     % Derive new facts
    ord_union(NewFacts, Base, NewBase),             % Add new facts to base
    fixed_point(Base, NewBase, Facts).              % Repeat with new base

derived(Fact, Base) :-
    rule(Fact if Condition),                        % Match a rule
    satisfy(Base, Condition).                       % Verify if condition is satisfied given base

satisfy(Base, G and Gs) :-    % Condition unifies with (G and Gs)
    !,
    member(G, Base),
    satisfy(Base, Gs).

satisfy(Base, G or Gs) :-     % Condition unifies with (G or Gs)
    !,
    (   member(G, Base)
    ;   satisfy(Base, Gs) ).

satisfy(Base, Condition) :-   % Condition is an atomic proposition
    member(Condition, Base).

% Knowledge base

rule(eats_flies(fritz) if true).
rule(croaks(fritz)     if true).
rule(eats_flies(frotz) if true). 
rule(croaks(frotz)     if true). 
rule(sings(tweety)     if true).
rule(chips(tweety)     if true).
rule(has_wings(tweety) if true).
rule(croaks(krogr)    if true).
rule(chips(kroger)     if true).
rule(canary(X)         if and(sings(X),chips(X),has_wings(X))).
rule(frog(X)           if and(croaks(X),eats_flies(X))).
rule(green(X)          if frog(X)).
rule(yellow(X)         if canary(X)).
rule(node(a) if true).
rule(node(b) if true).
rule(node(c) if true).
rule(node(d) if true).
rule(node(e) if true).
rule(connected(a,b) if true).
rule(connected(b,c) if true).
rule(connected(c,d) if true).
rule(connected(d,e) if true).
rule(funny(c,d) if true).
rule(wonderful(X,Y) if or(nice(X,Y),funny(X,Y))).
rule(connected(X,Z) if and(connected(X,Y),connected(Y,Z))).
rule(path([Node|[]]) if node(Node)).
rule(path([Node, NextNode|Nodes]) if and(connected(Node, NextNode),path([NextNode|Nodes]))).

    Examples:

    ?- forward(Base), member(path(P), Base), length(P, 5).
Base = [true, chips(kroger), chips(tweety), croaks(fritz), croaks(frotz), croaks(krogr), eats_flies(fritz), eats_flies(frotz), frog(...)|...],
P = [a, b, c, d, e] .

?- forward(Base), member(frog(X), Base).
Base = [true, chips(kroger), chips(tweety), croaks(fritz), croaks(frotz), croaks(krogr), eats_flies(fritz), eats_flies(frotz), frog(...)|...],
X = fritz ;
Base = [true, chips(kroger), chips(tweety), croaks(fritz), croaks(frotz), croaks(krogr), eats_flies(fritz), eats_flies(frotz), frog(...)|...],
X = frotz ;
false.

    REMARK I didn't check the correctness of all your code, just the most relevant parts to get the answers you wanted. But I saw that the precedence you assigned to the operator or is not adequate, as the logical connective or has lower priority than the logical connective and (note that, in predicate op/3, smaller numbers indicate higher priorities).