Introduction to Prolog - Course notes are available at York only
Contents
1. Is any one of them called matthew person name matthew _ sex _ Yes THE UNIVERSITY of fork An Alternative person firstname matthew surname grounds sex male person firstname alan Surname frisch sex male person firstname daniel Surname kudenko sex male Department of Computer Scene THE UNIVERSITY of fork Lists A list is an ordered set of elements In Prolog lists are used very extensively so it s good to understand them early In Prolog e a list is either empty 1 e or it is made up of a head H and a tail body T as follows H T Department of Computer Science THE UNIVERSITY of fork Examples of Lists 1 2 3 4 5 isa list with head 1 and tall PG EN likes ed guiness likes ed ghost isa list with head likes ed guiness and tail likes ed ghost Department of Computer Science THE UNIVERSITY Of York Syntax of Lists list gt head tail head gt term tail gt list Note that in the definition above head tail IS Prolog s way of writing head tail Department of Computer Science THE UNIVERSITY of fork More Syntactic Sugar The list X1 X2 X3 X4 Isa list 1 First element is X1 2 Second element is x2 3 Third element is X3 4 Remainder is the list x4 Note that the list above is different to X1 X2 X3 X4 THE UNIVERSITY Of York List Notation Commas separate individual list elements The b2. X 4s append Xs Ys Zs In English if you try to append a list with at least one element in it to a second list return a new list whose head is the head of the first list and whose tail is the second list glued on to the tail of the first list THE UNIVERSITY OfYOrR Appending Two Lists 4 e We recurse on only one argument as IS often the case e append IS left recursive e append describes an infinite relation e append IS also not fully polymodal e But some of the modes that append offers are very useful indeed Department of Computer Science THE UNIVERSITY of fork Reversing a List An example of the usefulness of append IS reversing a list reverse reverse X Xs YS reverse Xs ZS append Zs X Ys You ll get lots more practice in the practicals
3. Department of Computer Science THE UNIVERSITY of fork Logic Programming and Al Introduction to Prolog Department of Computer Science THE UNIVERSITY Of York Prolog Labs e Lab assignment see LPA web page e No hand in of lab problem solutions e Official solutions will be posted on the web THE UNIVERSITY OfYOrR Prolog Interpreter e We will be using SWI Prolog a freeware interpreter http www swi prolog org e There is a commercial Prolog interpreter on the computer science servers Sicstus Prolog THE UNIVERSITY OfYOrK Prolog books Bratko Prolog Programming for Artificial Intelligence 3 edition e Sterling amp Shapiro The Art of Prolog 2 edition e Rob Lucas Mastering Prolog e Clocksim amp Mellish Programming in Prolog Using the ISO standard 5 edition THE UNIVERSITY OfYOrR Free Prolog Books e Nilsson amp Maluszynski Logic Programming and Prolog htto www ida liu se ulfni lpp e Blackburn Bos amp Striegnitz Learn Prolog Now http www coli uni sb de kris learn prolog now THE UNIVERSITY of fork Logic Programming Declarative programming paradigm emphasis on what the program does not how it goes about doing It Use the language of logic to specify a problem and then use a proof procedure to do the computation Prolog use SLD resolution proof procedure THE UNIVERSITY OfYOrK Logic Programming System e A Logic Programming System should be su
4. Y Of York Queries 2 If we press the semicolon which means give me another answer Prolog would respond with parent X ed X helen x George and if we tried the semicolon again we d get No THE UNIVERSITY of fork Queries 3 What if we wanted to know every parent child pair f paron Ny L AE TOM Y harry XEON r Mery X harry Y john and so on until pressing the semicolon would return No THE UNIVERSITY Of York Prolog and Resolution The query parent X ed is equivalent to 3X parent X ed in the FOPC Can we have more complex queries Sure for example the following will return Ed s grandparents parent X ed parent Y X How about a great grandfather THE UNIVERSITY Of York The grandparent Relation Add the following rule to the database grandparent X Y parent X 2 parent 2Z Y The same in logic VX VY YZ grandparent xX Y lt parent X Z parent Z Y The same in English If some individual X is the parent of Z and Z is the parent of some other individual Y then X is the grandparent of Y THE UNIVERSITY of fork A New Program parent tom harry parent tom mary parent harry john parent harry helen parent mary helen parent mary george parent helen ed parent george ed grandparent X Y parent X 2 parent Z Y Department of Computer Science THE UNIVERSITY of fork Querie
5. ar 1 Pak oO DP separates an element and the rest of the list contains zero elements Y Ys contains at least one element Y1 Y2 Ys contains at least two elements Y1 Y2 Y3 is a syntax error Y1 Y2 Y3 isthe same as Y1 Y2 Y3 Y1 Y2 Y3 Is the same as Y1 Y2 Y3 Department of Computer Science THE UNIVERSITY Of York Pure Prolog Syntax 1 Program Clause Clause Program Clause gt Fact HornClause Fact gt Literal Literal p p t1 t2 tn where p is a predicate symbol and t1 t2 tn are terms Department of Computer Science THE UNIVERSITY of fork Pure Prolog Syntax 2 HornClause gt Head Body Head gt Literal Body Literal Literal Body Literal Body THE UNIVERSITY Of York A First Real Program e Write a program that can evaluate Boolean expressions e What do we need to write such a program Decide which Boolean functions to include and or not etc How do we define the Boolean functions in Prolog Choose a value for True and one for False Back to truth tables THE UNIVERSITY Of York Boolean Expressions Represent the and or and not Boolean functions Represent TRUE by the constant true Represent FALSE by the constant false Note that a truth table is simply a relation Represent the basic truth tables with ground rules Implement the evaluation mechanism th
6. are my ancestors e My ancestors are my parents my parent s parents my parents parents parents my parents parents parent s parents etc e My ancestors are either my parents or the ancestors of my parents e What is the definition of the ancestor relation in Prolog Department of Computer Science THE UNIVERSITY of fork Ancestors in Prolog parent tom harry parent mary harry parent steve emma parent helen emma parent harry ed parent emma ed ancestor X Y parent X Y ancestor X Y parent X Z ancestor Z Y THE UNIVERSITY Of York Queries and Search Trees What is the search tree associated with the query ancestor X ed 1 Translate the Prolog program back into the FOPC 2 Translate the query to a conclusion for the argument whose premises are the sentences from the Prolog program 3 Do the SLD resolution proof for the resulting argument Department of Computer Science THE UNIVERSITY of fork From Prolog to Logic Parent tom harry Parent mary harry Parent steve emma Parent helen emma Parent emma ed Parent x vi gt Ancestor x y COO N O OO A O PD Parent harry ed Parent x z a Ancestor z y gt Ancestor x y Ancestor x ed Department of Computer Science THE UNIVERSITY of fork Partial Search Space panunen ees E P g er Z A A z ed eg P tom harry P m
7. ary X parent X mary parent X Y Department of Computer Scene THE UNIVERSITY of fork Cleaner Output We want to find Tom s children who have children of their own parent tom X parent X Y X harry Y gt eq j No But we re just interested in the value of X not Y as long as some Y exists Department of Computer Science THE UNIVERSITY of fork Anonymous Variables We can use anonymous variables parent tom X parent X _ X harry No Department of Computer Science THE UNIVERSITY of fork Anonymity Pitfalls The query parent tom parent _ _ is not the same as parent tom X parent X _ but Is in fact equivalent to parent tom X parent Y Z Department of Computer Science THE UNIVERSITY OfYOrK Listing To get a listing of your Prolog program c LISCIO sometimes as you change your program Prolog remembers older definition of the predicates in your code In these cases it is a good idea to exit the interpreter and restart it to clear the memory THE UNIVERSITY of fork Trace trace parent tom X parent X Y Call 8 parent tom _G284 creep Exit 8 parent tom harry creep Call 8 parent harry G287 creep Exit 8 parent harry ed creep X harry Y ed Fail 8 parent harry G287 creep Fail 8 parent tom G284 creep No THE UNIVERSITY of fork Ancestors e Question Who
8. ary harry P steve emma P helen emma P harry ed P tom harry A A harry ed A harry ed A A emma ed A A emma ed A A ed ed A A harry ed A emma ed me TT A A zL ed THE UNIVERSITY Of York Prolog s Search Strategy Branches in the previous tree represent alternative solutions Prolog searches the tree in a depth first manner solutions are found by the Prolog interpreter in the same order as they are discovered by DFS The order of the clauses in the Prolog program is important Department of Computer Science a THE UNIVERSITY of fork A Different Program parent tom harry parent Mary harry parent steve emma parent helen emma parent harry ed parent emma ed ancestor X Y parent X 4 ancestor Z Y ancestor X Y parent X Y THE UNIVERSITY Of York What s the difference e What is the search tree associated with the same query as before ancestor X ed d e Is the search space different e Are the same solutions found THE UNIVERSITY of fork Another Pitfall Consider the following program likes ed emma likes ed john likes ed X likes X ed Department of Computer Science THE UNIVERSITY of fork Another Pitfall 2 What is the search space associated with the query likes ed X likes ed X A emma 7 X john What happens next Department of Computer Science THE UNIVERSITY of fork Anot
9. ch that if a solution to our problem exists then a proof should exist given the problem specification e Program logical specification of a problem e Computation proof i e running the program Department of Computer Science THE UNIVERSITY Of York Advantages e Very high level language e Easy to prototype e Shorter programs e More readable programs e Ideal for many Al applications THE UNIVERSITY Of York Disadvantages e Not intuitive to procedural programmers e Steep learning curve initially e Program execution comparatively slow often prototyping in Prolog and then optimized implementation in C C Department of Computer Science THE UNIVERSITY of fork Prolog without Variables Consider the following program ed lives in york ed is a cs student ed does 1lpa Once we load this program into Prolog we can type in the following query ed lives in york and Prolog will respond with Yes Department of Computer Science THE UNIVERSITY of fork Conjunction We could ask the following query from Prolog is it the case that Ed lives in York and that he does LPA This is how ed lives in york ed does lpa The obvious reply from Prolog given our previous program IS Yes Department of Computer Scene THE UNIVERSITY of fork Adding Simple Rules Consider this program ed lives in york ed La a cs student ed does 1lpa ed loves logic ed is a cs student ed does 1lpa The
10. guage e g the following queries perhaps should give type errors but they dont memb a alb Les memb b alb No How does Prolog come to the above two conclusions Department of Computer Science THE UNIVERSITY Of York Types 2 Suppose we define a predicate 1ist 1 where list X would be true if x is a list list list X Xs list Xs How could we then make the memb 2 predicate more type safe Department of Computer Science THE UNIVERSITY of fork Types 3 Then we could make memb type safe r memb X X Xs list Xs memb X Y Ys memb X Ys Now the previous queries behave as expected memb a a bl No memb b a b Department of Computer Science THE UNIVERSITY Of York Appending Two Lists 1 We d like to define the predicate append 3 where append Xs Ys Zs istrue If Zs ts the list formed by concatenating Ys to the end of Xs For example append La Dr c Lld el LD L Ta b c q el Department of Computer Science 7 THE UNIVERSITY OfYOrK Appending Two Lists 2 The base case of append 3 concerns the case where Xs is the empty list append Ys Ys In English if you try to append the empty list to another list simply return the other list THE UNIVERSITY of fork Appending Two Lists 3 If the first argument of append 3 IS a non empty list i e one that has at least one element append X Xs Ys
11. he body can be a conjunction or disjunction of predicates e Things that end in a full stop are known as clauses Department of Computer Science THE UNIVERSITY of fork Disjunction Disjunction exists in Prolog as the semicolon but it is good practice to avoid using It In fact we can always get rid of disjunctions from the body of a clause as follows Pp EE NM is the same as p q Oo 2 1 THE UNIVERSITY OfYOrK Beyond Propositional e So far we have only considered ground clauses and queries e Restriction to propositional logic makes it infeasible to handle bigger databases The real power of Prolog is only revealed with the use of variables Department of Computer Science THE UNIVERSITY of fork The parent database 1 tom vi ech A N john helen george ed Well it could have happened in ancient Greece Department of Computer Science a THE UNIVERSITY of fork Parent Program parent tom harry parent tom mary parent harry john parent harry helen parent mary helen parent mary george parent helen ed parent george ed Department of Computer Scene THE UNIVERSITY of fork Queries 1 How can we find out who is the parent of whom For example what query would we give to Prolog to find the parents of Ed parent X ed Prolog would respond with 2 X helen and it would sit there and wait Department of Computer Science THE UNIVERSIT
12. he next leashed event e skip the s key tells Prolog to carry on and produce no trace messages until another event occurs involving the current goal e leap the I key tells Prolog to carry on and produce no trace messages until either a spy point is reached or another event occurs involving the current goal THE UNIVERSITY of fork Trace Commands 2 e break the b key tells Prolog to exit the current trace It gives us a temporary new interpreter shell and we can resume our trace with Ctrl D e abort the a key tells Prolog to abandon the current trace altogether e exit the c key tells Prolog to exit the current trace and terminate the Prolog interpreter thus returning us to the shell THE UNIVERSITY Of York SWI Manual e As with all programming languages the most important aid in learning to develop good programs with Prolog is the language manual e Get it ati http www swi prolog org e The Prolog interpreter also has the help 0 and help 1 predicates for you to use which access the manual Department of Computer Scene THE UNIVERSITY of fork Back to Lists Consider the following list membership program memb X X __ memo X ITI memb X T Note that memb is not a fully polymodal predicate as we can t ask Prolog the queries 2 memb 1 X 2 Memo X Y Department of Computer Scene THE UNIVERSITY of fork Types 1 Prolog is not a typed lan
13. her Pitfall 3 Prolog went into an infinite loop trying to prove the goal likes ed ed THE UNIVERSITY Of York Infinite Loops e We can expect infinite computation when using infinite relations or mutually recursive ones But the way Prolog does things means that even some finite queries can fail Prolog s strategy Try clauses from top to bottom Try subgoals from left to right Department of Computer Science THE UNIVERSITY of fork Logic vs Prolog Four logically equivalent programs a X Y p X Y AK lt Dixy 4 AU NN athe Y Se Dinky Gy aia vd AL NN Nr GN a X Y 7 llr YX P X 4 a X Y ll Y ee AE ai NNN THE UNIVERSITY OfYOrK Rules of Thumb e Do not have recursive calls as the first subgoal so called left recursion e Put the base case as the first clause e Be prepared to break these rules THE UNIVERSITY OfYOrR Data Structures e Prolog supports only the term data structure A term in Prolog is a constant or a variable or a function symbol of arity n applied to n terms e Sometimes the words function symbol and functor are used interchangeably e Variables can have numerical or list values see later lectures I Department of Computer Science THE UNIVERSITY OfYOrR LPA staff database Consider the following database person name matthew grounds sex male person name alan frisch sex male person name daniel kudenko sex male
14. lues for X and Y make the expression X v Y a Y X true eval and or v X v Y and v Y v X true x true Y true Department of Computer Science THE UNIVERSITY Of York Unification 1 Prolog uses resolution as its only rule of inference The unification operator is Examples i love beer ed said 1_love_beer X said X ed hello you Y hello X f f0ol A you Y fool Department of Computer Science THE UNIVERSITY Of York Unification 2 Sometimes unification can also fail Department of Computer Scene THE UNIVERSITY of fork Operators in Prolog Say we want to write that 4 is less than 5 in Prolog How can we do it As it turns out Prolog does have these operators built in 2 140 95 a Day Yes Yes o gt gt 4D Sec gt Ga No No Department of Computer Science THE UNIVERSITY of fork Infix and Prefix e The operator functor lt in X lt Y is an infix operator e X lt Y is internally translated to the term lt X Y e The operator functor lt in lt X Y isa prefix operator THE UNIVERSITY OfYOrR Mixedfix e Another Prolog builtin operator is This is a mixedfix operator which also takes two arguments This operator is also translated to X Y internally e Note that is a functor symbol in this context and not a clause terminator THE UNIVERSITY of fork User defined Operators Prolog al
15. rough Prolog rules Department of Computer Science THE UNIVERSITY of fork Truth Tables P P Q j mm A 4 7 m 4 1 34 2 m 1 71 4 gt p g F F m 4 34 2 m d 4 4 lt Department of Computer Science THE UNIVERSITY Of York Ground Clauses eval and true true true eval and false true false eval and true false false eval and false false false eval or true true true eval or true false true eval or false true true eval or false false false eval not true false eval not false true THE UNIVERSITY Of York Boolean Evaluation 1 First we need some way to encapsulate the Boolean functions so that Prolog can match them eval v true true eval v false false Finally we are ready to ask ourselves What does it mean for P a Q P v Q P to be true Department of Computer Science THE UNIVERSITY Of York Boolean Evaluation 2 eval and A B V eval A AV eval B BV eval and AV BV V eval or A B V eval A AV eval B BV eval or AV BV V eval not A V eval A AV eval not AV V Department of Computer Science THE UNIVERSITY of fork Demonstration 1 Forward reasoning what is the truth value of the expression TRUE FALSE eval and v true v false X X false No Department of Computer Science THE UNIVERSITY of fork Demonstration 2 Backward reasoning what truth va
16. rule above is equivalent in logic to e ed loves logic ed IS a cs student ned does lpa e ed Is a cs student n ed does lpa gt ed loves logic Department of Computer Science THE UNIVERSITY of fork The Logic Perspective Ed s program in logic 1 ed_lives_in_york 2 ed IS a cs student 3 ed does lpa 4 ed Is a cs student ed does Ipa gt ed loves logic Can we deduce ed loves logic from the premises above What response can we expect for the query ed loves logic Department of Computer Science a THE UNIVERSITY of fork Another Example 1a P Se Dr P Fre Os Can we deduce o from this program THE UNIVERSITY Of York Another Example 1b How does Prolog go about deducing q SLD 1 to prove q we must prove both p and r 2 p is true given 3 to prove r we must prove both s and p 4 both s and p are true given 5 done This way by working through the implications Prolog only has to prove things that are relevant in proving the goal Department of Computer Science THE UNIVERSITY of fork Another Example 2a LP 2 5 3 PAR gt Q 4 SaP gt R Q Is this a valid argument of propositional logic THE UNIVERSITY of fork Another Example 2b Q 6 PAR 1 R KO SAP 2 P Ko E THE UNIVERSITY OfYOrR Prolog Body Parts e Informally the thing before the is the head and the thing after the is the body e In Prolog we can only have a head with one predicate whereas t
17. s on Grandparents A query to find Ed s grandparents grandparent X ed will return Harry and Mary A query to find Tom s grandchildren grandparent tom X will return John Helen and George THE UNIVERSITY OfYOrK Prolog vs C 1 A bunch of queries 1 given a person compute his her grandchildren 2 given a person compute his her grandparents 3 given two people compute whether the former is the grandparent of the latter 4 compute all grandparent grandchildren pairs THE UNIVERSITY Of York Prolog vs C 2 The same relation that of parenthood is involved in all cases In Prolog we can get away by just defining just one relation grandparent X Y parent X 2Z parent Z Y We then vary the query The variables X and Y in grandparent may be instantiated mapped to constants uninstantiated mapped to variables Department of Computer Science THE UNIVERSITY of fork A Smaller Parents Database mary steve helen Fae harry emma NLU ed Department of Computer Science THE UNIVERSITY OfYOrK The Parent Database in Prolog parent tom harry parent mary harry parent steve emma parent helen emma parent harry ed parent emma ed Department of Computer Scene THE UNIVERSITY of fork Polymodality Polymodality is the ability to have multiple modes in Our programs or queries Le multiple patterns of instantiation parent tom harry parent m
18. so allows you to define your own operators op 3 For example instead of writing and v 1 v 0 we can write v 1 amp v 0 provided we define amp as anew infix operator Often there s no need to define operators Check the user manual for more details THE UNIVERSITY OfYOrK Procedural vs Declarative Semantics 1 The prolog program O See Gy is Supposed to mean the same as pe 1 But in practice they are different Department of Computer Science THE UNIVERSITY OfYOrK Procedural vs Declarative Semantics 2 In the program P i qr how does Prolog solve the query T Pa 1 first solve q 2 then solve r Department of Computer Science THE UNIVERSITY of Ork Procedural vs Declarative Semantics 3 e Unfortunately we must sometimes take Prolog s way of solving queries into account to avoid infinite search for efficiency to hack certain tricks THE UNIVERSITY OfYOrR Prolog Tips and Tricks 1 e Spell the predicates correctly e Pass the right number of arguments to each function e Locate operators and determine their precedence e Introduce brackets to avoid confusion e Determine the pattern of instantiation of variables and make sure it matches the intended use by the rest of the program THE UNIVERSITY Of York Prolog Tips and Tricks 2 e It is good practice to put all ground clauses of a predicate at the top of the Prolog file p
19. ut all other clauses that define a predicate together below the ground ones e Common errors Forgetting the full stop at the end of a clause Having unmatched round brackets Square Brackets or curly brackets braces Department of Computer Science THE UNIVERSITY of fork Trace A very useful tool that comes with Prolog is the trace command It has the following events 1 Call Prolog starts trying to solve a goal 2 Exit Some goal has been solved by Prolog 3 Redo Prolog begins to re solve a goal 4 Fail Prolog has failed to solve a goal THE UNIVERSITY OfYOrK Trace Spy Points e To trace only a specific predicate pred of your program set a spy point spy pred e To remove the spypoint for a predicate pred nospy pred e f more than one version of pred exists e g one of arity 2 and one of arity 3 we can spy on them individually or together Example spy pred 2 THE UNIVERSITY Of York Trace Leashing e Another useful feature is eashing which controls which parts of a trace the user is shown e leash call tells Prolog that we are interested in the call event e leash fail tells Prolog that we are not interested in the fail event e leash oeall exit redo fail tells Prolog that we are interested in calls and exits but not in redos and failures THE UNIVERSITY of fork Trace Commands 1 e creep the Return key tells Prolog to carry on until t
Download Pdf Manuals
Related Search