prolog - recursive predicate sum(J,K,N)

Question

I'm trying to solve the exercise from book "Prolog Programming In Depth".

Define a recursive predicate sum(J,K,N) that instantiates N to the sum of the integers from J to K inclusive:

?- sum(-1,1,What).
What = 0
?- sum(1,3,What).
What = 6
?- sum(6,7,What).
What = 13

My predicate is below.

sum(J, K, N) :- sum_iter(J, K, N, J, 0).   % clause_1

sum_iter(J, K, N, I, S) :-                 % clause_2
  Kn is K+1,                               % clause_X
  I = Kn,
  N = S,!.

sum_iter(J, K, N, I, S) :-     % clause_2, I - index, S - SumTmp
  I =< K,
  NewI is I+1,
  NewS is S+I,
  sum_iter(J, K, N, NewI, NewS).

It works correctly but I don't understand:

why I should use clause_X (why +1)
and why I can't replace clause_2 by

sum_iter(J, K, N, K, N) :- !.

In this case predicate stops work on previous step. For example, expect:

?- sum(1,3,What).
What = 6

BUT Prolog output:

?- sum(1,3,What).
What = 3

Actually clause_2 is not the second clause of this predicate. Note that you made two predicates sum and sum_iter. — Willem Van Onsem

David Tonhofer David Tonhofer · Accepted Answer · 2020-03-07T16:01:47

Printing out some of the state:

sum(J, K, N) :- sum_iter(J, K, N, J, 0).

% the rule at the end of the recursion

sum_iter(J, K, N, I, S) :-
  format("rule 1: J=~w K=~w N=~w I=~w S=~w\n", [J, K, N, I, S]),
  Kn is K+1,
  I = Kn,
  format("...pos 1 passed\n"),
  N = S,
  format("...pos 2 passed\n"),
  !.

% the rule perfoming the recursion

sum_iter(J, K, N, I, S) :-
  format("rule 2: J=~w K=~w N=~w I=~w S=~w\n", [J, K, N, I, S]),
  I =< K,
  format("...pos 3 passed\n"),
  NewI is I+1,
  NewS is S+I,
  sum_iter(J, K, N, NewI, NewS).

?- sum(1,3,What).
rule 1: J=1 K=3 N=_11338 I=1 S=0
rule 2: J=1 K=3 N=_11338 I=1 S=0
...pos 3 passed
rule 1: J=1 K=3 N=_11338 I=2 S=1
rule 2: J=1 K=3 N=_11338 I=2 S=1
...pos 3 passed
rule 1: J=1 K=3 N=_11338 I=3 S=3
rule 2: J=1 K=3 N=_11338 I=3 S=3
...pos 3 passed
rule 1: J=1 K=3 N=_11338 I=4 S=6
...pos 1 passed
...pos 2 passed
What = 6.

At the end, the I = Kn becomes a test: both I and Kn are set to actual values, with I one "past the end".

You could do this, using an I > K "guard":

sum_iter(_, K, Res, I, Res) :- I > K,!.

But what you also want to do this:

Call the recursive rule by default, if it is applicable.
If it is not, call the "end of recursion rule".

So a rearrangement is best:

sum(J, K, N) :- sum_iter(J, K, N, J, 0).


% the rule perfoming the recursion, with a guard "I =< K", which, once
% successful, commits the computation to this one rule, so we add "!"

sum_iter(J, K, N, I, S) :-
  format("rule 2: J=~w K=~w N=~w I=~w S=~w\n", [J, K, N, I, S]),
  I =< K,!, 
  format("...pos 3 passed\n"),
  NewI is I+1,
  NewS is S+I,
  sum_iter(J, K, N, NewI, NewS).

% the rule at the end of the recursion, also with guard:

sum_iter(J, K, Res, I, Res) :-
  format("end: J=~w K=~w I=~w Res=~w\n", [J, K, I, Res]),
  I > K,!.

Actually, there is no need for the "cut" in the second rule, because it is the last rule. There is no need for the guard in this case either, it is just the negation of the guard in the first rule. But let's leave both for clarity.

?- sum(1,3,What).
rule 2: J=1 K=3 N=_15630 I=1 S=0
...pos 3 passed
rule 2: J=1 K=3 N=_15630 I=2 S=1
...pos 3 passed
rule 2: J=1 K=3 N=_15630 I=3 S=3
...pos 3 passed
rule 2: J=1 K=3 N=_15630 I=4 S=6
end: J=1 K=3 I=4 Res=6
What = 6.

prolog - recursive predicate sum(J,K,N)

1 Answers