Prolog Programming

By
Mr. Manish Kumar Sharma
Assistant Professor (Senior Scale)

Lecture Delivered on: 20/10/2021

1 of 51
 The Plan
• An example program
• Syntax of terms
• Some simple programs
• Terms as data structures, unification
• The Cut
• Writing real programs

2 of 51
 What is Prolog?
• Prolog is the most widely used language
to have been inspired by logic
programming research. Some features:
• Prolog uses logical variables. These are
not the same as variables in other
languages. Programmers can use them as
‘holes’ in data structures that are
gradually filled in as computation
proceeds.

3 of 51
 …More
• Unification is a built - in term -
manipulation method that passes
parameters, returns results, selects and
constructs data structures.
• Basic control flow model is backtracking.
• Program clauses and data have the same
form.
• The relational form of procedures makes
it possible to define ‘reversible’
procedures.

4 of 51
 …More
• Clauses provide a convenient way to
express case analysis and
nondeterminism.
• Sometimes it is necessary to use control
features that are not part of ‘logic’.
• A Prolog program can also be seen as a
relational database containing rules as
well as facts.

5 of 51
 What a program looks like
/* At the Zoo */

elephant(george).
elephant(mary).

panda(chi_chi).
panda(ming_ming).

dangerous(X) :- big_teeth(X).
dangerous(X) :- venomous(X).

guess(X, tiger) :- stripey(X), big_teeth(X), isaCat(X).

guess(X, koala) :- arboreal(X), sleepy(X).
guess(X, zebra) :- stripey(X), isaHorse(X).
6 of 51
 Prolog is a ‘declarative’ language
• Clauses are statements about what is
true about a problem, instead of
instructions how to accomplish the
solution.
• The Prolog system uses the clauses to
work out how to accomplish the solution
by searching through the space of
possible solutions.
• Not all problems have pure declarative
specifications. Sometimes extralogical
statements are needed.
7 of 51
 Example: Concatenate lists a and b
list procedure cat(list a, list b)
In an imperative language {
list t = list u = copylist(a);
while ([Link] != nil) t = [Link];
[Link] = b;
return u;
}

cat(a,b) 
In a functional language if b = nil then a
else cons(head(a),
cat(tail(a),b))
cat([], Z, Z).
In a declarative language cat([H|T], L, [H|Z]) :- cat(T, L, Z).

8 of 51
 Complete Syntax of Terms
Term

Constant Compound Term Variable

Names an individual Names an individual Stands for an individual
that has parts unable to be named when
program is written
Atom Number likes(john, mary) X
alpha17 0 book(dickens, Z, cricket) Gross_pay
gross_pay 1 f(x) Diagnosis
john_smith 57 [1, 3, g(a), 7, 9] _257
dyspepsia 1.618 -(+(15, 17), t) _
+ 2.04e-27 15 + 17 - t
=/= -13.6
’12Q&A’

9 of 51
 Compound Terms
The parents of Spot are Fido and Rover.

parents(spot, fido, rover)

Functor (an atom) of arity 3. components (any terms)

It is possible to depict the term as a tree:

parents

spot fido rover

10 of 51
 Compound Terms
Some atoms have built - in operator declarations so
they may be written in a syntactically convenient
form. The meaning is not affected. This example
looks like an arithmetic expression, but might not
be. It is just a term.

=/=(15+X, (0*a)+(2<<5)) =/=

+ +

* <<
15 X

0 a 2 5

11 of 51
 More about operators
• Any atom may be designated an operator. The
only purpose is for convenience; the only effect
is how the term containing the atom is parsed.
Operators are ‘syntactic sugar’.
• We won’t be designating operators in this
course, but it is as well to understand them,
because a number of atoms have built - in
designations as operators.
• Operators have three properties: position,
precedence and associativity.

more…

12 of 51
 Examples of operator properties
Position Operator Syntax Normal Syntax
Prefix: -2 - (2)
Infix: 5+ 17 +(17,5)
Postfix: N! !(N)

Associativity: left, right, none.

X+ Y+ Z is parsed as (X+ Y)+ Z
because addition is left - associative. These are all the
same as the
Precedence: an integer. normal rules of
X+ Y*Z is parsed as X+(Y*Z) arithmetic.
because multiplication has higher precedence.

13 of 51
 The last point about Compound
Terms…

Constants are simply compound terms of arity 0.

