Order of instructions and recursion in Prolog-CodePudding

I just started in prolog and I have a question regarding recursion.

I basically want to count the number of time a certain value is in a list, so I have for example:

count( a, [ a, s, d, f, g, a, s, d, a, s ], W ).  W = 3.

Where I want to count the number of time "a" is in the list and store the number in "W".

The correct answer is

count( _, [], 0 ). 
count( A, [B|S], X ) :- A==B, count( A, S, Y ), X is Y   1. 
count( A, [B|S], X ) :- \  A == B, count( A, S, X ).

Howhever, I do not understand why in line 2, the is a "X is Y 1" at the end. Shouldn't the line rather be

count( A, [A|S], X ) :- Y is X   1, count( A, S, Y ).

In that case, we first set Y to 1, then we send it to "count" again with the recursion.

If anyone can help me I'd appreciate it very much!

CodePudding user response：

Consider that when you call:

?- count(a,[a,s,d,f,g,a,s,d,a,s],W).

...then first predicate that matches is count(A,[B|S],X). So that means that it sees it like count(a,[a|S],X) where S & X are variables. X is just W from the original call so it is still a variable.

Suggesting that Y is X 1 is then evaluated doesn't make sense as X is a variable.

The original predicate, however, does make sense.

count(A,[B|S],X) :- A==B, count(A,S,Y), X is Y   1.

When it recurses it sends in a new variable Y into the 2nd count/3 predicate (or just passes the same variable in the 3nd predicate). And it keeps doing that until it hits the base case when it finally unifies the variable to 0. At that point it unwinds the recursion and now it can finally do X is Y 1 (because Y is a value) and hence X is now a value.

Prolog is a fun language because it almost has a sense of time travel in the way you have to think forwards and backwards to understand how a program works.

CodePudding user response：

count( A, [B|S], X ) :- A==B, count( A, S, Y ), X is Y   1.

This means: If S contains Y occurrences of A, and A == B, then [B | S] contains one more occurrence of A.

For example, imagine we're getting here while counting the occurrences of prolog in [prolog, prolog, prolog]. [B | S] = [prolog, prolog, prolog], so S = [prolog, prolog]. The number of occurrences of prolog in S is 2, so we should have Y = 2. The number of occurrences of prolog in [B | S] is 3, so we should have X = 3. Once we know Y = 2, then X is Y 1 computes this correct value of X.

count( A, [A|S], X ) :- Y is X   1, count( A, S, Y ).

This would mean: If [A | S] contains X occurrences of A, then S contains one more occurrence of A. This cannot be.

Using the above example again: Clearly [A | S] = [prolog, prolog, prolog] contains 3 occurrences of prolog, so X = 3 should hold. But then Y would have to be 4, and the goal in the body would try to prove that S = [prolog, prolog] contains 4 occurrences of prolog. This can clearly not be the case.

Note that this explanation is simply about the meaning of the predicate. It does not require us to think about recursion, or the order of goals, or the exact way that the program is actually executed. When doing Prolog programming, try to be clear about the logical meaning of your programs first.