Sum of the first n numbers in prolog

Question

Hello can anyone help me compute the sum of the first n numbers. For example n=4 => sum = 10. So far I've wrote this

    predicates
  sum(integer,integer)
clauses

  sum(0,0).
   sum(N,R):-
        N1=N-1,
        sum(N1,R1),
        R=R1+N.

This one works but I need another implementation. I don't have any ideas how I could make this differen . Please help

Answer 1

This is the "heart" of your program:

sum(N,R):-
    R=R+N,
    N=N-1,
    sum(N,R).

The =/2 predicate (note the /2 means it accepts 2 arguments) is the instantiation predicate, not an assignment, or logical equal. It attempts to unify its arguments to make them the same. So if N is anything but 0, then R=R+N will always fail because R can never be the same as R+N. Likewise for N=N-1: it will always fail because N and N-1 can never be the same.

In the case of =/2 (unification), expressions are not evaluated. They are just terms. So if Y = 1, then X = Y + 1 unifies X with 1+1 as a term (equivalently written +(1,1)).

Because of the above issues, sum will always fail.

Numerical assignment of an arithmetic expression is done in Prolog with the is/2 predicate. Like this:

X is Y + 1.

This operator unifies the value of X to be the same as the value of the evaluated expression Y+1. In this case, you also cannot have X is X+1 for the same reason given above: X cannot be made the same as X+1 and Prolog does not allow "re-instantiation" of a variable inside of a clause. So you would need something like, X1 is X + 1. Also note that for is/2 to work, everything in the expression on the right must be previously instantiated. If any variables in the expression on the right do not have a value, you will get an instantiation error or, in the case of Turbo Prolog, Free variable in expression....

So you need to use different variables for expression results, and organize the code so that, if using is/2, variables in the expression are instantiated.

---

EDIT

I understand from Sergey Dymchenko that Turbo Prolog, unlike GNU or SWI, evaluates expressions for =/2. So the = will work in the given problem. However, the error regarding instantiation (or "free variable") is still caused by the same issue I mentioned above.

Answer 2

What @mbratch said.

What you're computing is a triangular number. If your homework is about triangular numbers and not about learning recursive thinking, you can simply compute it thus:

triangular_number(N,R) :- R is N * (N+1) / 2 .

If, as is more likely, you're learning recursive thought, try this:

 sum(N,R) :-    % to compute the triangular number n,
   sum(N,1,0,R) % - invoke the worker predicate with its counter and accumulator properly seeded
   .

 sum(0,_,R,R).     % when the count gets decremented to zero, we're done. Unify the accumulator with the result.
 sum(C,X,T,R) :-   % otherwise,
   C > 0 ,         % - assuming the count is greater than zero
   T1 is T+X ,     % - increment the accumulator
   X1 is X+1 ,     % - increment the current number
   C1 is C-1 ,     % - decrement the count
   sum(C1,X1,T1,R) % - recurse down
   .               % Easy!

Edited to add:

Or, if you prefer a count down approach:

 sum(N,R) :- sum(N,0,R).

 sum(0,R,R).       % when the count gets decremented to zero, we're done. Unify the accumulator with the result.
 sum(N,T,R) :-     % otherwise,
   N > 0 ,         % - assuming the count is greater than zero
   T1 is T+N ,     % - increment the accumulator
   N1 is N-1 ,     % - decrement the count
   sum(N1,T1,R)    % - recurse down
   .               % Easy!

Both of these are tail-recursive, meaning that the prolog compiler can turn them into iteration (google "tail recursion optimization" for details).

If you want to eliminate the accumulator, you need to do something like this:

sum(0,0).
sum(N,R) :-
  N > 0 ,
  N1 is N-1 ,
  sum(N1,R1) ,
  R is R1+N
  .

A little bit simpler, but each recursion consumes another stack frame: given a sufficiently large value for N, execution will fail with a stack overflow.

Answer 3

sum(N, Sum) :-
    Sum is (N + 1) * N / 2 .

Answer 4

Since you already got plenty of advice about your code, let me throw in a snippet (a bit off-topic).

Counting, and more generally, aggregating, it's an area where Prolog doesn't shine when compared to other relational,declarative languages (read SQL). But some vendor specific library make it much more pleasant:

?- aggregate(sum(N),between(1,4,N),S).
S = 10.

Answer 5

sum(N, N, N).  
sum(M, N, S):-
  N>M,
  X is M+1,
  sum(X, N, T),
  S is M+T.


?- sum(1,5,N).
   N = 15 .