badger
means the same as
badger()

14 of 51
 Structure of Programs

• Programs consist of procedures.

• Procedures consist of clauses.
• Each clause is a fact or a rule.
• Programs are executed by posing queries.

An example…

15 of 51
 Example

Predicate

Procedure for elephant

Facts

elephant(george).
Clauses elephant(mary).
elephant(X) :- grey(X), mammal(X), hasTrunk(X).
Rule

16 of 51
 Example

?- elephant(george).
Queries
yes

?- elephant(jane).
Replies
no

17 of 51
Clauses: Facts and Rules

‘if’
‘provided that’
‘turnstile’

Head :- Body . This is a rule.

Head. This is a fact.

Full stop at the end.

18 of 51
Body of a (rule) clause contains goals.

Head Body

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

Goals

Exercise: Identify all the parts of

Prolog text you have seen so far.
19 of 51
 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 G 1, G2, …, Gn being provable.”

Procedural reading: “To execute procedure H, the

procedures called by goals G 1, G2,
…, Gn are executed first.”
20 of 51
male(bertram). ?- pair(percival, X).
male(percival). ?- pair(apollo, daphne).
?- pair(camilla, X).
female(lucinda). ?- pair(X, lucinda).
female(camilla). ?- pair(X, X).
?- pair(bertram, lucinda).
pair(X, Y) :- male(X), female(Y). ?- pair(X, daphne).
?- pair(X, Y).

21 of 51
 Worksheet 2
drinks(john, martini). ?- pair(X, john, martini).
drinks(mary, gin). ?- pair(mary, susan, gin).
drinks(susan, vodka). ?- pair(john, mary, gin).
drinks(john, gin). ?- pair(john, john, gin).
drinks(fred, gin). ?- pair(X, Y, gin).
?- pair(bertram, lucinda).
pair(X, Y, Z) :- ?- pair(bertram, lucinda, vodka).
drinks(X, Z), ?- pair(X, Y, Z).
drinks(Y, Z).

This definition forces X and Y to be distinct:

pair(X, Y, Z) :- drinks(X, Z), drinks(Y, Z), X \== Y.
22 of 51
 Worksheet 3
(a) Representing a symmetric relation.
(b) Implementing a strange ticket condition.

berkshire surrey

kent

wiltshire hampshire sussex

How to represent this relation?

Note that borders are symmetric.

23 of 51
 WS3
This relation represents
What about the other?
one ‘direction’ of border:
(a) Say border(kent, sussex).
border(sussex, kent).
border(sussex, kent).
border(sussex, surrey).
border(surrey, kent).
border(hampshire, sussex).
(b) Say
border(hampshire, surrey).
adjacent(X, Y) :- border(X, Y).
border(hampshire, berkshire).
adjacent(X, Y) :- border(Y, X).
border(berkshire, surrey).
border(wiltshire, hampshire).
border(wiltshire, berkshire). (c) Say
border(X, Y) :- border(Y, X).

24 of 51
 WS3
Now a somewhat strange type of discount ticket. For the
ticket to be valid, one must pass through an intermediate
county.

A valid ticket between a start and end county obeys the

following rule:

valid(X, Y) :- adjacent(X, Z), adjacent(Z, Y)

25 of 51
 WS3
border(sussex, kent). valid(X, Y) :-
border(sussex, surrey).
adjacent(X, Z),
border(surrey, kent).
border(hampshire, sussex). adjacent(Z, Y)
border(hampshire, surrey).
border(hampshire, berkshire).
border(berkshire, surrey).
border(wiltshire, hampshire). ?- valid(wiltshire, sussex).
border(wiltshire, berkshire). ?- valid(wiltshire, kent).
?- valid(hampshire, hampshire).
adjacent(X, Y) :- border(X, Y). ?- valid(X, kent).
adjacent(X, Y) :- border(Y, X). ?- valid(sussex, X).
?- valid(X, Y).

26 of 51
 Worksheet 4 a
b
c
arc d e
f
a(g, h). Note that Prolog can g h
a(g, d). distinguish between
a(e, d). the 0-ary constant a
a(h, f). (the name of a node)
a(e, f). and the 2-ary path(X, X).
a(a, e). functor a (the name path(X, Y) :- a(X, Z), path(Z, Y).
a(a, b). of a relation).
a(b, f). ?- path(f, f).
a(b, c). ?- path(a, c).
a(f, c). ?- path(g, e).
?- path(g, X).
?- path(X, h).

