How do recursive functions work in Prolog?

0
votes

I was reading a recursive function in prolog that returns the Sum of all the elements in a list as below :

sum([ ], 0).
sum( [Elem | Tail], S):- sum(Tail, S1),
                         S is S1 + Elem.

I can't understand two issues:

1: In the left side of ":-" we have the Goal. It means all the calculations will be done in the right side of ":-" and then we can use the Goal as a normal function. It means we give our arguments and variables that the result will be putted on them, and the right side is responsible for calculating.

But in this code the Goal, itself is calculating the Head and Tail. I mean in my mind the code should have been like this (however it doesn't work!) :

sum(Tail, S1):-sum( [Elem | Tail], S),........

Because the goal is supposed to give the arguments and the right side is in charge of calculating.

2: I cannot understand how this code works step by step. can anyone give me a very simple example like how it calculates the sum of [1,2,3]?

3
prolog
Your description, ...the goal is supposed to give the arguments and the right side is in charge of calculating makes it clear that you are thinking of Prolog predicates as if they were functions in an imperative language, but they are not. In Prolog, a predicate defines rules with one or more predicate clauses, and what you are calling the goal is the head of a clause which Prolog attempts to match by attempting unification between the query and the clause's head. If unification is achieved, then the rule matches and Prolog will exercise the rule (the clause body). - lurker

3 Answers

1
votes

An important part of prolog is matching (more generally, unification). When the Prolog run-time encounters a goal like sum(X,Y), it will try to match that term with the left-hand sides (head) of the rules for sum, in the order in which they appear. If the first rule fails, then the system will move to the second rule and so on.

In this case, the first head will only match if X is the empty list. If it is not empty, the match fails, and the next head is tried. This will succeed as long as X is any non empty list. Not only will it succeed, but it will bind the first element of the list to Elem , the rest of the list (which may be empty) to Tail. Since the second argument in the head of this rule is a variable, it will bind to whatever Y is.

Let's work through some examples:

sum([],X)?

First head matches, binding X to 0.

sum([1],X)?

First head does not match because [1] does not match []. Second one does with Elem <- 1, Tail<-[]. Therefore, we can proceed with the right-hand side of the rule: 

sum(Tail,S1), S is S1 + Elem

Since Tail<-[] , the goal sum(Tail,S1) will yield the binding S1<-0 (see above). So with Elem<-1 and S1<-0, S1+Elem = 1.

And so on. Hopefully there is enough here for you to do the rest.

1
votes

In the left side of :- you have a head of the rule; on the right side you have the body of the rule. When the :- side and the body are missing, the rule becomes a fact.

It is not correct to say that the calculation is performed only in the body, because the decision making process of Prolog works with both sides of the rule. The concept where the head of the rule plays an important role is unification, a process by which the language decides which clauses are applicable to the query, and makes checks and temporary assignments of variables in the rule head to parts of the query ("unifies" them).

For example, when you query sum([1,2,3], X), Prolog checks both sum clauses, and decides that the query unifies only with the second one, because [] cannot be unified with [1,2,3].

Now it needs to unify [1,2,3] with [Elem | Tail] by making a temporary assignment that lasts for as long as we are in the body of the rule: Elem=1, and Tail = [2,3]. At this point it tries to solve sum again, passing [2,3] as the first parameter. The first rule does not match, so another temporary assignment of Elem=2 and Tail=[3] is made. In the third level of recursion we reach an assignment Elem=3 and Tail=[]. This is when we hit the first rule, producing an assignment of S1=0. Third level of invocation adds 3 to it; second level adds 2. First level adds 1, and returns with X set to 6.

0
votes

Your speculations about what happens during the execution are rather strange. No functions are involved at all.

For the evaluation of the goal sum([1,2,3], X), the second clause is selected because there is no matching between [1,2,3] (first argument of the goal) and [] (in the head of the first clause).

The matching instantiates Elem=1, Tail=[2,3] and S = X. Then the goal sum([2,3], S1) is evaluated, and succeeds (after recursion), returning the substitution S1=5. Then S=5+1 binds S to 6.