CODEWITHSUNDEEP
prolog
gsamerica
gsamerica

Reputation: 153

Prolog methods not calling base case

I am trying to build a program that takes two integers (for example, 4 and 15) and returns the multiples of the first integer that divide into the second integer.

My program is as follows:

divisible(D,U,X):-
   divisible_ext(D,U,D,X).

divisible_ext(D,U,D,X):-
   U < D,
   !.
divisible_ext(D,U,S,X):-
   U > D,
   D1 is D + S,
   divisible_ext(D1,U,S,X1),
   X is D.

As far as I am aware, my program should fail the base case with each call until the D value is greater than U (so with 4 and 15, 16 > 15). However in the trace, I can see that the base case is only called the first time, and then never again. Thus when D = 16, the U > D call fails and the entire program fails.

Why is the base case only being called once? Is there something I am not understanding about Prolog that I need to know, or is there a change to my code that I should make?

Edit: Here is my trace:

[trace] 20 ?- divisible(4,15,X).
   Call: (7) divisible(4, 15, _G9543) ? creep
   Call: (8) divisible_ext(4, 15, 4, _G9543) ? creep
   Call: (9) 15<4 ? creep
   Fail: (9) 15<4 ? creep
   Redo: (8) divisible_ext(4, 15, 4, _G9543) ? creep
   Call: (9) 15>4 ? creep
   Exit: (9) 15>4 ? creep
   Call: (9) _G9622 is 4+4 ? creep
   Exit: (9) 8 is 4+4 ? creep
   Call: (9) divisible_ext(8, 15, 4, _G9625) ? creep
   Call: (10) 15>8 ? creep
   Exit: (10) 15>8 ? creep
   Call: (10) _G9625 is 8+4 ? creep
   Exit: (10) 12 is 8+4 ? creep
   Call: (10) divisible_ext(12, 15, 4, _G9628) ? creep
   Call: (11) 15>12 ? creep
   Exit: (11) 15>12 ? creep
   Call: (11) _G9628 is 12+4 ? creep
   Exit: (11) 16 is 12+4 ? creep
   Call: (11) divisible_ext(16, 15, 4, _G9631) ? creep
   Call: (12) 15>16 ? creep
   Fail: (12) 15>16 ? creep
   Fail: (11) divisible_ext(16, 15, 4, _G9631) ? creep
   Fail: (10) divisible_ext(12, 15, 4, _G9628) ? creep
   Fail: (9) divisible_ext(8, 15, 4, _G9625) ? creep
   Fail: (8) divisible_ext(4, 15, 4, _G9543) ? creep
   Fail: (7) divisible(4, 15, _G9543) ? creep
false.

Upvotes: 0

Views: 285

Answers (1)

Guy Coder
Guy Coder

Reputation: 24976

Why is the base case only being called once?

The base case is

divisible_ext(D,U,D,X) :-

and the other case is

 divisible_ext(D,U,S,X) :-

Notice that on the first call 

Call: (8) divisible_ext(4, 15, 4, _G9543) ? creep
          divisible_ext(D,  U, D,     X) :-                 <-- Base case
          divisible_ext(D,  U, S,     X) :-                 <-- Other case

For the base case D = 4 for both D and
for the other case D = 4 and S = 4
so both predicates can be called.

Notice on the second call

Call: (9) divisible_ext(8, 15, 4, _G9625) ? creep
          divisible_ext(D,  U, D,      X) :-                 <-- Base case
          divisible_ext(D,  U, S,      X) :-                 <-- Other case

For the base case D = 8 and D = 4 and
for the other case D = 4 and S = 4
so the base can not be called because the first D is now 8 and second D is 4 which means the unification will not work and thus the predicate can not be called.

Upvotes: 0

Related Questions