Transcription of Introduction to Prolog Programming
1 Institute for Logic, language and ComputationLecture NotesAn Introduction to Prolog ProgrammingUlle EndrissUniversiteit van Amsterdamc by Ulle Endriss, University of Amsterdam 1 September 2014 PrefaceThese lecture notes introduce the declarative Programming language Prolog . The em-phasis is on learning how to program, rather than on the theory of logic , a short chapter on the logic foundations of Prolog is included as examples have been tested using SWI- Prolog ( ) and can be ex-pected to work equally well with most other Prolog systems. These notes have originallybeen developed for a course I taught at King s College London in 1999 and , August present version corrects a number of minor errors in the text, most of whichhave been pointed out to me by students following a number of courses I have given atthe University of Amsterdam since , September The Getting Started: An Example.
2 Prolog Syntax .. , Programs and Queries .. Built-in Predicates .. Answering Queries .. Execution .. A Matter of Style .. Exercises .. 122 List Notation .. Head and Tail .. Some Built-in Predicates for List Manipulation .. Exercises .. 193 Arithmetic Theis-Operator for Arithmetic Evaluation .. Predefined Arithmetic Functions and Relations .. Exercises .. 234 Precedence and Associativity .. Declaring Operators withop/3.. Exercises .. 315 Backtracking, Cuts and Backtracking and Cuts .. Revisited .. with Backtracking .. Cuts .. with Cuts.
3 Negation as Failure .. Closed World Assumption .. \+-Operator .. Disjunction .. Example: Evaluating Logic Formulas .. Exercises .. 466 Logic Foundations of Translation of Prolog Clauses into Formulas .. Horn Formulas and Resolution .. Exercises .. 53A Recursive Complete Induction .. The Recursion Principle .. What Problems to Solve .. Debugging .. 57 Index59 Chapter 1 The BasicsProlog ( Programming inlogic) is one of the most widely used Programming languages inartificial intelligence research. As opposed to imperative languages such as C or Java (thelatter of which also happens to be object-oriented) it is adeclarativeprogramming lan-guage.
4 That means, when implementing the solution to a problem, instead of specifyinghowto achieve a certain goal in a certain situation, we specifywhatthe situation (rulesandfacts) and the goal (query) are and let the Prolog interpreter derive the solution forus. Prolog is very useful insomeproblem areas, such as artificial intelligence, naturallanguage processing, databases, .. , but pretty useless in others, such as graphics ornumerical following this course, you will learn how to use Prolog as a Programming languageto solve practical problems in computer science and artificial intelligence. You will alsolearn how the Prolog interpreter actually works. The latter will include an introductionto the logical foundations of the Prolog notes cover the most important Prolog concepts you need to know about, butit is certainly worthwhile to also have a look at the literature.
5 The following three arewell-known titles, but you may also consult any other textbook on Prolog . I. Programming for Artificial edition, Addison-Wesley Publishers, 2012. F. W. Clocksin and C. S. in edition, Springer-Verlag, 2003. L. Sterling and E. Art of edition, MIT Press, Getting Started: An ExampleIn the Introduction it has been said that Prolog is a declarative (or descriptive) in Prolog means describing the world. Using such programs means askingProlog questions about the previously described world. The simplest way of describingthe world is by statingfacts, like this one:12 Chapter 1. The Basicsbigger(elephant, horse).This states, quite intuitively, the fact that an elephant is bigger than a horse.
6 (Whetherthe world described by a Prolog program has anything to do with our real world is, ofcourse, entirely up to the programmer.) Let s add a few more facts to our little program:bigger(elephant, horse).bigger(horse, donkey).bigger(donkey, dog).bigger(donkey, monkey).This is a syntactically correct program, and after having compiled it we can ask the Prologsystem questions (orqueriesin proper Prolog -jargon) about it. Here s an example:?- bigger(donkey, dog).YesThe querybigger(donkey, dog)( , the question Is a donkey bigger than a dog? )succeeds, because the factbigger(donkey, dog)has previously been communicated tothe Prolog system. Now, is a monkey bigger than an elephant??- bigger(monkey, elephant).
7 NoNo, it s not. We get exactly the answer we expected: the corresponding query, namelybigger(monkey, elephant)fails. But what happens when we ask the other way round??- bigger(elephant, monkey).NoAccording to this elephants are not bigger than monkeys. This is clearly wrong as far asour real world is concerned, but if you check our little program again, you will find thatit says nothing about the relationship between elephants and monkeys. Still, we knowthat if elephants are bigger than horses, which in turn are bigger than donkeys, which inturn are bigger than monkeys, then elephants also have to be bigger than monkeys. Inmathematical terms: the bigger-relation is transitive. But this has also not been definedin our program.
8 The correct interpretation of the negative answer Prolog has given is thefollowing: from the information communicated to the systemit cannot be provedthatan elephant is bigger than a , however, we would like to get a positive reply for a query likebigger(elephant,monkey), we have to provide a more accurate description of the world. One way of doingthis would be to add the remaining facts, such asbigger(elephant, monkey), to ourprogram. For our little example this would mean adding another 5 facts. Clearly toomuch work and probably not too clever far better solution would be to define a new relation, which we will callis_bigger, as the transitive closure (don t worry if you don t know what that means)Ulle Endriss.
9 And Introduction to Prolog Programming3ofbigger. AnimalXis bigger than animalYeither if this has been stated as a fact or ifthere is an animalZfor which it has been stated as a fact that animalXis bigger thananimalZand it can be shown that animalZis bigger than animalY. In Prolog suchstatements are calledrulesand are implemented like this:is_bigger(X, Y) :- bigger(X, Y).is_bigger(X, Y) :- bigger(X, Z), is_bigger(Z, Y).In these rules:-means something like if and the comma between the two termsbigger(X, Z)andis_bigger(Z, Y)stands for and .X,Y, andZare variables, whichin Prolog is indicated by using capital can think of the thebigger-facts as data someone has collected by browsingthrough the local zoo and comparing pairs of animals.
10 The implementation ofis_bigger,on the other hand, could have been provided by a knowledge engineer who may notknow anything at all about animals, but understands the general concept of somethingbeing bigger than something else and thereby has the ability to formulate general rulesregarding this relation. If from now on we useis_biggerinstead ofbiggerin ourqueries, the program will work as intended:?- is_bigger(elephant, monkey).YesProlog still cannot find the factbigger(elephant, monkey)in its database, so it triesto use the second rule instead. This is done bymatchingthe query with the head of therule, which isis_bigger(X, Y). When doing so the two variables get instantiated:X =elephantandY = monkey.
