Need Help Understanding Somethings In Prolog

Am a beginner in Prolog and finding it hard to understand how backtracking works when using rules. I don't even know if backtracking works in rules(want to know it properly).

I have the following program that sums all the even integers in a list. I wrote it myself but finding it hard to understand the steps it takes to find the solution.

evenN(X):- (X mod 2) =:= 0.

sumEven([], 0).
sumEven([H|T], X):- evenN(H), sumEven(T,Y), X is Y+H.
sumEven([H|T], X):- \+evenN(H), sumEven(T,X).

output:::

?- sumEven([1,2,3,4,5,6],X).
X = 12

Need help in understand it better. I try to use the trace utility to understand the output but i don't understand it, that is why am asking it here.

QUESTIONS:

1)

When i comment out the second rule(last line), it gives me fail as an answer because 1 is not an even number and the whole sumEven() fail because evenN() fails which i understand. My question is: what happens afterwards? Does it go back to the top and try the sumEven([], 0) fact or ? I just want to know what happens.

2)

When the last li开发者_JAVA百科ne(second rule) is included, and the first rule fails, when it backtracks, does it look for another sumEven() that follows it(like the way the second rule follows the first rule which fails) or it goes back to the top and test sumEven([], 0) fact and start it from there?

I need to understand how it backtracks when rules are being used in prolog specifically in recursive situations like this one.

3) I found the following code(recursive) on the net. It divides a list into positive and negative lists.

% predicates
    split(list,list,list)

% clauses
    split([],[],[]).
    split([X|L],[X|L1],L2):-
        X>= 0,
        !,    
        split(L,L1,L2).

    split([X|L],L1,[X|L2]):-
        split(L,L1,L2).

Output :        

Goal: split([1,2,-3,4,-5,2],X,Y)

X=[1,2,4,2], Y=[-3,-5]

Can someone help me to understand the way it works to find the solution? I mean i want to understand step by step how it executes to come up with the solution.

---

Matching clauses are tried in the order they appear in the program. In nice declarative Prolog programs, the order of clauses does not change the meaning of your program. This is close to logic, where disjunction is commutative. sumEven/2 has this property. It is spectacularly misnamed though, since the sum is the second argument of the relation, not its first. A better name would be for example even_sum/2, you may come up with even better names. split/3 uses !/0, which destroys this property and lets the order of clauses matter. For this reason, a local if-then-else ((->)/2 and (;)/2) seems to be a better fit in this case. Instead of trace/0, use SWI-Prolog's graphical tracer with ?- gtrace, your_goal., it also shows you at which points alternatives remain to be tried. In general, think in terms of relations and ask: When does this clause hold? It holds if ... etc. This makes it possible to reason about much larger programs, where the exact flow of execution may be harder to understand.

---

See if you can get hold of "Prolog Programming for Artificial Intelligence" by Ivan Bratko.

He explains the process Prolog follows to satisfy goals very well.

I'll try to answer your questions individually:

clause 1: evenN(X):- (X mod 2) =:= 0.
clause 2: sumEven([], 0).
clause 3: sumEven([H|T], X):- evenN(H), sumEven(T,Y), X is Y+H.
clause 4: sumEven([H|T], X):- \+evenN(H), sumEven(T,X).

QUESTIONS:

1) When i comment out the second rule(last line), it gives me fail as an answer because 1 is not an even number and the whole sumEven() fail because evenN() fails which i understand. My question is: what happens afterwards? Does it go back to the top and try the sumEven([], 0) fact or ? I just want to know what happens.

A: You comment-out clause 4. Prolog tries to satisfy the goal, first trying clause 2, which fails because the list is not empty, it then tries clause 3, which fails on rule 1 when H is odd. It will now try to find another clause following on from clause 3 (it will not backtrack previous to clause 3) which will fail since you commented it out, and therefor the goal fails.

2) When the last line(second rule) is included, and the first rule fails, when it backtracks, does it look for another sumEven() that follows it(like the way the second rule follows the first rule which fails) or it goes back to the top and test sumEven([], 0) fact and start it from there?

A: No it does not backtrack when clause 3 fails but continues on to the next clause (4).

I need to understand how it backtracks when rules are being used in prolog specifically in recursive situations like this one.

A: If the rule evenN(H) succeeds, the sumEven(T, Y) starts the whole process again from clause 2 using T and Y. If sumEven(T,Y) fails for some reason, clause three will fail and Prolog backtrack and try clause 4. If the current call is sumEven([2,3,...],X) and sumEven([3,...],Y) fails for some reason, Prolog will backtrack and try to find another clause sumEven([2,3,...],X) following on from clause 3.

3) I found the following code(recursive) on the net. It divides a list into positive and negative lists.

clause 1:    split([],[],[]).
clause 2:    split([X|L],[X|L1],L2):- X>= 0, !, split(L,L1,L2).
clause 3:    split([X|L],L1,[X|L2]):- split(L,L1,L2).

Can someone help me to understand the way it works to find the solution? I mean i want to understand step by step how it executes to come up with the solution.

A: I'll use a shorter goal split(numlist, PosList, NegList) with numlist = [1,-1,2,-2]. Very roughly it works as follows (It actually uses a stack to place the matched values on and only instantiates the variables when it's goal finally succeeds when it unrolls this stack - see the Bratko book for the finer details):

Clause 1 fails since numlist is not empty.

Clause 2 is applied with: split([1|-1,2,-2],[1|L1],[Y|L2]) - since 1 >=0 PosList will now be [1], and split will be applied to the tail of numlist=[-1,2,-2].

Clause 1 again fails. Clause 2 is applied with split([-1|2,-2],[-1| L1],[Y|L2]) - it fails since -1 < 0, and Prolog will apply clause 3 with split([-1|2,-2], [1], [-1|L2] - NegList will now be [-1], and again split will be aplied to the tail of numlist=[2,-2].

Clause 1 fails; clause 2 succeeds and PosList becomes [1,2], and split is applied to numlist=[-2].

Clause 1 & 2 fails; clause 3 succeeds and NegList becomes [-1,-2]. the tail of numlist is empty and clause 1 succeeds and PosList=[1,2] and NegList[-1,-2] is returned.