2

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

user3043278
  • 174
  • 1
  • 3
  • 15
  • What happened when you ran your program? – lurker Jan 09 '14 at 22:01
  • can you please edit your code to make clear what is comment and what is code? This file wouldn't load/compile as is. – Christian Fritz Jan 09 '14 at 22:10
  • 2
    @ChristianF this appears to be Visual Prolog which uses named sections and allows definition of data types within the `domains` section. It's a little off-standard. The above code is syntactically valid Visual Prolog code (with the exeception of the misspelled "intger"). – lurker Jan 09 '14 at 22:11
  • I'm using Turbo Prolog. I get the following error : Free variable in expresion R=R+N – user3043278 Jan 09 '14 at 22:19
  • Turbo Prolog is the same as Visual Prolog. Borland bought it many, many years ago from Prolog Development Corp and then sold it back later on. :) – lurker Jan 09 '14 at 22:22

5 Answers5

7

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.

Nicholas Carey
  • 71,308
  • 16
  • 93
  • 135
  • I don't understand why you used X and T. I understand the recursive algorithm for the sum but I don't know how to write it in Prolog. If my number is bigger than 1 I add the number to the result and then call sum(number-1). – user3043278 Jan 10 '14 at 08:08
  • 1
    @user3043278: I prefer counting up, rather than down. Six of one; a half dozen of the other, as they say. I've added a simple count down version to my answer. Also added something closer to what you originally had with an explanation of why I took the approach I did. – Nicholas Carey Jan 10 '14 at 17:58
3
sum(N, Sum) :-
    Sum is (N + 1) * N / 2 .
salva
  • 9,943
  • 4
  • 29
  • 57
3

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.
CapelliC
  • 59,646
  • 5
  • 47
  • 90
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.

lurker
  • 56,987
  • 9
  • 69
  • 103
  • I tried this but still not working sum(N,R):- P=R+N, N1=N-1, sum(N1,P). – user3043278 Jan 09 '14 at 22:36
  • @user3043278 See elements of my answer regarding `=/2` versus `is/2`. Also see my description regarding cause of "Free variable in expression..." First, you need `is` instead of `=`. `=` isn't the right predicate. Secondly, in the order that they exist in your clause, `is` will fail due to an instantiation (free variable) error. – lurker Jan 09 '14 at 22:57
  • mbratch, Visual Prolog (and Turbo Prolog) is a funny thing, =/2 is used instead of is/2: see examples at http://progopedia.com/implementation/visual-prolog/ – Sergii Dymchenko Jan 10 '14 at 01:37
  • @SergeyDymchenko wow, that's interesting. It's been a long time since I used Turbo Prolog and I had forgotten that they deviated from the basic standard, which is too bad. The `=/2` versus `is/2` is something quite fundamental. I did try the example you linked to in GNU Prolog for interest and it stack overflowed (after I edited out the Turbo Prolog environment items), probably because it tried to unify with `=/2`, like it's supposed to. But that said, my comments about "Free variable..." still apply. – lurker Jan 10 '14 at 01:58
0
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 .
rashedcs
  • 3,588
  • 2
  • 39
  • 40