How to stop backtracking and end the recursion in Prolog

Question

I'm currently learning SWI-Prolog. I want to implement a function factorable(X) which is true if X can be written as X = n*b.
This is what I've gotten so far:

isTeiler(X,Y) :- Y mod X =:= 0.

hatTeiler(X,X) :- fail,!.  
hatTeiler(X,Y) :- isTeiler(Y,X), !; Z is Y+1, hatTeiler(X,Z),!.

factorable(X) :- hatTeiler(X,2).

My problem is now that I don't understand how to end the recursion with a fail without backtracking. I thought the cut would do the job but after hatTeilerfails when both arguments are equal it jumps right to isTeiler which is of course true if both arguments are equal. I also tried using \+ but without success.

if you put cut before the fail, it will be freeze the backtracking. — Ali
Ohh wow, I really did not see that. But it works. Thank you. Can you briefly explain to me why I have to put it there? — Lukas Schüler
Use of cuts this way, though, is usually a sign that your predicate design isn't as good as it should be. What you want to do is be precise in your conditions. For example, if you really intend hatTeiler(X,Y) to apply when X is greater than Y then you should include that condition in the body of the predicate: ... :- X > Y, isTeiler(Y, X), .... Without the condition, this could run away if X < Y since you keep increasing the second argument. You shouldn't need any cuts for this problem. Anyway, your code, when working, always succeeds since every number is its own factor. — lurker

lambda.xy.x lambda.xy.x · Accepted Answer · 2018-08-21T20:54:58

It looks like you add cuts to end a recursion but this is usually done by making rule heads more specific or adding guards to a clause.

E.g. a rule:

x_y_sum(X,succ(Y,1),succ(Z,1)) :-
  x_y_sum(X,Y,Z).

will never be matched by x_y_sum(X,0,Y). A recursion just ends in this case.

Alternatively, a guard will prevent the application of a rule for invalid cases.

hatTeiler(X,X) :- fail,!.

I assume this rule should prevent matching of the rule below with equal arguments. It is much easier just to add the inequality of X and Y as a conditon:

hatTeiler(X,Y) :-
  Y>X,
  isTeiler(Y,X),
  !;
  Z is Y+1,
  hatTeiler(X,Z),
  !.

Then hatTeiler(5,5) fails automatically. (*)

You also have a disjunction operator ; that is much better written as two clauses (i drop the cuts or not all possibilities will be explored):

hatTeiler(X,Y) :- % (1)
  Y > X,
  isTeiler(Y,X).
hatTeiler(X,Y) :- % (2)
  Y > X,
  Z is Y+1,
  hatTeiler(X,Z).

Now we can read the rules declaratively:

(1) if Y is larger than X and X divides Y without remainder, hatTeiler(X,Y) is true. (2) if Y is larger than X and (roughly speaking) hatTeiler(X,Y+1) is true, then hatTeiler(X, Y) is also true.

Rule (1) sounds good, but (2) sounds fishy: for specific X and Y we get e.g.: hatTeiler(4,15) is true when hatTeiler(4,16) is true. If I understand correctly, this problem is about divisors so I would not expect this property to hold. Moreover, the backwards reasoning of prolog will then try to deduce hatTeiler(4,17), hatTeiler(4,18), etc. which leads to non-termination. I guess you want the cut to stop the recursion but it looks like you need a different property.

Coming from the original property, you want to check if X = N * B for some N and B. We know that 2 <= N <= X and X mod N = 0. For the first one there is even a built-in called between/2 that makes the whole thing a two-liner:

hT(X,B) :-
   between(2, X, B),
   0 is (X mod B).


?- hT(12,X).
X = 2 ;
X = 3 ;
X = 4 ;
X = 6 ;
X = 12.

Now you only need to write your own between and you're done - all without cuts.

(*) The more general hasTeiler(X,X) fails because is (and <) only works when the right hand side (both sides) is variable-free and contains only arithmetic terms (i.e. numbers, +, -, etc).

How to stop backtracking and end the recursion in Prolog

2 Answers