CS 381, Spring 2002
Programming Assignment 7
Due: Wednesday, May 29

Introduction to Prolog

In this programming assignment we will start our investigation of Prolog and logic programming. As I did with the Lisp assignment, I will introduce Prolog by walking you through an example of the language, and then have the actual programming assignment at the end.

Logic programming as exemplified by Prolog is based on three types of statements: facts, rules of inference, and questions. The facts describe known information, the rules of inference describe how new information can be derived from known information, and the questions drive a search. A prolog program then tries to answer the questions by starting from the facts and using the rules of inference.

Logic programming is also sometimes referred to as relational programming, so what better place to start than with family relations? The following picture shows the relationships in a typical ancient greek family. 

picture

I have taken some liberties here by providing names for individuals mentioned in the Greek myths but not named. For example, it is noted that Heracles (you probably know him better by his Roman name Hercules) and Megara had three sons, but at least the sources I have examined do not provide them with names. I have reduced this number of two, and christened them Bert and Ernie. Horizontal lines represent marriages (or liaisons) while vertical lines indicate offspring.

This could be encoded as a series of facts in prolog form in the following fashion: 

motherOf(leda,helen).
motherOf(leda,clytemnestra).
motherOf(leda,castor).
motherOf(leda,pollux).
motherOf(alcmene,heracles).
motherOf(helen,hermione).
motherOf(clytemnestra,iphigena).
motherOf(clytemnestra,orestes).
motherOf(hermione,sam).
motherOf(hermione,alice).
motherOf(megara,bert).
motherOf(megara,ernie).
fatherOf(zeus,helen).
fatherOf(tyndareus,clytemnestra).
fatherOf(tyndareus,castor).
fatherOf(zeus,pollux).
fatherOf(zeus,heracles).
fatherOf(menelaus,hermione).
fatherOf(agamemnon,iphigena).
fatherOf(agamemnon,orestes).
fatherOf(orestes,alice).
fatherOf(neoptolemy,sam).
fatherOf(heracles,bert).
fatherOf(heracles,ernie).

There are two types of facts being defined here. One is the fatherOf relationship and one is the motherOf relationship. The values being discussed by these relationships are simply symbols. These are similar to the symbols we encountered in Lisp -- they are simply names, having no intrinic meaning but instead having whatever meaning we impose on them.

The file containing these facts can be found in /usr/local/classes/cs/cs381/data/family.pl. You should copy this file into your own directory.

You start the prolog system by typing the command gprolog. After the prompt, enter the line 


	consult('family.pl').

After the period you should get some output indicating that the file has been processed. After that you can then start asking questions. The simplest type of question are simple yes/no questions, such as ``is leda the mother of helen'' (helen being helen of troy fame). You can ask this question by typing the following: 


	motherOf(leda,helen).

