COMP313A Programming
Languages
Logic Programming (2)
1
Lecture Outline
• Horn Clauses
• Resolution
• Some Prolog
2
A little bit of Prolog
• Objects and relations between objects
• Facts and rules
parent(pam, bob).
parent(tom, liz).
parent(bob, pat).
parent(tom,bob).
parent(bob, ann).
parent(pat, jim).
? parent(bob, pat).
? parent(bob, liz).
? parent(bob, ben).
? parent(bob, X).
? parent(X, Y).
3
Prolog
grandparent (X,Y) :- parent(X, Z), parent(Z, Y).
For all X and Y
X is the grandparent of Y if
X is a parent of Z and
Z is a parent of Y
sister (X,Y) :- parent(Z, X), parent(Z, Y), female(X)
For all X and Y
X is the sister of Y if
Z is the parent of both X and Y and
X is a female
4
Horn Clauses
• A clause is either a single predicate called a
fact
or
• a rule of the form
condition conclusion
• Conclusion is a single predicate
• Condition is a conjunction of predicates
a1  a2  a3 …  an
parent(X,Z)  parent(Z,Y) grandparent(X,Y)
5
Horn Clauses
• Horn clauses don’t have any quantifiers
• Assumes that the variables in the head
are universally quantified and the
variables in the body are existentially
quantified (if they don’t appear in the
head)
6
Horn Clauses
grandparent(X,Y) parent(X,Z)  parent(Z,Y)
grandparent(X,Y) :- parent(X,Z),parent(Z,Y)
Equivalent to
"x : "y : $z parent(X,Z)  parent(Z,Y) 
grandparent(X,Y)
7
Horn clauses continued
• A fact
mammal(human) 
• A query or goal
 mammal(human)
8
Horn clause example
" x mammal(x)  legs(x,2)  legs(x,4)
mammal(x)  legs(x,2)  legs(x,4)
mammal(x) legs(x, 4) legs(x, 2)
Prolog
legs(x,4) :- mammal(x), not legs(x,2)
legs(x,2) :- mammal(x), not legs(x,4)
9
legs(x,4)  mammal(x)   legs(x,2).
legs(x,2)  mammal(x)   legs(x,4).
mammal(human).
mammal(horse).
 legs(horse, 2).
10
Resolution
• Inference rule for Horn clauses
• Combine left and right hand sides of two
horn clauses
• Cancel those statements which match on
both sides
11
Resolution example
Example 1
Fact:
Query:
mammal(human).
 mammal(human).
Resolution:
 mammal(human).
mammal(human) mammal(human).

12
Resolution example
Example 1
Facts:
Query:
see slide 10
 legs(horse,4).
Resolution:
 legs(horse,4).
legs(horse,4)
 legs(horse,4),
mammal(horse),
 legs(horse, 2).
 mammal(horse),
 legs(horse, 2).
…..
13
• Turn the following sentences into
formulae in first order predicate logic
•
•
•
•
•
•
John likes all kinds of food
Apples are food
Chicken is food
Anything anyone eats and isn’t killed by is food
Bill eats peanuts and is still alive
Sue eats everything Bill eats
• Prove that John likes peanuts using backward
chaining
14
" x : food(x)  likes(John, x)
food(Apples)
food(Chicken)
" x : " x : eats(x,y)   killed_by(x,y)  food(x)
eats(Bill, Peanuts)
alive (Bill)
"x :eats(Bill, x)  eats(Sue,x)
We have no “or”s. Drop the qualifiers to get the
horn clauses
15
1. likes(John, x)  food(x).
2. food(Apples).
3. food(Chicken).
4. food(x)  eats(x,y)   killed_by(x,y).
5. eats(Bill, Peanuts).
6. alive (Bill).
7. eats(Sue,x)  eats(Bill, x).
8. alive(x,y)  killed_by(x,y).
9.  killed_by(x,y)  alive(x,y).
Proves that John likes Peanuts using resolution
16
Horn clause example
• The Euclidian algorithm to compute the
gcd of two positive integers, u and v:
The algorithm
The gcd of u and 0 is u
The gcd of u and v, if v is not 0, is the same
as the gcd of v and the remainder of
dividing v into u.
17
Horn clause example
greatest common divisor
"u gcd(u, 0, u)
" u, " v, " w,
 zero(v)  gcd(v, u mod v, w) gcd(u,v,w)
