Prolog Programming

Prolog: PROgramming in LOGic

• A Declarative and Logical Programming language
• Built-in inference mechanism based on Backward chaining and Unification
• Hence… Very similar to FOL
• Program in Prolog is a collection of facts and rules or logical assertions
• Logical assertions are horn clauses
• Prolog uses backward chaining and it starts with the goal
• Implication statements define the legimate reasoning path and the atomic
assertions provide the starting point.
• If goal contains variables it unifies it with the values and assigns the value
for which the goal is true
 Prolog Programming..
• Download from www.swi-prolog.org
• Type pl to start.
• Type halt. to exit.

Pl
?-
Welcome to SWI-Prolog……
For help, use ?- help(Topic).
 Structure of a Prolog Program
• Every goal in Prolog ends with dot
• A Prolog program consists of a KB of facts and rules where:
• Fact: head but no body
man(Marcus).
man(Plato).
• Rules: head and body
mortal(X) :- man(X).
• Questions: body but no head
mortal(Marcus).
Use ``;'' to get next possible answer
Yes means true with no variables, no means not consistent with database.
Clauses: Facts and Rules
‘if’
‘provided that’
‘turnstile’

Head :- Body. This is a rule.

Head. This is a fact.

Full stop at the end.

Body of a (rule) clause contains goals.
Head Body

likes(mary, X) :- human(X), honest(X).

Goals
Example: A very simple Program(Only facts)
Facts:
likes(john,flowers).
likes(john,mary).
likes(paul,mary).
Question:
?- likes(john,X)
Answer:
X=flowers and wait
;
mary
;
no
Example: A very simple Program(facts and
rules)
Facts:
likes(john,flowers). likes(john,mary).likes(paul,mary).likes(flowers, mary).

likes(john,X):-likes(X, mary).
Query: ?likes(john,paul) yes
Query: ?likes(john,mary) no
Query: ?likes(john,X)
X =john;
X = paul;
X = flowers;
No
Query: ?likes(X,paul)
no
 Logical Operators in Prolog
a :- b. /* a if b */
a :- b,c. /* a if b and c. */
a :- b;c. /* a if b or c. */
a :- not b. /* a if b fails */
a :- b -> c;d. /* a if (if b then c else d) */
Interpretation of Clauses
Clauses can be given a declarative reading or a procedural
reading.

Form of clause: H :- G1, G2, …, Gn.

“That H is provable follows from

Declarative reading:
goals G1, G2, …, Gn being provable.”

Procedural reading: “To execute procedure H, the

procedures called by goals G1, G2,
…, Gn are executed first.”
Facts
• John likes Mary : likes(john,mary)
• Names of relationship and objects must begin with a lower-case
letter.
• Relationship is written first (typically the predicate of the sentence).
• Objects are written separated by commas and are enclosed by a pair
of round brackets.
• The full stop character ‘.’ must come at the end of a fact.
More facts
Predicate Interpretation

valuable(gold) Gold is valuable.

owns(john,gold) John owns gold.

father(john,mary) John is the father of

Mary
gives (john,book,mary) John gives the book to
Mary
Queries or questions based on facts
• Answered by matching
• Two facts match if their predicates are same (spelt the same way) and
the arguments each are same.
• If matched, prolog answers yes, else no.
• “No” does not mean falsity.
Prolog does theorem proving
• When a question is asked, prolog tries to match transitively.
• When no match is found, answer is no.
• This means not provable from the given facts.
Variables
• Always begin with a capital letter
• ?- likes (john,X).
• ?- likes (john, Something).
• But not
• ?- likes (john,something)
Disjunction
•;
• Multiple rules
• P :- Q. P :- R, S. Equivalent to

P :- Q; R, S.
• ancestor(X,Z):- parent(X,Z); parent(X,Y), ancestor(Y,Z).
Conjunctions
• Use ‘,’ and pronounce it as and.
• Example
• Facts:
• likes(mary,food).
• likes(mary,tea).
• likes(john,tea).
• likes(john,mary)
• ?-
• likes(mary,X),likes(john,X).
• Meaning is anything liked by Mary also liked by John?
Backtracking (an inherent property of prolog
programming)
Unification with backtracking
likes(mary,X),likes(john,X)

