SWI Prolog does not terminate

Question

:- use_module(library(clpfd)).

fact(treated=A) :- A in 0..1.
fact(numYears=B) :- B in 0..sup.
fact(numDrugs=C) :- C in 0..sup.
fact(treated2=D) :- D in 0..1.
fact(cParam=E) :- E in 0..4.

is_differentfact(X,X) :- false.
is_differentfact(Element=_,OtherElement=_) :-
    dif(Element,OtherElement).

is_fakt([]).
is_fakt([X|Xs]) :-
    fact(X),
    maplist(is_differentfact(X),Xs),
    is_fakt(Xs).

Why does ?- is_fakt(X) return a list of results answers but after a number of results answers it hangs. I don't know why Prolog cannot return all possible values of X.

Answer 1

You ask:

Why does ?- is_fakt(L) ... but after a number of results answers it hangs.

You say a number. That number is 62 times pressing SPACE to get to that moment of looping. Pretty long isn't it? And your program is tiny. How will you ever get the chance to do the same with a bigger program? Don't worry, there is help. But you need to look at the program from a different angle.

In Prolog understanding the very precise execution of a concrete query is next to impossible. You have two different kinds of control flows interleaved plus strange data structures that do not need to be present, but "come in" later ; sometimes. All that opens up a veritable panoply of possible execution traces that are so full of detail, that your mind will overflow — worse: your mind will still pretend you understand everything but effectively you don't. And the bugs have big party time in your program. Those bugs will bite at some point in time in the future, but only on a bug-to-bite basis. That can be very demoralizing. After all, the program is so small, that should be easy to understand (by the standards of imperative languages). But then, Prolog programs tend to be very compact for problems that are very complex in other languages.

Try to step through with a tracer to see what I mean. You will see all kinds of things happening. And most of them are irrelevant.

Fortunately, there are ways to understand Prolog, but here you have to rely on nice properties of the language itself. For localizing reasons for non-termination, the best is to start to consider a failure-slice. You obtain a failure slice from your program by adding goals false into your program. If the resulting program then still does not terminate, we have a reason why also our original program does not terminate.

Think of it: instead of trying to understand your program we do something humans are much better at: Making an educated guess. That guess can go wrong but we can check that easily. In the beginning you will be pretty awful at guessing. Soon you will see that you can do a lot of things systematically. All code that now becomes irrelevant is stike through.

:- use_module(library(clpfd)).

fact(treated=A) :- A in 0..1.     
fact(numYears=B) :- B in 0..sup, false.
fact(numDrugs=C) :- C in 0..sup, false.
fact(treated2=D) :- D in 0..1, false.
fact(cParam=E) :- E in 0..4, false.

is_differentfact(X,X) :- false.
is_differentfact(Element=_,OtherElement=_) :-
    dif(Element,OtherElement).

is_fakt([]).
is_fakt([X|Xs]) :-
    fact(X),
    maplist(is_differentfact(X),Xs),
    is_fakt(Xs).

What did we gain? We can narrow down the problem much faster:

?- is_fakt(Xs).
   Xs = []
;  Xs = [treated=_A], _A in 0..1
;  loops.

Before continuing, I try to understand what you mean with is_fakt/1. You probably mean: All the facts by their name, and make sure none is repeated. Now we have only the fact named treated, so we can only produce a list of length 1. And then it loops.

You said:

I don't know why Prolog cannot return all possible values of X.

To be picky, that is not true. Prolog did enumerate all possible values of X. But then it did not terminate.

((Some remarks to consider: Do you really want to get that list in that manner? You will get all permutations! With a list of length n you will get n! different answers. For n = 10 that is 3628800. Is this, what you want? Probably not.))

But let us first stick to identify the precise reason for non-termination.

To better identify the reason, lets "turn off" all answers. So we query is_fakt(L), false instead with:

:- use_module(library(clpfd)).

fact(treated=A) :- A in 0..1.     
fact(numYears=B) :- B in 0..sup, false.
fact(numDrugs=C) :- C in 0..sup, false.
fact(treated2=D) :- D in 0..1, false.
fact(cParam=E) :- E in 0..4, false.

is_differentfact(X,X) :- false.
is_differentfact(Element=_,OtherElement=_) :-
    dif(Element,OtherElement).

is_fakt([]) :- false.
is_fakt([X|Xs]) :-
    fact(X),
    maplist(is_differentfact(X),Xs), false,
    is_fakt(Xs).

That is a minimal failure-slice. So it is the maplist/2 which does not terminate in the first place. Your idea was to ensure that X has a fact-name that is different to the fact-names in Xs. But if Xs is not bound, that will never terminate. Let's try it:

?- maplist(is_differentfact(X),Xs).
   Xs = []
;  X = (_A=_B), Xs = [_C=_D], dif(_A,_C)
;  X = (_A=_B), Xs = [_C=_D,_E=_F], dif(_A,_C), dif(_A,_E)
;  X = (_A=_B), Xs = [_C=_D,_E=_F,_G=_H],
   dif(_A,_C), dif(_A,_E), dif(_A,_G)
;  X = (_A=_B), Xs = [_C=_D,_E=_F,_G=_H,_I=_J],
   dif(_A,_C), dif(_A,_E), dif(_A,_G), dif(_A,_I)
;  X = (_A=_B), Xs = [_C=_D,_E=_F,_G=_H,_I=_J,_K=_L],
   dif(_A,_C), dif(_A,_E), dif(_A,_G), dif(_A,_I), dif(_A,_K)
;  ... .

Not so nice to look at... but we can do it better:

?- maplist(is_differentfact(X),Xs), false.
   loops.

So it loops. This is the reason for non-termination. To fix the problem we have to do something in the remaining visible part of the failure slice...

For more, look up other explanations tagged failure-slice