gcd(u,0,u)
gcd(u,v,w)  zero(v)  gcd(v, u mod v, w)
What is the greatest common denominator of 15, and 10. i.e.
find and instantiation for X in
gcd(15,10,X)
What value of X makes gcd(15,10,X) True
18
COMP313A Programming
Languages
Logic Programming (3)
19
Lecture Outline
• Some Prolog
• Unification
20
Some more prolog
• Recursive rules
example predecessor relation
predecessor(X,Z) :- parent(X,Z).
predecessor(X,Z) :- parent(X,Y), parent(Y,Z)
And so on…
predecessor(X,Z) :- parent(X,Y), predecessor(Y,Z).
21
Some more prolog
parent(pam,bob).
parent(tom,bob).
parent(tom,liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
? predecessor(pam,bob).
? predecessor(pam, ann).
? predecessor(pam, liz).
? predecessor(pam, X).
22
A prolog program comprises clauses - facts,
rules and queries
PROGRAM
big(bear).
big(elephant).
small(cat).
%clause 1
%clause 2
%clause 3
brown(bear).
black(cat).
grey(elephant).
%clause 4
%clause 5
%clause 6
dark(Z) :- black(Z).
dark(Z) :- brown(Z).
%clause 7
%clause 8
?dark(X), big(X).
23
Data Objects
Atoms versus numbers
versus Variables
• Atoms
– strings of letters, digits, and the underscore
character beginning with a lower case letter
– some strings of special characters
– can enclose strings of characters in single
quotes e.g. ‘Fred’
• Numbers
– integers and floats
24
Data Objects
Atoms versus Variables
• Variables are strings of characters, digits and
underscores that begin with an uppercase letter
or an underscore
• Can use the anonymous underscore
hasachild(X) :- parent(X,Y)
hasachild(X) :- parent(X,_)
? parent(X, _)
25
Data Objects
Structured objects
• objects that have several components
location(X, Y, Orientation).
location(156, 786, 25).
location(156, 786, Orientation).
location is the functor
26
Structures
date(X,Y,Z).
date(20, june, 2005).
date(Day, june, 2005).
date(Day, Month, Year) :- Day > 0, Day <= 31,…….
27
data objects
structures
simple objects
constants
atoms
variables
numbers
These are all terms
28
Operations on lists
Membership
• The member relation member(X,L)
? member(d, [a, b, h, d]).
?
? member(d, [a,b,[d h], e]).
?
?member([d, h], [a, [d,h], e f]).
?
29
Membership
• X is a member of L if
– X is the head of L, or
– X is a member of the tail of L.
member(X, [X|Tail]).
member(X, [Head | Tail]) :- member(X,Tail).
Note two separate clauses
30
Membership
• X is a member of L if
– X is the head of L, or
– X is a member of the tail of L, or
– X is a member of a sublist of L
member(X, [X|Tail]).
member(X, [Head | Tail]) :- member(X,Tail).
plus one more clause……
31
Concatenation
• The concatenation relation – conc(L1, L2, L3)
? conc([a,b], [c,d], [a,b,c,d])
yes
? conc([a,b], [c,d], [a, b, [c,d]])
no
?conc([a,b], [c,d], X).
X = [a,b,c,d]
32
Concatentation
• conc(L1, L2, Result)
• If L1 is the empty list
– then L2 and Result must be equal
• If L1 is nonempty
– then have [X|L1tail]
– recursively X becomes the head of Result and
we use conc to find the tail of result
[X|TailResult]
– Eventually will have exhausted L1 and
TailResult will be L2.
33
Concatentation
conc([], L, L).
conc([X | L1], L2, [X | L3]) :- conc(L1, L2, L3).
34
Unification
• Matching clauses with variables
• Have to find the appropriate substitutions
for variables so that the clauses match
• Process is called unification
– Process by which variables are instantiated
35
GCD example
gcd(u,0,u)
gcd(u,v,w) not zero(v), gcd(v, u mod v, w)
Using resolution the goal
 gcd(15, 10, x)
36
Unification in Prolog
• A constant unifies only with itself
? me = me.
Yes
?me = you.
No
Gcd(5, 0, 5)
Gcd(5, 10, w)


Gcd(5, 0, 5)
Gcd(5, 0, w)
37
Unification in Prolog…
• A variable that is uninstantiated unifies with
anything and becomes instantiated with that thing
? me = X.
X = me
? f(a,X) = f(Y, b).
X=b
Y=a
? f(X) = f(Y)
gcd(u,v,w) not zero(v), gcd(v, u mod v, w), gcd(15, 10, x).
gcd(15, 10, x)  not zero(10), gcd(10, 15 mod 10, x), gcd(15,
10, x).
38
Unification in Prolog
• A structured term (predicate or function applied
to arguments requires
– Same predicate/function name
– Same number of arguments
– Arguments can be unified recursively
? f(X) = g(X)
? f(X) = f(a,b)
? f(a, g(X)) = f(Y, b)
? f(a, g(X)) = f(Y, g(b))
39
Unification examples
• Unify the following :
p(X,Y) and p(a, Z)
p(X,X) and p(a,b)
ancestor(X,Y) and ancestor(bill, W)
p(X,a,Y) and p(Z,Z,b)
p(Marcus, g(X,Y)) and f(x, g(Caesar,
Marcus))
g(X, X) and g(f(X), f(X))
40
COMP313A Programming
Languages
Logic Programming (4)
41
Lecture Outline
• Some Prolog
– lists
• Unification
42
Concatentation
conc([], L, L).
conc([X | L1], L2, [X | L3]) :conc(L1, L2, L3).
Can use concat to decompose lists
How?
Can use concat to define the member predicate -
member2(X, L) :- conc(L1, [X|L2], L).
43
Adding and deleting
•
How do you add an item to a list?
•
Deleting an item from a list – del(X, L, Result)
1. If X is the head of L – result is the tail of L
2. If X is contained in the tail of L then recursively
split L into its head and tail until X is at the head.
Then 1 will apply.
44
Deleting…
del(X, [X|Tail], Tail]).
del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1)
Deletes one occurrence from the list
What happens when:
del(a, [a, b, a, a], X).
What if we changed it to
del(X, [X|Tail], Tail]).
del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1), X=\=Y.
45
Delete
• What if we want to delete every instance
from the list
46
del (X, [], []).
del (X, [X|Tail], Tail1) :- del (X, Tail, Tail1).
del (X, [Y|Tail], [Y|Tail1]) :- del (X, Tail, Tail1).
47
Relations/Terms/Queries
An important note
• You can define different relations with the same
name but with different numbers of arguments
• e.g. member/1, member/2, member/3
• If you leave off an argument prolog thinks it is a
different relation
• If it is undefined for that number of arguments
you will get an error message
• And if there is such a relation predefined…….
48
• Define two predicates evenlength(List) and
oddlength(List) so that they are true if their
argument is a list of even or odd length
respectively. For example
? evenlength([a,b,c,d])
? yes
?oddlength([c, d, e])
?yes
The trick is to define them as mutually recursive
clauses. Start with []
49
[] is even
A list is even if its tail is odd
A list is odd if its tail is even
50
evenlength([]).
evenlength([First | Rest]) :- oddlength(Rest).
oddlength([First | Rest]) :- evenlength(Rest).
51
Unification
• Matching clauses with variables
• Have to find the appropriate substitutions
for variables so that the clauses match
• Process is called unification
– Process by which variables are instantiated
52
GCD example
gcd(u,0,u)
gcd(u,v,w) not zero(v), gcd(v, u mod v, w)
Using resolution the goal
 gcd(15, 10, x)
