Prolog - Part 1

Agile Software Development Lab 2008Dr. Günter Kniesel, Daniel Speicher, Tobias Rho, Pascal Bihler

Spring 2008 R O O T S

Prolog - Part 1

Alexis RaptarchisPatrick Rypalla

raptarch@cs.uni-bonn.derypalla@cs.uni-bonn.de

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 2

Table of Contents

1. Facts, Rules and Queriesa. Prolog examplesb. Prolog Syntaxc. Exercise 1

2. Matchinga. Proof Searchb. Exercise 2

3. Recursiona. Exercise 3

4. List5. Arithmetic6. Cuts and Negation7. Meta-Predicates

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 3

Facts, Rules, and Queries

There are only three basic constructs in Prolog: facts, rules, and queries Collection of facts and rules is called a knowledge base (KB) Queries are questions about the information stored in the KB

Facts are used to state things that are unconditionally true of the domain of interest

We can ask Prolog whether Mia is a woman by posing a query

If we ask whether Jody is a woman Prolog will answer no, because Jody is not known to the KB

woman(mia).

?- woman(mia).

fact

query

Prolog will answer:

yes

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 4

Facts, Rules, and Queries

Rules state information that is conditionally true of the domain of interest

playsAirGuitar(mia) :- listens2Music(mia).

The rule says that Mia plays air guitar if she listens to music :- should be read as ``if'', or ``is implied by'‘ In general rules say: if the body of the rule is true, then the head of the rule is true too

The body can contain more then one fact, for example:

playsAirGuitar(mia):- listens2music(mia), happy(mia).

head body

rule

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 5

Facts, Rules, and Queries

Lets add a fact to our KB, namely

listens2Music(mia).playsAirGuitar(mia) :- listens2Music(mia).

We will ask Prolog whether Mia plays air guitar

?- playsAirGuitar(mia).

Remember playsAirGuitar(mia) Is not a fact in our KB

But Prolog will respond yes! Hence Prolog can use so called modus ponens to deduce facts from the KB

This new fact is not explicitly recorded in the knowledge base. It is only implicitly present

factrule

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 6

Facts, Rules, and Queries

man(vincent).

woman(mia).woman(jody).

woman(yolanda).

?- woman(X).

X = mia

?- ;

X = jody;

X = yolanda;

no

• Prolog answers this query by working from top to bottom through the KB, trying to match the expression woman(X) with the information KB contains.

• Prolog instantiates X to mia, or that it binds X to mia

• ; means or, so this query means: are there any more women?

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 7

Facts, Rules, and Queries

happy(yolanda).listens2music(mia).listens2music(yolanda):- happy(yolanda).playsAirGuitar(mia):- listens2music(mia),happy(mia).playsAirGuitar(yolanda):- listens2music(yolanda).

?- playsAirGuitar(mia).

no

?- playsAirGuitar(yolanda).

yes

The facts and rules contained in a KB

are called clauses.

In this case the KB contains 5 clauses, namely 2 facts and

3 rules

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 8

Facts, Rules, and Queries

woman(mia).

woman(jody).loves(vincent, mia).

loves(marsellus, mia).loves(pumpkin, honey_bunny).loves(honey_bunny, pumpkin).

jealous(X,Y):- loves(X,Z), loves(Y,Z).

?- loves(pumpkin,X), woman(X).

no

loves(marcellus,X),woman(X).

X = mia

?- jealous(marsellus,W).

W = vincent

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 9

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

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 10

Prolog Syntax: Atoms and Variables

Atoms are sequence of characters of upper-case letters, lower-case letters, digits, or underscore, starting with a lowercase letter• Examples: butch, mia, playGuitar

An arbitrary sequence of characters enclosed in single quotes• Examples: 'Vincent', 'Five dollar shake', '@$%'

A sequence of special characters• Examples: : , ; . :-

Variables Same as Atoms, just starting with either an uppercase letter or an underscore

Examples: X, Y, Variable, Vincent, _tag

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 11

Prolog Syntax: Complex Terms

Operators Implication :- Conjunction , Disjunction ;

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

Examples we have seen before: playsAirGuitar(jody) loves(vincent, mia) jealous(marsellus, W)

argumentfunctor

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 12

Prolog Syntax: Arity

Complex terms inside complex terms: hide(X,father(father(father(butch))))

Functor is hide and it has two arguments: X and the complex term father(father(father(butch)))

The number of arguments a complex term has is called its arity Examples:

woman(mia) /1 is a term with arity 1 loves(vincent,mia) /2 has arity 2 father(father(butch)) /1 arity 1

In Prolog documentation arity of a predicate is usually indicated with the suffix "/" followed by a number to indicate the arity

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 13

Exercise 1

Which of the following sequences of characters are atoms and which are variables? vINCENT Footmassage variable23 big_kahuna_burger 'big kahuna burger' Jules ‘@Jules‘

How many facts, rules and clausesare there in the following knowledge base? What are the heads of the rules, and what are the goals they contain?woman(vincent).woman(mia).man(jules).person(X) :- man(X); woman(X).loves(X,Y) :- knows(Y,X).father(Y,Z) :- man(Y), son(Z,Y).father(Y,Z) :- man(Y), daughter(Z,Y).

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 14

Exercise 1 - Solution

Which of the following sequences of characters are atoms and which are variables? vINCENT atom Footmassage variable Variable23 atom big_kahuna_burger atom 'big kahuna burger‘ atom Jules variable ‘@Jules‘ atom

