Logic ProgrammingReading AssignmentSlide 3PrologExample: Logical DatabaseLogical Database QueriesN-Queens ProblemN-Queens in PrologType Inference in MLFlight Planning ExampleQueries in PrologLogical Variables in PrologNon-DeterminismLogical ConjunctionDerived PredicatesRecursionProlog Program ElementsHorn ClausesFacts, Rules, and ProgramsHorn Clauses and PredicatesListsAppending a ListList MembershipMore List FunctionsAnswering Prolog QueriesSlide 26Flight Planning: Proof SearchFlight Planning: BacktrackingUnificationExample: List MembershipSoundness and CompletenessFlight Planning: Small Change“Is” OperatorTracingTracing FactorialThe CutTracing Bubble SortNegation in Prologslide 1Vitaly ShmatikovCS 345Logic Programmingslide 2Reading AssignmentMitchell, Chapter 15slide 3Logic ProgrammingFunction (method) is the basic primitive in all languages we have seen so far•F(x)=y – function F takes x and return yRelation (predicate) is the basic primitive in logic programming•R(x,y) – relationship R holds between x and yslide 4PrologShort for Programmation en logique•Alain Colmeraurer (1972)Basic idea: the program declares the goals of the computation, not the method for achieving themApplications in AI, databases, even systems•Originally developed for natural language processing•Automated reasoning, theorem proving•Database searching, as in SQL•Expert systems•Recent work at Berkeley on declarative programmingslide 5Example: Logical DatabaseAUSDALOKCHOUPHXnonstop(aus, dal).nonstop(aus, hou).nonstop(aus, phx).nonstop(dal, okc).nonstop(dal, hou).nonstop(hou, okc).nonstop(okc, phx).nonstop(aus, dal).nonstop(aus, hou).nonstop(aus, phx).nonstop(dal, okc).nonstop(dal, hou).nonstop(hou, okc).nonstop(okc, phx).In Prolog:slide 6Logical Database QueriesWhere can we fly from Austin?SQL•SELECT dest FROM nonstop WHERE source=“aus”;Prolog•?- nonstop(aus, X).•More powerful than SQL because can use recursionslide 7N-Queens ProblemPlace N non-attacking queens on the chessboard•Example of a search problem (why?)slide 8N-Queens in Prologdiagsafe(_, _, []).diagsafe(Row, ColDist, [QR|QRs]) :- RowHit1 is Row + ColDist, QR =n= RowHit1, RowHit2 is Row - ColDist, QR =n= RowHit2, ColDist1 is ColDist + 1, diagsafe(Row, ColDist1, QRs).safe_position([_]).safe_position([QR|QRs]) :- diagsafe(QR, 1, QRs), safe_position(QRs).nqueens(N, Y) :- sequence(N, X), permute(X, Y), safe_position(Y).slide 9Type Inference in MLGiven an ML term, find its type x fun@@+ 2slide 10Flight Planning ExampleAUSDALOKCHOUPHXnonstop(aus, dal).nonstop(aus, hou).nonstop(aus, phx).nonstop(dal, okc).nonstop(dal, hou).nonstop(hou, okc).nonstop(okc, phx).nonstop(aus, dal).nonstop(aus, hou).nonstop(aus, phx).nonstop(dal, okc).nonstop(dal, hou).nonstop(hou, okc).nonstop(okc, phx).Relation: nonstop(X, Y) – there is a flight from X to YEach line iscalled a clauseand representsa known factA fact is true ifand only if wecan prove it true using some clauseslide 11Queries in PrologAUSDALOKCHOUPHX?-Yes?-Yes?-No?-nonstop(aus, dal).nonstop(dal, okc).nonstop(aus, okc).slide 12Logical Variables in PrologAUSDALOKCHOUPHX?-X=phx ;No?-Y=aus ;No?-nonstop(okc, X).nonstop(Y, dal).Is there an X such thatnonstop(okc, X) holds?slide 13Non-DeterminismAUSDALOKCHOUPHX?-X=hou ;X=okc ;No?-No?-nonstop(dal, X).nonstop(phx, X).Predicates may return multiple answers or no answersslide 14Logical ConjunctionAUSDALOKCHOUPHX?-X=dal ;X=hou ;No?-nonstop(aus, X), nonstop(X, okc).Combine multiple conditions into one queryslide 15Derived PredicatesAUSDALOKCHOUPHX?-Via=dal ;Via=hou ;No?-flyvia(From, To, Via) :- nonstop(From, Via), nonstop(Via, To).flyvia(aus, okc, Via).• Define new predicates using rules• conclusion :- premises.- conclusion is true if premises are trueslide 16RecursionAUSDALOKCHOUPHX?-X=aus ;X=dal ;…?-reach(X, X).reach(X,Z) :- nonstop(X, Y), reach(Y, Z).reach(X, phx).• Predicates can be defined recursivelyslide 17Prolog Program ElementsProlog programs are made from terms•Variables, constants, structuresVariables begin with a capital letter•BobConstants are either integers, or atoms•24, zebra, ‘Bob’, ‘.’Structures are predicates with arguments•n(zebra), speaks(Y, English)slide 18Horn ClausesA Horn clause has a head h, which is a predicate, and a body, which is a list of predicates p1, p2, …, pn •It is written as h  p1, p2, …, pn•This means, “h is true if p1, p2, …, and pn are simultaneously true”Example•snowing(C)  precipitation(C), freezing(C) •This says, “it is snowing in city C if there is precipitation in city C and it is freezing in city C”slide 19Facts, Rules, and ProgramsA Prolog fact is a Horn clause without a right-hand side •Term.–The terminating period is mandatoryA Prolog rule is a Horn clause with a right-hand side (:- represents )•term :- term1, term2, … termn.•LHS is called the head of the ruleProlog program = a collection of facts and rulesslide 20Horn Clauses and PredicatesAny Horn clause h  p1, p2, …, pn can be written as a predicate p1  p2  …  pn  h, or, equivalently, (p1  p2  …  pn)  hNot every predicate can be written as a Horn clause (why?)•Example: literate(x)  reads(x)  writes(x)slide 21ListsA list is a series of terms separated by commas and enclosed in brackets•The empty list is written []•A “don’t care” entry is signified by _, as in [_, X, Y] •A list can also be written in the form [Head | Tail]slide 22Appending a Listappend([], X, X).append([Head | Tail], Y, [Head | Z]) :- append(Tail, Y, Z).•The last parameter designates the result of the function, so a variable must be passed as an argumentThis definition says:•Appending X to the empty list returns X•If Y is appended to Tail to get Z, then Y can be appended to a list one element larger [Head | Tail] to get [Head | Z]slide 23List Membershipmember(X, [X | _]).member(X, [_ | Y]) :- member(X, Y).The test for membership succeeds if either:•X is the head of the list [X | _]•X is not the head of the list [_ | Y] , but X is a member of the remaining list YPattern matching governs tests for equality“Don’t care” entries (_) mark parts of a list that aren’t important to the ruleslide 24More List FunctionsX is a prefix of Z if there is a list Y that can be appended to X to make Z•prefix(X, Z)