What's happening when I call `even(3)`, with `even` being a generator function?

Question

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?

Answer 1

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.

Answer 2

The X is Y + 1 goal becomes 3 is 1 + 1and it fails, resulting in backtracking of the previous call, odd(Y). This is turn uses the second clause for the odd/1 predicate to try to find an alternative solution. The second clause body calls even(Y) instantiating Y to 0and then trying X is 0+1, X>1, which fails resulting into backtracking to the previous call to the even/1 predicate. From here is like a never ending game of ping-pong between the odd/1 and even/1 predicates. You can use your Prolog compiler trace feature to follow step-by-step what's happening.

Also note that, in Prolog, variables are local to clauses. Maybe that's what's confusing you?

Answer 3

When you call even(3) (so, as a test), 3 doesn't match 0, so it falls in the compound clause.

The first thing that clause does is invoke odd on unbound variable Y, so as a generator. The only way it could end up as a success is if odd(Y) could return an odd Y such that 3 is Y+1. The generator will return 1, 3, 5, etc, so that will never happen. But Prolog has no way to know that, so all it can do is try them all. There happens to be an infinity [*] of them, hence the infinite loop.

[*] depending on your Prolog implementation's integer settings, but it'll take a long time no matter whether it actually finishes or not.

Answer 4

To make Prolog code bi-directional, you have to add clauses for different modes, and use the meta-variable tester var/1 to decided between the two variants:

The generator:

even(0).
even(X) :- odd(Y), X is Y+1, X>0.

odd(1).
odd(X) :- even(Y), X is Y+1, X>1.

The tester:

even(0).
even(X) :- X>0, Y is X-1, odd(Y).

odd(1).
odd(X) :- X>1, Y is X-1, even(Y).

The bi-directional code:

even(0).
even(X) :- var(X), !, odd(Y), X is Y+1, X>0.
even(X) :- X>0, Y is X-1, odd(Y).

odd(1).
odd(X) :- var(X), !, even(Y), X is Y+1, X>1.
odd(X) :- X>1, Y is X-1, even(Y).

Prolog systems, libraries and user code implement many predicates via this technique. One reason could be that using such bi-directional predicates, could simplify defining other bi-directional predicates.

But matters are not that simple, since when predicates are combined goals might still need some reordering. So maybe we only doit to save namespace. BTW here is a bi-directional between/3 implementation.