CIS301 Assignment 9

12 points; due Saturday, May 3

Question 1.

Here is a drawing of part of the Simpsons family tree, as taken from http://public.genoom.com/trees/Simpsons/Bart-Simpson, which (I believe) is based on the book, The Simpsons Uncensored Family Album (by Matt Groening, Harper Design, 2006).

===================================================

                                                        'Clancy Bouvier'=='Jacqueline Gurney'
'Carnival Woman'=='Abraham Simpson'                                     |  
                | 'Abraham Simpson'=='Penelope Olsen'   +------------------+--------------+
                |                  |                    |                  |              |
           'Herbert Powell'     'Homer Simpson'=='Marge Bouvier' 'Patricia Bouvier' 'Selma Bouvier'
                                               |                                          |
                                +-----------------+----------------+                'Ling Bouvier'
                                |                 |                |                 (adopted)
                             'Bart Simpson' 'Lisa Simpson' 'Maggie Simpson'

===================================================

(A==B means that A married B; their children are listed underneath the ==. Note that 'Abraham Simpson' married twice. If you are into this Simpsons thing, you will notice that I omitted Amber Simpson from the tree because it is just flat weird that she was married to both Homer and Abraham Simpson. )-:

Part 1(a).
Make a file named simpsons.pl to hold the Prolog clauses that model the above tree structure. Here is part of the coding; you do the rest:

===================================================

female('Carnival Woman').
male('Abraham Simpson').
female('Penelope Olsen').
male('Herbert Powell').
male('Homer Simpson').
male('Bart Simpson').
/* ...you do the remainder of the gender clauses;
   consult the above web link if you are unsure about any person's gender. */
female('Ling Bouvier').

/* predicate   parents(CHILD, FATHER, MOTHER)  asserts that 
   CHILD  has FATHER as its father and  MOTHER  as its mother:
*/
parents('Herbert Powell', 'Abraham Simpson', 'Carnival Woman').
parents('Homer Simpson', 'Abraham Simpson', 'Penelope Olsen').
parents('Bart Simpson', 'Homer Simpson', 'Marge Bouvier').
/* ...you do the remainder of the parent clauses up to this last one: */
parents('Ling Bouvier', none, 'Selma Bouvier').

/* sister(X, Y)  defines that  X  has  Y as a sister if
   Y is female,  X's and Y's parents are the same,  and  X != Y  */
sister(X,Y) :- female(Y),
               parents(X,Father,Mother), parents(Y,Father,Mother),
               X \= Y.

Run this test: ?- sister('Marge Bouvier', Z).
type semicolons till the prover prints False (or No). You should obtain: Z = 'Patricia Bouvier' ; Z = 'Selma Bouvier' ; False

Part 1(b).
Code this Prolog predicate and add it to simpsons.pl: X has A as an aunt if X's father has A as a sister or if X's mother has A as a sister:

/* aunt(X, A)  defines that  X  has  A  as an aunt */

(Hint: Code your definition of aunt so that it matches exactly what I said above.)

Test your definition with at least these test cases:

?- aunt('Bart Simpson', Z).
Z = 'Patricia Bouvier' ;
Z = 'Selma Bouvier' ;
false.

?-  aunt(X, 'Patricia Bouvier').
X = 'Bart Simpson' ;
X = 'Lisa Simpson' ;
X = 'Maggie Simpson' ;
X = 'Ling Bouvier'.
   (note: the order in which you receive the answers does not matter)

?- aunt(X,Y).
(there should be a long list!)

Copy and paste your test cases and their outputs into a txt file named simpsons.txt.

Part 1(c).
Code these Prolog predicates and add them to simpsons.pl:

Uncle is defined like aunt: /* uncle(X, U) defines that X has U as an uncle */

X has Y as a niece, if Y is female and Y has X as an aunt or uncle.
/* niece(X, Y) defines that X has Y as a niece. */

X has Y as a nephew, if Y is male and Y has X as an aunt or uncle. /* nephew(X, Y) defines that X has Y as a nephew. */

Test your definition with at least these test cases: ?- niece('Patricia Bouvier', N). ?- niece(X, Y). ?- nephew(X, 'Bart Simpson').
Copy and paste your test cases and their outputs into simpsons.txt.

Question 2

Place this library database into a file named library.pl. It's a little different from the one we studied in class.

===================================================

/* Functor for defining book and dvd objects:
      ITEM ::=  book(TITLE, AUTHOR)  |  dvd(TITLE)
                     where TITLE and AUTHOR are strings

   Predicates that define ownership of an object
   and when an object is borrowed from the library:
      PRED ::=  owns(KEY, ITEM)  |  borrowed(KEY, PERSON, DUEDATE)
                    where KEY is an atom that begins with  k
                          ITEM is defined above
                          PERSON is an atom
                          DUEDATE is an int
*/
owns(k0, book('David Copperfied', 'Charles Dickens')).
owns(k1, book('Tale of Two Cities', 'Charles Dickens')).
owns(k2, book('Tale of Two Cities', 'Charles Dickens')).
owns(k3, dvd('Tale of Two Cities')).
owns(k4, book('Moby Dick', 'Herman Melville')).
owns(k5, dvd('Brothers Karamazov', 'Fyodor Dostoyevski')).