likes(mary,food)
likes(mary,tea)
likes(john,tea)
likes(john,mary)

1. First goal succeeds. X=food

2. Satisfy likes(john,food)
Backtracking (continued)
Returning to a marked place and trying to resatisfy is called
Backtracking
likes(mary,X),likes(john,X)

likes(mary,food)
likes(mary,tea)
likes(john,tea)
likes(john,mary)

1. Second goal fails

2. Return to marked place
and try to resatisfy the first goal
Backtracking (continued)

likes(mary,X),likes(john,X)

likes(mary,food)
likes(mary,tea)
likes(john,tea)
likes(john,mary)

1. First goal succeeds again, X=tea

2. Attempt to satisfy the likes(john,tea)
Backtracking (continued)

likes(mary,X),likes(john,X)

likes(mary,food)
likes(mary,tea)
likes(john,tea)
likes(john,mary)

1. Second goal also suceeds

2. Prolog notifies success and waits for a reply
Rules
• Statements about objects and their relationships
• If-then conditions
• I use an umbrella if there is a rain
• use(i, umbrella) :- occur(rain).
• Generalizations
• All men are mortal
• mortal(X) :- man(X).
• Definitions
• An animal is a bird if it has feathers
• bird(X) :- animal(X), has_feather(X).
Syntax
• <head> :- <body>
• Read ‘:-’ as ‘if’.
• E.G.
• likes(john,X) :- likes(X,cricket).
• “John likes X if X likes cricket”.
• i.e., “John likes anyone who likes cricket”.
• Rules always end with ‘.’.
Another Example
sister_of (X,Y):- female (X),
parents (X, M, F),
parents (Y, M, F).

X is a sister of Y is
X is a female and
X and Y have same parents
Question Answering in presence of rules
• Facts
• male (ram).
• male (shyam).
• female (sita).
• female (gita).
• parents (shyam, gita, ram).
• parents (sita, gita, ram).
 Question Answering: Y/N type: is sita the sister of
shyam?
?- sister_of (sita, shyam)

parents(sita,M,F) parents(shyam,M,F)
female(sita)

parents(shyam,gita,ram)
parents(sita,gita,ram)

success
 Question Answering: wh-type: whose sister is sita?

?- ?- sister_of (sita, X)

parents(sita,M,F) parents(Y,M,F)
female(sita)

parents(Y,gita,ram)

parents(sita,gita,ram)
parents(shyam,gita,ram)

Success
Y=shyam
Exercise
1. From the above it is possible for somebody to be her own sister.
How can this be prevented?
Another Example to recap the control flow
r(a).
s(b,c).
m(b).
n(a).
q(X):- m(X).
q(X):- n(X).
p(X,Y) :- q(X), r(Y).
p(X,Y) :- r(X), s(X,Y).
Goal is: p(a,Y)
How will Prolog respond to the query if we
keep entering..
p(a,b).
P(b,c).
P(X,Y):-p(Y,X).

Query:
?-p(X,Y).
Unification
• Two terms unify if substitutions can be made for any variables in the terms so
that the terms are made identical. If no such substitution exists, the terms do not
unify.
• The Unification Algorithm proceeds by recursive descent of the two terms.
• Constants unify if they are identical
• Variables unify with any term, including other variables
• Compound terms unify if their functors and components unify.
Examples
The terms f(X, a(b,c)) and f(d, a(Z, c)) unify.
f

f d a

X a
Z c

b c

The terms are made equal if d is substituted for X,

and b is substituted for Z. We also say X is
instantiated to d and Z is instantiated to b, or X/d,
Z/b.
Exercise
Do terms g(Z, f(A, 17, B), A+B, 17) and
g(C, f(D, D, E), C, E) unify?

g g

Z f + 17 C f C E

A B
A 17 B D D E
Second lecture of Prolog
 Writing a Prolog program for following facts
