1
Declarative Programming
l Knowledgebases and queries in propositional logic are
made up of propositions and connectives.
l Predicate logic adds the notion of predicates and
variables.
l We take a non-theoretical approach to predicate logic
by introducing declarative programming.
l Declarative programming is the use of mathematical
logic to describe the logic of computation without
describing its control flow.
l Useful for: expert systems, diagnostic systems, machine
learning, parsing text, theorem proving, …
2
Declarative Programming
l Programmer gives a declarative specification of the
problem, using the language of logic.
l The programmer should not have to tell the computer
what to do.
l To get information, the programmer simply asks a
query.
3
Datalog
l Prolog is a declarative (logical) programming language
and stands for PROgramming in LOGic
l We only look at a subset of the language which is
(roughly) equivalent to Datalog.
http://www.learnprolognow.org
http://www.learnprolognow.org/
4
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Basic idea of Datalog/Prolog
• Describe the situation of interest
• Ask a question
• Prolog logically deduces new facts
about the situation we described
• Prolog gives us its deductions back as
answers
5
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Consequences
• Think declaratively, not procedurally
– Challenging
– Requires a different mindset
– Has similarities with other programming
paradigms such as functional programming.
• High-level language
– Not as efficient
– Useful in many AI applications
6
The interpreter
• Prolog has an interactive interpreter
• After starting the interpreter, it can start reading your
Prolog files and answer your queries.
• To exit Prolog simply type the command halt. (note
the full-stop)
• Prolog program files usually have the extension .pl
or .pro
7
Where is the program written?
• Facts and Rules are stored in one or more files
forming our Knowledge Base
• Files containing KB are loaded into the interpreter
• After changing these files, the files should be loaded
again to be effective
• Queries are asked in the interactive mode in front of
the question prompt: ?-
8
Reading Files
• consult (filename).
– Reads and compiles a Prolog source file. Example:
– consult (‘/home/user/prolog/sample.pl’).
• reconsult (filename).
– Reconsult a changed source files. Example
reconsult(‘/home/user/prolog/sample.pl’).
• [‘filename’]. (valid but don’t use it; can be confused with lists!)
[‘/home/user/prolog/sample.pl’].
• make.
– Reconsult all changed source files.
9
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
10
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?-
11
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- woman(mia).
12
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- woman(mia).
yes
?-
13
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- woman(mia).
yes
?- playsAirGuitar(jody).
14
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- woman(mia).
yes
?- playsAirGuitar(jody).
yes
?-
15
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- woman(mia).
yes
?- playsAirGuitar(jody).
yes
?- playsAirGuitar(mia).
no
16
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- tattoed(jody).
17
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- tattoed(jody).
no
?-
18
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- tattoed(jody).
ERROR: predicate tattoed/1 not defined.
?-
19
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- party.
20
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- party.
yes
?-
21
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- rockConcert.
22
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 1
woman(mia).
woman(jody).
woman(yolanda).
playsAirGuitar(jody).
party.
?- rockConcert.
no
?-
23
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 2
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
24
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 2
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
fact
25
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 2
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
fact
fact
26
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 2
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
fact
fact
rule
27
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 2
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
fact
fact
rule
rule
28
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 2
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
fact
fact
rule
rule
rule
29
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 2
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
head body
30
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 2
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
?-
31
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 2
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
?- playsAirGuitar(mia).
yes
?-
32
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 2
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
?- playsAirGuitar(mia).
yes
?- playsAirGuitar(yolanda).
yes
33
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Clauses
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
There are five clauses in this knowledge base:
two facts, and three rules.
The end of a clause is marked with a full stop.
34
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Predicates
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
There are three predicates
in this knowledge base:
happy, listens2music, and playsAirGuitar
35
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 3
happy(vincent).
listens2music(butch).
playsAirGuitar(vincent):- listens2music(vincent), happy(vincent).
playsAirGuitar(butch):- happy(butch).
playsAirGuitar(butch):- listens2music(butch).
36
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Expressing Conjunction
happy(vincent).
listens2music(butch).
playsAirGuitar(vincent):- listens2music(vincent), happy(vincent).
playsAirGuitar(butch):- happy(butch).
playsAirGuitar(butch):- listens2music(butch).
The comma “,” expresses conjunction in Prolog
37
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 3
happy(vincent).
listens2music(butch).
playsAirGuitar(vincent):- listens2music(vincent), happy(vincent).
playsAirGuitar(butch):- happy(butch).
playsAirGuitar(butch):- listens2music(butch).
?- playsAirGuitar(vincent).
no
?-
38
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 3
happy(vincent).
listens2music(butch).
playsAirGuitar(vincent):- listens2music(vincent), happy(vincent).
playsAirGuitar(butch):- happy(butch).
playsAirGuitar(butch):- listens2music(butch).
?- playsAirGuitar(butch).
yes
?-
39
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Expressing Disjunction
happy(vincent).
listens2music(butch).
playsAirGuitar(vincent):- listens2music(vincent), happy(vincent).
playsAirGuitar(butch):- happy(butch).
playsAirGuitar(butch):- listens2music(butch).
happy(vincent).
listens2music(butch).
playsAirGuitar(vincent):- listens2music(vincent), happy(vincent).
playsAirGuitar(butch):- happy(butch); listens2music(butch).
40
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Prolog and Logic
• Clearly Prolog has something to do with
logic
• Operators
– Implication :-
– Conjunction ,
– Disjunction ;
• Use of modus ponens
41
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 4
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
42
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Prolog Variables
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
?- woman(X).
43
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Variable Instantiation
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
?- woman(X).
X=mia
44
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Asking Alternatives
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
?- woman(X).
X=mia;
45
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Asking Alternatives
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
?- woman(X).
X=mia;
X=jody
46
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Asking Alternatives
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
?- woman(X).
X=mia;
X=jody;
X=yolanda
47
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Asking Alternatives
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
?- woman(X).
X=mia;
X=jody;
X=yolanda;
no
48
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 4
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
?- loves(marsellus,X), woman(X).
49
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 4
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
?- loves(marsellus,X), woman(X).
X=mia
?-
50
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 4
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
?- loves(pumpkin,X), woman(X).
51
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 4
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent, mia).
loves(marsellus, mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
?- loves(pumpkin,X), woman(X).
no
?-
52
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 5
loves(vincent,mia).
loves(marsellus,mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
jealous(X,Y):- loves(X,Z), loves(Y,Z).
53
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 5
loves(vincent,mia).
loves(marsellus,mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
jealous(X,Y):- loves(X,Z), loves(Y,Z).
?- jealous(marsellus,W).
54
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Knowledge Base 5
loves(vincent,mia).
loves(marsellus,mia).
loves(pumpkin, honey_bunny).
loves(honey_bunny, pumpkin).
jealous(X,Y):- loves(X,Z), loves(Y,Z).
?- jealous(marsellus,W).
W=vincent
?-
55
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Prolog Syntax
• What exactly are facts, rules and
queries built out of?
Terms
Simple Terms Complex Terms
Constants Variables
Atoms Numbers
Terms
Simple Terms Complex Terms
Constants Variables
Atoms Numbers
56
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Atoms
• A sequence of characters of upper-case letters,
lower-case letters, digits, or underscore, starting
with a lowercase letter
• Examples: butch, big_kahuna_burger, playGuitar
• An arbitrary sequence of characters enclosed in
single quotes
• Examples: ‘Vincent’, ‘Five dollar shake’, ‘@$%’
• A sequence of special characters
• Examples: : , ; . :-
57
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Numbers
• Integers: 12, -34, 22342
• Floats: 34573.3234
58
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Variables
• A sequence of characters of upper-case
letters, lower-case letters, digits, or
underscore, starting with either an
uppercase letter or an underscore
• Examples:
X, Y, Variable, Vincent, _tag
59
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Complex Terms
• Atoms, numbers and variables are
building blocks for complex terms
• Complex terms are built out of a functor
directly followed by a sequence of
arguments
• Arguments are put in round brackets,
separated by commas
• The functor must be an atom
60
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Examples of complex terms
• Examples we have seen before:
– playsAirGuitar(jody)
– loves(vincent, mia)
– jealous(marsellus, W)
• Complex terms inside complex terms:
– hide(X,father(father(father(butch))))
61
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Arity
• The number of arguments a complex
term has is called its arity
• Examples:
woman(mia) is a term with arity 1
loves(vincent,mia) has arity 2
father(father(butch)) arity 1
62
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Arity is important
• In Prolog you can define two predicates
with the same functor but with different
arity
• Prolog would treat this as two different
predicates
• In Prolog documentation arity of a
predicate is usually indicated with the
suffix “/” followed by a number to
indicate the arity
63
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example of Arity
• This knowledge base defines
– happy/1
– listens2music/1
– playsAirGuitar/1
happy(yolanda).
listens2music(mia).
listens2music(yolanda):- happy(yolanda).
playsAirGuitar(mia):- listens2music(mia).
playsAirGuitar(yolanda):- listens2music(yolanda).
64
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Unification
• Working definition:
• Two terms unify if they are the same term or if
they contain variables that can be uniformly
instantiated with terms in such a way that the
resulting terms are equal.
65
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Unification
• This means that:
• mia and mia unify
• 42 and 42 unify
• woman(mia) and woman(mia) unify
• This also means that:
• vincent and mia do not unify
• woman(mia) and woman(jody) do not unify
66
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Unification
• What about the terms:
• mia and X
67
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Unification
• What about the terms:
• mia and X
• woman(Z) and woman(mia)
68
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Unification
• What about the terms:
• mia and X
• woman(Z) and woman(mia)
• loves(mia,X) and loves(X,vincent)
69
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Instantiations
• When Prolog unifies two terms it
performs all the necessary
instantiations, so that the terms are
equal afterwards
• This makes unification a powerful
programming mechanism
70
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Revised Definition 1/3
1. If T1 and T2 are constants, then
T1 and T2 unify if they are the same atom, or
the same number.
71
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Revised Definition 2/3
1. If T1 and T2 are constants, then
T1 and T2 unify if they are the same atom, or
the same number.
2. If T1 is a variable and T2 is any type of term,
then T1 and T2 unify, and T1 is instantiated to
T2. (and vice versa)
72
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Revised Definition 3/3
1. If T1 and T2 are constants, then
T1 and T2 unify if they are the same atom, or
the same number.
2. If T1 is a variable and T2 is any type of term,
then T1 and T2 unify, and T1 is instantiated to
T2. (and vice versa)
3. If T1 and T2 are complex terms then they
unify if:
1. They have the same functor and arity, and
2. all their corresponding arguments unify, and
3. the variable instantiations are compatible.
73
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Prolog unification: =/2
?- mia = mia.
yes
?-
74
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Prolog unification: =/2
?- mia = mia.
yes
?- mia = vincent.
no
?-
75
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Prolog unification: =/2
?- mia = X.
X=mia
yes
?-
76
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
How will Prolog respond?
?- X=mia, X=vincent.
77
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
How will Prolog respond?
?- X=mia, X=vincent.
no
?-
Why? After working through the first goal,
Prolog has instantiated X with mia, so
that it cannot unify it with vincent
anymore. Hence the second goal fails.
78
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example with complex terms
?- k(s(g),Y) = k(X,t(k)).
79
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example with complex terms
?- k(s(g),Y) = k(X,t(k)).
X=s(g)
Y=t(k)
yes
?-
80
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example with complex terms
?- k(s(g),t(k)) = k(X,t(Y)).
81
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example with complex terms
?- k(s(g),t(k)) = k(X,t(Y)).
X=s(g)
Y=k
yes
?-
82
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
One last example
?- loves(X,X) = loves(marsellus,mia).
83
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Programming with Unification
vertical( line(point(X,Y),
point(X,Z))).
horizontal( line(point(X,Y),
point(Z,Y))).
84
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Programming with Unification
vertical( line(point(X,Y),
point(X,Z))).
horizontal( line(point(X,Y),
point(Z,Y))).
?-
85
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Programming with Unification
vertical( line(point(X,Y),
point(X,Z))).
horizontal( line(point(X,Y),
point(Z,Y))).
?- vertical(line(point(1,1),point(1,3))).
yes
?-
86
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Programming with Unification
vertical( line(point(X,Y),
point(X,Z))).
horizontal( line(point(X,Y),
point(Z,Y))).
?- vertical(line(point(1,1),point(1,3))).
yes
?- vertical(line(point(1,1),point(3,2))).
no
?-
87
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Programming with Unification
vertical( line(point(X,Y),
point(X,Z))).
horizontal( line(point(X,Y),
point(Z,Y))).
?- horizontal(line(point(1,1),point(1,Y))).
Y = 1;
no
?-
88
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Programming with Unification
vertical( line(point(X,Y),
point(X,Z))).
horizontal( line(point(X,Y),
point(Z,Y))).
?- horizontal(line(point(2,3),Point)).
Point = point(_554,3);
no
?-
89
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Proof Search
• Now that we know about unification, we are in a
position to learn how Prolog searches a knowledge
base to see if a query is satisfied.
• In other words: we are ready to learn about proof
search
• Prolog has a specific way of answering queries:
Ø Search knowledge base from top to bottom
Ø Processes clauses from left to right
Ø Backtracking to recover from bad choices
90
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example
f(a).
f(b).
g(a).
g(b).
h(b).
k(X):- f(X), g(X), h(X).
?- k(Y).
91
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: search tree
f(a).
f(b).
g(a).
g(b).
h(b).
k(X):- f(X), g(X), h(X).
?- k(Y).
?- k(Y).
92
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: search tree
f(a).
f(b).
g(a).
g(b).
h(b).
k(X):- f(X), g(X), h(X).
?- k(Y).
?- k(Y).
?- f(X), g(X), h(X).
Y=X
93
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: search tree
f(a).
f(b).
g(a).
g(b).
h(b).
k(X):- f(X), g(X), h(X).
?- k(Y).
?- k(Y).
?- f(X), g(X), h(X).
?- g(a), h(a).
X=a
Y=X
94
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: search tree
f(a).
f(b).
g(a).
g(b).
h(b).
k(X):- f(X), g(X), h(X).
?- k(Y).
?- k(Y).
?- f(X), g(X), h(X).
?- g(a), h(a).
?- h(a).
X=a
Y=X
95
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: search tree
f(a).
f(b).
g(a).
g(b).
h(b).
k(X):- f(X), g(X), h(X).
?- k(Y).
?- k(Y).
?- f(X), g(X), h(X).
?- g(a), h(a).
?- h(a).
X=a
†
Y=X
96
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: search tree
f(a).
f(b).
g(a).
g(b).
h(b).
k(X):- f(X), g(X), h(X).
?- k(Y).
?- k(Y).
?- f(X), g(X), h(X).
?- g(a), h(a).
?- h(a).
X=a
?- g(b), h(b).
X=b
†
Y=X
97
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: search tree
f(a).
f(b).
g(a).
g(b).
h(b).
k(X):- f(X), g(X), h(X).
?- k(Y).
?- k(Y).
?- f(X), g(X), h(X).
?- g(a), h(a).
?- h(a).
X=a
?- g(b), h(b).
X=b
?- h(b).
†
Y=X
98
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: search tree
f(a).
f(b).
g(a).
g(b).
h(b).
k(X):- f(X), g(X), h(X).
?- k(Y).
Y=b
?- k(Y).
?- f(X), g(X), h(X).
?- g(a), h(a).
?- h(a).
X=a
?- g(b), h(b).
X=b
?- h(b).
†
Y=X
99
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: search tree
f(a).
f(b).
g(a).
g(b).
h(b).
k(X):- f(X), g(X), h(X).
?- k(Y).
Y=b;
no
?-
?- k(Y).
?- f(X), g(X), h(X).
?- g(a), h(a).
?- h(a).
X=a
?- g(b), h(b).
X=b
?- h(b).
†
Y=X
100
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another example
loves(vincent,mia).
loves(marsellus,mia).
jealous(A,B):-
loves(A,C),
loves(B,C).
?- jealous(X,Y).
101
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another example
loves(vincent,mia).
loves(marsellus,mia).
jealous(A,B):-
loves(A,C),
loves(B,C).
?- jealous(X,Y).
?- jealous(X,Y).
102
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another example
loves(vincent,mia).
loves(marsellus,mia).
jealous(A,B):-
loves(A,C),
loves(B,C).
?- jealous(X,Y).
?- jealous(X,Y).
?- loves(A,C), loves(B,C).
X=A Y=B
103
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another example
loves(vincent,mia).
loves(marsellus,mia).
jealous(A,B):-
loves(A,C),
loves(B,C).
?- jealous(X,Y).
?- jealous(X,Y).
?- loves(A,C), loves(B,C).
?- loves(B,mia).
A=vincent
C=mia
X=A Y=B
104
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another example
loves(vincent,mia).
loves(marsellus,mia).
jealous(A,B):-
loves(A,C),
loves(B,C).
?- jealous(X,Y).
X=vincent
Y=vincent
?- jealous(X,Y).
?- loves(A,C), loves(B,C).
?- loves(B,mia).
A=vincent
C=mia
B=vincent
X=A Y=B
105
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another example
loves(vincent,mia).
loves(marsellus,mia).
jealous(A,B):-
loves(A,C),
loves(B,C).
?- jealous(X,Y).
X=vincent
Y=vincent;
X=vincent
Y=marsellus
?- jealous(X,Y).
?- loves(A,C), loves(B,C).
?- loves(B,mia).
A=vincent
C=mia
B=vincent
B=marsellus
X=A Y=B
106
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another example
loves(vincent,mia).
loves(marsellus,mia).
jealous(A,B):-
loves(A,C),
loves(B,C).
?- jealous(X,Y).
X=vincent
Y=vincent;
X=vincent
Y=marsellus;
?- jealous(X,Y).
?- loves(A,C), loves(B,C).
?- loves(B,mia).
A=vincent
C=mia
?- loves(B,mia).
A=marsellus
C=mia
B=vincent
B=marsellus
X=A Y=B
107
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another example
loves(vincent,mia).
loves(marsellus,mia).
jealous(A,B):-
loves(A,C),
loves(B,C).
….
X=vincent
Y=marsellus;
X=marsellus
Y=vincent
?- jealous(X,Y).
?- loves(A,C), loves(B,C).
?- loves(B,mia).
A=vincent
C=mia
?- loves(B,mia).
A=marsellus
C=mia
B=vincent B=vincent
B=marsellus
X=A Y=B
108
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another example
loves(vincent,mia).
loves(marsellus,mia).
jealous(A,B):-
loves(A,C),
loves(B,C).
….
X=marsellus
Y=vincent;
X=marsellus
Y=marsellus
?- jealous(X,Y).
?- loves(A,C), loves(B,C).
?- loves(B,mia).
A=vincent
C=mia
?- loves(B,mia).
A=marsellus
C=mia
B=vincent B=vincent
B=marsellus B=marsellus
X=A Y=B
109
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another example
loves(vincent,mia).
loves(marsellus,mia).
jealous(A,B):-
loves(A,C),
loves(B,C).
….
X=marsellus
Y=vincent;
X=marsellus
Y=marsellus;
no
?- jealous(X,Y).
?- loves(A,C), loves(B,C).
?- loves(B,mia).
A=vincent
C=mia
?- loves(B,mia).
A=marsellus
C=mia
B=vincent B=vincent
B=marsellus B=marsellus
X=A Y=B
110
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Recursive Definitions
• Prolog predicates can be defined
recursively
• A predicate is recursively defined if one
or more rules in its definition refers to
itself
111
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: Descendant
child(anna,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y):- child(X,Y).
descend(X,Y):- child(X,Z), descend(Z,Y).
?-
112
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: Descendant
child(anna,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y):- child(X,Y).
descend(X,Y):- child(X,Z), descend(Z,Y).
?- descend(anna,donna).
yes
113
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another recursive definition
p:- p.
?- p.
114
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another recursive definition
p:- p.
?- p.
ERROR: out of memory
115
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: Successor
• Suppose we use the following way to
write numerals:
1. 0 is a numeral.
2. If X is a numeral, then so is succ(X).
116
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: Successor
numeral(0).
numeral(succ(X)):- numeral(X).
117
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: Successor
numeral(0).
numeral(succ(X)):- numeral(X).
?- numeral(succ(succ(succ(0)))).
yes
?-
118
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: Successor
numeral(0).
numeral(succ(X)):- numeral(X).
?- numeral(X).
119
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: Successor
numeral(0).
numeral(succ(X)):- numeral(X).
?- numeral(X).
X=0;
X=succ(0);
X=succ(succ(0));
X=succ(succ(succ(0)));
X=succ(succ(succ(succ(0))))
120
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: Addition
?- add(succ(succ(0)),succ(succ(succ(0))), Result).
Result=succ(succ(succ(succ(succ(0)))))
yes
121
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: Addition
add(0,X,X). %%% base clause
?- add(succ(succ(0)),succ(succ(succ(0))), Result).
Result=succ(succ(succ(succ(succ(0)))))
yes
122
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: Addition
add(0,X,X). %%% base clause
add(succ(X),Y,succ(Z)):- %%% recursive clause
add(X,Y,Z).
?- add(succ(succ(0)),succ(succ(succ(0))), Result).
Result=succ(succ(succ(succ(succ(0)))))
yes
123
Examples from the book
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
124
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
descend1.pl
child(anna,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y):- child(X,Y).
descend(X,Y):- child(X,Z), descend(Z,Y).
?- descend(A,B).
A=anna
B=bridget
125
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
descend2.pl
child(anna,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y):- child(X,Z), descend(Z,Y).
descend(X,Y):- child(X,Y).
?- descend(A,B).
A=anna
B=emily
126
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
descend3.pl
child(anna,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y):- descend(Z,Y), child(X,Z).
descend(X,Y):- child(X,Y).
?- descend(A,B).
ERROR: OUT OF LOCAL STACK
127
©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
descend4.pl
child(anna,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y):- child(X,Y).
descend(X,Y):- descend(Z,Y), child(X,Z).
?- descend(A,B).
128
Using dif predicate
mother(X, Y) :- parent(X, Y), female(X).
sister(X, Y) :-
parent(Z, X),
parent(Z, Y),
female(X).
• What is wrong with this rule?
– Any female is her own sister
• Solution?
– Use dif (\=) predicate: …, X \= Y.
129
Comments
• Multi-line :
/* This is a comment
This is another comment */
• Short :
% This is also a comment
130
Notation of Predicate Descriptions
+ Argument must be fully instantiated.
Think of the argument as input.
– Argument must be unbound.
Think of the argument as output.
? Either instantiated or unbound
Think of the argument as either input or output
Examples:
Write a predicate sum(+List, ?Sum) so that …
Write a predicate append(?List1, ?List2, ?List1AndList2)
such that …
131
Side effects
• Some built-in “Predicates” may have side
effects.
• Example: The built-in predicate write(+Term)
print_if_positive(X) :- X > 0, write(X).
132
Logical quantification
• Variables that appear in the head of a rule are universally
quantified.
• Variables that only appear in the body of a rule are
existentially quantified.
path(X,Y) :- edge(X,Z), path(Z,Y).
For all nodes X and Y, there is a path from X to Y if there exists
a node Z such that there is an edge from X to Z and there
is path from Z to Y.