Learn Prolog Now!
Kristina Striegnitz
Copyright c by , and Kristina Striegnitz, 2001
Copyright By PowCoder代写 加微信 powcoder
This course is also available online:
http://www.coli.uni-sb.de/ kris/learn-prolog-now
1 Facts, Rules, and Queries 1
1.1 Somesimpleexamples…………………… 1 1.1.1 KnowledgeBase1 …………………. 1 1.1.2 KnowledgeBase2 …………………. 3 1.1.3 KnowledgeBase3 …………………. 4 1.1.4 KnowledgeBase4 …………………. 6 1.1.5 KnowledgeBase5 …………………. 8
1.2 PrologSyntax ……………………….. 8 1.2.1 Atoms ……………………….. 9 1.2.2 Numbers………………………. 9 1.2.3 Variables………………………. 9 1.2.4 Complexterms …………………… 10
1.3 Exercises………………………….. 11
1.4 PracticalSession1 …………………….. 13
2 Matching and Proof Search 17
2.1 Matching………………………….. 17 2.1.1 Examples ……………………… 19 2.1.2 Theoccurscheck………………….. 22 2.1.3 Programmingwithmatching…………….. 23
2.2 ProofSearch………………………… 26
2.3 Exercises………………………….. 31
2.4 PracticalSession2 …………………….. 33
3 Recursion 37
3.1 Recursivedefinitions ……………………. 37 3.1.1 Example1:Eating …………………. 37 3.1.2 Example2:Descendant………………. 40 3.1.3 Example3:Successor……………….. 43 3.1.4 Example3:Addition ………………… 45
3.2 Clause ordering, goal ordering, and termination . . . . . . . . . 47
3.3 Exercises………………………….. 49
3.4 PracticalSession3 …………………….. 51
4 Lists 55
4.1 Lists…………………………….. 55 4.2 Member…………………………… 59 4.3 Recursingdownlists ……………………. 61 4.4 Exercises………………………….. 65 4.5 PracticalSession4 …………………….. 66
5 Arithmetic 69
5.1 ArithmeticinProlog…………………….. 69 5.2 Acloserlook………………………… 71 5.3 Arithmeticandlists …………………….. 73 5.4 Comparingintegers…………………….. 75 5.5 Exercises………………………….. 78 5.6 PracticalSession5 …………………….. 79
6 More Lists 81
6.1 Append…………………………… 81 6.1.1 Definingappend ………………….. 82 6.1.2 Usingappend……………………. 84
6.2 Reversingalist ………………………. 87 6.2.1 Naivereverseusingappend…………….. 87 6.2.2 Reverseusinganaccumulator …………… 88
6.3 Exercises………………………….. 89
6.4 PracticalSession6 …………………….. 90
7 Definite Clause Grammars 93
7.1 Contextfreegrammars…………………… 93 7.1.1 CFGrecognitionusingappend …………… 95 7.1.2 CFG recognition using difference lists . . . . . . . . . . . 98
7.2 Definiteclausegrammars …………………. 100 7.2.1 Afirstexample …………………… 100 7.2.2 Addingrecursiverules……………….. 102 7.2.3 ADCGforasimpleformallanguage . . . . . . . . . . . . 104
7.3 Exercises………………………….. 105
7.4 PracticalSession7 …………………….. 106
8 More Definite Clause Grammars 109
8.1 Extraarguments………………………. 109 8.1.1 Contextfreegrammarswithfeatures . . . . . . . . . . . . 109 8.1.2 Buildingparsetrees ………………… 114 8.1.3 Beyondcontextfreelanguages…………… 117
8.2 Extragoals…………………………. 118 8.2.1 Separatingrulesandlexicon ……………. 119
8.3 Concludingremarks…………………….. 121
8.4 Exercises………………………….. 122
8.5 PracticalSession8 …………………….. 122
9 A Closer Look at Terms 125
9.1 Comparingterms ……………………… 125
9.2 Termswithaspecialnotation ……………….. 127 9.2.1 Arithmeticterms ………………….. 127 9.2.2 Listsasterms……………………. 129
9.3 ExaminingTerms ……………………… 131 9.3.1 TypesofTerms …………………… 131 9.3.2 TheStructureofTerms……………….. 133
9.4 Operators………………………….. 136 9.4.1 Propertiesofoperators……………….. 136 9.4.2 Definingoperators …………………. 137
9.5 Exercises………………………….. 138
9.6 PracticalSession ……………………… 140
10 Cuts and Negation 145
10.1Thecut…………………………… 145 10.2If-then-else…………………………. 152 10.3Negationasfailure …………………….. 152 10.4Exercises………………………….. 156 10.5PracticalSession10 ……………………. 156
11 Database Manipulation and Collecting Solutions 159
11.1Databasemanipulation…………………… 159 11.2Collectingsolutions…………………….. 164 11.2.1findall/3……………………… 164 11.2.2bagof/3 ………………………. 165 11.2.3setof/3 ………………………. 167 11.3Exercises………………………….. 168 11.4PracticalSession11 ……………………. 170
12 Working With Files 171
12.1SplittingProgramsOverFiles ……………….. 171 12.1.1ReadinginPrograms………………… 171 12.1.2Modules ………………………. 172 12.1.3Libraries ………………………. 174
12.2WritingToandReadingFromFiles…………….. 174 12.3PracticalSession ……………………… 176 12.3.1Step1 ……………………….. 176 12.3.2Step2 ……………………….. 176 12.3.3Step3 ……………………….. 176 12.3.4Step4 ……………………….. 177 12.3.5Step5 ……………………….. 177 12.3.6Step6 ……………………….. 177
Facts, Rules, and Queries
This introductory lecture has two main goals:
1. To give some simple examples of Prolog programs. This will introduce us to the three basic constructs in Prolog: facts, rules, and queries. It will also introduce us to a number of other themes, like the role of logic in Prolog, and the idea of performing matching with the aid of variables.
2. To begin the systematic study of Prolog by defining terms, atoms, variables and other syntactic concepts.
Some simple examples
There are only three basic constructs in Prolog: facts, rules, and queries. A collection of facts and rules is called a knowledge base (or a database) and Prolog programming is all about writing knowledge bases. That is, Prolog programs simply are knowledge bases, collections of facts and rules which describe some collection of relationships that we find interesting. So how do we use a Prolog program? By posing queries. That is, by asking questions about the information stored in the knowledge base. Now this probably sounds rather strange. It’s certainly not obvious that it has much to do with programming at all – after all, isn’t programming all about telling the computer what to do? But as we shall see, the Prolog way of programming makes a lot of sense, at least for certain kinds of applications (computational linguistics being one of the most important examples). But instead of saying more about Prolog in general terms, let’s jump right in and start writing some simple knowledge bases; this is not just the best way of learning Prolog, it’s the only way …
Knowledge Base 1
Knowledge Base 1 (KB1) is simply a collection of facts. Facts are used to state things that are unconditionally true of the domain of interest. For example, we can state that Mia, Jody, and Yolanda are women, and that Jody plays air guitar, using the following four facts:
woman(mia). woman(jody). woman(yolanda). playsAirGuitar(jody).
Chapter1. Facts,Rules,andQueries
This collection of facts is KB1. It is our first example of a Prolog program. Note that the names mia, jody, and yolanda, and the properties woman and playsAirGuitar, have been written so that the first letter is in lower-case. This is important; we will see why a little later.
How can we use KB1? By posing queries. That is, by asking questions about the information KB1 contains. Here are some examples. We can ask Prolog whether Mia is a woman by posing the query:
?- woman(mia).
Prolog will answer
for the obvious reason that this is one of the facts explicitly recorded in KB1. Inci- dentally, we don’t type in the ?-. This symbol (or something like it, depending on the implementation of Prolog you are using) is the prompt symbol that the Prolog inter- preter displays when it is waiting to evaluate a query. We just type in the actual query (for example woman(mia)) followed by . (a full stop).
Similarly, we can ask whether Jody plays air guitar by posing the following query:
?- playsAirGuitar(jody).
Prolog will again answer “yes”, because this is one of the facts in KB1. However, suppose we ask whether Mia plays air guitar:
?- playsAirGuitar(mia).
We will get the answer
Why? Well, first of all, this is not a fact in KB1. Moreover, KB1 is extremely simple, and contains no other information (such as the rules we will learn about shortly) which might help Prolog try to infer (that is, deduce whether Mia plays air guitar. So Prolog correctly concludes that playsAirGuitar(mia) does not follow from KB1.
Here are two important examples. Suppose we pose the query:
?- playsAirGuitar(vincent).
Again Prolog answers “no”. Why? Well, this query is about a person (Vincent) that it has no information about, so it concludes that playsAirGuitar(vincent) cannot be deduced from the information in KB1.
Similarly, suppose we pose the query:
?- tatooed(jody).
Again Prolog will answer “no”. Why? Well, this query is about a property (being tatooed) that it has no information about, so once again it concludes that the query cannot be deduced from the information in KB1.
1.1. Somesimpleexamples 3
1.1.2 Knowledge Base 2
Here is KB2, our second knowledge base:
listensToMusic(mia).
happy(yolanda).
playsAirGuitar(mia) :- listensToMusic(mia). playsAirGuitar(yolanda) :- listensToMusic(yolanda). listensToMusic(yolanda):- happy(yolanda).
KB2 contains two facts, listensToMusic(mia) and happy(yolanda). The last three items are rules.
Rules state information that is conditionally true of the domain of interest. For exam- ple, the first rule says that Mia plays air guitar if she listens to music, and the last rule says that Yolanda listens to music if she if happy. More generally, the :- should be read as “if”, or “is implied by”. The part on the left hand side of the :- is called the head of the rule, the part on the right hand side is called the body. So in general rules say: if the body of the rule is true, then the head of the rule is true too. And now for the key point: if a knowledge base contains a rule head :- body, and Prolog knows that body follows from the information in the knowledge base, then Prolog can infer head.
This fundamental deduction step is what logicians call modus ponens.
Let’s consider an example. We will ask Prolog whether Mia plays air guitar:
?- playsAirGuitar(mia).
Prolog will respond “yes”. Why? Well, although playsAirGuitar(mia) is not a fact explicitly recorded in KB2, KB2 does contain the rule
playsAirGuitar(mia) :- listensToMusic(mia).
Moreover, KB2 also contains the fact listensToMusic(mia). Hence Prolog can use modus ponens to deduce that playsAirGuitar(mia).
Our next example shows that Prolog can chain together uses of modus ponens. Suppose we ask:
?- playsAirGuitar(yolanda).
Prolog would respond “yes”. Why? Well, using the fact happy(yolanda) and the rule
listensToMusic(yolanda):- happy(yolanda),
Prolog can deduce the new fact listensToMusic(yolanda). This new fact is not explicitly recorded in the knowledge base — it is only implicitly present (it is inferred knowledge). Nonetheless, Prolog can then use it just like an explicitly recorded fact. Thus, together with the rule
Chapter1. Facts,Rules,andQueries
playsAirGuitar(yolanda) :- listensToMusic(yolanda)
it can deduce that playsAirGuitar(yolanda), which is what we asked it. Summing up: any fact produced by an application of modus ponens can be used as input to further rules. By chaining together applications of modus ponens in this way, Prolog is able to retrieve information that logically follows from the rules and facts recorded in the knowledge base.
The facts and rules contained in a knowledge base are called clauses. Thus KB2 con- tains five clauses, namely three rules and two facts. Another way of looking at KB2 is to say that it consists of three predicates (or procedures). The three predicates are:
listensToMusic
playsAirGuitar
The happy predicate is defined using a single clause (a fact). The listensToMusic and playsAirGuitar predicates are each defined using two clauses (in both cases, two rules). It is a good idea to think about Prolog programs in terms of the predicates they contain. In essence, the predicates are the concepts we find important, and the various clauses we write down concerning them are our attempts to pin down what they mean and how they are inter-related.
One final remark. We can view a fact as a rule with an empty body. That is, we can think of facts as “conditionals that do not have any antecedent conditions”, or “degenerate rules”.
Knowledge Base 3
KB3, our third knowledge base, consists of five clauses:
happy(vincent).
listensToMusic(butch).
playsAirGuitar(vincent):-
listensToMusic(vincent),
happy(vincent). playsAirGuitar(butch):-
happy(butch). playsAirGuitar(butch):-
listensToMusic(butch).
There are two facts, namely happy(vincent) and listensToMusic(butch), and three rules.
KB3 defines the same three predicates as KB2 (namely happy, listensToMusic, and playsAirGuitar) but it defines them differently. In particular, the three rules that define the playsAirGuitar predicate introduce some new ideas. First, note that the rule
1.1. Somesimpleexamples 5
playsAirGuitar(vincent):-
listensToMusic(vincent),
happy(vincent).
has two items in its body, or (to use the standard terminology) two goals. What does this rule mean? The important thing to note is the comma , that separates the goal listensToMusic(vincent) and the goal happy(vincent) in the rule’s body. This is the way logical conjunction is expressed in Prolog (that is, the comma means and). So this rule says: “Vincent plays air guitar if he listens to music and he is happy”.
Thus, if we posed the query
?- playsAirGuitar(vincent).
Prolog would answer “no”. This is because while KB3 contains happy(vincent), it does not explicitly contain the information listensToMusic(vincent), and this fact cannot be deduced either. So KB3 only fulfils one of the two preconditions needed to establish playsAirGuitar(vincent), and our query fails.
Incidentally, the spacing used in this rule is irrelevant. For example, we could have written it as
playsAirGuitar(vincent):- happy(vincent),listensToMusic(vincent).
and it would have meant exactly the same thing. Prolog offers us a lot of freedom in the way we set out knowledge bases, and we can take advantage of this to keep our code readable.
Next, note that KB3 contains two rules with exactly the same head, namely:
playsAirGuitar(butch):- happy(butch).
playsAirGuitar(butch):- listensToMusic(butch).
This is a way of stating that Butch plays air guitar if either he listens to music, or if he is happy. That is, listing multiple rules with the same head is a way of expressing logical disjunction (that is, it is a way of saying or). So if we posed the query
?- playsAirGuitar(butch).
Prolog would answer “yes”. For although the first of these rules will not help (KB3
does not allow Prolog to conclude that happy(butch)), KB3 does contain listensToMusic(butch) and this means Prolog can apply modus ponens using the rule
playsAirGuitar(butch):- listensToMusic(butch).
Chapter1. Facts,Rules,andQueries
to conclude that playsAirGuitar(butch).
There is another way of expressing disjunction in Prolog. We could replace the pair of
rules given above by the single rule
playsAirGuitar(butch):- happy(butch); listensToMusic(butch).
That is, the semicolon ; is the Prolog symbol for or, so this single rule means exactly the same thing as the previous pair of rules. But Prolog programmers usually write multiple rules, as extensive use of semicolon can make Prolog code hard to read.
It should now be clear that Prolog has something do with logic: after all, the :- means implication, the , means conjunction, and the ; means disjunction. (What about nega- tion? That is a whole other story. We’ll be discussing it later in the course.) Moreover, we have seen that a standard logical proof rule (modus ponens) plays an important role in Prolog programming. And in fact “Prolog” is short for “Programming in logic”.
Knowledge Base 4
Here is KB4, our fourth knowledge base:
woman(mia).
woman(jody).
woman(yolanda).
loves(vincent,mia). loves(marcellus,mia). loves(pumpkin,honey_bunny). loves(honey_bunny,pumpkin).
Now, this is a pretty boring knowledge base. There are no rules, only a collection of facts. Ok, we are seeing a relation that has two names as arguments for the first time (namely the loves relation), but, let’s face it, that’s a rather predictable idea.
No, the novelty this time lies not in the knowledge base, it lies in the queries we are going to pose. In particular, for the first time we’re going to make use of variables. Here’s an example:
?- woman(X).
The X is a variable (in fact, any word beginning with an upper-case letter is a Prolog variable, which is why we had to be careful to use lower-case initial letters in our earlier examples). Now a variable isn’t a name, rather it’s a “placeholder” for information. That is, this query essentially asks Prolog: tell me which of the individuals you know about is a woman.
Prolog answers this query by working its way through KB4, from top to bottom, trying to match (or unify) the expression woman(X) with the information KB4 contains. Now
1.1. Somesimpleexamples 7
the first item in the knowledge base is woman(mia). So, Prolog matches X to mia, thus making the query agree perfectly with this first item. (Incidentally, there’s a lot of different terminology for this process: we can also say that Prolog instantiates X to mia, or that it binds X to mia.) Prolog then reports back to us as follows:
That is, it not only says that there is information about at least one woman in KB4, it actually tells us who she is. It didn’t just say “yes”, it actually gave us the variable binding, or instantiation that led to success.
But that’s not the end of the story. The whole point of variables — and not just in Prolog either — is that they can “stand for” or “match with” different things. And there is information about other women in the knowledge base. We can access this information by typing the following simple query
Remember that ; means or, so this query means: are there any more women? So Prolog begins working through the knowledge base again (it remembers where it got up to last time and starts from there) and sees that if it matches X with jody, then the query agrees perfectly with the second entry in the knowledge base. So it responds:
It’s telling us that there is information about a second woman in KB4, and (once again) it actually gives us the value that led to success. And of course, if we press ; a second time, Prolog returns the answer
X = yolanda
But what happens if we press ; a third time? Prolog responds “no”. No other matches are possible. There are no other facts starting with the symbol woman. The last four entries in the knowledge base concern the love relation, and there is no way that such entries can match a query of the form of the form woman(x).
Let’s try a more complicated query, namely
loves(marcellus,X),woman(X).
Now, remember that , means a
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com