27 of 51
 But what happens if…

a(g, h). path(X, X).

path(X, Y) :- a(X, Z), path(Z, Y).
a(g, d).
a a(e, d). This program works
b c a(h, f). only for acyclic graphs.
d e The program may
f a(e, f).
infinitely loop given a
g a(a, e).
h cyclic graph. We need
a(a, b). to leave a ‘trail’ of
a(b, f). visited nodes. This is
a(b, c). accomplished with a
a(f, c). data structure (to be
seen later).
a(d, a).
28 of 51
 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.

29 of 51
 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.
30 of 51
 Examples
The terms f(X, a(b,c)) and f(Z, a(Z, c)) unify.
f

f Z a

X a
Z c

b c

Note that Z co - refers within the term.

Here, X/ b, Z/ b.

31 of 51
 Examples
The terms f(c, a(b,c)) and f(Z, a(Z, c)) do not
unify.
f

f Z a

c a
Z c

b c

No matter how hard you try, these two terms

cannot be made identical by substituting terms
for variables.
32 of 51
 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

33 of 51
 Exercise
First write in the co - referring variables.

g g

Z f + 17 C f C E

A B D D E
A 17 B

34 of 51
 Exercise
Now proceed by recursive descent
Z/C, C/Z We go top-down, left-to-right, but
the order does not matter as long as
it is systematic and complete.
g g

Z f + 17 C f C E

A B D D E
A 17 B

35 of 51
 Exercise
Z/C, C/Z, A/D, D/A

g g

Z f + 17 C f C E

A B
A 17 B D D E

36 of 51
 Exercise
Z/C, C/Z, A/17, D/17

g g

Z f + 17 C f C E

A B
A 17 B D D E

37 of 51
 Exercise
Z/C, C/Z, A/17, D/17, B/E, E/B

g g

Z f + 17 C f C E

A B
A 17 B D D E

38 of 51
 Exercise
Z/17+B, C/17+B, A/17, D/17, B/E, E/B

g g

Z f + 17 C f C E

A B
A 17 B D D E

39 of 51
 Exercise
Z/17+17, C/17+17, A/17, D/17, B/17, E/17

g g

Z f + 17 C f C E

A B
A 17 B D D E

40 of 51
 Exercise – Alternative Method
Z/ C

g g

Z f + 17 C f C E

A B
A 17 B D D E

41 of 51
 Exercise – Alternative Method
Z/ C

g g

C f + 17 C f C E

A B
A 17 B D D E

42 of 51
 Exercise – Alternative Method
A/ D , Z/ C

g g

C f + 17 C f C E

A B
A 17 B D D E

43 of 51
 Exercise – Alternative Method
D/ 17 , A/ D, Z/ C

g g

C f + 17 C f C E

D B
D 17 B D D E

44 of 51
 Exercise – Alternative Method
D/ 17, A/ 17, Z/ C

g g

C f + 17 C f C E

17 17 B 17 B
17 17 E

45 of 51
 Exercise – Alternative Method
B/ E, D/ 17, A/ 17, Z/ C

g g

C f + 17 C f C E

17 17 B 17 B
17 17 E

46 of 51
 Exercise – Alternative Method
B/ E, D/ 17, A/ 17, Z/ C

g g

C f + 17 C f C E

17 17 E 17 E
17 17 E

47 of 51
 Exercise – Alternative Method
C/ 17+ E , B/ E, D/ 17, A/ 17, Z/ C

g g

C f + 17 C f C E

17 17 E 17 E
17 17 E

48 of 51
 Exercise – Alternative Method
C/ 17+ E, B/ E, D/ 17, A/ 17, Z/ 17+ E

g g
+ +
f + 17 f + E
17 E 17 E
17 17 E 17 E 17 17 E 17 E

49 of 51
 Exercise – Alternative Method
E/ 17 , C/ 17+ E, B/ E, D/ 17, A/ 17, Z/ C

g g
+ +
f + 17 f + E
17 E 17 E
17 17 E 17 E 17 17 E 17 E

50 of 51
 Exercise – Alternative Method
E/ 17, C/ 17+ 17, B/ 17, D/ 17, A/ 17, Z/ C

g g
+ +
f + 17 f + 17
17
17 17 17
17 17 17 17 17
17 17 17 17 17

51 of 51