borrowed(k2, 'Homer', 10).
borrowed(k4, 'Homer', 20).
borrowed(k3, 'Lisa', 40).
borrowed(k0, 'Lisa', 45).
borrowed(k5, 'Homer', 90).

/* fineOf  calculates the fine,  HowMuch,  of  ItemKey  as of  Today.
  (Note that an item that is not yet overdue will have  HowMuch =< 0.)  */
fineOf(ItemKey, Today, HowMuch) :- borrowed(ItemKey, _, DueDate),
                                   HowMuch is  Today - DueDate.
                                 
/* isOverdue  holds true when  ItemKey is borrowed and is past due as of  Today */
isOverdue(ItemKey, Today) :- fineOf(ItemKey, Today, Amount),
                             Amount > 0.
                           
/* printTitles(KeyList)  looks up the items named by the keys in  Keylist
   and prints the title of each item.  */
printTitles([]).
printTitles([H|Rest]) :- printTitle(H), nl, printTitles(Rest).

printTitle(Key) :- owns(Key, book(Title, _)), write(Title).
printTitle(Key) :- owns(Key, dvd(Title)), write(Title).                 

===================================================

Part 2(a).
Write this definition in Prolog and add it to library.pl:

/* getBorrowed(Who, ItemList)  calculates  in  ItemList  a list of  
   of all the  Keys  of the items  Who  has borrowed. */

(Hint: use findall.)

Test your definition on these queries:

?- getBorrowed('Homer', L).
L = [k2, k4, k5].

?- getBorrowed(_, All).
All = [k2, k4, k3, k0, k5].

Copy your test cases and their outputs into a txt file named library.txt.

Part 2(b).
Write this definition in Prolog and add it to library.pl:

/* totalFine(KeyList, Today, Amount)  adds up all the fines for all the
   items whose  Keys  are in  KeyList  and are *overdue* as of  Today.  */

Use list-argument patterns for argument KeyList in your answer, which should consist of two clauses, like this: totalFine([], ... ). totalFine([Key|Rest], ... ) :- ... .
See printTitles in the starter file, library.pl, to see the use of list-argument patterns.

Also, you might want to use Prolog's not operator. It works like this:

?- not(isOverdue(k5, 45)).
true.

?- not(isOverdue(k2, 45)).
false.

Test your definition on these queries:

?- totalFine([], 90, A).
A = 0.

?- totalFine([k0, k4, k2], 40, A).
A = 50.

?- getBorrowed('Homer', L), totalFine(L, 90, Amount).
L = [k2, k4, k5],
Amount = 150.

Copy your test cases and their outputs into library.txt.

Part 2(c).
Write this definition in Prolog and add it to library.pl:

/* extractOverdue(KeyList, Today, OverdueList)  examines each  Key
   in  KeyList  and includes the Key in the list,  OverdueList,  if the
   item with the  Key  isOverdue  as of  Today.  */

You must use list-argument patterns for both the first and third arguments to extractOverdue --- see Section 7.3.1 in the Lecture Notes, Chapter 7.

Also, you might want to use Prolog's not operator. It works like this:

?- not(borrowed(k3, 'Homer', _)).
true.

?- not(borrowed(k2, 'Homer', 10)).
false.

?- not(borrowed(_, 'Marge', _)).
true.

Test your definition on these queries:

?- extractOverdue([], 40, L).
L = [].

?- extractOverdue([k0, k4, k2], 40, A).
A = [k4, k2] ;
false.

?- getBorrowed('Homer', L), extractOverdue(L, 40, Bads).
L = [k2, k4, k5],
Bads = [k2, k4]] ;
false.

Finally, copy these lines into library.pl:

===================================================

/* prints the titles and fine of overdue items for  Who  as of  Today. */
printOverdues(Who, Today) :-
        getBorrowed(Who, Items),
        extractOverdue(Items, Today, Bads),
        write('Overdue items for '), write(Who), write(':'), nl,
        printTitles(Bads), 
        totalFine(Bads, Today, Cash),
        write(''), write(Cash), nl, !. 

===================================================

and run this last test: ?- printOverdues('Homer', 90). Overdue items for Homer: Tale of Two Cities Moby Dick 150 true.

Implementation

Study the examples in the lecture notes and the example programs I posted on the CIS Lectures web page.

Do the questions in the order stated; each one builds on its predecessors.

When you load a Prolog program, verify there are no errors. (Often an error is triggered by a missing period or comma on the previous line.)

Use the listing and trace predicates to see what is happening inside Prolog when you use it.

Plan for several days to do the exercise, because if you get stuck, it might take a day to understand what to do.

If you are stuck, you are welcome to contact me, but don't wait till the last minute to do so. In particular, I cannot guarantee that I can respond to email questions on the due date, Saturday, May 3.

Submission

When you are ready to submit, make a folder named Ex9, and place into it

simpsons.pl (Prolog clauses) and simpsons.txt (the test cases for all parts of Question 1)
library.pl (Prolog clauses) and library.txt (the test cases for all parts of Question 2)

Zip the folder. Submit Ex9.zip at K-State Online.