3

I'm a beginner at prolog programming and I hope you humble and help me to pass this confusion

I'm facing a problem to calculate the sum in prolog and I have the answer but it's not so clear to me. The answer is:

list_sum([], 0).
list_sum([Head | Tail], Total) :-
   list_sum(Tail, Sum1),
   Total = Head + Sum1.

what I did not understand is what is the Sum1 and how the program will work in steps

it first will check the first condition list_sum([], 0). while the condition is not met it will divide the list into 2 parts Head and Tail then?


I hope you accept a little beginner and give him some time to correct his confusing.
Thanks you guys

lurker
  • 56,987
  • 9
  • 69
  • 103
user3018890
  • 49
  • 5

2 Answers2

5

This is the classic recursive approach - you need to get comfortable with it to understand Prolog.

Your rule has two clauses - the one for the empty list, and the one for a non-empty one. The empty list clause says that the sum of elements of an empty list is zero (which is perfectly reasonable). This is called "the base case of recursion". Every terminating recursive rule must have a base case.

The second clause is a little more complex. It says roughly this: "to compute the sum of elements in a non-empty list, first chop off the initial element, and compute the sum of elements in a shorter list that results. Call that sum Sum1. Now compute the Total by adding the value of the initial element to the value of Sum1.

The second clause recursively decomposes the list into a series of shorter lists until they get to an empty list. At this point the first clause steps in, providing the sum of an empty list.

Consider this example:

list_sum([12, 34, 56], X)
    list_sum([34, 56], <unknown-1>)
        list_sum([56], <unknown-2>)
            list_sum([], 0)         ---> succeeds with Total bound to 0
        <unknown-2> becomes 0 + 56  ---> succeeds with Total bound to 56
    <unknown-1> becomes 0 + 56 + 34 ---> succeeds with Total bound to 90
X becomes 0 + 56 + 34 + 12          ---> succeeds with X bound to 102

This works because each invocation level in the recursive chain gets its own variable for Sum1. These values start unbounded, but once the recursive invocation chain "bottoms out", Sum1s start getting values computed by each prior level. Eventually, the call chain reaches the top level, binding the final result to the variable passed by the caller.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • Totally appreciate it . Thank you very much . God bless you . It was too hard for me to understand that in the first . But you made it all simply clear for me – user3018890 Nov 21 '13 at 19:21
  • Good explanation, but "returning with 102", etc., is a bit misleading, especially to someone used to thinking procedurally. Prolog clauses don't return values; they don't "return" at all. It would be more accurate to say something like "succeeds with `X` bound to 102", etc. – Ted Hopp Nov 21 '13 at 19:30
  • @TedHopp I thought about that, too - return is a little misleading. I added "with", trying to imply that the value is not "returned" in a procedural sense. I like your wording better than mine, though, - thanks for a great comment! – Sergey Kalinichenko Nov 21 '13 at 19:47
5

There is a tiny error in your program to start with - the line Total = Head + Sum means that Total is a structure + with two arguments. You probably mean is in place of = meaning arithmetic evaluation. But the best is to use #= instead.

In your question you are asking what the program will do. That is quite a reasonable question in command-oriented ("imperative") languages, because the only meaning you can get out of the program is its step-by-step action. But here in Prolog things are a bit different. You can still try to apply that step-by-step thinking but sooner or later you will realize that things can get extremely complex here, simply because Prolog has not one control-flow but two at the same time called (AND- and OR-control). And even the "data-structures" are different...

But there is a way to read a Prolog program, that has no counterpart in imperative languages: You can understand a program as a relation between the arguments. In this manner, you can concentrate on what the relation looks like instead on procedural aspects. After all, if the relation described is wrong, there is no point in asking how the program does this.

So let me rephrase your program:

:- use_module(library(clpfd)).
list_sum([], 0).
list_sum([E|Es], S) :-
   S #= E+T,
   list_sum(Es, T).

it first will check the first condition list_sum([], 0). while the condition is not met it will divide the list into 2 parts H and T then ?

Your question implies that there is a single control flow ("while is such typical construct that implies it"). But it might also work differently. Consider the query:

?- list_sum(Xs,0).
   Xs = []
;  Xs = [0]
;  Xs = [_A,_B], _A+_B#=0
;  ... .

Here we ask What lists exists whose sum is 0. Now your "while" no longer makes sense.

The answers we get are: The empty list ; a list with 0 ; a two-element list where the sum of the elements is 0 ; etc...

The best way to understand such programs is to read them as relations like so:

list_sum([], 0: An empty list has sum 0.

The rule now reads best in the direction of the arrow :- that is, right-to-left:

  • list_sum(Es, T).: *Provided Es is a list with sum T and ...

  • S #= E+T: ... S is E plus T ...

  • :- ... then we can conclude that ...

  • list_sum([E|Es], S): S is the sum of the list [E|Es].

In this manner these things can be understood without referring too much to procedural details. There is more to it like understanding termination see .

false
  • 10,264
  • 13
  • 101
  • 209
  • 1
    +1, I highly recommend this style for reading predicates, and using finite domain constraints for integer arithmetic. – mat Nov 22 '13 at 01:13