I have the following generators of odd and even numbers in prolog
even(0).
even(X) :- odd(Y), X is Y+1, X>0.
odd(1).
odd(X) :- even(Y), X is Y+1, X>1.
I'd like to understand why I can't use these functions as testers, i.e. ?even(3). This results in an infinite loop.
Isn't this what's happening when I call ?even(3).?
X gets instantiated to 3.
Try to find any Y (starting at 0) that is odd. Finds Y=1.
Now comes the part I don't understand. I don't know what happens when it has to process the clause X is Y+1. Considering X was already given, what's hapenning here?
You are trying here to understand the precise termination property of your program which is a bit surprising when you come from procedural languages. In Prolog, there are several control flows interlaced which makes actual execution often hard-to-follow.
To understand it, you could trace the program step-by-step to get an idea of what is actually happening, but that method gets complex pretty soon. And your program is as simple as it can get. Instead, I will show you another method, using failure-slices.
You were quite lucky to use the query even(3) which shows you immediately that there is a problem. You could have used another query, like even(2). which does not show you the problem immediately. In fact, Prolog nicely succeeds for this query. Everything seems fine, unless you ask to see further answers.
So how can we make sure that we face the problem as soon as possible? A way to do this is to pose the query even(2), false instead. In this case, we expect that the query fails, since false never succeeds. However, instead of failing, the query might produce an infinite loop (or an error). By adding false at the end we say: Skip all the answers, and simply show whether or not the query terminates.
What is now nice in (pure, monotonic) Prolog is that we can do the same with your program. So we may add goals false into your program. If the resulting program, called a failure-slice, now loops, then also the original program will actually loop.
Here is the minimal failure-slice that still loops:
even(0) :- false. even(X) :- odd(Y), false,X is Y+1, X>0.odd(1) :- false. odd(X) :- even(Y), false,X is Y+1, X>1.
It is this tiny remaining part which is responsible for all the looping. Now, you can not only justify, why even(2) loops, but you can see something even more general: This failure slice will loop independently of the argument for even/1. So it will loop for any query!
For more see failure-slice.