Can someone describe this Prolog code step by step?

Question

Prolog is new to me. I'm trying to understand this code. If anyone could explain it step by step in child language that would be a great help ;) thankyou!

divide_by(X,D,I,R) :- 
   X < D,
   I is 0,
   R is X.
divide_by(X,D,I,R) :- 
   X >= D,
   Q is X - D, 
   divide_by(Q, D, S, R),
   I is S +1.

Answer 1

Well, I can't. You are asking the wrong question. The right question would be:

What relation does the predicate describe?

Actually, that is quite difficult to answer, as we would have go through it step-by-step. But there is a better and much cleaner way! As your program uses integers only, we can map the moded relations (<)/2, (is)/2 and the like to their declarative counterparts in CLP(FD). So I change < to #<, is to #=, >= to #>=.

:- use_module(library(clpfd)).

divide_by(X,D,I,R):-
    X #< D, I #= 0, R #= X.
 divide_by(X,D,I,R):-
    X #>= D, Q #= X - D,
    I #= S +1,
    divide_by(Q, D, S, R).

The big advantage now is that I can ask Prolog what it thinks the relation is describing. Simply ask: _{(Don't worry about the Q=Q, it's just to reorder variables)}

• N ... dividend
• D ... divisor
• Q ... quotient
• R ... remainder

---

?- Q=Q, divide_by(N,D,Q,R).
 Q = 0,
 N = R,
 R#=<D+ -1

This answer reads as follows: The quotient is zero, the dividend and remainder is the same and the remainder is less than the divisor. So this describes all situations where 0 is the "result" or quotient.

Next answer:

;
 Q = 1,
 R+D#=N,
 N#>=D,
 R#=<D+ -1

The quotient is 1 and the dividend is the divisor plus remainder, and — as in all answers — the remainder is less than the divisor

;
 Q = 2,
 _G1665+D#=N,
 N#>=D,
 R+D#=_G1665,
 _G1665#>=D,
 R#=<D+ -1

This answer is the same as R+D+D#= N. The system has introduced some extra variables. Not wrong, but a bit clumsy to read.

;
 Q = 3,
 _G1930+D#=N,
 N#>=D,
 _G1951+D#=_G1930,
 _G1930#>=D,
 R+D#=_G1951,
 _G1951#>=D,
 R#=<D+ -1
;
 Q = 4,
 _G2195+D#=N,
 N#>=D,
 _G2216+D#=_G2195,
 _G2195#>=D,
 _G2237+D#=_G2216,
 _G2216#>=D,
 R+D#=_G2237,
 _G2237#>=D,
 R#=<D+ -1 ...

And so on. Let me summarize. All answers look like that:

N#>=D, R#< D,  R+D+...+D#= N
                 ^^^^^^^ Q times

or even better:

N#>=D, R #< D, R+Q*D #= N, Q #>= 0.

So what we have answered is what this relation is describing.

When you start Prolog, focus on the declarative side. As what (set/relation) a predicate describes. The procedural side will join without any effort later on.

Answer 2

The first rule is called the base case. It will terminate the recursion.

divide_by(X,D,I,R):- 
    X < D,   % this rule apply only if numerically X is < D
    I is 0,  % will fail if I \= 0
    R is X.  % if I = 0 assign expression X to R

This other it's the recursive step.

divide_by(X,D, I, R):- 
    X >= D,      % this rule apply only if X is >= D
    Q is X - D,  % evaluate Q
    divide_by(Q, D, S, R),  % recursive call. Q & D are surely instantiated
    I is S + 1.  % evaluate I as S + 1

So, I would say: it will compute the integer division of X by D, with remainder R, when called in mode divide_by(+,+,-,-), that is with first two arguments bound to integers and the last two free.

Anyway, false' answer is very good, as show a possible way to reason about arithmetic that is not available in 'common' programming languages.