listrecursionprologlogicconstraints

# Why does this Prolog program not terminate?

I’m new to Prolog and I wanted to write a simple predicate that checks if a given value is in a list.

I do not know exactly if the way I was taught lists is correct. I was taught that it is a car/cdr or head/tail relation (familiar from LISP/Haskell) that is “matched on” with `[X|Xs]`.

I first tried with this program:

``````in([ ], _) :- false.
in([X|_], X).
in([_|Xs], X) :- in(Xs, X).
``````

Now this program doesn’t terminate if fed with any query that should return `true.` (e.g. `?- in([1, 2], 2).`). Instead, it does print out `true` (without a period) and then hangs.

I considered that perhaps, after encountering a unifying rule at `in([X|_], X).` Prolog continues to search for other values that unify with `in([_|Xs], X)`. It is unclear to me why this would not terminate since the recursive descent always reduces the argument. Nonetheless, I then attempted this program:

``````in([ ], _) :- false.
in([X|_], X).
in([X|Xs], Y) :- in(Xs, Y), X \= Y.
``````

I hoped this would prevent Prolog from descending on the other rule but this preserved the previous behaviour. I then remembered that the order of predicates in a rule matters, so I attempted this:

``````in([ ], _) :- false.
in([X|_], X).
in([X|Xs], Y) :- X \= Y, in(Xs, Y).
``````

The behaviour prevailed. In frustration and suspecting I had completely misunderstood Prolog evaluation I tried reversing all clauses, to the most curious effect:

``````in([X|Xs], Y) :- X \= Y, in(Xs, Y).
in([X|_], X).
in([ ], _) :- false.
``````

This now causes Prolog to terminate if the list is empty or the element is found at the head, so:

``````?- in([ ], 10).
false.

?- in([1, 2], 1).
true.

?- in([1, 2], 2).
true
``````

and then it hangs.

I don’t understand how such behaviour comes about. What is Prolog doing?

I am using SWI-Prolog 9.1.10

Solution

• This is expected behaviour, it pauses when it has found a solution. It keeps track of the paths through the code as it searches, and when there are still unexplored paths it prompts you for what to do next ("hangs"). Press `?` (question mark) at that point, and SWI Prolog will show you the options:

``````  Possible actions:
; (n,r,space,TAB): redo              | t:         trace&redo
*:                 show choicepoint  | c (a,RET): stop
w:                 write             | p:         print
b:
``````

Semi-colon, space are the ones which continue searching ("redo"). `c` and `a`bort and RETurn will stop there.

If it has found true, what other solutions can there be?

You know there are no more, it doesn't - it's not intelligent. It can only report finding no more solutions if it can finish searching the entire code. Try `?- member(2, [1,2,3,2,1]).` and then try `?- member(X, [1,2,3]).` and see how they find more than one solution.