Logic Prolog Logic Programming Prolog COMS W4115 All Caltech graduates are nerds Prof Stephen A Edwards Spring 2003 Columbia University Department of Computer Science Stephen is a Caltech graduate More Logic The Basic Idea of Prolog My Enemy s Enemy is My Friend friend X Z enemy X Y enemy Y Z friend stephen jordan yes friend stephen X enemy stephen ryan X jordan enemy ryan jordan friend X Y enemy jordan jacob Is Stephen a nerd X stephen Y jordan AI programs often involve searching for the solution to a problem Why not provide this search capability as the underlying idea of the language Result Prolog Facts nerd X techer X techer stephen Query nerd stephen Search Execution Result yes Stephen is a Caltech graduate techer stephen Is Stephen a nerd nerd stephen yes Prolog Mostly declarative Program looks like a declaration of facts plus rules for deducing things Running the program involves answering questions that refer to the facts or can be deduced from them More formally you provide the axioms and Prolog tries to prove theorems X ryan Y jacob Prolog Execution All Caltech graduates are nerds nerd X techer X Simple Searching Simple Searching Starts with the query techer stephen nerd X techer X nerd stephen nerd stephen Can we convince ourselves that nerd stephen is true given the facts we have techer stephen nerd X techer X Unifying nerd stephen with the head of the second rule nerd X we conclude that X stephen First says techer stephen is true Not helpful We re not done for the rule to be true we must find that all its conditions are true X stephen so we want techer stephen to hold Second says that we can conclude nerd X is true if we can conclude techer X is true More promising This is exactly the first clause in the database we re satisfied The query is simply true More Clever Searching More Clever Searching More Clever Searching techer stephen techer todd nerd X techer X nerd X techer stephen techer todd nerd X techer X nerd X Tell me about everybody who s provably a nerd Unifying techer X with techer stephen succeeds setting X stephen but we re not done yet tmp beta prolog bp Beta Prolog Version 1 2 C 1990 1994 user techer stephen techer todd nerd X techer X D yes nerd X X stephen X todd no As before start with query Rule only interesting thing Unifying nerd X with nerd X is vacuously true so we need to establish techer X Unifying techer X with techer todd also succeeds setting X todd but we re still not done Unifying techer X with nerd X fails returning no Order Matters tmp beta prolog bp Beta Prolog Version 1 2 C 1990 1994 user techer todd techer stephen nerd X techer X D yes nerd X Todd returned first Searching and Backtracking The Prolog Environment Database consists of clauses X Each clause consists of terms which may be constants variables or structures X XO X O X O X X O X X O X OX XO X XO X XO X XO X XO X X O O O XO Constants foo my Const 1 43 X Variables X Y Everybody My var X OX OX O X OX OX O X X OX OX O X X OX OX O X Structures rainy rochester teaches edwards cs4115 X todd X stephen no yes Structures and Functors Unification Unification Examples A structure consists of a functor followed by an open parenthesis a list of comma separated terms and a close parenthesis Part of the search procedure that matches patterns The operator checks whether two structures unify The search attempts to match a goal with a rule in the database by unifying them a a yes a b no 5 3 a no 5 3 X X 5 3 no foo a X no foo a X X a no foo X b X a Y b no foo X a X no Functor paren must follow immediately bin tree foo bin tree bar glarch X OX OX O XO X OX OX O OX X X OX OX O XXO yes no no Recursive rules A constant only unifies with itself Two structures unify if they have the same functor the same number of arguments and the corresponding arguments unify What s a structure Whatever you like A predicate nerd stephen A relationship teaches edwards cs4115 A data structure bin bin 1 3 4 X OX OX O OX A variable unifies with anything but forces an equivalence Constant unifies with itself Mismatched constants Mismatched constants Variables unify foo X b X a required but inconsistent foo X a X a is consistent foo a Y X a then b Y foo b a c X b required but inconsistent The Searching Algorithm Order matters Order Affects Efficiency search goal g variables e search goal g variables e In the order they appear edge a b edge b c path a a edge c d edge d e for each clause h t1 tn in the database for each clause h t1 tn in the database e unify g h e e unify g h e if successful if successful for each term t1 tn e search tk e path a a Consider the query path a a Good programming practice Put the easily satisfied clauses first Order can cause Infinite Recursion Prolog as an Imperative Language edge a b edge b c A declarative statement such as Goal path a a path X Y X a Y a path X Z edge Z Y edge a Z P if Q and R and S path a a edge b e edge d f path a a path X Y path X Y Subgoal X a Y a path a Z Z b path b a Consider the query Unify can also be interpreted procedurally as implies path X X edge a Z edge a b path a a yes edge c d edge d e path X X Consider the query X a edge X Z path Z Y return no edge c d edge d e edge X Z path Z Y In the order they appear e search tk e Order Affect Efficiency edge b e edge d f path X Y if all successful return e return no path X Y path X X for each term t1 tn if all successful return e edge a b edge b c edge b e edge d f path a a path X X To solve P solve Q then R then S edge Z a path a Z path X Y path a a X a Y Z path a Z edge Z a path a Z path X Y This is the problem with the last example path X Y path X Z edge Z Y To solve P solve P Will eventually produce the right answer but will spend much more time doing so Like LL k grammars Prolog as an Imperative Language Cuts Cuts go …
View Full Document
Unlocking...