HOME | MODULE | CURRICLUM Introduction to Prolog Author: Winfred Phillips Prev [Introduction to Logic for ProtoThinker] Next [Introduction to Natural Language Processing] What is Prolog? Prolog is a programming language particularly well suited to logic and artificial intelligence programming. "Prolog" in fact stands for "Programming in Logic." In this brief introduction we will try to give you a little taste of Prolog without bogging you down with a great deal of technical jargon. By the end of this section you should be able to use Prolog and write some little programs that give you a feel for the language. Feel free to consult the books and Web sites on Prolog mentioned later should you want to go further. A person uses a computer programming language to direct a computer to perform desired tasks. You might be familiar already with the names of some common programming languages, such as C, Basic, Pascal, or Cobol. Not all programming languages work the same way. In languages you might be familar with already, such as C, the programmer commonly tells the computer that some letters or words are to be variables, for example that the letter "X" is to be considered a variable that will stand for an integer number (such as 1, 2, etc.). The C program might then involve a loop mechanism (a repeating set of commands) in which the computer assigns different integer values to X every time it goes through the loop. In fact a large part of the program could consist of variable declarations, "iterative" loops, calculations of values, and assignments of values to the variables. The programmer tells the programmer not only what to do, but how to do it. A Prolog program is likely to look a little different than a typical C program. The programmer tells the computer less the "how" than the "what." For example, in Prolog the programmer might begin by telling the computer a bunch of "facts." The facts can be about characteristics of people or things in the world ("Spot is frisky"), about relations of such things ("John is the father of Susan"), and about "rules" pertaining to such facts ("Scott is the grandfather of Susan" is true if "Scott is father the John" is true and "John is the father of Susan" is true). The Prolog program could then be used to ask the computer about the facts already given and the computer would be able to provide answers. Given the facts in the previous paragraph, if the computer is asked "Is John the father of Susan?" it would reply "Yes." If asked, "Is John the father of James" it would reply "No" because it was not given that fact or other facts from which it could be deduced. Of course, Prolog, like any other common programming language, will not be able to process ordinary English sentences such as those given above; rather it requires the programmer to write statements in a particular way . The programmer must know how to phrase Prolog sentences properly. In a moment we will show you how to write some simple Prolog statements, so that you can directly use the Prolog facility (PT-Prolog) within PT-Thinker. But let's point out that you don't have to know Prolog in order to use its logical abilities - that is where PT-Thinker can help you. PT-Thinker is a Prolog program that can take ordinary English sentences and translate them into a form suitable for processing by Prolog. So you can see the kind of logical inferences PT-Thinker can make by telling PT-Thinker facts and then seeing how it deduces conclusions from those facts. As already mentioned, should you decide to do so you can also use the Prolog facility within PT-Thinker to give the computer such facts and questions phrased in the Prolog language. How to Write Prolog Statements Let's start off with some examples of Prolog statements. Note that Prolog is case sensitive, that is, capital letters are considered different than lower-case letters, so don't just substitute an "A" for an "a" and assume it will mean the same thing. Let's tell the computer some facts about a family we know. We'll put the Prolog statement after the English statement. English Prolog John is the father of Susan. father(john,susan). John is the husband of Martha. husband(john,martha). John eats pizza. eats(john,pizza). Susan eats pizza. eats(susan,pizza). Martha eats pizza. eats(martha,pizza). Susan eats oranges. eats(susan,oranges). John bought pizza for Martha. bought(john,pizza,martha). Susan is tired. tired(susan). Now let's talk about these statements. We can define a fact in the Prolog language by placing the verb or adjective first and the relevant related nouns in parentheses. The period defines the end of the statement. (Notice that we aren't using capital letters to start the names; capital letters or terms starting with them we reserve for variables.) We would type the above facts and then load them into Prolog. The exact command here may vary with the specific Prolog program/version with which one is working. (In PT-Thinker Prolog, one first types "assert" to enter the mode for fact loading, types in the statements, and then enters F10 to load the facts.) Think of this loading process as teaching Prolog the above facts. Prolog then responds with a "prompt," (such as "?-"), that is, the opportunity for the user to ask questions. Let's continue with examples, but this time with questions you can ask Prolog. Below are sample English questions, their Prolog equivalent, and the answer from Prolog. Assume we have loaded the above facts into Prolog already. English question Prolog (at prompt ?-) Prolog responds Is John the father of Susan? father(john,susan). yes (or true) Is Susan tired? tired(susan). yes Is Martha tired? tired(martha). no (or false) Who is tired? tired(X). X = susan Who is the husband of Martha? husband(X,martha). X = john Who eats pizza? eats(X,pizza). X = john Who else eats pizza? merely hit spacebar X = martha Who else eats pizza? hit spacebar again X = susan Who else eats pizza? hit spacebar yet again no When we ask Prolog above about John being the father of Susan, we do not have to change the form of the Prolog statement from that which we used to tell Prolog that John is the father of Susan. This same statement may be used to tell the computer the fact initially or inquire about it later. The computer knows it is an inquiry in the second circumstance because we have typed it in response to the Prolog prompt, rather than loading it in as a fact. Note that we use the variable letter "X" to ask the computer who is tired ("tired(X).") and who Martha's husband is ("husband(X,martha)."). Another way to translate these Prolog statements is as "Give me all those who are tired." and "Give me all those who are a husband of Martha." We use the same strategy when asking about who eats pizza ("eats(X,pizza).". In such cases, Prolog's response ends by asking us in effect "Do you want me to look for another?" In PT-Prolog, we signal yes by hitting our space bar, and Prolog attempts to find another. When there are no more to find, it responds "no." (In other Prolog facilities, one may press the "return" key rather than the spacebar, and a semi-colon may end the line rather than a question asking us if we want to find another.) At this point you can go to the PT-Prolog facility within PT-Thinker, enter some facts, and ask some questions. For a start you might put in facts about countries and capitals ("capital(london,england") and ask Prolog to give them back to you ("capital(X,france)") or tell you the truth of statements ("capital(london,germany)"). Or type in some facts about particular people and the foods they like or the colors they prefer. How Prolog satisfies goals When we ask the computer a question, it looks back through the facts it has been given and tries to find a match. Prolog will search the list of facts you gave it (entered in an earlier step) from the top with the goal of "satisfying" the question. If a question such as "eats(john,pizza)" is satisfied by finding it as a fact, Prolog will report "yes" or "true" (depending on the particular Prolog system). If a sentence such as "eats(X,pizza)." is satisfied by finding a facts about someone who eats pizza, Prolog responds with the name of the X who satisfies it. Note that the computer only knows what you've told it (or loaded into it). If you ask it whether Cincinnati is a city in Ohio, it looks to see if it has been given that information or other information from which it can deduce this. If it cannot find any such information, it reports "no." It will report this even though Cincinnati really is a city in Ohio. The computer has no way of knowing Cincinnati is an Ohio city apart from having been given that fact earlier. So "no" here from the computer should be interpreted more as "was not able to verify" or "did not find a match for this claim" rather than "this statement is false in the real world." Consider the following: English Prolog (at prompt ?-) Prolog response Who eats pizza and oranges? eats(X,pizza), eats (X,oranges). susan This statement, in Prolog, asks for Prolog to find an X such that it true both that X eats pizza and that X eats oranges. The comma acts as an "and" here. Prolog starts at the top of the list of facts it has been given and tries to satisfy the first part, and it finds that John eats pizza. It then tries to satisfy the second part with john for X (X is instantiated to john), starting at the top of the list, since this is a new goal. But it fails to find that John eats oranges. (Recall that we told it that John eats pizza but not that John eats oranges.) So it backtracks to where it previously found that John eats pizza and tries to resatisfy the statement with a different X. It finds that Susan eats pizza (X is instantiated to susan now), and so it then tries to satisfy "susan eats oranges" by starting at the top of the list. It finds this as a fact, so it then gives the response of "susan." Due to the way Prolog satisfies goals, sometimes Prolog will engage in a search that starts at the top of the list (if it takes it to be a new goal) and other times backtrack to where it last satisfied the goal (if it is trying to resatisfy a goal). This needs to be taken into account when designing a complex program; sometimes Prolog can engage in too much backtracking in attempting to resatisfy goals, and in this case a "cut" ("!") can be introduced into the statement to prevent backtracking beyond the point of the cut. To find out more about backtracking and the cut please consult a Prolog text or tutorial. Rules Now that we understand the structure of simple Prolog statements and queries, we can investigate some more complicated statements. We can give Prolog some facts about conditionals, that is, what happens if something else is the case. English Prolog Martha is the wife of John, if John is the husband of Martha. wife (martha, john) :- husband (john, martha). John converses with anyone, if that person fancies baseball and is smart converses (john, X) :- fancies (X, baseball), smart (X). A good way to look at Prolog's handling of such statements is the following. To Prolog, the first statement is interpreted as a rule to the effect that "If "husband (john, martha)" succeeds, then "wife (martha, john)" succeeds. The second statement is "converses (john, X)" succeeds if "fancies (X, baseball)" succeeds and "smart (X)" succeeds. The ":-" symbols tell Prolog how to read the rule. As we've said, in Prolog we give the computer facts and rules about facts and then we can ask it questions. All these facts and rules we give it are stored in an internal database, and we can save this database in the form of a file that we can use in a later session. If we don't save it, the computer will not "remember" it if we turn off the computer and run Prolog later. Prolog elements We've already talked about variables, which are letters or phrases that can assume any value. Conventions vary, but traditionally variables are capital letters, words starting with capital letters, words starting with an underscore (_), or an underscore itself (called the "anonymous" variable). Prolog recognizes ordinary words (beginning with a lower case letter, with no spaces), or words surrounded by single quotation marks (these can include spaces and start with capital letters). All these are taken as constants, not variables. Prolog can recognize integers (such as -244, 0, 3, etc.), and some versions can recognize floating point numbers (such as 3.45, -22.005, etc.). Another type of data recognized by Prolog are structures, such as "state(Illinois)" and "shirt(brand(izod))." We've already seen these. And Prolog can handle lists. You give Prolog a list of elements by enclosing it in brackets, as in [baseball,football,basketball,soccer]. and [a,b,c]. Prolog can handle a list by treating it as having a head and a tail. The head is the first element in the list, and the tail is everything after the head. So in the above example of the list [a,b,c], the head is "a" and the tail is the remaining list "b,c." The division between head and tail can be indicated by using "|" as in the case of a list with a head of "a" and a tail of the rest of the list: [a|b,c,d,e]. Prolog also allows one to signify the head and the tail of a list using variables and the symbol "|" as in "[X|Y]." Here the X denotes the head of the list and the Y denotes the tail of the list. Or consider the use of "[a|T]" to indicate all of the lists with "a" as the head and anything as the tail; "[H|b]" indicates all of the lists with anything as the head and "b" as the tail. In this way we can ask the computer to search for lists that match a particular pattern, and it will find lists that instantiate that pattern. Here are some examples: List using "|" Lists that instantiate it (match its pattern) [X|Y] [a,b,c,d] X = a Y = [b,c,d] [X,Y|Z] [a,b,c,d], X = a, Y = b, Z = [c,d] [X,Y,Z|A] [dogs,cats,birds,fish,lizards], X = dogs, Y = cats, Z = birds, A = [fish,lizards] The predefined predicate "append" can be used in Prolog to join lists together. For example, "append([1,2,3],[4,5,6],X)." will cause Prolog to reply "X = [1,2,3,4,5,6]". Arithmetic Prolog can handle arithmetic in a pretty normal fashion. Note the following Prolog symbols: = indicates "equals" \= indicates "is not equal" < indicates "is less than" > indicates "is greater than" =< indicates "is less than or equal to" >= indicates "is greater than or equal to" + indicates "plus" - indicates "minus" / indicates "divided by" * indicates "multiplied by" To do arithmetic, Prolog accepts notation in a variety of orders, the easiest to follow being the traditional "infix" manner such as appears in the following: 5*6 10/2 2+3 7-5 If you leave out clarifying parentheses in complex expressions, Prolog solves them the way we learned in elementary school, with multiplication evaluated before addition, etc. Note that to get Prolog to actually evaluate each of the above expressions to an answer, you have to use "is." A is 5*6 B is 10/2 C is 2+3 D is 7-5 Prolog then gives you the value of the variable A, for example. You might try some arithmetic with Prolog - it's really easy. What is 5*651+4-77+34*46+333*22-5642? Other examples of Prolog statements and capabilities To help you get a better feel for Prolog, below are some additional examples of Prolog interpretations of English sentences. English Prolog John eats a pepperoni pizza. eats (john, pizza (pepperoni)). X and Y are parents of Z if X is the mother of Z and Y is the father of Z parent(X,Y,Z) :- mother(X,Z) , father(Y,Z). Sparky barks at anyone who walks quickly. barks(sparky,X) :- walks(X,quickly). A equals B A = B. A does not equal B A /= B. We can briefly mention some other Prolog matters. One can specify that an output appear on the computer screen by using the predefined predicate "write." For example, suppose that the variable X has been instantiated to "socrates." To get the computer to show "socrates" on the screen, type "write(X)." "nl" takes you to the next line. "tab(14)" moves the cursor 14 spaces to the right; substitute any desired integer for 14 to move that many spaces. The predefined predicate "read" will read in any term that you type (follow the term with a period and a space). "read(X)" reads in the next term and instantiates it to the variable X. How to symbolize logic in Prolog Deductive logic concerns itself with valid arguments in the sense of one or more statements (premises) from which another statement (the conclusion) follows necessarily. To capture the logic of the kinds of statements used in arguments, logicians use propositional logic and prediciate logic. Propositional logic involves the way in which statements are connected into more complex compound statements using "truth-functional" connectives such as "and," "or," "not," and "if...then." Some types of arguments are valid for reasons other than the operation of these connectives, and so logicians rely on predicate logic to get inside of each statement and symbolize the subjects and predicates with logical symbols. For a fuller discussion of logic see the logic section on these Web pages. Prolog is ideally suited to dealing with logical arguments. However, the syntax that must be used in Prolog to handle many types of logical argument is called "clausal" form. Translating most propositional logic and first-order predicate logic statements and arguments into clausal form is too complicated for this introduction to Prolog; you are urged to consult a book on Prolog for more information. We can still get a feel for how Prolog can handle logic by seeing how it deals with some simple arguments whose validity is truth-functional (propositional logic) and some simple syllogisms whose predicate logic translation is simple enough to avoid the clausal form translation issue. Some of the inferences in the above discussion have shown you simple truth-functional arguments already. For example, Modus Ponens is the form of the following argument If the assignment is due tomorrow, then we're all in deep yogurt. The assignment is due tomorrow. therefore We're all in deep yogurt. The premises and conclusion can be put into a format Prolog can process by the following: deepyogurt(we) :- duetomorrow(assignment). duetomorrow(assignment). deepyogurt(we). Thus Prolog can be given the premises as facts, and if you ask it about the conclusion, it will respond "yes" or "true" (depending on the version of Prolog used). If you like you can make these predicate names shorter or longer, of course. Syllogisms with affirmative, universal statements are also easily translated and tested for validity in Prolog. Consider the following syllogism: All cats are mammals. All mammals are animals. therefore All cats are animals. It's easy to see that this is a valid argument. How can we put it into Prolog? The way Prolog is constructed allows it to interpret variables as universally quantified already. That is, the variable "X" will stand for all X's automatically. So the above argument in a form Prolog can understand will be: mammal(X) :- cat(X). animal(X) :- mammal(X). animal(X) :- cat(X). If the premises are given to Prolog as facts, and you ask it about the conclusion, it will reply in the affirmative, thus showing the argument's validity. In a fashion similar to the above, you may wish to construct your own simple arguments and test their validity using the PT-Prolog facility within PT-Thinker. Some elementary exercises Now that you have an idea of how Prolog programming works, try out some exercises to get a better feel for Prolog. The exercises below are more like little games, with the answers available on another Web page. Given: If John feels hungry, then he eats quickly. If he eats quickly, he gets heartburn. If he gets heartburn, he takes medicine. John feels hungry. Conclusion: Given the above facts, what can we conclude about John taking medicine? Does he or doesn't he? The above argument is a sorites argument, or it can be interpreted as a series of modus ponens arguments. This one is easy! Of course John takes medicine. Now can you get Prolog to tell you this? Answer: give Prolog the following facts: eats(john,quickly) :- feels(john,hungry). gets(john,heartburn) :- eats(john,quickly). takes(john,medicine) :- gets(john,heartburn). feels(john,hungry). ask Prolog "takes(john,medicine)." the answer should be "yes" Given: John is dating Nancy, but right now he is wondering if he must leave the country. Now John will take a vacation in either of two circumstances: if the IRS is after him, or if he is doomed. He is also dating Susan. If he is dating both of them, then Nancy knows this. Now John is in fact doomed if both Nancy and Susan know he is dating both of them. If John will take a vacation, then he must leave the country. So must John leave the country? Conclusion: What do you think? This one is a little more difficult. Answer: give Prolog the following facts: dates(john,nancy). takes(john,vacation) :- (after(irs,john) ; is(john,doomed)). dates(john,susan). knows(nancy, (dates(john,nancy) , dates(john,susan))):-(dates(john,nancy),dates(john,susan)). is(john,doomed):- (knows(nancy, (dates(john,nancy) , dates(john,susan))) , knows(susan, (dates(john,nancy) , dates(john,susan)))). leaves(john,country) :- takes(john,country). ask Prolog "leaves(john,country)." the answer should be "no" because the computer hasn't been told that Susan knows that John is dating both Nancy and Susan, and so it interprets this statement as false (unproved) and so the inference doesn't go through. Can you get Prolog to compute these answers? 4 + 5 * 10 (4 + 5) * 10 Answers: Type: X is 4 + 5 * 10. Prolog responds: X is 54 Type: X is (4 + 5) * 10. Prolog responds: X 90 Many Prolog textbooks use family relationships to illustrate Prolog. Can you construct a family? Given: Pete is the parent of Mike. Pete is the parent of Julie. Pete is the parent of Amanda. Mary is the parent of Mike. Mary is the parent of Julie. Mary is the parent of Amanda. Mary is female. Julie is female. Amanda is female. Mike is male. Pete is male. Mike is the sibling of Julie. Mike is the sibling of Amanda. Amanda is the sibling of Mike. Julie is the sibling of Mike. A male parent is a father. A female parent is a mother. A male sibling of someone is a brother of that person, unless the person in question is yourself. A female sibling of someone is a sister of that person, unless the person in question is yourself. (We could go on with aunts, uncles, grandparents, etc. but you get the idea.) Ask Prolog: Who is a sister of Mike? Who is a father of Julie. Is Amanda a sister of Julie? Is Mike a sister of anyone? Answer: Give Prolog the following facts: parent(pete,mike). parent(pete,julie). parent(mary,mike). parent(mary,julie). parent(pete,amanda). parent(mary,amanda). female(mary). female(julie). female(amanda). male(mike). male(pete). sibling(mike,julie). sibling(mike,amanda). sibling(amanda,mike). sibling(julie,mike). sibling(julie,amanda). sibling(amanda,julie). father(X) :- male(X) , parent(X). mother(X) :- female(X) , parent(X). brother(X,Y):- (male(X) , sibling (X,Y), X /= Y. sister(X,Y):- (female(X) , sibling (X,Y), X /= Y. Ask Prolog: sister(X,mike). father(X,julie). sister(amanda,julie). sister(mike,X). Here are some recommendations for further exploration: A famous Prolog book is Programming in Prolog, by W.F. Clocksin and C.S.Mellish A tutorial on Prolog is at http://www.amzi.com/AdventureInProlog/adufrtop.htm Information and links on Prolog are at http://www.amzi.com/share.htm Information and links on Prolog are at http://www.practical_applications.co.uk/Prolog/index.html A freeware version of Prolog is at http://www.lpa.co.uk A freeware version (for educational purposes) of Prolog is at http://www.swi.psy.uva.nl/usr/jan/SWI-Prolog.html Copyright: 2006 Prev [Introduction to Logic for ProtoThinker] Next [Introduction to Natural Language Processing]