CS计算机代考程序代写 prolog AI interpreter 1

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.