Announcements. The current topic: Prolog. Using not for inequality. Using not instead of cut to avoid wrong answers. Term Test 2 has been marked.

Please download to get full document.

View again

of 9
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

News & Politics

Published:

Views: 0 | Pages: 9

Extension: PDF | Download: 0

Share
Related documents
Description
The current topic: Prolog! Introduction! Object-oriented programming: Python! Functional programming: Scheme! Python GUI programming (Tkinter)! Types and values Logic programming: Prolog! Introduction!
Transcript
The current topic: Prolog! Introduction! Object-oriented programming: Python! Functional programming: Scheme! Python GUI programming (Tkinter)! Types and values Logic programming: Prolog! Introduction! Rules, unification, resolution, backtracking, lists.! More lists, math, structures.! More structures, trees, cut. Next up: Negation. Syntax and semantics Exceptions Term Test 2 has been marked. Announcements Handed back at the end of class today. The deadline for submitting a re-mark request is the end of class, Friday vember 28th. Make sure you understand the posted solutions before submitting a re-mark request. Average: 68.4% 1 2 Using not instead of cut to avoid wrong answers Using not for inequality Prolog has a not operator, but its behaviour is more subtle than in other languages. Example: Replacing a cut with not: With cut: A :- B,!, C. A :- D. With not: A :- B, C. A :- not(b), D. Observe that not can be more cumbersome than cut. repetitive if-then-else Example: crispy(snap). crispy(crackle). crispy(pop). breakfast(a,b,c) :- crispy(a), crispy(b), crispy(c).?- breakfast(a,b,c). A = snap B = snap C = snap ; A = snap B = snap C = crackle ;... But we really want A, B, and C to be different from each other. 3 4 crispy(snap). crispy(crackle). crispy(pop). Using not for inequality breakfast(a,b,c) :- crispy(a), crispy(b), crispy(c), not(a=b), not(a=c), not(b=c).?- breakfast(a,b,c). A = snap B = crackle C = pop ; A = snap B = pop C = crackle ;... Negation in Prolog not(b) can also be written as \+ B. And not(x=y) can also be written as X \= Y. The goal \+ X succeeds iff X s. Examples:?- \+ member(b, [a,b,c]).?- \+ member(x, [a,b,c]).?- \+ member(x, [a,b,c]). 5 6 Negation in Prolog Negation as ure?- \+ member(x, [a,b,c]). It might look like this query is asking Does there exist an X for which member(x, [a,b,c]) does not succeed? . We know there are lots of values of X for which member(x, [a,b,c]) does not succeed. But that's not what negation means in Prolog. There exists X for which member(x, [a,b,c]) succeeds. So then \+ member(x, [a,b,c]) s. Prolog assumes that if it can't prove an assertion, then the assertion is false. And Prolog assumes that if it can prove an assertion, then the assertion is true. This is the closed world assumption : in the universe of facts Prolog knows about, ure to prove is proof of ure. But if we know something Prolog doesn't, this can lead to surprises: things that Prolog thinks are false when we know they're true, and the opposite. Example: university(uoft).?- university(york).?- \+ university(york). 7 8 Be careful with negation Tracing negation sad(x) :- \+ happy(x). happy(x) :- beautiful(x), rich(x). rich(bill). beautiful(michael). rich(michael). beautiful(cinderella).?- sad(bill).?- sad(cinderella).?- sad(michael).?- sad(jim).?- sad(someone). Isn't anyone sad?, that just means that it's not true we can't find anyone happy. In other words, there exists someone who is happy. Let's look at how Prolog answers sad(someone).:?- sad(someone). Call: (7) sad(_g283)? creep Call: (8) happy(_g283)? creep Call: (9) beautiful(_g283)? creep Exit: (9) beautiful(michael)? creep Call: (9) rich(michael)? creep Exit: (9) rich(michael)? creep Exit: (8) happy(michael)? creep Fail: (7) sad(_g283)? creep 9 10 Set overlap What does that mean? Write a predicate overlap(s1, S2) that succeeds if lists S1 and S2 have a common element. Then write a predicate disjoint(s1, S2) that succeeds if S1 and S2 have no common element. overlap(s1, S2) :- member(x, S1), member(x, S2). disjoint(s1, S2) :- \+ overlap(s1, S2).?- overlap([a,b,c], [c,d,e]).?- disjoint([a,b,c], [c,d,e]).?- overlap([a,b,c], [d,e,f]).?- disjoint([a,b,c], [d,e,f]).?- disjoint([a,b,d], S).?- disjoint([a,b,d], S). The query should mean can you find a list S that is disjoint from the list [a,b,d] (and if so what is it)? . Obviously there are many such sets, so why ? Answer: because Prolog succeeded in finding a set that did overlap with S, so it announced ure of the original query.?- overlap([a,b,d], S). S = [a _G226] ; S = [_G225, a _G229] ; S = [_G225, _G228, a _G232] ; The goal not(g) is safe if either: Safe use of negation G is fully instantiated when not(g) is processed, or G has uninstantiated variables, but they don't appear anywhere else in the clause. Safe example: childlessman(x) :- male(x), \+ parent(x,y). X is instantiated in male(x), and Y isn't used elsewhere. Unsafe example: childlessman(x) :- \+ parent(x,y), male(x). X is not instantiated before the negation, and is used elsewhere. If necessary, add a precondition to warn the programmer. recall that +Var means that Var must be instantiated. % disjoint(+s1, +S2) succeeds if... disjoint(s1, S2) :- \+ overlap(s1, S2). When the precondition is satisfied, this negation is safe. Double-negation doesn't cancel out In other languages, not(not( expression )) is equivalent to expression . But not in Prolog.?- member(x,[a,b,c]). X = a ; X = b ; X = c ;?- not(not(member(x,[a,b,c]))). X = _G166 ; Double-negation doesn't cancel out ?- not(not(member(x,[a,b,c]))). X = _G166 ; Why is X uninstantiated in this example? Since member(x, [a,b,c]) succeeds (by instantiating X to, say, a), not(member(x, [a,b,c])) s. When a goal s, the variables it instantiated get uninstantiated. So X gets uninstantiated. But since not(member(x, [a,b,c])) s, not(not(member(x, [a,b,c]))) succeeds. The predicate s immediately. Example: p(x) :-.?- p(csc326). We can use to state that something is false Example: We want to represent Colbert does not like bears (regardless of whatever else he likes). One solution: Add not(bear(x)) to every rule describing what Colbert likes. For example: likes(colbert, X) :- animal(x), not(bear(x)). likes(colbert, X) :- toy(x), not(bear(x)). likes(colbert, X) :- livesinarctic(x), not(bear(x)).... Let's try to use instead. First attempt: bear(yogi). animal(yogi). likes(colbert, X) :- bear(x),. likes(colbert, X) :- animal(x).?- likes(colbert, yogi). We need to add a cut to prevent other rules from being tried after the first rule reaches. Second attempt: bear(yogi). cat(tom). animal(yogi). animal(tom). likes(colbert, X) :- bear(x),!,. likes(colbert, X) :- animal(x).?- likes(colbert, yogi).?- likes(colbert, tom).?- likes(colbert, X). Downside: This solution only works when X is instantiated Defining not using cut and Another example: Define a predicate different(x, Y) that succeeds if X and Y don't unify. different(x, Y) :- X=Y,!,. different(_, _).?- different(a, b).?- different(a, a). We can define the not predicate as follows: not(x) :- X,!,. not(_). (To test this out, use a name other than not , since Prolog won't let you redefine the built-in not ). tice that the above definition is equivalent to: different(x, Y) :- not(x=y) Recall the original version of bstmem(tree, X): bstmem(node(x, _, _), X). bstmem(node(k, L, _), X) :- X K, bstmem(l, X). bstmem(node(k, _, R), X) :- X K, bstmem(r, X). Recall that this version was inefficient. Inefficiency in bstmem [trace]?- bstmem(node(5, node(3,empty,empty), emtpy), 1). Call: (8) bstmem(node(5, node(3, empty, empty), emtpy), 1)? creep ^ Call: (9) 1 5? creep ^ Exit: (9) 1 5? creep Call: (9) bstmem(node(3, empty, empty), 1)? creep ^ Call: (10) 1 3? creep ^ Exit: (10) 1 3? creep Call: (10) bstmem(empty, 1)? creep Fail: (10) bstmem(empty, 1)? creep Redo: (9) bstmem(node(3, empty, empty), 1)? creep ^ Call: (10) 1 3? creep ^ Fail: (10) 1 3? creep Redo: (8) bstmem(node(5, node(3, empty, empty), emtpy), 1)? creep ^ Call: (9) 1 5? creep ^ Fail: (9) 1 5? creep Tracing the new bstmem We solved the inefficiency illustrated on the previous slide as follows: bstmem(node(x, _, _), X). bstmem(node(k, L, _), X) :- X K,!, bstmem(l, X). bstmem(node(k, _, R), X) :- X K, bstmem(r, X). What if we try to instead solve this inefficiency by using : bstmem(empty,_) :-!,. bstmem(node(x, _, _), X). bstmem(node(k, L, _), X) :- X K, bstmem(l, X). bstmem(node(k, _, R), X) :- X K, bstmem(r, X). [trace]?- bstmem(node(5, node(3,empty,empty), emtpy), 1). Call: (8) bstmem(node(5, node(3, empty, empty), emtpy), 1)? creep ^ Call: (9) 1 5? creep ^ Exit: (9) 1 5? creep Call: (9) bstmem(node(3, empty, empty), 1)? creep ^ Call: (10) 1 3? creep ^ Exit: (10) 1 3? creep Call: (10) bstmem(empty, 1)? creep Call: (11)? creep Fail: (11)? creep Fail: (10) bstmem(empty, 1)? creep Redo: (9) bstmem(node(3, empty, empty), 1)? creep ^ Call: (10) 1 3? creep ^ Fail: (10) 1 3? creep Redo: (8) bstmem(node(5, node(3, empty, empty), emtpy), 1)? creep ^ Call: (9) 1 5? creep ^ Fail: (9) 1 5? creep 23 24 What went wrong? only affects the present goal (bstmem(empty, 1) in the example). It does not directly cause the ure of a previous goal (so, in the example, Prolog still looks for other rules for the goal bstmem(node(3,empty,empty), 1)). Advice on writing Prolog To minimize bugs, especially with cut and not: Use cut and not as necessary to avoid wrong answers. Follow the rules for safe use of not. Follow the rules for doing arithmetic. Always use ; when testing to check all possible answers. It's easy to get first answer right and rest wrong if else misused. Test with variables in every combination of positions. Use preconditions to state where variables are disallowed. Use cut to avoid duplicate answers. Use cut where possible for efficiency. Use _ where possible for efficiency Summary: logic programming and Prolog Bubble sort Logic programming: Unification, resolution, backtracking. Specify kind of result wanted (what you want), not how to get it. Write a predicate bsort(+before,?after) that succeeds if After is a sorted version of Before. bsort should use bubble sort to sort the list. bsort(before, After) :- bsortaux(before, [], After). Prolog: The major logic programming language. Efficiency can be a worry: cut ordering the predicates Helper predicate bsortaux(+prelower, +Preupper,?Sorted) succeeds if Sorted is a list that consists of a sorted version of Prelower followed by (an unchanged) Preupper. bsortaux([], Preupper, Preupper) :-!. bsortaux(prelower, Preupper, Sorted) :- bubble(prelower, Preupper, Postlower, Postupper), bsortaux(postlower, Postupper, Sorted) Bubble sort Helper predicate bubble(+prelower, +Preupper,?Postlower,?Postupper) succeeds if performing one round of bubble sort on unsorted portion Prelower and sorted portion Preupper results in unsorted portion Postlower and sorted portion Postupper. bubble([x, Y Rest], Preupper, [X Bubbled], Postupper) :- X = Y,!, % swap needed. bubble([y Rest], Preupper, Bubbled, Postupper). bubble([x, Y Rest], Preupper, [Y Bubbled], Postupper) :- bubble([x Rest], Preupper, Bubbled, Postupper). bubble([x], Preupper, [], [X Preupper]) :-!. bubble([], Preupper, [], Preupper). % not needed, we hope Tracing bsort [trace]?- bsort([2,1], S). Call: (7) bsort([2, 1], _G290)? creep Call: (8) bsortaux([2, 1], [], _G290)? creep Call: (9) bubble([2, 1], [], _L206, _L207)? creep ^ Call: (10) 2= 1? creep ^ Fail: (10) 2= 1? creep Redo: (9) bubble([2, 1], [], _L206, _L207)? creep Call: (10) bubble([2], [], _G346, _L207)? creep Exit: (10) bubble([2], [], [], [2])? creep Exit: (9) bubble([2, 1], [], [1], [2])? creep Call: (9) bsortaux([1], [2], _G290)? creep Call: (10) bubble([1], [2], _L245, _L246)? creep Exit: (10) bubble([1], [2], [], [1, 2])? creep Call: (10) bsortaux([], [1, 2], _G290)? creep Exit: (10) bsortaux([], [1, 2], [1, 2])? creep Exit: (9) bsortaux([1], [2], [1, 2])? creep Exit: (8) bsortaux([2, 1], [], [1, 2])? creep Exit: (7) bsort([2, 1], [1, 2])? creep S = [1, 2] Tracing bsort Tracing bsort [trace]?- bsort([3,2,1], S). Call: (7) bsort([3, 2, 1], _G293)? creep Call: (8) bsortaux([3, 2, 1], [], _G293)? creep Call: (9) bubble([3, 2, 1], [], _L206, _L207)? creep ^ Call: (10) 3= 2? creep ^ Fail: (10) 3= 2? creep Redo: (9) bubble([3, 2, 1], [], _L206, _L207)? creep Call: (10) bubble([3, 1], [], _G352, _L207)? creep ^ Call: (11) 3= 1? creep ^ Fail: (11) 3= 1? creep Redo: (10) bubble([3, 1], [], _G352, _L207)? creep Call: (11) bubble([3], [], _G358, _L207)? creep Exit: (11) bubble([3], [], [], [3])? creep Exit: (10) bubble([3, 1], [], [1], [3])? creep Exit: (9) bubble([3, 2, 1], [], [2, 1], [3])? creep Call: (9) bsortaux([2, 1], [3], _G293)? creep Call: (10) bubble([2, 1], [3], _L266, _L267)? creep ^ Call: (11) 2= 1? creep ^ Fail: (11) 2= 1? creep Redo: (10) bubble([2, 1], [3], _L266, _L267)? creep Call: (11) bubble([2], [3], _G367, _L267)? creep Exit: (11) bubble([2], [3], [], [2, 3])? creep Exit: (10) bubble([2, 1], [3], [1], [2, 3])? creep Call: (10) bsortaux([1], [2, 3], _G293)? creep Call: (11) bubble([1], [2, 3], _L305, _L306)? creep Exit: (11) bubble([1], [2, 3], [], [1, 2, 3])? creep Call: (11) bsortaux([], [1, 2, 3], _G293)? creep Exit: (11) bsortaux([], [1, 2, 3], [1, 2, 3])? creep Exit: (10) bsortaux([1], [2, 3], [1, 2, 3])? creep Exit: (9) bsortaux([2, 1], [3], [1, 2, 3])? creep Exit: (8) bsortaux([3, 2, 1], [], [1, 2, 3])? creep Exit: (7) bsort([3, 2, 1], [1, 2, 3])? creep S = [1, 2, 3] 31 32 Exercises Fix the sibling predicate (that we previously defined) so that it doesn't consider a person to be there own sibling. Then make sure that this fix has eliminated any unusual behaviour in the aunt, uncle, nephew, and niece predicates that you defined in a previous set of exercises. Trace bsort on more interesting (and larger) examples. For example, trace the call: bsort([1,5,2,6,3,4], S). Challenge: Recall that the efficiency of bubble sort can be improved by halting after the first iteration during which no swaps are performed (we can halt at that point since if no swaps are performed, the list must be already sorted). Modify bsort by adding this improvement. 33
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks