Logic Programming Prolog COMS W4115 Aristotle Prof Stephen A Edwards Fall 2004 Columbia University Department of Computer Science Logic All Caltech graduates are nerds Stephen is a Caltech graduate Is Stephen a nerd Prolog All Caltech graduates are nerds nerd X techer X Stephen is a Caltech graduate techer stephen Is Stephen a nerd nerd stephen yes More Logic 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 X stephen Y jordan X ryan Y jacob The Basic Idea of Prolog 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 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 Prolog Execution Facts nerd X techer X techer stephen Query nerd stephen Search Execution Result yes Simple Searching Starts with the query nerd stephen Can we convince ourselves that nerd stephen is true given the facts we have techer stephen nerd X techer X First says techer stephen is true Not helpful Second says that we can conclude nerd X is true if we can conclude techer X is true More promising Simple Searching techer stephen nerd X techer X nerd stephen Unifying nerd stephen with the head of the second rule nerd X we conclude that X stephen 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 This is exactly the first clause in the database we re satisfied The query is simply true More Clever Searching techer stephen techer todd nerd X techer X nerd X Tell me about everybody who s provably a nerd 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 More Clever Searching techer stephen techer todd nerd X techer X nerd X Unifying techer X with techer stephen succeeds setting X stephen but we re not done yet 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 More Clever Searching 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 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 X todd X stephen no Searching and Backtracking X X XO X O X O X X O X O X OX XO X XO X X OX OX O X OX OX O X yes X OX OX O X X OX OX O OX X OX OX O XO X OX OX O OX X X OX OX O XXO no no X OX OX O X yes XO X XO X XO X XO X X X O O O The Prolog Environment Database consists of clauses Each clause consists of terms which may be constants variables or structures Constants foo my Const 1 43 Variables X Y Everybody My var Structures rainy rochester teaches edwards cs4115 Structures and Functors A structure consists of a functor followed by an open parenthesis a list of comma separated terms and a close parenthesis Functor paren must follow immediately bin tree foo bin tree bar glarch What s a structure Whatever you like A predicate nerd stephen A relationship teaches edwards cs4115 A data structure bin bin 1 3 4 Unification Part of the search procedure that matches patterns The search attempts to match a goal with a rule in the database by unifying them 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 A variable unifies with anything but forces an equivalence Unification Examples The operator checks whether two structures unify 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 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 search goal g variables e for each clause h t1 tn in the database e unify g h e if successful for each term t1 tn e search tk e if all successful return e return no Order matters search goal g variables e In the order they appear for each clause h t1 tn in the database e unify g h e if successful In the order they appear for each term t1 tn e search tk e if all successful return e return no Order Affects Efficiency edge a b edge b c path a a edge c d edge d e edge b e edge d f path X X path X Y path a a path X X X a yes edge X Z path Z Y Consider the query path a a Good programming practice Put the easily satisfied clauses first Order Affect Efficiency edge a b edge b c path a a edge c d edge d e edge b e edge d f path X Y edge X Z path Z Y path a a path X Y X a Y a edge a Z path X X edge a Z edge a b Consider the query path a a Z b path b a Will eventually produce the right answer but will spend much more time doing so Order can cause Infinite Recursion edge a b edge b c Goal edge c d edge d e path a a edge b e edge d f path a a path X Y path X Y path X Z edge Z Y Subgoal X a Y a implies path X X path a Z edge Z a Consider the query 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 Like LL k grammars X a Y Z Unify Bill and Ted in Prolog super band X on guitar X eddie van halen on guitar X eddie van halen triumphant video X triumphant video X decent instruments X decent instruments X know how to play X know how to play X on guitar X eddie van halen super band wyld stallyns What will Bill and Ted …
View Full Document
Unlocking...