Prolog Worksheet 1, due Monday, April 13

Problems for this Worksheet 1 with Prolog

1. The British Royal Family Tree (contemporary): Many diagrams show the family tree of the [almost] current British Royal Familly, including the upper-left image in this diagram from tes.com (formerly The Times Educational Supplement and referenced by the BBC).

   Notes:

   • This family tree does not show the marriage between Prince Harry and Meghan Markle and their subsequent son Archie Harrison Mountbatten.
   • Within this family tree, all siblings have the same mother and the same father. That is, there is no instance when one partner had a child, remarried, and then had a child with the second partner. (This observation may help simplify some queries asked later in this problem.)

   In using the family tree as a reference, this Prolog file shows parent-child and husband-wife relationships among the people identified in the diagram, as well as current gender assignments. (Note: Although the Prolog file has been proofread several times, typographical errors and omissions are still possible. Please contact me immediately, if you encounter an error in the file!)

   The Initial problems for this worksheet ask you to write rules and queries to address several relationships within this British Royal Family Tree (although the

   1. Write a rule granddaughter(GrandP, GrandD) that is true when GrandD is the the granddaughter of GrandP, and false otherwise. (Here, the grandparent may be either male or female.P
   2. Write a rule grandmother(GrandM, GrandC) that is true when GrandM is the the grandmother of GrandC, and false otherwise. (Here, the grandchild may be either male or female.)
   3. Write a rule sister(Sibling, Sister) that is true when Sister is a sister of the Sibling, and false otherwise. (Here, a sister must be different from the sibling. That is, a person cannot be one's own sister.)
   4. Two people are considered cousins, if their parents are different, but they have a grandparent in common. Write a rule cousins(Person1, Person2, which is true if the two people are cousins and false otherwise. (In a more general setting that the British Royal Family given, the common grandparent could be either a grandmother or a grandfather. The rule should not require that the individual has both the same grandmother and the same grandfather.)
   5. Person 1 is considered a step-parent of another (Person 2), if Person 1 is not the parent of Person 2, but Person 2 is married to Person 3, and Person 3 is a parent of Person 2. Write a rule stepParent(Pers1, Pers2) if Pers1 is a step-prent of Pers2. Use this rule to retrieve all pairs of step-parent/step-child within the British Royal Family (as identified in the diagram).

Lists in Prolog

2. List Suffix: Write a rule suffixHayThere(Suffix, WordList that is successful if the WordList starts with hay, there and if the Suffix contains all of the words in the WordList after the two words hay, there.

   Examples:

         suffixHayThere(Suffix, [hay, there, what, are, you, doing]).
            reports Suffix = [what, are, you doing]
         suffixHayThere(Suffix, [this, is, a, test]).
            reports false (the word list does not begin with hay, there)
       

3. List Prefix: Write a rule prefixCS(Prefix, WordList) that is successful if the WordList ends with cs and if the Prefix contains all of the words in the WordList up to, but not including cs.

   Examples:

         prefixCS(Prefix, [computer, science, is, abbreviated, cs]).
            reports Prefix = [computer, science, is, abbreviated]
         prefixCS(Prefix, [this, is, a, test]).
            reports false (the word list does not end with cs)
       

4. Generating Sentences: Consider the following dictionary, with words and parts of speech:

   %Problem 1
   %listing of adjectives
   adjective(many).
   adjective(good).
   adjective(excited).
   
   %listing of nouns for sentences subjects or objects
   noun(people).
   noun(homes).
   noun(pets).
   
   %listing of verbs
   verb(need).
   verb(love).
   
     

   Write a query sentence(Sent) that produces all possible lists of four elements: an adjective, noun, verb, and noun, where the first node is different from the second noun.

   For example, the following sentences should be included among the numerous sentences generated.

       [all, people, need, homes]
       [all, homes, need, pets]
       [all, people, love, homes]
     

5. Deleting an Element from a List: In class, one example of list processing involved determining if Lst2 could be obtained from list Lst1 by inserting an element Item into Lst1 somewhere.

     insert(Item, Lst1, Lst2) :- append(SubL1, SubL2, Lst1), append(SubL1, [Item | SubL2], Lst2).
       

   Write a corresponding rule delete(Item, Lst1, Lst2) which succeeds if Lst2 can be obtained by removing some copy of Item from Lst1.

   Hint: This exercise is REALLY easy and can be done if under a minute!

6. Determining Subsets and Subbags: In mathematics, a set contains zero or more elements, all of which are distinct. Expressed as Prolog list, two examples follow.

   • [a, b, c] is a set of three elements.
   • [a, b, a, c] cannot be considered a set, because a appears twice.

   In mathematics, a bag is a collection of zero or more elements, some of which may be repeated. Thus, both lists in the previous example could be considered as bags.

   Considering a bag B as a starting point, a subbag S is a collection of elements, so that B can be obtained from S by adding zero or more elements. Alternatively, S is a subbag of B if S can be obtained from B by deleting zero or more elements. Three examples follow.

   • For a bag B, then B and the empty collection are subbags of B.
   • In Prolog notation, both [a, b, c, a, d, a] and a, a, a, b, c, d are subbags of [a, b, a. c, a, d, a], because in each case the first bag can be obtained from the second. (In considering bags, the order of the elements does not matter.)
   • In Prolog notation, [a, b, a, c, a, d, a] is not a subbag of [a, b, c, a, d, a], because the first bag has more a's than are in the second.

   Write a Prolog rule subbag(SubBag, Bag) which succeeds if SubBag is a subbag of Bag.

   Note:

   • This rule should be written, using the delete rule from Problem 5—recursively removing elements of the SubBag from the Bag, until the SubBag is empty.

Extra Credit Problem

7. Write a rule between(First, Second, Sublist, List) which succeeds if First and Second are in the List, with First coming before Second, and if SubList contains all elements that appear (in order) within List between First and Second.

   Examples:

         between(computer, to, Sublist, [computer, science, is, very, exciting, to, me]).
              succeeds with Sublist = [exciting, is, very, exciting]
         between(to, computer, Sublist, [computer, science, is, very, exciting, to, me]).
              fails, because to comes after computer in the list
         between(mathematics, to, Sublist, [computer, science, is, very, exciting, to, me]). 
              fails, since mathematics is not located in the string
       

created 2 April 2020 revised 4 April 2020 expanded 7 April 2020
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.