CODEWITHSUNDEEP
listrecursionprologlogicconstraints
schuelermine
schuelermine

Reputation: 2290

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

Upvotes: 0

Views: 114

Answers (1)

TessellatingHeckler
TessellatingHeckler

Reputation: 28963

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 abort 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.

Upvotes: 2

Related Questions