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