Knowledge Representation and Reasoning Prolog and AILog
Contents
1. Note that the following five lists a b c al b c Cal bl c al bl cl 1131 la bl c 10 are different representations of what essentially is the same list The handout Introduction to PROLOG includes an example of a simple PROLOG pro gram This program identifies whether a particular element is a member of a set of elements represented as a list The following clauses are given the predicate member was replaced by element as member is already included in most PROLOG systems 1 element X X _ 2 element X _IY element X Y Examples of queries to this program are element d a b c d e f Note that the predicate element both occurs in the body of clause 2 and also in its head Hence this is an example of a recursive rule In fact you have seen recursion before when we considered Dutch royalty The two PROLOG clauses are included in the file exercisel pl Consult this file and query the system For example try element a b a c element d b a c element X a b c d Again try to understand what is happening 4 3 Unification and matching An important mechanism underlying every PROLOG interpreter is the unification of terms Unification basically attempts to make two terms equal by substituting appropriate terms for the variables occurring in the two terms In all cases the so called most general unifier mgu is determined A2. In SQL like syntax this could be stated as follows SELECT FROM employee WHERE department_number 1 AND scale gt 2 Expressed as a PROLOG query the purpose is to select tuples satisfying the following condi tion employee Name Department_N Scale Department_N 1 Scale gt 2 Consult the file exercise8 pl and enter the PROLOG query given above The following output is produced 21 Name mcardon Department_N 1 Scale 5 By entering the operator the logical V connective is it again possible to find out whether there are any alternative solutions as PROLOG will then backtrack and will check whether there are any other employees satisfying the conditions Note that in fact we have not yet produced a functionally complete implementation of the selection operator as only a single tuple is selected from the database but we are nearly there Recall the trick we considered before where we made use of the fail predicate in order to enforce backtracking Here we use this trick again This gives us the following implementation of the selection operator selection X Y call X call Y write X nl fail selection _ _ The predicate call generates a subgoal determined by the binding of its variable argument It is assumed that the first argument of selection represents the relation from which tuples are to be selected the second argument contains the set of selection conditions which should be sa
3. follows projection employee Name Department_N Scale Name Scale Note that this is still not a complete implementation of the projection as the resulting relation may not include doubles As incorporating this in the program as well would make it quite a bit more complicated hardly worth the effort for small databases we leave the program as it is Experiment with the projection program until you fully understand how it works It is now quite straightforward to combine selection and projection This would imply not only specifying the attributes used in projecting a relation but also giving the conditions on the attributes which need to be satisfied by the selected tuples Consider for example the following query Print the name and scale of those employees in department 1 with a salary higher than scale 2 In SQL like notation SELECT name scale FROM employee WHERE department_number 1 AND scale gt 2 Define yourself the predicate sel_pro which is meant to combine selection and projection The final database operation which we will consider is the join The join simply merges tuples in relations based on a join condition Suppose that one would like to obtain a list of employees with for every employee the salary included For this purpose we need information from two different relations employee and salary For every employee we need to find the salary corresponding to the salary scale Hence the join conditio
4. how predecessor emma beatrix lt 1 predecessor wilhelmina beatrix 2 ruler emma 3 parent emma wilhelmina How Number up retry ok prompt help 2 ruler emma lt 1 queen emma How Number up retry ok prompt help gt Try to understand the way these commands work from the AILOG user manual gt Load the knowledge base exercise10 ail into AILOG ask questions and experiment with the explanation facilities 5 4 User interaction AILOG also allows prompting users by means of the anskable build in predicate For exam ple by replacing father hendrik juliana by askable father hendrik juliana in the file exercise10 ail one obtains the following behaviour ailog ask predecessor X Y Is father hendrik juliana true yes no unknown why help yes Answer predecessor emma beatrix ok more how help gt Change one of the facts in the file exercise10 ail to askable and see what happens when you query the knowledge base 26 5 5 Model based and probabilistic reasoning You will use AILOG in assignments on model based and probabilistic reasoning Model based reasoning is done by making some of the atoms in the knowledge base assumable Probabilistic reasoning is done by adding probabilistic information to clauses Consult the AILOG manual for details 27
5. of arguments of the predicate For example spy path spy branch 2 A spy point can be removed by the predicate nospy nospy path nospy branch 2 The structure of the information generated by the PROLOG interpreter in the case of spy points is almost identical to the information that is generated by using trace gt Experiment with spy points using the tree search algorithm 15 4 6 Variation of input output parameters An argument of a query can both function as an input and an output parameter depending on the context of the query This ensures that a program can be used for sometimes completely different even opposite purposes like construction and analysis Consider the the following program which is available in the file exercise3 pl conc L L conc X L1 L2 X L3 conc L1 L2 L3 This program can be used to concatenate two lists but in fact it can be used as well to split up a list into its parts Check the statement above by consulting the file exercise3 pl ask the following questions to 6 the PROLOG interpreter when the interpreter returns with a response enter in order to enforce backtracking so that PROLOG will attempt to find alternative solutions conc X Y a b c d e conc a b c d X The fact that it is possible to use the same program for such different purposes follows from the fact that PROLOG is essentially a declarative language based on a mat
6. BIY L B lt A conc X B AlY M I bubsort M S bubsort L L conc L L conc H T L HI V conc T L V Investigate the workings of this program it is available in file exercise7 pl 4 11 A relational database in PROLOG Basically PROLOG programs are about defining relation among objects in a domain As storing data as instances of relations is the essential feature you are probably not surprised to learn the PROLOG is very good in performing the sort of operations on data which many people normally associate with a relational database management system For example consider salary scale amount which is the sort of relation defined in a relational data model Recall that scale and amount are referred to as attributes whereas specific instances of this relation are called tuples A relational database contains tuples defined according to the data model Retrieving data stored in the database according to particular constraints on the attributes is called querying the database The file exercise8 pl includes an example of a database with the following data model Note that the data model is really implicit in this case which is because we simply make use of standard PROLOG facilities without implementing anything extra e employee name department_number scale e department department_number name_department e salary scale amount The database PROLOG database in this case included the following tuples facts aga
7. Knowledge Representation and Reasoning Prolog and AlLog Practical 2012 2013 Exercises Peter Lucas Institute for Computing and Information Sciences iCIS Radboud University Nijmegen Contents 1 Learning outcomes 3 2 AI programming and representation 3 2 1 Symbol manipulationvss 2 2 ace sean Pa oe ek Se ew Bh na Ps 3 2 2 Characteristics of PROLOG 2 0 0 0 a Ea a a ee 4 23 AlL g hean WS oN te deal ih ea in OR a eb Be he eee 5 3 Introductory remarks about PROLOG 6 3 1 PROLOG under Linux and Windows 4 6 32 PROLOG programs so oss e aR ek oie he RSD ene et Re ne ae 7 4 PROLOG exercises 8 4 1 Meet The Dutch Royal Family facts queries and rules 8 4 2 Lists and recursion 1 a 10 4 3 Unification and matching siosar yee i ln See a ee Be Ve ed 11 AA Backtracking ero A a die Pbk vee oo 13 45 Tracing and Spyin ed de amp ced A ee Been es Re wk Goel G 13 4 6 Variation of input output parameters soosoo a 000004 16 4 7 The order of clauses and conditions 2 0002000 16 48 Pailvand Cute wo ok sew Syeda he a Bo ee Ee ee dd ee G 18 4 9 A finite automaton 2 18 ASO SOTUN Gs ci eee hoe Gea ee Mh Godden decd BE eet ae Be td He a 20 4 11 A relational database in PROLOG 0 00 04 20 4 12 Natural language processing 2 e 24 5 AILog exercises 24 5 1 AlLog representation sooo o a ee 24 92 Using AMLO Di e neg ase be Gay eh ee Bhan Be
8. and AI are often mentioned in one phrase this does not mean that PROLOG is only suitable for the development of AI programs In fact the language has and is being used as a vehicle for database programming language medical informatics and bioinformatics research And finally the language is used by many people simply to solve a problem they have to deal with resulting in systems that from the user s point of view are indistinguishable from other systems as in particular commercial PROLOG systems offer extra language facilities to develop attractive GUIs 2 2 Characteristics of PROLOG There are a number of reasons why PROLOG is so suitable for the development of advanced software systems e Logic programming PROLOG is a logical language the meaning of a significant frac tion of the PROLOG language can be completely described and understood in terms of the Horn subset of first order predicate logica Horn clause logic So this is the mathematical foundation of the language explaining its expressiveness e A single data structure as the foundation of the language PROLOG offers the term as the basic data structure to implement any other data structure lists arrays trees records queues etc The entire language is tailored to the manipulation of terms Simple syntax The syntax of PROLOG is much simpler than that of the imperative programming languages A PROLOG program is actually from a syntactical point of view simply a seq
9. at the bodies of these rules consist of a single condition X and Y in these rules are variables They seem similar to atoms but are required to start with an upper case letter or underscore Variables can be bound or instantiated to constants or other variables by a process called matching or unification see below Section 4 3 Surely one of the most popular questions asked by American tourists visiting the Nether lands is who predecesses who Now this can be easily formulated into another two rules predecessor X Y parent X Y ruler X ruler Y predecessor X Y ruler X parent X Z predecessor Z Y Note that these rules have multiple conditions constituting the body that must be satisfied in order for a rule to be satisfied Also note the indentation of the body in comparison to the head it makes PROLOG programs more readable The facts and rules above constitute a PROLOG program The clauses of a PROLOG program are loaded into a part of the PROLOG system called the PROLOG database which is rather confusing terminology as a PROLOG system is not a database system It can be invoked by means of queries or goals The complete PROLOG program is included in the file exercise0 pl Consult this file and query the program If the PROLOG system returns with a response you can enter a semicolon 5 Another one is how much their possessions are worth 6 and PROLOG will give an alternative solution If you simp
10. ckboard The material made available in the course will be sufficient for you to complete the course successfully 2 AI programming and representation 2 1 Symbol manipulation AI programs can be written in any decent sufficiently expressive programming language including typical imperative programming languages such as C C and Java However many developers prefer to use programming languages such as PROLOG and Lisp Both languages have a basis which cannot be traced back to the early ideas of computing as state change of variables as holds for the imperative languages but instead to more abstract mathematical notions of computing It is this formal foundation which explains why these two languages are enormously expressive much more than the imperative languages As a consequence it is straightforward to create and manipulate complex data structures in these languages which is not only convenient but really essential for AI as AI people tend to solve complicated problems Although much of what will be said in this introduction also holds for LISP we will not pay further attention to this latter programming language In general LISP is not as closely linked to research on knowledge representation and reasoning as PROLOG This is the main reason why PROLOG has been selected for the course PROLOG is frequently used for the development of interpreters of particular formal lan guages such as other programming languages algebraic or lo
11. creep Fail 8 path b e creep Redo 8 branch a _L155 creep Exit 8 branch a c creep Call 8 path c e creep Call 9 branch c _L167 creep 14 Exit 9 branch c d creep Call 9 path d e creep Call 10 branch d _L190 creep Fail 10 branch d _L190 creep Fail 9 path d e creep Redo 9 branch c _L167 creep Exit 9 branch c e creep Call 9 path e e creep Exit 9 path e e creep Exit 8 path c e creep Exit 7 path a e creep Yes This information can be interpreted as follows The number between parentheses represents the recursion level of the call 7 as a starting level Call is followed by the subgoal that has to be proven Exit indicates that the subgoal has been proven en Fail indicates that proving the subgoal failed If the program as a consequence of a failed subgoal backtracks to a previously considered subgoal then this is indicated by Redo Note that variables are renamed to unique internal names such as _L155 gt The above program is available in the file exercise2 pl Now experiment with the trace facility so that you understand it thoroughly Switch off debug mode by nodebug Selective information of the execution is obtained by means of spy points A spy point is indicated as follows spy lt specification gt where lt specification gt is the name of a predicate or a name follows by the arity number
12. ecessor of Z 1 predecessor1 X Z parent X Z 2 predecessor1 X Z parent X Y predecessor1 Y Z gt Query this program and find out how PROLOG is able to give answers to your queries using PROLOG s debug facilities There are three other declaratively correct specifications of the problem possible which only differ with respect to order of clauses and conditions Firstly the order of the two clauses can be reversed This results in the following program 3 predecessor2 X Z parent X Y predecessor2 Y Z 4 predecessor2 X Z parent X Z gt Ask again a number of queries and compare the results with those obtained for the first program Can you explain the differences It is also possible to interchange the two conditions in the second clause yielding the following program 5 predecessor3 X Z parent X Z 6 predecessor3 X Z predecessor3 X Y parent Y Z gt Which queries will this program be unable to answer Finally we can interchange clause 1 as well interchange both conditions in clause 2 The following result is then obtained 7 predecessor4 X Z predecessor4 X Y parent Y Z 8 predecessor4 X Z parent X Z gt Investigate which queries cannot be answered by this program and try to explain why they cannot 17 4 8 Fail and cut Some of the predicates which PROLOG offers can be used to control PROLOG s execution method in
13. ene ye Be a doe a 25 5 3 Explanation Tacilities Laa B S eee a Bee ee OS a kes 26 5 4 User interactions 4 4 ce 15 Geach Fok wl ee aw ee aa 26 5 5 Model based and probabilistic reasoning 1 Learning outcomes This PROLOG and AILOG practical offers you the opportunity to familiarise yourself with the basic principles of the programming language PROLOG and principles behind knowledge representation and reasoning systems In the practical you will learn e About the role and place of PROLOG in the area of Artificial Intelligence AI and in programming language research more in general See Section 2 e The basic principles of PROLOG by doing a number of exercises described in Section 4 the results you obtain for the two marked exercises should be discussed with the lecturer e How to use AILOG e To use AILOG reasoning systems on your own by making the assignments which will be distributed to you later in the course We will use SWI PROLOG a good PROLOG interpreter and compiler available in the public domain SWI PROLOG is very close to standard PROLOG the examples in this practical manual are therefore based on SWI PROLOG A good book to learn programming in PROLOG in the context of Al is I Bratko PRO LOG Programming for Artificial Intelligence 3rd ed Addison Wesley Harlow 2001 earlier editions are also useful but there are many other good books about PROLOG There is an AILOG manual available on the website and bla
14. erpreter by typing assuming you are in the directory where the file resides exercise0 This is called consulting a file the symbol is the system prompt If a file has the extension pl the extension need not be typed in as the file name is automatically com pleted Hence normally files with extension pl indicate PROLOG programs this convention is unfortunately also used for Perl programs If one prefers to use another extension than pl the full name of the file in between single quotes must be supplied For example prog pro causes the program in the file prog pro to be loaded The above also works for the Windows environment It is also possible although not very convenient to type in a program in the PROLOG system itself This is accomplished by consulting the file user 3http www cs ru nl peterl teaching KeR user The file user represents your keyboard Its input can be terminated by lt cntrl gt d In most cases it is better to use an editor such as emacs or some other editor as these offer editing possibility far superior to the user interface There is normally a special PROLOG mode available for emacs users Note that a program that has been typed in at user is lost when leaving the system In the next sections it is assumed that the meaning of most PROLOG predicates is known The handout Introduction to PROLOG and any book about PROLOG contain descriptions of the standa
15. gical languages and knowledge representation languages in general Languages are defined in terms of preserved key words See http www swi prolog org there are free SWI PROLOG systems available for Linux Mac OS and Windows i e symbolic names with a fixed meaning In Java for instance the keywords class public super are used It is rather straightforward to develop a PROLOG program that is able to identify such keywords and to interpreter these keywords in their correct semantic context Of course this does not mean that it is not possible to develop such interpreters in imperative languages but almost all necessary facilities to do so are already included in any PROLOG system and really constitute the core of the language Compare this to the situation in imper ative programming languages where one needs to resort to preprocessors and class libraries making it often far from easy to understand what is happening In other words the level of abstraction offered by PROLOG is much closer to the actual problem one is trying to solve than to the machine or software environment being used Using abstraction is preferred by most people when developing a program for an actual problem as it means to ignore as many irrelevant details as possible and to focus on the problem issues that really matter When you are sufficiently versed in PROLOG the languages allows you to develop significant programs with only limited effort Although PROLOG
16. he facts about the Dutch Royal Family mother wilhelmina juliana mother juliana beatrix mother juliana christina mother juliana irene mother juliana margriet mother beatrix friso mother beatrix alexander mother beatrix constantijn mother emma wilhelmina father hendrik juliana father bernard beatrix father bernard christina father bernard irene father bernard margriet father claus friso father claus alexander father claus constantijn father willem wilhelmina queen beatrix queen juliana queen wilhelmina queen emma king willem In these facts mother and father are called predicates or functors elements such as beatrix are called constants or atoms an atom is a constant that is not a number The meaning of the fact mother juliana beatrix is that Princess Juliana the previous queen is the mother of Queen Beatrix the present queen The meanings of the other mother and father facts are similar Now if you are either a mother or father of a person you are also seen as the parent of that person This is a general rule which even applies to members of the Royal Family A rule however which uniquely applies to the Royal family is the one which defines kings and queens as rulers These two principles can be formulated as four PROLOG rules parent X Y mother X Y parent X Y father X Y ruler X queen X ruler X king X Note th
17. he unification algorithm is known as the occur check It is often left out for efficiency reasons To make a distinction between unification that includes the occur check and unification without the latter is often called matching 4 4 Backtracking Backtracking is a mechanism in PROLOG that is offered to systematically search for solutions of a problem specified in terms of PROLOG clauses A particular PROLOG specification may have more than one solution and PROLOG normally tries to find one of those When it is not possible to prove a subgoal given an already partially determined solution to a problem PROLOG does undo all substitutions which were made to reach this subgoal and alternative substitutions are tried The search space that is examined by the PROLOG system has the form of a tree More insight into the structure of this space is obtained by a PROLOG program that itself defines a tree data structure 1 branch a b 2 branch a c 3 branch c d 4 branch c e 5 path X X 6 path X Y branch X Z path Z Y Load the file exercise2 pl into the PROLOG interpreter and pose the following queries to the PROLOG database Check the answers returned by PROLOG path a d Figure 1 shows the tree corresponding to the program This figure is useful for understanding the execution steps carried out by the PROLOG interpreter In the next section we shall consider a number of facilities offered by mos
18. hematical logical notion of computing 4 7 The order of clauses and conditions According to the principle of logic programming neither the order of PROLOG clauses nor the order of conditions in the bodies of PROLOG clauses really matters However as a consequence of its fixed backtracking scheme this is not entirely the case for PROLOG For example it is possible that there does exist a solution to a problem according to the logical interpretation of a PROLOG program whereas PROLOG is not able to find it As a consequence any PROLOG programmer requires a good understanding of where and when order in and among clauses matters and when not The program we are going to study in order to get a better understanding of the order issues in PROLOG is available in the file exercise4 pl The following facts concern the relation parent X Y which expresses that X is a parent of Y parent pam bob parent tom bob parent tom liz parent bob ann parent bob pat parent pat jim SThe predicate conc is known in PROLOG as append but as this is often a built in we have renamed append to conc 16 gt Pose a number of queries to the program For example how do you find out what the names are of Tom s children And who are Bob s parents The following two clauses recursively define that X is a predecessor of Z predecessor1 X Z if X is a parent of Z or if there is a person Y such that X is a parent of Y and Y is a pred
19. in included in exercise8 pl 20 employee mcardon 1 5 employee treeman 2 3 employee chapman 1 2 employee claessen 4 1 employee petersen 5 8 employee cohn 1 7 employee duffy 1 9 department 1 board department 2 human_resources department 3 production department 4 technical_services department 5 administration salary 1 1000 salary 2 1500 salary 3 2000 salary 4 2500 salary 5 3000 salary 6 3500 salary 7 4000 salary 8 4500 salary 9 5000 Relational database theory offers a number of useful operations which can be carried out to extract information from a given database The result of these operations is a new relation i e a new set of tuples Typical examples of such database operations are selection projec tion and the join Below we shall discuss simple PROLOG implementations of the selection projection and join just to give you an impression of how such programs may look like The implementation of a more complete relational database package would of course be more involving than would be realistic for this practical We will make use of an SQL like notation as you know SQL is the most popular query language in relational databases The purpose of a selection is to request tuples which fulfil certain conditions with respect to their attribute values Consider for example the query Select all employees from de partment 1 with a salary higher than scale 2
20. losophers will note that we have not really studied the effects of the empty program as the tested program actually consisted of a single clause the query nothing When we type in nothing at all we get the real response to the empty program from PROLOG which is So this is the real nothing we speak of the head and the body of a clause which again is terminology that derives from the procedural interpretation of PROLOG Hence using this terminology a PROLOG clause is defined as clause head body where body is defined as body disjunction disjunction disjunction condition condition condition However even when using the procedural terminology it is difficult to ignore the logical basis of PROLOG as the comma has the meaning of conjunction A AND and the semicolon has the meaning of disjunction V OR We will use both terminologies in this practical to conform to the practice in the PROLOG and logic programming community 4 PROLOG exercises It is assumed you have copied the files to your directory as indicated in Section 3 4 1 Meet The Dutch Royal Family facts queries and rules Consider the following facts concerning the Dutch Royal Family This family is so large that I declare myself unable to unravel the details of the relationships among the members of the family hence only the most obvious facts have been represented but you are invited to exend the program T
21. ly enter lt return gt PROLOG stops looking for alternatives For example enter the following queries parent beatrix alexander parent beatrix X parent beatrix emma parent X Y ruler Y predecessor X beatrix Try to understand the answers returned by PROLOG by studying the program But be careful not to turn into a royalist 4 2 Lists and recursion The list is one of the most popular data structures in PROLOG A list is simply a sequence of elements separated by commas and embraced by brackets e1 C23 gt en Each element e 1 lt i lt n n gt 0 can be an arbitrary PROLOG term including a list Consider now the following list a b c d It consists of four elements where each element in this case is an atom recall that this is a constant symbol that is not a number The following list consists of three elements e1 e2 3 but is actually defined as e1 Ceo Leg where e1 is called the head of the list and e2 e3 is called its tail Thus as you already suspected a list is a term of which the functor from a logical point of view the functor is now not a predicate but a function symbol has two arguments the head and the tail A list containing a single element e is really the following term el J A simplified notation as ej e2 e3 is called syntactic sugar as it makes dealing with lists easier Syntactic sugar makes your programs more tasty
22. n in this case is equality of tuples in the two relations concerning the attribute scale In SQL like notation JOIN employee WITH salary WHERE employee scale salary scale The following two clauses offer an implementation of the join operator join X Y Z call X call yY call Z write X write Y nl fail join _ _ _ 23 The first and second arguments represent relations the third argument is used to specify join conditions For example join employee Name Department_N Scalel salary Scale2 Amount Scalel Scale2 will yield the requested result P 2 Express in PROLOG a join between the relations employee and department and inspect the result 4 12 Natural language processing From its inception PROLOG has been enormously popular with researchers in the field of natural language processing Due to its declarative nature the language is both suitable for the development of programs that analyse sentences as well as for language generation In this case we only consider a very simplistic example of a program as natural language processing is a field in its own right involving many special issues The following program is given in the file exercise9 pl sentence X noun_phrase X Y verb_phrase Y noun_phrase X Y Y noun X noun_phrase X1 X2 X3 Y Y article X1 adjective X2 noun X3 verb_phrase X Y Z verb X noun_phrase Y Z Develop a small dictiona
23. ng query p X a f Y g b p b a f c g b leads to the following substitutions X f b Y c because e the two functors of the two terms are equal both p e to make the first arguments syntactically equal the term f b has to be substituted for the variable X e the second arguments are already equal e in order to make the third arguments equal we have to unify the terms f Y g b and f c g b The functors of these two arguments are already equal as are the second arguments of the terms If we substitute the term c for the variable Y the second arguments will also have become equal If two terms have been successfully unified it is said that a match has been found otherwise there is no match Investigate whether the following pairs of terms match and if they do which substitutions do make them equal p f X g8 b Y and p h q Y g b p X a g X and p f b a g b Ca b and X Y p X f X and p Y Y It is not possible to find a match for the last pair of terms Yet PROLOG is not able to recognise this fact First the matching algorithm substitutes Y for X 12 X Y The second arguments of p would become equal if Y f X This creates a cyclic binding between the variables X and Y hence it is not possible to unify these two terms Many PROLOG interpreters however are not able to detect this fact and get stuck in an infinite loop What is missing in the implementation of t
24. nsition s1 a s2 transition s1 b s1 transition s2 b s3 transition s3 b s4 silent s4 s3 The following rules investigate whether a string is either or not accepted accept S end S accept S X Rest transition S X S1 accept S1 Rest accept S String silent S S1 accept S1 String P 1 Investigate using this program which input string with 3 and 4 symbols are accepted by the finite automaton The program is included in the file exercise6 pl The first argument of accept is the initial state the second argument is a string represented as a list of symbols 19 4 10 Sorting As you already know there are quite a number of different algorithms for sorting elements of a set or multiset assuming that a total order is defined on these elements One of the simplest is the well known bubble sort algorithm In the bubble sort two successive elements in a sequence of here numbers are examined If they are in the right order the algorithm proceeds to the next pair otherwise the two numbers are interchanged and the algorithm proceeds by considering the next pair This goes on until there are no elements left which need to be interchanged Both worst and average case time complexity of the bubble sort is quadratic It is quite straightforward to express this algorithm in terms of a PROLOG program Assuming that a set of elements is represented as a list one possible program is bubsort L S conc X A
25. particular ways Two important ones are the fail and the cut predicate If the fail predicate is used as a condition then this condition will always fail regardless of anything else hence of course the name of this predicate Usually the fail predicate is used to enforce backtracking in order to obtain or consider alternative solutions for a problem Now consider the program given in the file exercise5 pl elementi X X _ elementi X _lY element1 X Y all_elementsi L elementi X L write X nl fail all_elementsi _ By means of the clauses all_elements1 the elements of a list L are printed one by one Note that the element1 predicate is called in all_elements1 Experiment with the all_elements1 program Do you understand why there is also a second all_elements1 clause included Next the effects of the cut predicate on program execution are considered Whereas the fail predicate enforces backtracking the cut tries to prevent it So these two predicates are more or less complementary Consider the following use of the cut element2 X X _ element2 X _IY element2 X Y all_elements2 L element2 X L write X nl fail all_elements2 _ Study the difference in behaviour between all_elements1 and all_elements2 and try to explain this difference 4 9 A finite automaton A finite automaton is a mathematical object which is used to determine whether a particular string of symbols has
26. rd predicates 3 2 PROLOG programs A PROLOG program consists of a sequence of clauses a PROLOG clause is either e a fact e a query or goal or e a rule Either or all of these may be empty so the simplest PROLOG program is nothing Let us see what response we get from PROLOG when trying to execute the empty program knuth 1 gt pl Welcome to SWI Prolog Multi threaded Version 5 6 35 Copyright c 1990 2007 University of Amsterdam SWI Prolog comes with ABSOLUTELY NO WARRANTY This is free software and you are welcome to redistribute it under certain conditions Please visit http www swi prolog org for details For help use help Topic or apropos Word nothing WARNING Undefined predicate nothing 0 No The PROLOG prompt basically asks the user to type in a query What is typed in is shown in italised bold face and includes the terminating dot PROLOG issues a warning as it does not recogise the query nothing However this warning is not part of PROLOG but a feature of SWI PROLOG to help in program debugging The response of PROLOG to this empty program is No which means that this program has failed 4 Above we have only employed the declarative terminology of PROLOG which views PRO LOG as a logical language There also exists a procedural terminology where facts and rules are called procedure entries and queries or goals are called procedure calls In addition Deep Phi
27. ry that can be used to generate sentences Why are the predicate noun_phrase and verb_phrase supplied with a second argument Is this program also capable of generating sentences We could also have made use of the conc predicate in developing this program see exercise3 pl How would this have affected the program 5 AILog exercises 5 1 AlLog representation As PROLOG AILOG supports Horn clauses However it is preferred to use in AILOG a syntax that slightly different from PROLOG A clause has to conform to the following syntax clause head lt body 24 In a body one is advised to use the ampersand amp for logical conjunction rather than the comma This allows making a syntactic distinction between PROLOG programs and AILOG representations although AILOG is also able to parse PROLOG syntax 5 2 Using AlLog First one needs to download the ailog2 p1 PROLOG program program available at http www cs ru nl peterl teaching KeR AlLog ailog2 pl The AILOG user manual can be downloaded at http www cs ru nl peterl teaching KeR AlLog ailog man pdf Next AILOG must be loaded into PROLOG ailog2 AlLog Version 2 3 3 Copyright 2009 David Poole AILog comes with absolutely no warranty A11 inputs end with a period Type help for help ailog One can load knowledge bases into AILOG using the load command ailog load example However it is also possible to communicate clauses to AILOG man
28. t PROLOG systems which assist in debugging programs 4 5 Tracing and spying PROLOG systems offer a number of facilities to debug a program Two of those techniques will be considered in this section They are probably quite useful when working through the remainder of the exercises A program can be debugged by using 13 Figure 1 A binary tree e the trace predicate which makes sure that every execution step is shown e selective tracing of a program which is made possible by so called spy points This is accomplished by the spy predicate By means of an example we illustrate below how debugging with those two facilities works in practice After consulting a program the trace facility can be switched on by the query trace For example if after loading the file exercise2 pl as described in Section 4 4 into PROLOG and after switching on the trace facility and querying PROLOG trace Yes path a e the following is shown Call 7 path a e The question marks indicates that the user may enter an option to change the behaviour of the interpreter A list of all possible options is obtained by entering the letter h Each next execution step is shown by entering lt return gt path a e Call 7 path a e creep Call 8 branch a _L155 creep Exit 8 branch a b creep Call 8 path b e creep Call 9 branch b _L178 creep Fail 9 branch b _L178
29. term can both be a condition and a head of a clause but also a structure deeply nested into a condition or head To answer a query the PROLOG interpreter starts with the first condition in the query taking it as a procedure call The PROLOG database is subsequently searched for a suitable entry to the called procedure the search starts with the first clause in the database and continues until a clause has been found which has a head that can be matched with the procedure call A match between a head and a procedure call is obtained if there exists a substitution for the variables occurring both in the head and in the procedure call such that the two become syntactically equal after the substitution has been applied to them Such a match exists e if the head and the procedure call contain the same predicate and e if the terms in corresponding argument positions after substitution of the variables are equal one then also speaks of a match for argument positions 11 Applying a substitution to a variable is called instantiating or binding the variable to a term For example the query parent X Y yields the following instantiations given the program in the file exercise0 pl discussed in Section 4 1 X Y juliana wilhelmina 7 A user can force unifying two terms by means of the infix predicate functor As an example consider the following two terms p X a f Y g b and p f b a f c g b The followi
30. the right structure or syntax Finite automata are for example used to build compilers of programming languages but also to build simulators 18 An automaton is always in a one of a given set of states One of those states is the initial state another one is the final state By examining one of the symbols in the given string the automaton may go to another state as specified by means of a transition function If the automaton is in the final state after processing the string it is said that the string is accepted otherwise it is said that the string has been rejected For the automaton that is considered here the following set is defined S 81 2 53 sa Assume that s is the initial state and that s3 is the final state The transition function is defined by means of the following productions 1 gt as 1 gt asa 1 gt bs S2 bs3 Sa bs4 S4 gt 83 The last transition is a silent transition the automaton simply moves to another state without reading a symbol The transition function can be easily specified in PROLOG for example the predicate transition s1 c s2 says that the automaton changes from state s to s2 after reading the symbol c The condition silent s1 s2 represents a silent transition The fact that s3 is a silent transition is indicated by the predicate end The transition function as defined above can therefore be defined in PROLOG as follows end s3 transition si a s1 tra
31. ties offered by AILoG are e a knowledge representation and reasoning system that supports different forms of logical and probabilistic reasoning e an ask tell interface that allow users to communicate with AILoG e explanation facilities allowing users to explore why and how the system did or did not derive a particular fact 3 Introductory remarks about PROLOG By means of a number of small PROLOG programs which can be found in the directory vol practica IS Prolog and as a zip file on the course s website the most important features of the PROLOG language will be studied in this practical The programs are available in the following files exercise0 pl facts queries and rules exercisel pl lists and recursion exercise2 pl backtracking exercise3 pl parameters exercise4 pl order of clauses exercise5 pl fail and cut exercise6 pl finite automaton exercise7 pl sorting exercise8 pl relational database exercise9 pl natural language processing Copy these files to your own directory 3 1 PROLOG under Linux and Windows Under Linux and Windows SWI PROLOG is activated and reads in a PROLOG program by clicking on the program which should have the pl1 extension in order to be recognised One can quit the system by the command halt The SWI PROLOG system can also be activated under Linux by typing in pl A program stored in a file for example the file exercise0 pl can be read into the PROLOG int
32. tisfied by the selected tuples For example all employees in department 1 with a salary scale higher than 2 are selected by the following query selection employee Name Department_N Scale Departments_N 1 Scale gt 2 Design a PROLOG query to select those employees who earn between 3 000 and 4 500 per month Also select all employees who are in salary scale 1 and working in department 1 The projection operator in relational database theory is used to select some attributes or columns in the corresponding tables from a relation For example the query give for all employees only the name and scale in SQL like notation SELECT name scale FROM employee However the PROLOG query does again give rise to the selection of a single tuple 7 employee Name _ Scale But as you already know by using the operator the other tuples can be selected as well Type in the above given PROLOG query Can you explain why we use here the anonymous variable _ As you may have guessed the resulting PROLOG implementation of the projection operator is quite similar to the implementation of the selection operator discussed above 22 projection X Y call X write Y nl fail projection _ _ The first argument of projection should be the relation that is being projected the second argument lists the attributes on which the relationship must be projected For example name and scale of employees are obtained as
33. ually by means of the ask tell command interface By means of the tell command clauses are added to the knowledge bases ailog tell parent X Y lt mother X Y ailog tell mother juliana beatrix One can query the knowledge base by means of the ask command ailog ask parent X Y Answer parent juliana beatrix If one wishes to inspect the content of the knowledge base the command listing can be used ailog listing parent A B lt mother A B mother juliana beatrix ailog Note that the variable names X and Y are renamed gt Compare the PROLOG program exercise0 pl to the AILOG knowledge base exercise10 ail What are the differences gt Load the knowledge base exercise10 ail into AILOG and inspect its content 25 gt Ask questions to the knowledge base and compare the results to those obtained for exercise0 pl Do you notice differences You may have noticed that AILOG does not go into infinite recursion rather it used a depth bound to limited recursion The used can increase the depth bound interactively when necessary 5 3 Explanation facilities The userinterface of AILOG allows determining how a particular fact was derived why a particular fact was not derived and why a particular fact was derived This is done by the commands how whynot and why respectively Have a look at the following example ailog ask predecessor X Y Answer predecessor emma beatrix ok more how help
34. uence of terms For example the following PROLOG program p X q X corresponds to the term p X q X Whereas the definition of the formal syntax of a language such as Java or Pascal requires many pages PROLOG s syntax can be described in a few lines Finally the syntax of data is exactly the same as the syntax of programs SWI PROLOG offers a special object oriented library for GUI development called XPCE This is not covered in this practical however e Program data equivalence Since in PROLOG programs and data conform to the same syntax it is straightforward to interpret programs as data of other programs and also to take data as programs This feature is of course very handy when developing interpreters for languages e Weak typing Types of variables in PROLOG do not have to be declared explicitly Whereas in C or Java the type of any object for example int real char needs to be known before the compiler is able to compile the program the type of a variable in PROLOG only becomes relevant when particular operations are performed on the variable This so called weak typing of program objects has as a major advantage that program design decisions can be postponed to the very last moment This eases the programmer s task However weak typing not only comes with advantages as it may make finding program bugs more difficult Expert programmers are usually able to cope with these problems while in addition most PROLOG s
35. ystems come with tools for the analysis of programs which may be equally useful for finding bugs e Incremental program development Normally a C or Java program needs to be developed almost fully before it can be executed A PROLOG program can be developed and tested incrementally Instead of generating a new executable only the new program fragments need to be interpreted or compiled It is even possible to modify a program during its execution This offers the programmer the possibility of incremental program development a very powerful and flexible approach to program development It is mostly used in research environments and in the context of prototyping e Extensibility A PROLOG system can be extended and modified It is even possible to modify the PROLOG language and to adapt both its syntax and semantics to the needs For example although PROLOG is not an object oriented language it can be extended quite easily into an object oriented language including primitives for inheritance and message passing Compare this to the task of modifying a Java interpreter into a PROLOG compiler something which would require an almost complete redesign and re implementation of the original Java system 2 3 AlLog Rather than a programming language such as PROLOG AILOG is a knowledge representation and reasoning system built on top of PROLOG The language one can use in AILOG for modelling however is very similar to that of PROLOG The main facili
Download Pdf Manuals
Related Search