FAMILY TREE Josie Taylor, Jan 1984 This TEACH file tells you how to construct a database of family relationships. The database will contain FACTS and RULES, and you will be able to find out about relationships by asking QUESTIONS which contain VARIABLES. For example, you could ask: Who is the mother of William II? ?- mother(X, william2). Who is a brother of William II? ?- brother(X, william2). and more complex questions which will be discussed later. You should already have looked at TEACH VEDPROLOG and TEACH RULES before trying these exercises. In TEACH VEDPROLOG you will have met PROLOG FACTS and VARIABLES. TEACH RULES introduces you to PROLOG RULES. In this file, we elaborate on the use of rules and variables. INDEX FOR THIS FILE: -- FAMILY TREES -- SOME REVISION AND NEW TERMINOLOGY -- FAMILIES IN PROLOG -- THREE PLACE PREDICATES -- ASKING QUESTIONS -- MAKING SIMPLE RULES -- USING 'NOT' -- BUILDING WITH FACTS -- USING RULES TO BUILD MORE RULES -- MORE AND MORE RELATIVES! -- FAMILY TREES ----------------------------------------------------------- Let's take the following (truncated) family tree: WILLIAM I (the Conqueror) m Matilda | ------------------------------------------------------- | | | | | | Robert (Curthose) Cecily WILLIAM II Agatha HENRY I Adela m Edith | Matilda m Geoffrey | HENRY II m Eleanor | ------------------------------------------------- | | | RICHARD 1 (the Lionheart) Joan JOHN (Kings are written in capital letters) The above is a tree diagram, and is the usual way to represent family relationships. Tree diagrams are good representations for people to use because the information is clearly laid out, and relationships can be traced by following the branches up or down. Note that not all the information contained in this tree is represented explicitly. Family trees just give names of individuals (from which it's usually possible to deduce the sex of the individuals), and their parentage. If you wanted to find a person's aunt, you would have to work it out by reference to brothers or sisters of the person's parents. We can make PROLOG perform this kind of deduction for us, but tree diagrams like the one above are of little use to PROLOG. -- SOME REVISION AND NEW TERMINOLOGY ------------------------------------ To give PROLOG the information you need to write a program which contains facts and rules. Some more terminology for you: ** PROLOG facts are often called ASSERTIONS. ** A collection of facts and rules can be also be described as a set of CLAUSES. A clause might be a fact or a rule - it saves having to say 'facts and rules' all the time! ** A PREDICATE is another word for what up till now has been called a 'relation' (e.g. is_in, next_to etc). So, your program will be a set of clauses. These have to be sent, via VED, to the PROLOG DATABASE. When this has been done, you can ask PROLOG questions. Remember that PROLOG knows nothing other than what you have told it, so if you put gibberish in, or miss out essential facts or rules, you'll get gibberish back! If any of this is confusing to you, check back over TEACH VEDPROLOG and TEACH RULES. -- FAMILIES IN PROLOG --------------------------------------------------- Imagine what a family tree would look like if every possible relationship were labelled explicitly - it would be a very large, sprawling mass of information which we would find virtually unintelligible. By giving the minimum essential facts, and a few rules to combine them, we are able to understand complex family trees quite easily. It is much the same when programming in PROLOG. You may find that a lot of effort goes into discovering what facts are or are not essential to produce the information you need. The economy with which PROLOG programs can be written makes it quite different from other languages, and is one reason why it is used in the development of intelligent systems. In what follows, we will be looking at ways of representing the family tree which minimise the amount of typing we have to do, without restricting the information PROLOG is given. This involves not only consideration of the way PROLOG works, but also of the type of information we are dealing with. A very important feature in defining family relationships such as brother, sister, aunt, uncle etc., is the sex of each individual. Create a file called 'family.pl' (don't forget the '.pl'). Read up until the asterisks before you actually put things in your file. You need to put the sex of each individual in your file. Two things to remember. First, all objects in PROLOG must begin with a lower case letter, so get rid of all the capitals in the names. Second, there are some people who have the same names - e.g. the various williams and matildas. If no distinction has been made between one william and the next, they will be treated as one object. A person's real name bears no relation to their PROLOG name. You could call people anything, and PROLOG won't mind. For the benefit of humans it's wise to use PROLOG names which we would recognize as a particular individual. You can distinguish between williams by adding their 'kingly' numeral as an ordinary number at the end of their names e.g. william1, william2. And the same for the women (although it happens that none of them were monarchs in their own right) - e.g. matilda1, matilda2. Note that numerals can appear in object names. You can add people's nick-names by using the underscore character if you like - e.g. robert_curthose. The sex of the person will be the predicate name. So, your list should look like this: male(william1). male(robert_curthose). male(william2). male(henry1). male(geoffrey). male(henry2). male(richard1). male(john). female(matilda1). female(cecily). female(agatha). female(adela). female(edith). female(matilda2). female(eleanor). female(joan). N.B. To save typing, you can mark the above as a range, go into your own file and do ti where 'ti' stands for 'transcribe in' to your file from the marked range in this file. See TEACH RANGE. However, be sure you have read the items carefully first, and understand what changes have been made and why. When you have entered the list of males and females, mark it as a range and load it with -d. You can then ask the simple question 'who is male?' (or female): ?- male(X). Don't forget to type the ?- otherwise PROLOG won't know you are asking a question. If you press the semi-colon after PROLOG has found you one instantiation of X, you will see how it works progressively down the program giving you each person in turn until the end of the list. ****************************************************************************** -- THREE PLACE PREDICATES ----------------------------------------------- Another important aspect of family trees is who is the child of whom. In this relationship there are three objects: the child, the father, and the mother. So this is called a THREE PLACE PREDICATE. The 'parents' relation is the predicate name, followed by the 'objects': parents(william1, matilda1, robert_curthose). which, in English, says: william1 and matilda1 are the parents of robert_curthose. The ordering of objects is important. Our interpretation of this clause - in which we must be consistent - is that the child's father will be the first object in the clause (after the predicate name); the next object is the child's mother; the next object is the child. Your 'parents' section should look like this: parents(william1, matilda1, robert_curthose). parents(william1, matilda1, cecily). parents(william1, matilda1, william2). parents(william1, matilda1, agatha). parents(william1, matilda1, adela). parents(william1, matilda1, henry1). parents(henry1, edith, matilda2). parents(geoffrey, matilda2, henry2). parents(henry2, eleanor, richard1). parents(henry2, eleanor, john). parents(henry2, eleanor, joan). Put this in your file below the male and female predicates. You can use ti again if you want to save typing. To get the text coming into your file BELOW the other text, put the cursor in the place where you want the incoming text to go before you go to the command line to give the 'ti' command. BE SURE YOU HAVE NO SPELLING ERRORS AND THAT YOUR PUNCTUATION IS CORRECT. CHECK CAREFULLY!!!!!! -- ASKING QUESTIONS -------------------------------------------------- You can now ask some more questions. Mark the range in your file and load it using -d. (Don't forget you can switch files by doing -e.) Correct any errors if you get mishap messages. If you do change the file at all, remember to re-mark it if necessary (check where the white bar on the left is) and do -d again. Then go into your output file to ask questions such as: ?- parents(X, Y, richard1). This question contains two variables: the X and Y. It is essential to put the corresponding number of variables in the question as objects in the rule. We said earlier that the 'parent' predicate was a three place one, with father, mother and child. When PROLOG answers your query, it MUST have a 'place' to put the solution. One variable cannot stand for two different objects. So, for example, to the following question: ?- parents(X, X, richard1), PROLOG will simply respond 'no'. Play around with putting unknown variables in different places and see what you get. E.g. ?- parents (henry2, X, Y). ?- parents (henry2, X, richard1). Remember to type the ?-. What response would you get to this question: ?- parents(edith, X, matilda2). Why? -- MAKING SIMPLE RULES -------------------------------------------------------- It's all very well being able to ask who the parents of people are, but that is asking for explicit information which you can already see in your program. How about asking who is the brother of whom? That information is not explicit, but needs to be deduced. That is, if william1 and matilda1 have two sons - robert and william2, then those two must be brothers. See if you can work out (in English if you like) the rules that PROLOG would need to have in order to deduce who is a brother of whom, using only the information in your program. Answer below this line of asterisks! **************************************************************************** For one person to be a brother of another, you must have two rules: first that the first person is male (the one being the brother) second that both people have the same parents. So, for example, providing that robert is male (which he is), and his parents are william1 and matilda1, then PROLOG can look for anybody who is also a child of william1 and matilda1. If anybody is found, then robert is his or her brother, according to these rules. In PROLOG the clause looks like this: brother(X, Y) :- male (X), parents (Pa, Ma, X), parents (Pa, Ma, Y). In English: X is the brother of Y if X is male, and Pa and Ma are the parents of X and Pa and Ma are the parents of Y Note that the variable names 'Pa' and 'Ma' have more than one character in them. This is perfectly legal, and makes for easier reading, provided that the first letter is upper-case. Put this clause into your file below the facts you already have. Load it, and ask the question: ?- brother(william2, X). This question asks: who is william2 the brother of? -- USING 'NOT' -------------------------------------------------------------- PROLOG should give you each of william's brothers and sisters. You will also get william2 himself, since he too is a male whose parents are william1 and matilda1. There is nothing in the program to tell PROLOG that someone cannot be their own brother (or sister). You can fix things quite easily by incorporating a line in the clause which says that whoever X is, Y must not be the same person - X does not equal Y. In PROLOG this is written: not(X = Y). 'NOT' and '=' are two special 'words' which PROLOG already knows about. Put the 'not' statement at the very end of the clause, so it should now look like this: brother(X, Y) :- male(X), parents(Pa, Ma, X), parents(Pa, Ma, Y), not(X=Y). What happens if you ask: ?- brother(X, william2). This question asks: who is a brother to william2? Define your own 'sister' rule and put it in. Play around with your program for a while, making sure you understand PROLOG's responses. ** N.B. The variable names in the rule and the variable names in the question DO NOT HAVE to be the same. Any variable name can be used at any time with one restriction: within a single question or clause, the SAME VARIABLE NAME must be used to indicate the SAME OBJECT. -- BUILDING WITH FACTS ------------------------------------------------------- Because the parent predicates are three-place ones, at present we can only talk about a child's parents, i.e. father AND mother, not father OR mother. In geneaology, one might well have to refer to a parent as an individual. We could enter each separate fact in - the father of so-and-so is such-and-such - but this would be tedious to type, and is unnecessary. You can write rules to tell PROLOG how to find the father or mother of a child, using the parent predicates. The mother and father rules will be very succinct. Because we know that in the parent predicate, the second object is always the male parent, we can use the relevant variable name to write the rule as follows: father(Pa, Y) :- parents(Pa, Ma, Y). (Pa is the father of Y if Pa is a parent of Y) In this particular instance we are not interested in who Ma might be. And similarly for the mother relation: mother(Ma, Y) :- parents(Pa, Ma, Y). (Ma is the mother of Y if Ma is a parent of Y) and we don't care about Pa. We don't need to check whether Pa is male or Ma is female, because in the parents predicate, the male parent if always first and the female is always second. So, if we use the same variable name in the HEAD of the rule (the bit before the :- sign) as in the correct place in the BODY of the rule (the rest after the :- sign), then PROLOG will know that it is the same object in both places. Add the mother and father relations at the bottom of your program. -- USING RULES TO BUILD MORE RULES ------------------------------------------ Your program is becoming quite complex. You can find out who the parents of a child are, who is the mother, who is the father, who the brothers and sisters are. What about grandparents? It is quite simple, using the parent predicate, and the father and mother rules. There are two ways to be a grandmother, for instance - by being the mother of either the child's mother or the child's father. Prolog will need two rules to cope with each of these possibilities, as follows: grandmother(Gm, X) :- parents(Pa, Ma, X), mother(Gm, Pa). grandmother(Gm, X) :- parents(Pa, Ma, X), mother(Gm, Ma). Gm is the grandmother of X if Pa and Ma are the parents of X and Gm is the mother of Pa. and Gm is the grandmother of X if Pa and Ma are the parents of X and Gm is the mother of Ma. Write the corresponding rules for grandfathers. After you've done that, you could write another rule so that you can ask who the grandparents of a child are. This is remarkably simple: grandparents(Gf, Gm, Z) :- grandfather(Gf, Z), grandmother(Gm, Z). The Gf and Gm are the grandparents of Z provided that Gf is the grandfather of Z and Gm is the grandmother of Z. Try all that out. -- MORE AND MORE RELATIVES! ------------------------------------------------ How might you go about writing rules to find aunts and uncles? To find out who the aunts of a child are, you need to know who the child's parents are, and then whether one of those parents has a sister. If so the sister - or sisters - will be aunt(s) to the child. There is a slight complication, because whilst it is easy to find out who the parents of the child are, we then have to find the siblings of EACH of the parents, Pa and Ma. We cannot do this in one clause. We need to write one clause that deals with the possibility of Pa's having sisters, and then another for Ma. aunt(Aunt,Y) :- parents(Pa, Ma, Y), sister(Aunt, Pa). aunt(Aunt,Y) :- parents(Pa, Ma, Y), sister(Aunt, Ma). Aunt is the aunt of Y if Pa and Ma are the parents of Y and Aunt is the sister of Pa/Ma. Write the corresponding rules for uncles. -- FURTHER EXERCISES ----------------------------------------------------- You could go on to elaborate on either this family tree, or one of your own. For example, write rules to find cousins, and second-cousins. Or great-grandparents, great-aunts and uncles. -- WHERE TO GO NEXT -------------------------------------------------------- After finishing this teach file you should move on to TEACH SIR, where you can learn how to write programs which converse in English. --- $poplocal/local/plog/teach/family --- Copyright University of Sussex 1993. All rights reserved. ----------