and rules
(1) Jia is a woman. woman(jia).
(2) John is a man. man(john)
(3) John is healthy. healthy(john)
(4) Jia is healthy. healthy(jia)
(5) John is wealthy. wealthy(john)
(6) Anyone is a traveler if he is healthy and wealthy.
traveler(X):- healthy(X), wealthy(X).

(7) anyone can travel if he is a traveler. travel(X):- traveler(X).

- Goals.
(1) Who can travel?
(2) Who is healthy and wealthy?
 Create Rules ….
• M is the mother of P if she is a parent of P and is female.
• F is the father of P if he is a parent of P and is male
• X is a sibling of Y if they both have the same parent.
• sister, brother, aunt, uncle, grandparent, cousin
 Arithmetic Operators
Operators +, -, *, /, sqrt, exp, cos, etc are available.
But, such expressions will not “match” a variable.
If given: prime(2). prime(3).
Then prime(1+1) will fail, because cannot be unified
with any entry in the KB.
We can write predicates like this:
positive(N) :- N>0.
non_zero(N) :- N<0 ; N>0.
 Factorial Program
• In C, we write recursive program for factorial, in Prolog also it is a
recursive program.
• It has a base condition and then recursive definition is given.
• But in Prolog, it is in the form of predicate which has first term as
input and second term as output.
factorial(0, 1).
factorial(A, B) :- A>0, C is A-1, factorial(C, D), B is A*D.

?- factorial(10,What). Or fact(3, 6).

 Lists and recursion in Prolog
• Till now we have only considered simple items as arguments to our Prolog
programs.
• But, in Prolog a very common data-structure is the list.
• List is an ordered sequence of elements that can have any length.
• Ordered means that order of elements matters in the sequence.
• The syntax of list is: It always starts and ends with square brackets and
each item is separated by a comma.
• Obviously list contains same type of elements but we can have [1,2,9.0]
• Example: [a,b,c,d], [apple,mango,banana], [A, mohan]
 Structure of list