In response the prolog system should answer yes, followed by a question mark. Just hit return in response to the question mark. (try it! If you don't get any response it means you probably left off the period. Period is statement termintor for prolog, and nothing happens until it is typed). But there are more than yes/no questions you can ask. For example, suppose you don't remember who the parents are of the twins castor and pollox (these are the twins in the Gemini constellation, by the way). You can find out by typing a command that includes a variable. A variable differs from a symbol in that it begins with an upper case letter. Try entering the following: 


	motherOf(X,castor).

You should get back some output indicating who the mother of castor is. Who is the mother of his twin brother pollux? What command would you type to find the father of castor? How about the father of pollox?

The scope of a variable is the line that contains it. It is normal to use one or two letter names for variables, although anything that begins with an upper case letter could be used.

An interesting thing about Prolog statements is that they can go both directions. Sometimes one variable can act as input and other as output, and sometimes the reverse. For example, we can ask who Leda is the mother of: 


	motherOf(leda,X).

Of course, there is more than one correct answer to this question. The prolog system starts by giving one just one answer. If you want to see another, enter a semicolon instead of a return in response to the question mark. This will give you the next answer. You can continue this until there are no more answers. Try this.

The comma is used as the logical ``and'' connective in Prolog. Suppose we want to find the child of Leda and Zeus. We can ask this by entering the following: 


	motherOf(leda,X),fatherOf(zeus,X).

Because we have used the same variable X in both parts, the prolog system searches for a value that satisfies both parts. It may have to reject several values that satisfy just the first clause before it finds one that satisfies both the first and the second. This process is called {\em backtracking}.

So far we haven't seen any rules of inference. Lets define one. Suppose we want to generalize the process we have just described. Lets create the relationship parentsOf(X,Y,Z). This will say that X and Y are the parents of Z if X is the mother of Z and Y is the father of Z. Quit the prolog system by entering a control-D, and then add the following line to the end of the file family.pl: 


	parentsOf(X,Y,Z) :- motherOf(X,Z),fatherOf(Y,Z).
The colon-dash tells the Prolog system that this is a rule of inference. Restart the prolog system, and consult the file once again. We can now use this rule in a query, just like we used the earlier rules: 

	parentsOf(leda,zeus,X).

Let us define another relationship. Two people are called siblings if they have both the same parents in common. Again, exit prolog, then define this as follows: 


	sibling(X,Y) :- motherOf(M,X),motherOf(M,Y),fatherOf(F,X),fatherOf(F,Y).
We read this as saying that X is a sibling of Y if the mother of X is M and M is also the mother of Y and the father of X is F and F is also the father of Y. How would you now find the siblings of orestes? How would you list all of them? Do you find anything surprizing in this list?

Negation is one element that is very tricky in Prolog. One reason is that negation can be used as a filter, but not a generator. What does this mean? Well, take a look at the two motherOf clauses in the sibling relationship. The first is being used to search for an element to fill the variable M. Thus, we say that this clause is generating the variable. The second is being used to test the value of M to see if it satisfies another property. Thus, we say that this clause is filtering out values we don't want. A not equals clause is written something like the following 


	 \=(X,Y)
However, not equals can only be used to filter out values where X is not equal to Y. It cannot be used to generate all the possible values where X is not equal to Y. We can add a negation to the end of our sibling relation as follows: 

sibling(X,Y) :- motherOf(M,X),motherOf(M,Y),fatherOf(F,X), fatherOf(F,Y),\=(X,Y).
Now try enumerating all the siblings of orestes. Try just asking for sibling using two variables. What are other siblings in our family tree?

Sometimes there are two or more ways of satisfying a relation. For example, a half sibling is somebody who has the same mother as another, or the same father, but not both. We could define half sibling as follows: 

halfSibling(X,Y) :- motherOf(M,X),motherOf(M,Y),fatherOf(F1,X),fatherOf(F2,Y),\=(X,Y),\=(F1,F2).
halfSibling(X,Y) :- fatherOf(F,X),fatherOf(F,Y),motherOf(M1,X),motherOf(M2,Y),\=(X,Y),\=(M1,M2).
The fact that we have two separate rules is interpreted by the Prolog system as a logical or -- the relationship can be satisfied either by the first rule or by the second. Who are the half siblings in our family tree? How would you find this? Why do you think that some pairs are listed twice?

Although it is easier to explain prolog by separating out facts and rules of inference, the prolog system actually treats them as being the same. We can illustrate this by defining the relation female. We can say that somebody is a female if they are a mother: 


	female(X) :- motherOf(X, Y).
Notice that we don't care what value fills the variable Y, just as long as some variable does. This works for all the interior nodes in our family tree, but not for the leaves. For those we have to explicitly write them as facts: 

	female(iphigenia).
	female(alice).
The relation female can be used either as a generator or as a filter -- some times it is being defined using a rule of inference (a person is a female if they are a mother) and sometimes just by consulting the known facts (iphigenia is a female).

Your Programming Assignment

Copy the family database into a file named ProgSeven.pl . Then add to the end of this file definitions for the following:

  1. The relations sibling, halfSibling, and female we have defined earlier in this document.
  2. The relation male. You can assume that anybody we have not defined as a female is a male.
  3. The relation brotherOf(X,Y) where X is a brother of Y if X is a male, and X and Y have either a mother or father in common (or both). The equivalent relation sisterOf(X,Y).
  4. The relation brotherSister(X,Y) where X is the brother of Y and Y is the sister of X. (Are there any examples of this in our database?)
  5. The relation auntOf(X,Y). An X is an aunt of Y if X is a sister of a parent of Y. The similar relation uncleOf(X,Y).
  6. The relation grandChildOf(X,Y) which is true if X is a grandchild of Y, along either the mothers or the fathers side (or both!)
  7. The relation grandMotherOf(X,Y) which is true if X is a grandmother of Y.
  8. The relation cousin(X,Y). Two distinct people are cousins if their parents are siblings. (Unlike some other languages, English does not make a distinction between male and female cousins).
  9. nieceOf(X,Y). A niece is a female child of a sibling.
  10. secondCousin(X,Y) second cousins are distinct children of (first) cousins. (If you ask I can also tell you want a first cousin once removed is, although I'm not having you define this relation).