Prolog does not terminate on query with 2 arguments

Question

I'm new to Prolog and have a question to a programming exercise:

I have a program, that is for my opinion working most of the time, but with a specific query, I do not get an answer

is_number(0).
is_number(s(N)) :-
  is_number(N).

numberpair(pair(X,Y)) :-
  is_number(X),
  is_number(Y).

?- numberpair(pair(A,B)), A=s(s(0)), B=s(s(s(0))).

So I understand, that Prolog now tries every possible number for A and B -> [0,s(0),s(s(0)),s(s(s(0))), ...] but if it founds an answer for A (namely s(s(0))) it fails at B and in the next call, it tries the next answer for A (namely s(s(s(0)))) and so on. Now the thing is, that I want Prolog to stop, if it founds an answer for A, and only searches now for an answer for B.

Can anybody give me a hint, how to solve this?

This doesn't have an answer because your query doesn't make sense. You're asking Prolog to somehow magically see the future of the query. It can only succeed for one goal at a time. You can't make it fail on the third goal (B=s(s(s(0)))) and have it backtrack to the first goal (numberpair(pair(A,B))) but to skip over the second goal (A=s(s(0))) while backtracking. You need to redefine your query so that it makes sense. — Enigmativity
@lurker: Not. The D was a very broad hint how to solve this. — false
@Enigmativity: The query does make sense. It reads: When being asked for all solutions, will this particular solution be found as well. In other words, is the enumeration fair or unfair. — false

Ben373 Ben373 · Accepted Answer · 2017-11-12T13:35:55

Edit: As false pointed out: ~~The reason you won't find an answer is that your rule numberpair/1 won't terminate.~~ The reason you won't find an answer is that Prolog enumerates your answer in a way that it first lists all possibilities for A and then the possibilities for B (note that both have infinite possibilities). What Prolog tries is to find an answer first for the clause numberpair(pair(A,B)) but and then for the following clauses A=s(s(0)) and B=s(s(s(0))). But since numberpair already won't terminate, it won't "come" so far.

If you change the order of your ~~clauses~~ goals and simply call A=s(s(0)) before numberpair(pair(A,B)), it will give list you all answers for the possibilities of B (note that this still won't terminate!).

?- A=s(s(0)), numberpair(pair(A,B)).

A = s(s(0)),
B = 0 ;
A = s(s(0)),
B = s(0) ;
A = B, B = s(s(0)) ;
A = s(s(0)),
B = s(s(s(0))) .

Edit 2, to provide also a version, which will enumerates in a "fair" way!

is_number(0).
is_number(s(N)) :-
  is_number(N).

number_number_sum(0,A,A).
number_number_sum(s(A),B,s(C)) :-
    number_number_sum(A,B,C).

numberpair(pair(X,Y)) :-
    is_number(Z),
    number_number_sum(X,Y,Z).

Which will provide us with

?- numberpair(pair(A,B)).
A = B, B = 0 ;
A = 0,
B = s(0) ;
A = s(0),
B = 0 ;
A = 0,
B = s(s(0)) ;
A = B, B = s(0) ;
A = s(s(0)),
B = 0 ;
A = 0,
B = s(s(s(0))) ;
A = s(0),
B = s(s(0)) ;
A = s(s(0)),
B = s(0) ;
A = s(s(s(0))),
B = 0 .

Prolog does not terminate on query with 2 arguments

1 Answers