• A list is either empty or contains elements. Prolog understands list as a
right-branching tree shown in figure.
• Or we can say that list is represented as right branching tree.
• So the structure of [a, b, c] would be:
Cont..
• Prolog also has a special facility to split the first part of the list
(called the head) away from the rest of the list (known as the tail).
• We can place a special symbol | (pronounced 'bar') in the list to
distinguish between the first item in the list and the remaining list.
• For example, consider the following: [a,b,c] = [X|Y]
• Then unification succeeds with X = a and Y =[b,c]
• X is bound to the first item in the list, and Y to the remaining list.
Example: How unification will take place
• ?- [ ] = X.
X=[]?
• ?- [a] = [X].
X=a?
• ?-[a, b] = [X].
No
• ?-[a, b] = [X, Y].
X = a,
Y=b?
• ?- [a, b] = [X | Y].
X = a,
Y = [b] ?
Cont…
Consider the following fact: p([H|T], H, T).
Lets see what happens when we ask some simple queries.
?- p([a,b,c], X, Y).
X=a
Y=[b,c]
yes
?- p([a], X, Y).
X=a
Y=[]
yes
?- p([], X, Y).
No (([H|T] can not be empty, there has to be atleast one element
Some simple Prolog programs using lists
append([],List,List).

append([Head|Tail],List2,[Head|Result]):-
append(Tail,List2,Result).

• member(X,[X|_]).
Note: _ is called anonymous variable, which can be unified with any
value
• member(X, [_|Y]):- member(X,Y).
Prolog Program Flow, BackTracking and
Cut
Controlling the program flow
 How Prolog computes?
• Depth First Search: to find a goal
• Pursues a goal till the end
• Conditional AND; falsity of any goal prevents satisfaction of further
clauses.
• Conditional OR; satisfaction of any goal prevents further clauses being
evaluated.
Control flow (top level)
Given
g:- a, b, c. (1)
g:- d, e, f; g. (2)

If prolog cannot satisfy (1), control will automatically fall through to (2).
Control Flow within a rule
Taking (1): g:- a, b, c.
• If a succeeds, prolog will try to satisfy b, succeeding which, c will be
tried.
• For ANDed clauses, control flows forward till the ‘.’, iff the current
clause is true.
• For ORed clauses, control flows forward till the ‘.’, iff the current
clause evaluates to false.
Fundamental Principle of prolog programming

• Always place the more general rule AFTER a specific rule.

 Backtracking in Prolog
• Prolog is a highly recursive language and all of its strength comes
from the recursion
• But, sometimes, we would like to break recursion for certain
conditions or we can say that we would like to change the traditional
way of Prolog backtracking to our choice
• Backward chaining starts with the goal and to satisfy it… further
subgoals are generated and if subgoals are satisfied it says yes..
otherwise it says no..
• Let us learn how to temper the process of Prolog Backtracking and
how much we can temper??
Cont..
• Prolog uses DFS for backtracking… It works like this..
• Suppose it finds a match at a particular point, then this point is marked…
• If at certain point goal fails then it backtracks to the nearest clause marked
for backtracking and at that point..
• The variables that were previously bound in an attempt to satisfy goal
become unbound after the backtrack point
• For example: adjacent(r1,r2). adjacent(r2,r3). adjacent(r4,r5).
adjacent(r1,r3). adjacent(r2,r4).
goal(A,C):-adjacent(A,B),adjacent(B,D), adjacent(D,C).
?-goal(X,Y)
 The cut ‘!’ for controlling
• ! is called the cut predicate which always succeeds but when it is
encountered in the process of verifying a conjunction of subgoals
• The cut forces Prolog to commit to all the bindings made till the cut
predicate (this means whatever binding have been done before cut, those
will not be changed)
• Hence, the cut ! may be viewed as a fence which the unification process
may cross only once in unifying from left to right
• So if we have r:- a,b,!,c.
• Then no back tracking will be done once a and b succeed but for c
backtracking will be done
• adjacent(r1,r2). adjacent(r2,r1). adjacent(r1,r3). adjacent(r3,r4). goal(A,C):-
adjacent(A,B),!, adjacent(B,C).
CUT
• Cut tells the system that:

IF YOU HAVE COME THIS FAR

DO NOT BACKTRACK

EVEN IF YOU FAIL SUBSEQUENTLY.

‘CUT’ WRITTEN AS ‘!’ ALWAYS SUCCEEDS.

 Fail
• This predicate always fails.
• Cut and Fail combination is used to produce negation.
• Since the LHS of the neck cannot contain any operator, A  ~B is
implemented as
B :- A, !, Fail.
It is basically saying that ~B is true if A is true
Examples..
• Find the maximum of two:
max(X, Y, X):-X>=Y,!.
max(X, Y, Y).
Cut-fail combination
Suppose we have: Jane likes all jewellary except rings
Likes(jane,X):-ring(X),!,fail.
likes(jane,X):-jewellary(X).
Cont..
• Sum(1,1):-!.
• Sum(N, Res):-N1=N-1,sum(N1,Res1), Res is Res1 +N.
• Suppose a person can not be a average tax payer if he is a foreigner so we
can form rules like:
• Average_taxpayer(X):-foreigner(X),fail.
• Average_taxpayer(X):-some rules….
• In this case, Prolog will back track so we will write it as:
• Average_taxpayer(X):-foreigner(X),!,fail.
• (Write a prolog program which assigns attendance marks to students, if the
attendance is greater than 75, it gives 5, if between 60 and 75 then 3,
otherwise 0)
 Problems with cut
First Program: no_of_parents(adam,0):-!.
no_of_parents(eve,0) :-!.
no_of_parents(X,2).
What is wrong with this?
This will give: no_of_parents(eve,2) as true
Second Program: no_of_parents(adam,N):-!, N=0.
no_of_parents(eve,N) :-!,N=0.
no_of_parents(X,2).
 Assignment
• Write a recursive definition that will translate a string of English
words into Hindi. You will need a set of 2-place facts giving the English
and Hindi counterparts, and a two-place recursive rule that works its
way down a list, looking up the word-translations item by item, and
putting the resulting translation into the second argument. The
predicate should produce the following kind of result:
• translate(['John', is, clever], Hindi).
Hindi = [John, hai, chatur]
End of second lecture