53
Unification in Prolog
• A constant unifies only with itself
? me = me.
Yes
?me = you.
No
Gcd(5, 0, 5)
Gcd(5, 10, w)


Gcd(5, 0, 5)
Gcd(5, 0, w)
54
Unification in Prolog…
• A variable that is uninstantiated unifies with
anything and becomes instantiated with that thing
? me = X.
X = me
? f(a,X) = f(Y, b).
X=b
Y=a
? f(X) = f(Y)
gcd(u,v,w) not zero(v), gcd(v, u mod v, w), gcd(15, 10, x).
gcd(15, 10, x)  not zero(10), gcd(10, 15 mod 10, x), gcd(15,
10, x).
55
Unification in Prolog
• A structured term (predicate or function applied
to arguments requires
– Same predicate/function name
– Same number of arguments
– Arguments can be unified recursively
? f(X) = g(X)
? f(X) = f(a,b)
? f(a, g(X)) = f(Y, b)
? f(a, g(X)) = f(Y, g(b))
56
Unification examples
• Unify the following :
p(X,Y) and p(a, Z)
p(X,X) and p(a,b)
ancestor(X,Y) and ancestor(bill, W)
p(X,a,Y) and p(Z,Z,b)
p(Marcus, g(X,Y)) and f(x, g(Caesar,
Marcus))
g(X, X) and g(f(X), f(X))
57
COMP313A Programming
Languages
Logic Programming (5)
58
Lecture Outline
• Cut operator
• Negation as Failure
• Control Information
59
Backtracking
PROGRAM
big(bear).
big(elephant).
small(cat).
%clause 1
%clause 2
%clause 3
brown(bear).
black(cat).
grey(elephant).
%clause 4
%clause 5
%clause 6
dark(Z) :- black(Z).
dark(Z) :- brown(Z).
%clause 7
%clause 8
?dark(X), big(X).
60
Controlling Backtracking
1
2
3
4
5
6
7
8
9
Knight’s Tour Problem
move(1,8).
move(1,6).
move(2,9).
move(2,7).
move(3,8).
move(3,4).
move(4,3).
move(4,9).
move(6,1).
move(6,7).
move(7,2).
move(7,6).
move(8,1).
move(8,3).
move(9,2).
move(9,4).
61
Controlling Backtracking…
• Find all the two-move paths
path2(X,Y) :- move(X,Z), move(Z,Y).
path2(1,W).
?W=1
?W=3
?W=1
?W=7
62
Controlling Backtracking…
path2(X,Y) :- move(X,Z), !, move(Z,Y).
? path2(1, W).
?W=1
?W=3
! is the cut operator
63
Controlling Backtracking…
path2(X,Y) :- move(X,Z), move(Z,Y),!.
? path2(1, W).
64
Controlling Recursive Calls
predicate path determines if there is a path between two
nodes.
path1(Z,Z,L).
path1(X,Z,L) :- move(X,Y), not (member(Y,L)), path(Y, Z, [Y|L]).
path2((Z,Z,L).
path2(X,Z,L) :- move(X,Y), not (member(Y,L)), path(Y, Z, [Y|L]), ! .
path1(1,3, []).
path2(1,3, []).
65
Negation as Failure
• Closed world assumption
• The goal not (X) succeeds whenever the goal X
fails!
?mother(amy, bob).
?not(parent(amy, bob)).
Why did it fail?
66
Negation as Failure
• Nonmonotonic reasoning – more
information sometimes means fewer
things can be proved
human(bob).
?human(X).
?not human(X).
?not (not human(X)).
X = bob
no
X= X
why?
67
Control Information
• Prolog uses a depth first search strateggy
• Therefore order is important
pred1(X,Z) :- parent(X,Z).
pred1(X,Z) :- parent(X,Y), pred1(Y,Z).
pred2(X,Z) :- pred2(Y,Z), parent(X,Y).
pred2(X,Z) :- parent(X,Z).
68
parent(pam,bob).
parent(tom,bob).
parent(tom,liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
? pred(tom, pat).
69
COMP313A Programming
Languages
Logic Programming (6)
70
Some More Prolog
• structures
71
I/O in Prolog
• Files associated with input and output streams
• I/O from terminal – user
• In some Prologs only two files/streams are active
at any one time
– current input stream
– current output stream
• see switches input streams
• tell switches output streams
• In prolog I/O is a side effect of the predicate
72
Tkeclipse Prolog
• stdin, stdout
– standard input and output streams
?- write("fred").
Yes (0.00s cpu)
• open a stream for input or output
– open(SourceSink, Mode, Stream)
? open('//C/Documents and Settings/mjeff/My
Documents/prolog/fred.txt', read, Fred),
read_string(Fred, "\r\n ", 10, X).
Fred = 31
X = "freddy"
Yes (0.00s cpu)
73
Bits and pieces
• Anonymous variables
family(person(tom, fox, date(7,may, 1950), employed),
person(ann, fox, date(9, may, 1951), employed),
[person(pat, fox, date(5, may, 1973), unemployed),
person(jim, fox, date(5, may, 1973), unemployed)]).
husband(X) :- family(X,Y, Z).
Y and Z are singleton variables
husband(X) :- family(X, _, _)
74
More bits and pieces
• Comparison operators
–
–
–
–
–
–
–
–
X>Y
X<Y
X >= Y
X =< Y
X=Y
X \= Y
X =:= Y
X =\= Y
1+A=B+2
1+A=2+B
1 + 2 =:= 2 + 1 1 + A =:= B + 2
75
Structures
a family database
family(person(tom, fox, date(7,may, 1950), employed),
person(ann, armstrong, date(9, may, 1951), employed),
[person(pat, fox, date(5, may, 1973, unemployed),
person(jim, fox, date(5, may, 1973), unemployed)]).
family(_,_,_).
family(person(_, fox, _, _), _, _).
family(_, person(_,armstrong, _, _), _)
% any family
% the fox
family
% or the armstrong family
family(_, _, [_, _, _]).
% any three child
family
family(_,person(Name, Surname, _, _), [_, _, _, | _]).
% all married women
who have at
least three children
76
husband(X) :- family(X, _, _).
wife(X) :- f amily(_,X,_).
?- husband(X).
X = person(tom, fox, date(7, may, 1950), employed)
Yes (0.00s cpu)
?- wife(X).
X = person(ann, armstrong, date(9, may, 1951), employed)
Yes (0.00s cpu)
Problem – this may be too simplistic
77
husband2(X,Y) :- family(person(X,Y,_,_), _, _).
married(X,Y) :- family(person(X, _, _, _), person(Y,_, _, _),_).
married(X,Y) :- married(Y,X).
child(X) :- family(_, _, Children), member(X, Children).
?? child(X)
??
78
but
?? child(pat)
child(X) :- family(_, _, Children), mem_children (X, Children).
mem_children (X, [person(X, _, _, _) | Tail]).
mem_children (X, [person(Y, _, _, _) | Tail]) :- mem_children1(X, Tail).
79
Selectors
Define relation which allow us to access particular
components of a structure without knowing the details
the structure
This is data abstraction
These selectors are useful when we want to create instances
of families, for example
husband(family(Husband, _, _), Husband).
wife(family(_, Wife, _), Wife).
children(family(_, _, Childlist), Childlist).
80
Selectors…
firstchild(Family, First) :- children(Family, [First | _]).
secondchild(Family, Second) :- children(Family, [_, Second | _]).
nthchild(N, Family, Child) :- children(Family, ChildList),
nth_member(ChildList, N, Child).
firstname(person(Name, _, _,_), Name).
surname(person(_, Surname, _, _), Surname).
81
nth_member([X|_], 1, X).
nth_member([_| L], N, Child) :- N1 is N-1, nth_member(L, N1, Child).
82
Using them..
• Tom Fox and Jim Fox belong to the same
family and Jim is the second child of Tom
firstname(Person1, tom), surname(Person1, fox),
% person1 is Tom Fox
firstname(Person2, jim), surname(Person2, fox),
%person2 is Jim Fox
husband(Family, Person1),
secondchild(Family, Person2).
Person1 = person(tom, fox, _, _)
Person2 = person(jim, fox, _, _)
Family = family(person(tom, fox, _, _), _, [_, person(jim, fox, _,_) | _])
83
Logic Puzzles
• Use the following clues to write a prolog
program to determine the movies the
robots tinman, r2d2, johnny five, and a
dalek starred in.
– Neither Tinman nor Johnny five were one of
the daleks in Dr Who and the Daleks
– The movie Short Circuit did not star Tinman.
– R2d2 wowed the audiences in Star Wars.
– A dalek did not star in the Wizard of Oz.
84
Structure is important
• Solution(L) :We want a binding for L which will
contain the result we are after
• What is the result we want?
85
L = [movie(X1, wizardofoz),
movie(X2, drwhoandtheDaleks),
movie(X3, starwars),
movie(X4, shortcircuit)],
Now we have to supply a mechanism for instantiating X1..X4
We need a way of selecting a value and then checking it against
some constraints
86
L = [movie(X1, wizardofoz),
movie(X2, drwhoandtheDaleks),
movie(X3, starwars),
movie(X4, shortcircuit)],
87
L = [movie(X1, wizardofoz),
movie(X2, drwhoandtheDaleks),
movie(X3, starwars),
movie(X4, shortcircuit)],
Robotslist = [tinman, dalek, r2d2, johnnyfive],
We will draw the values for X1..X2, from Robotslist
We do this using the member predicate
88
L = [movie(X1, wizardofoz),
movie(X2, drwhoandtheDaleks),
movie(X3, starwars),
movie(X4, shortcircuit)],
Robotslist = [tinman, dalek, r2d2, johnnyfive],
89
L = [movie(X1, wizardofoz),
movie(X2, drwhoandtheDaleks),
movie(X3, starwars),
movie(X4, shortcircuit)],
X1
\=
Robotslist = [tinman, dalek, r2d2, johnnyfive],
member(X1, Robotslist),
X1 \= dalek,
member(X2, Robotslist),
X2 \= tinman,
X2 \= johnnyfive,
member(X3, Robotslist),
X3 = r2d2,
member(X4, Robotslist),
X4 \= tinman,
dalek,
There are just two more things left to do
90
solution(L):-
L = [movie(X1, wizardofoz),
movie(X2, drwhoandtheDaleks),
movie(X3, starwars),
movie(X4, shortcircuit)],
Robotslist = [tinman, dalek, r2d2, johnnyfive],
member(X1, Robotslist),
X1 \= dalek,
member(X2, Robotslist),
X2 \= tinman,
X2 \= johnnyfive,
member(X3, Robotslist),
X3 = r2d2,
member(X4, Robotslist),
X4 \= tinman,
X2 \= X1, X2 \= X3, X2 \= X4, X3 \= X1, X3 \= X4, X4 \= X1,
print_movies(L).
91
print_movies([A|B]) :- !,
write(A), nl, print_movies(B).
print_movies([]).
92
Descargar

0657.313A Programming Languages