3

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.
repeat
  • 18,496
  • 4
  • 54
  • 166
user2326995
  • 163
  • 1
  • 11
  • 1
    I would vote to close as a migration problem. Possibly should be migrated to: < http://codereview.stackexchange.com/ >, but this doesn't appear as an option for migration inside of the menu that comes up for close voting. – ely Nov 15 '13 at 15:54
  • Similar to http://stackoverflow.com/questions/19954314/divison-and-remainder-in-prolog – lurker Nov 16 '13 at 03:43

2 Answers2

3

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, N#=<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, R#=<D+ -1, N#>=D

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, _A+D#=N, R+D#=_A, R#=<D+ -1, N#>=D, _A#>=D

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, _A+D#=N, _B+D#=_A, R+D#=_B, R#=<D+ -1, N#>=D, _A#>=D, _B#>=D
;  Q = 4, _A+D#=N, _B+D#=_A, _C+D#=_B, R+D#=_C, R#=<D+ -1,
   N#>=D, _A#>=D, _B#>=D, _C#>=D
;  ... .

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.

false
  • 10,264
  • 13
  • 101
  • 209
1

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.

CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • 1
    The base case does **not** terminate recursion. It is the `X#>=D` in the recursive rule which does. – false Nov 15 '13 at 18:27