CODEWITHSUNDEEP
prolog
Lukas Schüler
Lukas Schüler

Reputation: 47

How to stop backtracking and end the recursion in Prolog

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.

Upvotes: 2

Views: 5130

Answers (2)

lambda.xy.x
lambda.xy.x

Reputation: 4998

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

Upvotes: 1

Ali
Ali

Reputation: 666

If you put cut before the fail, it will be freeze the backtracking.
The cut operation freeze the backtracking , if prolog cross it.
Actually when prolog have failed, it backtracks to last cut.
for example : 

a:- b,
    c,!,
    d,
    e,!,
    f.

Here, if b or c have failed, backtrack do not freeze.
if d or f have failed, backtrack Immediately freeze, because before it is a cut
if e have failed , it can backtrack just on d

I hope it be useful

Upvotes: 0

Related Questions