Artificial Intelligence
Dr Khadija Kanwal
Institute of CS&IT
The Women University Multan
Prolog Programming
slides written by
The Plan
An example program
Syntax of terms
Some simple programs
Terms as data structures, unification
The Cut
Writing real programs
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.
…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.
…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.
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).
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.
Example: Concatenate lists a
and b
list procedure cat(list a, list b)
{
In an imperative language list t = list u = copylist(a);
while (t.tail != nil) t = t.tail;
t.tail = 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).
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’
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
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
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’.
A number of atoms have built-in designations
as operators.
Operators have three properties: position,
precedence and associativity.
more…
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.
The last point about Compound
Terms…
Constants are simply compound terms of arity 0.
badger
means the same as
badger()
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…
Example
Predicate
Procedure for elephant
Facts
elephant(george).
Clauses elephant(mary).
elephant(X) :- grey(X), mammal(X),
hasTrunk(X).
Rule
Example
?- elephant(george).
Queries
yes
?- elephant(jane).
Replies
no
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
Exercise: Identify all the parts of
Prolog text you have seen so
far.
Interpretation of Clauses
Clauses can be given a declarative reading or a
procedural reading.
Form of clause: H :- G1, G2, …, Gn.
Declarative reading: “That H is provable follows from
goals G1, G2, …, Gn being
provable.”
Procedural reading: “To execute procedure H, the
procedures called by goals G1, G2,
…, Gn are executed first.”
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,
pair(X, Y) :- male(X), lucinda).
female(Y). ?- pair(X, daphne).
?- pair(X, Y).
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,
drinks(X, Z), vodka).
drinks(Y, Z). ?- pair(X, Y, Z).
This definition forces X and Y to be distinct:
pair(X, Y, Z) :- drinks(X, Z), drinks(Y, Z), X \
== Y.
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.
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).
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)
WS3
border(sussex, kent).
valid(X, Y) :-
border(sussex, surrey).
border(surrey, kent). adjacent(X,
border(hampshire, sussex). Z),
border(hampshire, surrey). adjacent(Z, Y)
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).
a
Worksheet 4 b c
arc d e
f
a(g, h). Note that Prolog g
a(g, d). can distinguish h
a(e, d). between the 0-ary
a(h, f). constant a (the
a(e, f). name of a node) and path(X, X).
a(a, e). the 2-ary functor a path(X, Y) :- a(X, Z), path(Z, Y).
a(a, b). (the name of a
a(b, f). relation). ?- path(f, f).
?- path(a, c).
a(b, c).
?- path(g, e).
a(f, c). ?- path(g, X).
?- path(X, h).
But what happens if…
a(g, h). path(X, X).
a(g, d). path(X, Y) :- a(X, Z), path(Z, Y).
a(e, d).
a b This program works
c a(h, f). only for acyclic
d e a(e, f).
graphs. The program
f a(a, e). may infinitely loop
g h a(a, b). given a cyclic graph.
a(b, f). We need to leave a
a(b, c). ‘trail’ of visited nodes.
a(f, c). This is accomplished
a(d, a). with a data structure
(to be seen later).
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 a
d
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.
Examples
The terms f(X, a(b,c)) and f(Z, a(Z, c)) unify.
f
f a
Z
X a
Z c
b c
Note that Z co-refers within the term.
Here, X/b, Z/b.
Examples
The terms f(c, a(b,c)) and f(Z, a(Z, c)) do not unify.
f a
Z
c a
Z c
b c
No matter how hard you try, these two terms
cannot be made identical by substituting
terms for variables.
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
Exercise
First write in the co-referring variables.
g g
Z f + 17 C f C E
A B
A 17 B D D E
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
A 17 B D D E
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
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
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
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
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
Exercise – Alternative Method
Z/C
g g
Z f + 17 C f C E
A B
A 17 B D D E
Exercise – Alternative Method
Z/C
g g
C f + 17 C f C E
A B
A 17 B D D E
Exercise – Alternative Method
A/D, Z/C
g g
C f + 17 C f C E
A B
A 17 B D D E
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
Exercise – Alternative Method
D/17, A/17, Z/C
g g
C f + 17 C f C E
17 B
17 17 B 17 17 E
Exercise – Alternative Method
B/E, D/17, A/17, Z/C
g g
C f + 17 C f C E
17 B
17 17 B 17 17 E
Exercise – Alternative Method
B/E, D/17, A/17, Z/C
g g
C f + 17 C f C E
17 E
17 17 E 17 17 E
Exercise – Alternative Method
C/17+E, B/E, D/17, A/17, Z/C
g g
C f + 17 C f C E
17 E
17 17 E 17 17 E
Exercise – Alternative Method
C/17+E, B/E, D/17, A/17, Z/17+E
g g
+ +
f + 17 f + E
17 E
1 E
17 E 1 E
17 17 E 7 17 17 E
7
Exercise – Alternative Method
E/17, C/17+E, B/E, D/17, A/17, Z/C
g g
+ +
f + 17 f + E
17 E
1 E
17 E 1 E
17 17 E 7 17 17 E
7
Exercise – Alternative Method
E/17, C/17+17, B/17, D/17, A/17, Z/C
g g
+ +
f + 17 f + 17
17 17
1 1
17 17 1 1
17 17 17 7 717 17 1
7 7 7
Thank You!