How many facts, rules and clauses are there in the following knowledge base? What are the heads of the rules, and what are the goals they contain?woman(vincent).woman(mia).man(jules).person(X) :- man(X); woman(X).loves(X,Y) :- knows(Y,X).father(Y,Z) :- man(Y), son(Z,Y).father(Y,Z) :- man(Y), daughter(Z,Y).

3 facts

4 rules

7 clauses

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 15

Matching

Two terms match, if they are equal or if they contain variables that can be instantiated in such a way that the resulting terms are equal

Exampels:

=(mia,mia) match, because they are the same atom woman(mia) = woman(mia) match, because they are the same complex term mia = X match, because X can be instantiated to mia

How about loves(vincent, X) and loves(X, mia)?

no match, because its impossible to find an instantiation of X

And does kill(shoot(gun), stab(knife)) = kill (X, stab(Y)) match?

X = shoot(gun) Y = knife

yes

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 16

Matching

Definition of Matching

1. If term1 and term2 are constants, then term1 and term2 match if and only if they are the same atom, or the same number.

2. If term1 is a variable and term2 is any type of term, then term1 and term2 match, and term1 is instantiated to term2.

3. If term1 and term2 are complex terms, then they match if and only if: They have the same functor and arity. All their corresponding arguments match and the variable instantiations are compatible. (I.e. it is not possible to instantiate

variable X to mia, when matching one pair of arguments, and to then instantiate X to vincent, when matching another pair of arguments.)

4. Two terms match if and only if it follows from the previous three clauses that they match.

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 17

Matching - occurs check

Consider the following query: father(X) = X.

Let`s try and instantiate X to father(father(butch)):father(father(father(butch))) = father(father(butch))

Prolog is desperately trying to match these terms, but it won't succeed.X = father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(father(….

newer versions of Prolog can detect cycles in termsX = father(father(father(father(father(father(...))))))))))yes

Now we know about matching Next: we will learn how Prolog actually searches a KB to see if a query is satisfied

Proof search

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 18

Proof Search

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).

?- g(b), h(b).

X=b

?- h(b).

†

Y=X

?- g(a), h(a).

X=a

?- h(a).

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 19

Proof Search

loves(vincent,mia).loves(marsellus,mia).

jealous(A,B):- loves(A,C), loves(B,C).

?- jealous(X,Y).

X=marsellus

Y=vincent;

X=vincent

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

X = vincent

Y = vincent;

X = vincent

Y = marsellus;

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 20

Exercise 2

Which of the following pairs of terms match? Give the variable instantiations that lead to successful matching.

food(bread,X,beer) = food(Y,sausage,X) food(bread,X,beer) = food(Y,kahuna_burger) meal(food(bread),drink(beer)) = meal(X,Y) ?- loves(X,X) = loves(marsellus,mia). ?- k(s(g),Y) = k(X,t(k)). ?- k(s(g),t(k)) = k(X,t(Y)).

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 21

Exercise 2 - Solution

food(bread,X,beer) = food(Y,sausage,X)

noX = beer and X = sausage

food(bread,X,beer) = food(Y,kahuna_burger)

noBecause we have 3 arguments on the left side but only 2 on the right

meal(food(bread),drink(beer)) = meal(X,Y)

X = food(bread)Y = drink(beer)Yes

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 22

Exercise 2 - Solution

?- loves(X,X) = loves(marsellus,mia).

noX = marsellus and X = mia

?- k(s(g),Y) = k(X,t(k)).

X=s(g)Y=t(k)yes

?- k(s(g),t(k)) = k(X,t(Y)).

X=s(g)Y=kyes

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 23

Recursion

Prolog predicates can be defined recursively A predicate is recursively defined if one or more rules in its definition refers to

itself

Let’s take a look on two rules:

descend(X,Y):- child(X,Y).descend(X,Y):- child(X,Z), descend(Z,Y).

What does this say? 1. if Y is a child of X, then Y is a descendant of X2. if Z is a child of X, and Y is a descendant of Z, then Y is a descendant of X

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 24

Recursion - descend

child(martha, charlotte).child(charlotte, caroline).   child(caroline, laura).   child(laura, rose).

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

child(X,Z),descend(Z,Y).

?- descend(martha, laura)

yes

child(martha,laura)

descend(martha,laura)

child (martha,Y)

descend(Y,laura)

descend(charlotte,laura)

†

child(charlotte,laura)

†child (charlotte,Y)

descend(Y,laura)

descend(charlotte,laura)

child(charlotte,laura)

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 25

Recursion - 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).

That is, succ(X) represents the number obtained by adding one to the number represented by X

It simply says that 0 is a numeral, and that all other numerals are built by stacking succ symbols in front.

numeral(0).numeral(succ(X)) :- numeral(X).

Exercise:What will happen if you ask:

?- numeral(X)

X = 0 ;

X = succ(0) ; X = succ(succ(0)) ; X = succ(succ(succ(0))) ; X = succ(succ(succ(succ(0)))) ; X = succ(succ(succ(succ(succ(0))))) ; X = succ(succ(succ(succ(succ(succ(0)))))) ;  

Agile Software Development Lab Spring 2008 R O O T S

Vortragstitel (in „Ansicht -> Master änderbar) 26

Exercise 3

child(ron, hermione).child(hermione, draco).child(draco, harry).   

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

child(X,Z),descend(Z,Y).

?- descend(ron, harry)

child(ron,harry)

descend(ron,harry)

child (ron,Y)

descend(Y,harry)

descend(hermione,harry)

†

child(hermione,harry)

†child (hermione,Y)

descend(Y,harry)

descend(draco,harry)

child(draco,harry)