Prolog - confused about return results of recursive rule

Question

I'm playing around with recursion in Prolog, and I'm confused. I am trying to write rules that can determine if a number is even or odd. I know that there are other stackoverflow questions about this, but I don't care about having a working solution, I am more interested in knowing why mine doesn't work.

Here are my rules:

even(0).
even(N) :- N>0, N1 is N-1, odd(N1).
odd(N) :- N>0, N1 is N-1, even(N1).

When I query even(0), I get returned 2 results. The first result is true, the 2nd is false. This also happens with odd(1), even(2), odd(3), etc. Why am I getting 2 return results? Shouldn't I just get 1?

Answer 1

When you query even(0), it succeeds as you have seen. But you've also seen it prompts you for more results because it left a choicepoint, which is a place in the logic where Prolog decides it can come back and explore other alternatives for a potentially successful query. Upon going back to the choicepoint and attempting to find more solutions, it does not find more, so it comes back "false" since it found no more solutions. So it did just find one solution, but the choice point caused backtracking after which it found no additional solutions. This is the case with your other successful queries as well.

You'll note that if you make a more general query, it gives an error (example taken from GNU Prolog):

| ?- even(N).

N = 0 ? ;
uncaught exception: error(instantiation_error,(>)/2)
| ?-

This is because you are using specific arithmetic expression operators that require that the variables be instantiated. These are relational operators like (>)/2 and the is/2 operator. You can make the solution more relational by using the CLP(FD) operators which are designed for reasoning with integers:

even(0).
even(N) :-
    N #> 0,
    N1 #= N-1,
    odd(N1).
odd(N) :-
    N #> 0,
    N1 #= N-1,
    even(N1).

Then you get a more general solution, which is more complete and more useful:

| ?- even(N).

N = 0 ? ;

N = 2 ? ;

N = 4 ? ;

N = 6 ? ;
...

| ?- odd(N).

N = 1 ? ;

N = 3 ? ;

N = 5 ? ;

N = 7 ?
...

---

If you know there is at most one answer, or if you only care about the first possible answer, you can use once/1 (examples taken from SWI Prolog here):

2 ?- even(2).
true ;
false.

3 ?- once(even(2)).
true.

4 ?- even(N).
N = 0 ;
N = 2 ;
N = 4 ;
...

5 ?- once(even(N)).
N = 0.

6 ?-

As expected, once(even(N)) terminates after finding the first solution.

Answer 2

The return values you have are correct. The point is how Prolog is evaluating predicates. When you query i.e.

even(2)

Prolog firstly evaluate that this predicate is Yes / true. When going through next possibility it return No / false, because it cannot find any more.

To check what exactly is performed under the hood go to: https://swish.swi-prolog.org

on the left side type rules (i.e. odd/even) and on the query window type like 'odd(2)', but just before running click 'solutions'->'debug(trace)'. It will let you go step by step of what Prolog is doing.

Also please take a look at the successor example in tutorial below. http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse9

from a link above, try such code for a reversed example:

numeral(0). 
numeral(succ(X))  :-  numeral(X).

Now evaluating numeral(0) for the first time return succ(0), another time succ(succ(0)) etc.

Each time next evaluation brings another possible solution for a query.

Answer 3

What Prolog does is a "depth-first search", which means Prolog walks through a decision tree until it either finds a solution and succeeds OR it fails. In either case a process called "backtracking" kicks in. Along the way, going through the tree of choices, Prolog keeps track of where it has MULTIPLE possible routes that could potentially satisfy the goal. Such a point in the decision tree is called a "choice point".

This means Prolog will

1. search ->
2. succeed or fail ->
3. go back to the last choice point ->
4. repeat until all possible paths have been tried

Given your program:

even(0).
even(N) :- N>0, N1 is N-1, odd(N1).
odd(N) :- N>0, N1 is N-1, even(N1).

We can clearly see TWO ways to satisfy even(0).. The first is the fact even(0) and the second is the recursive rule even(N). Prolog reads top to bottom, left to right so the first encounter is even(0). which is true, and the second is even(N). which goes through N-1 making the result N1 = -1, then goes through odd(N) making the result N1 = -2, which in unequal to even(0). so it fails and then calls even(N) again. Your specific version of Prolog likely sees that it is an infinitely recursive predicate and doesn't even try to satisfy it even though it's a valid declarative path , but not a valid procedural path.

Answer 4

If you know that the mode is (+), you can place a cut, to suppress the unnecessary choice point:

even(0) :- !.
even(N) :- N > 0, N1 is N-1, odd(N1).
odd(N) :- N > 0, N1 is N-1, even(N1).

The above is better than wrapping a query with once/1 since it allows the Prolog interpreter to use last call optimization. There is now no more problem with an extra choice point:

?- even(3).
false.

?- even(4).
true.

But if the mode is not fixed, you have to be more careful with cuts. Probably write a separate carefully crafted predicate for each mode.

CLP(FD) itself seems not to help, it cannot avoid the need to place cuts, but can sometimes avoid the need to code different variants for different modes.