Artificial Intelligence

Programming in Prolog

An Introduction
Part 1
 What is Prolog?
• Prolog is a logic programming language.
• The name Prolog is taken from programmation en
logique ("programming in logic"). It was created by Alain
Colmerauer and Robert Kowalski around 1972 as an
alternative to the American-dominated Lisp programming
languages.
• Prolog is a declarative language: you specify what
problem you want to solve rather than how to solve it.
• Prolog is used in many artificial intelligence programs,
expert systems, and in computational linguistics
(especially natural language processing).
• Prolog is based on first-order predicate calculus

2
 Prolog programs
• A Prolog program is a list of Clauses.
– In fact Horn Clauses
• Each clause is a Fact or a Rule.

Terms
Atoms
Predicate
Facts
parent (tom, bob) . Variables and
if
Clauses parent (bob, liz) .

grandParent (X,Y) :- parent (X,Z) , parent (Z,Y) .

Rule Head Body

3
 What is a Term?
Term

Constant Variable Compound Term

(Names an individual) (Stands for an individual (Names an individual
unable to be named when that has parts)
program is written)

Atom Number X
mary 57 Person Structures Lists
ball 1.618 Stu_Avg
_257 date(2010,may,3) []
ball22 2.04e-27 mother(ali)
stu_avg -13.6 _ [4,6,7]
‘Mary’ [ali,reza]
‘john smith’ [[3,4],[7,8]]
- Always start with an upper case alphabetic character or an underline
- There
-always start with arecase
a lower no “types” for variables
alphabetic character
- All
-All prolog atoms Prolog
have variables
a global scopehave a “local” scope
 What is a Query?
• A query is the action of asking the
program about information contained in
its data base (Goal)
• ?- parent(tom,bob).
Yes
• ?- parent(tom,liz).
No
• ?- parent(tom,X).
X=bob
Yes
5
A Family Example
pam tom

bob liz

ann pat

jim

6
 A Family Example
parent(pam,bob).
parent(tom,bob).
parent(tom,liz).
parent(bob,ann).
parent(bob,pat).
parent(pat,jim).

7
 A Family Example
?- parent(bob,pat).
Yes
pam tom

?- parent(liz,pat). bob liz

No

pat
?- parent(X,liz). ann

X = tom
jim

?- parent(X,jim), parent(Y,X).
X=pat, Y=bob

8
 A Family Example
female(pam). grandParent(X,Y) :-
female(liz). parent(X,Z), parent(Z,Y).
female(pat).
female(ann). sister(X,Y) :-
male(tom). parent(Z,X), parent(Z,Y),
male(bob). female(X).
male(jim).

child(X,Y) :- parent(Y,X).

mother(X,Y) :-
parent(X,Y), female(X).

9
 A Family Example

grandParent(tom,pat) grandParent(X,Y) :-
parent(X,Z) , parent(Z,Y)
{X=tom, Y=pat}

parent(tom,Z) , parent(tom,bob)
parent(Z, pat)
{Z=bob}

parent(bob,pat) parent(bob,pat)

[]

10
 Backtracking

grandParent(bob,Who) grandParent(X,Y) :-
parent(X,Z) , parent(Z,Y)
{X=bob, Y=Who}

parent(bob,Z) , parent(bob,ann)
parent(Z, Who)
{Z=ann} Backtrack
parent(ann,Who)

Fail

11
 Backtracking

grandParent(bob,Who) grandParent(X,Y) :-
parent(X,Z) , parent(Z,Y)
{X=bob, Y=Who}

parent(bob,Z) , parent(bob,pat)
parent(bob,ann)
parent(Z, Who)
{Z=pat}

parent(pat,Who) parent(pat,jim)

{Who=jim}

[]

12
 Backtracking

grandParent(Who,jim) grandParent(X,Y) :-
parent(X,Z) , parent(Z,Y)
{X=Who, Y=jim}

parent(pam,bob)
parent(Who,Z) , parent(tom,bob)
parent(bob,pat)
parent(Z, jim) parent(tom,liz)
{Who=bob, Z=pat} parent(bob,ann)

parent(pat,jim) parent(pat,jim)

[]

13
 Recursive Rules
• The predecessor relation
predecessor(X,Y) :- parent(X,Y).
predecessor(X,Y):-:-parent(X,Z)
predecessor(X,Y) parent(X,Z),,
parent(Z,Y).
predecessor(Z,Y).
predecessor(X,Y) :- parent(X,Z1) ,
parent(Z1,Z2),
parent(Z2,Y).

predecessor(X,Y) :- parent(X,Z1) ,
parent(Z1,Z2),
parent(Z2,Z3),
parent(Z3,Y).

14
 Recursive Rules

predecessor(bob,jim) predecessor(X,Y) :- parent(X,Y).

{X=bob, Y=jim}

parent(bob,jim)

Fail

15
 Recursive Rules

predecessor(bob,jim) predecessor(X,Y) :- parent(X,Z)

parent(X,Y).,
predecessor(Z,Y)
{X=bob, Y=jim}

parent(bob,Z) , parent(bob,ann)
predecessor(Z, jim)
{Z=ann}

predecessor(ann,jim) predecessor(X,Y) :- parent(X,Y).

{X=ann, Y=jim}

parent(ann, jim)

Fail

16
 Recursive Rules

predecessor(bob,jim) predecessor(X,Y) :- parent(X,Z) ,

predecessor(Z,Y)
{X=bob, Y=jim}

parent(bob,Z) , parent(bob,ann)
predecessor(Z, jim)
{Z=ann}

predecessor(ann,jim) predecessor(X,Y) :- parent(X,Z)

parent(X,Y).,
predecessor(Z,Y)
{X=ann, Y=jim}

parent(ann, Z) ,
predecessor(Z,jim)

Fail
17
 Recursive Rules

predecessor(bob,jim) predecessor(X,Y) :- parent(X,Z) ,

predecessor(Z,Y)
{X=bob, Y=jim}

parent(bob,Z) , parent(bob,ann)
parent(bob,pat)
predecessor(Z, jim)
{Z=pat}

predecessor(pat,jim) predecessor(X,Y) :- parent(X,Y).

{X=pat, Y=jim}

parent(pat, jim) parent(pat, jim).

[]
18
 More About Variables
• Binding Values
– Different from the variable in imperative language
– The value of logical variable is bound by matching
– When bounded can not change
• Scope
– Limited in a rule
– Variable with the same name in a single rule
represent the same meaning
– However, same variable name in different rules
refer to different meaning

19
 More About Variables
• Anonymous Variables
• An Example
– hasChild(X) :- parent(X,Y).
– What is the role of Y here?
– hasChild(X) :- parent(X,_).

20
Declarative vs Procedural Meaning
• Consider this clause:
• P :- Q, R.
– Declarative Meaning:
• P is true if Q and R are true.
– Procedural Meaning:
• To solve problem P, first solve the subproblem
Q and then the subproblem R
• What is the difference?
– Order

21
 Declarative vs Procedural Meaning
• The main advantage of Prolog is its
declarative approach.
• Unfortunately sometimes it is not sufficient.
• An Example: Declarative Meaning: it is true.

predecessor(X,Y) :- Procedural Meaning: it will never

predecessor(X,Z), find the answer
parent(Z,Y).
predecessor(X,Y) :-
parent(X,Y).

22