Sum to a number program in Prolog

user_14693830 0
Viewed 601

Can someone explain how this code works. I am new to Prolog and I am having trouble thinking like a Prolog programmer. When you input a number followed by a comma and any variable name, it gives you the sum up to that number

sum_to(1,1) :- !.
sum_to(N, R) :- N1 is N-1, sum_to(N1,TR), R is TR + N.

So sum_to(4, N) gives N = 10.

prolog
2 Answers

This is a very imperative-style program implementing an inductive definition concidentally written in Prolog.

It relates two numbers:

In the first clause 1 is related to 1. The ! indicates that the interpreter should stop looking for further solutions in the sum_to/2 predicate.

If the first clause doesn't match (because any of the arguments in the call was different from 1) then the second clause is examined.

And now we simply:

  • Compute N1 as N-1

  • Make a recursive call with N1, and getting a value in TR such that N1 and TR are related via sum_to/2 (i.e. TR should be the sum of all integers up to N1). Once we get that, we compute R as the sum of TR and N.

  • The sum_to relation is correct for the first argument being 1.

  • The sum_to relation at N is correct if the sum_to relation is correct for N-1.

  • Computation will terminate if the recursive call "makes something smaller" on each call and will eventually hit a smallest value. It does indeed make N smaller on each call and will eventually hit 1. (Unless one calls this predicate with a 0 N or smaller. Then: catastrophe!)

Looking good.

(Incidentally, inductive definitions tend to go from a constant x to +oo, i.e. "going upwards"; above I am stating correctness moving from any N down towards 1. Am I justified in doing so?)

user_8844630

Your definition can be equivalently written as

sum_to( N, R) :- N = 1, R = 1, !.
sum_to( N, R) :- N1 is N-1, sum_to( N1, R1), R is R1+N.

This is a recursive definition -- it contains a call to the same predicate as the predicate itself. Under the condition that you're going to always call it with a free variable as the second argument and a concrete (hopefully positive) number as the first argument, it expresses a function which calculates the second argument's value from the given first argument.

Thus what you have is a recursive functional definition.

Now let's work through some examples, from the simplest to the progressively more and more complex:

sum_to( 1, R1) :- 1 = 1, R1 = 1, !.
                  \______________/
                         R1 = 1.

sum_to( 2, R2) :- N1 is 2-1, sum_to( N1, R1), R2 is R1+2.
                  \________/
                    N1 is 1, sum_to( 1, R1),
                             \____________/
                                      R1 = 1, R2 is 1+2   
                  \_____________________________________/
                                              R2 = 3.

sum_to( 3, R3) :- N2 is 3-1,  sum_to( N2, R2),        R3 is R2+3.
                  \________/
                    N2 is 2,   sum_to( 2, R2),
                               \____......____/
                                \__________________/
                                              R2 = 3, R3 is 3+3   
                  \_____________________________________________/
                                                      R3 = 6.

Right? As the execution progresses through the goals left to right, our variables take on their concrete values one after the other, thus enabling the execution of the next goal, and the next, which instantiate yet more variables, until the final value becomes known.

Now do sum_to( 4, R4).

user_8498910
Related