CS2360
Summer 1998
Homework Assignment 4
Due no later than 8:00 a.m., Tuesday, July 28, 1998


Please note that this assignment is worth twice as much as each of the
previous homeworks assignments has been.  The extra weight is due to
this assignment's length.

Other notes about this assignment

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -


   "Hello.  My name is Inigo Montoya.  You killed my father.  Prepare to die."


That's right, it's _The_Princess_Bride_, that classic Rob Reiner film
with fencing, fighting, torture, revenge, giants, monsters, chases,
escapes, true love, and miracles.  This week's homework will give you
the opportunity to recall some of your favorite funny moments from this
fabulous fairy tale.

If you haven't seen the movie, don't worry, as you'll be able to do the
assignment just fine (but what rock have you been hiding under?); if you
have, then the database below should refresh your memory about the
characters in the movie.


There's nothing _I_ love more after watching a good movie than sitting
back and trying to map out all the attributes and relationships between
the main characters--don't you?  And of course, what better way to try
and represent this knowledge base than with my good friend Common LISP.

Your assignment will be to construct a few functions that will serve as
the backbone for this movie-character-database-system.  I've taken the
liberty of starting us off with a bit of information from the movie and
encoding it in a big association list below.  Each element in the list
contains a character, some attributes of the character, and the
relationships that person has with others in the movie.

One thing to note before looking at the big list below is that I kind of
"reversed" my a-lists in a sense; that is, it might have made more sense
to say:

   (westley
       (played-by  cary_elwes)
       (tidbit     "the hero")
       (killed     vizzini) ...

rather than (the way it is actually set up):

   (westley
       (cary_elwes  played-by)
       ("the hero"  tidbit)
       (vizzini     killed) ...

but--what can I say--I was up really late when I was first creating the
association list.  Fortunately I know that minor, unexpected snags like
this will seem hardly a trifle to you-all, since you do such a good job
at data abstraction anyways.  Provided you write some good functions for
data abstraction, the fact that my representation looks a little goofy
won't matter at all in the long run.

In any case, here's the long-awaited database of facts about the movie
_The_Princess_Bride_:

;;;; The database

(defvar *database*

'((westley 
    (cary_elwes played-by)
    ("the hero" tidbit)
    (vizzini killed)
    (inigo_montoya fezzik friend-of)
    (prince_humperdinck enemy-of)
    (buttercup true-love-of)
    ("As you wish." quote))
  (buttercup
    (robin_wright played-by)
    ("the girl" tidbit)
    (westley true-love-of)
    ("Farm boy, fetch me that pitcher." quote))
  (inigo_montoya
    (mandy_patinkin played-by)
    ("outstanding swordsman" tidbit)
    (count_rugen killed)
    (fezzik westley friend-of)
    (vizzini worked-for)
    (count_rugen enemy-of)
    (domingo_montoya son-of)
    ("Hello, my name is Inigo Montoya. You killed my father. Prepare to die."
       quote))
  (fezzik
    (andre_the_giant played-by)
    ("the colossus" tidbit)
    (inigo_montoya westley friend-of)
    (vizzini worked-for)
    ("Anybody want a peanut?" quote))
  (vizzini
    (wallace_shawn played-by)
    ("wacky evil Sicilian" tidbit)
    (westley killed-by)
    (fezzik inigo_montoya employed)
    ("Inconceivable!" quote))
  (prince_humperdinck
    (chris_sarandon played-by)
    ("the bad guy" tidbit)
    (the_king son-of)
    (the_impressive_clergyman employed)
    (westley miracle_max enemy-of)
    ("Please consider me as an alternative to suicide." quote))
  (count_rugen
    (christopher_guest played-by)
    (inigo_montoya killed-by)
    (inigo_montoya enemy-of)
    (domingo_montoya killed)
    (the_albino employed)
    ("the six-fingered man" tidbit)
    ("I swear it will be done." quote))
  (the_albino
    (mel_smith played-by)
    (count_rugen worked-for)
    ("Nobody withstands the machine." quote))
  (the_impressive_clergyman
    (peter_cook played-by)
    (prince_humperdinck worked-for)
    ("has a speech impediment" tidbit)
    ("Mawwiage is what bwings us togethaw today." quote))
  (the_grandson
    (fred_savage played-by)
    ("Is this a kissing book?" quote)
    ("a sick kid" tidbit))
  (the_grandfather
    (peter_falk played-by)
    ("the narrator" tidbit)
    ("That's right, when I was your age, television was called books." quote))
  (miracle_max
    (billy_crystal played-by)
    ("Have fun stormin' da castle!" quote)
    (valerie married-to)
    (prince_humperdinck enemy-of))
  (valerie
    (carol_kane played-by)
    (miracle_max married-to)
    ("The chocolate coating makes it go down easier." quote))
  (the_king
    (willoughby_gray played-by)
    ("She kissed me!" quote)
    (prince_humperdinck father-of))
  (domingo_montoya
    (inigo_montoya father-of)
    (count_rugen killed-by))
))

You may note that I used DEFVAR to make *DATABASE* a global variable.
This is most certainly a side-effect.  You-all, of course, still aren't
allowed to use side-effects--but I am allowed--that's just one of the
perks of being the instructor.  In any case, consider it a favor, as
"*DATABASE*" will be a whole lot easier for you to type when you are
testing your functions than that whole big huge list.

In the data structure above, the characters appear in no particular
order--like any a-list, the order of the elements doesn't matter.
WESTLEY could have appeared as the last element, rather than the
first, and nothing would have really changed.

Similarly, the order of attributes for each character makes no
difference; I could just as well replace THE_ALBINO above with

  (the_albino
    ("Nobody withstands the machine." quote)    ; these are now
    (count_rugen worked-for)                    ; in a different
    (mel_smith played-by))                      ; order

and it would mean exactly the same thing.


Another thing to note is that some attributes have mutiple values, for
instance, in the information about WESTLEY:

    (inigo_montoya fezzik friend-of)           

we can see he has _two_ characters that he is a FRIEND-OF.

And speaking of those relationships, like FRIEND-OF, I'll kindly
supply you with a list of all of the relationships and their
reciprocals:

   (defvar *relationships*
      '((worked-for employed)
        (employed worked-for)
        (friend-of friend-of)
        (enemy-of enemy-of)
        (married-to married-to)      
        (killed killed-by)
        (killed-by killed)
        (father-of son-of)
        (son-of father-of)
        (true-love-of true-love-of)))

Note that each relationship has a "reciprocal"--a kind of "back
pointer".  For example, "fezzik worked-for vizzini", and "vizzini
employed fezzik" (and inigo, too).  The database above is
self-consistent in that every character with a relationship with
another implies that the second character ought to have a reciprocal
relationship back to the first one.  (Don't bother re-reading that last
sentence if it didn't make sense; instead, read the next one.)  If
DOMINGO was the FATHER-OF INIGO, then that means INIGO must be the
SON-OF DOMINGO.  Makes perfect sense now, right?

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

So by now, you're certainly wondering "what do I have to do with all of
this information?"  Your task is to write three functions, as specified
below.  One function finds relationships between two characters.
Another adds a new character to the database.  And the third removes a
character from the database.  

More specifically:

   (find-relationship 'westley 'inigo_montoya *database* *relationships*)

would return

   (WESTLEY KILLED VIZZINI EMPLOYED FEZZIK FRIEND-OF INIGO_MONTOYA)

Whoa!  Why not just return the much simpler

   (WESTLEY FRIEND-OF INIGO_MONTOYA)

instead, you wonder?  Well I'll tell you.  It's because you are required
to do a _depth_first_search_ of the database.  We'll be talking more
about depth-first searches in class "real soon now".  In fact, you've
already had exposure to them--a depth-first search is the same as a
preorder traversal.  Except that this data structure is not just a
tree.  Its structure is more complicated, and, what's more, it has
cycles.  So you'll have to guard against your program getting "stuck"
in a cycle that might give you a result like:

   (WESTLEY KILLED VIZZINI KILLED-BY WESTLEY KILLED VIZZINI KILLED-BY ...)

It might not be obvious how to do this, but as I already mentioned,
we'll be talking about searches a bit more in the lecture days to
come.  In the meantime, you can think about the other functions, like
ADD-PERSON.  It takes a new person's information, as in

   (defvar *new-person*
     '(yellin
        (malcomb_storry played-by)
        ("The gate has but one key, and I carry that." quote)
        (prince_humperdinck worked-for)
   ))

and adds it to the database, when called with

   (add-person *new-person* *database* *relationships*)

Of course, ADD-PERSON doesn't have side-effects; the function will
return a new copy of the database.  You might be thinking that this
function is trivial--we can just CONS the person onto the front of the
database, right?  Wrong.  Recall that the database must ensure
"relational integrity", that is, we must match up the relations like
FATHER-OF and SON-OF and so forth.  (You'd forgotten about that detail
already, hadn't you?)  So, when we add YELLIN, for example, we'll have
to note that he WORKS-FOR PRINCE_HUMPERDINCK, and update the prince's
information accordingly.  Since the reciprocal of WORKS-FOR is EMPLOYED,
you might be tempted to think we could just add

    (yellin employed)

to the prince's info.  But again, that'd be overly simple--in fact, the
prince already has an employee listed.  As a result, his updated info
should look like:

   (prince_humperdinck
       (chris_sarandon played-by)
       ("the bad guy" tidbit)
       (the_king son-of)
       (yellin the_impressive_clergyman employed)        ; note this line
       (westley miracle_max enemy-of)
       ("Please consider me as an alternative to suicide." quote))

and _not_ like

   (prince_humperdinck
       (chris_sarandon played-by)
       ("the bad guy" tidbit)
       (the_king son-of)
       (yellin employed)                                 ; two
       (the_impressive_clergyman employed)               ; "employed"s
       (westley miracle_max enemy-of)
       ("Please consider me as an alternative to suicide." quote))

Note the difference: the right way doesn't "duplicate" the EMPLOYED
attribute.  So as a result, the whole call to

   (add-person *new-person* *database* *relationships*)

should return (look in the right margin for comments on the changes)

 ((yellin                                    ; this entire node
    (malcomb_storry played-by)               ; is new
    ("The gate has but one key, and I carry that." quote)
    (prince_humperdinck worked-for))
  (westley 
    (cary_elwes played-by)
    ("the hero" tidbit)
    (vizzini killed)
    (inigo_montoya fezzik friend-of)
    (prince_humperdinck enemy-of)
    (buttercup true-love-of)
    ("As you wish." quote))
  (buttercup
    (robin_wright played-by)
    ("the girl" tidbit)
    (westley true-love-of)
    ("Farm boy, fetch me that pitcher." quote))
  (inigo_montoya
    (mandy_patinkin played-by)
    ("outstanding swordsman" tidbit)
    (count_rugen killed)
    (fezzik westley friend-of)
    (vizzini worked-for)
    (count_rugen enemy-of)
    (domingo_montoya son-of)
    ("Hello, my name is Inigo Montoya. You killed my father. Prepare to die."
       quote))
  (fezzik
    (andre_the_giant played-by)
    ("the colossus" tidbit)
    (inigo_montoya westley friend-of)
    (vizzini worked-for)
    ("Anybody want a peanut?" quote))
  (vizzini
    (wallace_shawn played-by)
    ("wacky evil Sicilian" tidbit)
    (westley killed-by)
    (fezzik inigo_montoya employed)
    ("Inconceivable!" quote))
  (prince_humperdinck
    (chris_sarandon played-by)
    ("the bad guy" tidbit)
    (the_king son-of)
    (yellin the_impressive_clergyman employed)     ; this is new, too
    (westley miracle_max enemy-of)
    ("Please consider me as an alternative to suicide." quote))
  (count_rugen
    (christopher_guest played-by)
    (inigo_montoya killed-by)
    (inigo_montoya enemy-of)
    (domingo_montoya killed)
    (the_albino employed)
    ("the six-fingered man" tidbit)
    ("I swear it will be done." quote))
  (the_albino
    (mel_smith played-by)
    (count_rugen worked-for)
    ("Nobody withstands the machine." quote))
  (the_impressive_clergyman
    (peter_cook played-by)
    (prince_humperdinck worked-for)
    ("has a speech impediment" tidbit)
    ("Mawwiage is what bwings us togethaw today." quote))
  (the_grandson
    (fred_savage played-by)
    ("Is this a kissing book?" quote)
    ("a sick kid" tidbit))
  (the_grandfather
    (peter_falk played-by)
    ("the narrator" tidbit)
    ("That's right, when I was your age, television was called books." quote))
  (miracle_max
    (billy_crystal played-by)
    ("Have fun stormin' da castle!" quote)
    (valerie married-to)
    (prince_humperdinck enemy-of))
  (valerie
    (carol_kane played-by)
    (miracle_max married-to)
    ("The chocolate coating makes it go down easier." quote))
  (the_king
    (willoughby_gray played-by)
    ("She kissed me!" quote)
    (prince_humperdinck father-of))
  (domingo_montoya
    (inigo_montoya father-of)
    (count_rugen killed-by)))

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

The third piece of functionality you need to implement, as mentioned
above, is DELETE-PERSON.  So, if we wanted to remove the character who
died by ingesting the deadly Iocaine powder during a battle of wits, we
could call

   (delete-person 'vizzini *database* *relationships*)

and it would return

 ((westley 
    (cary_elwes played-by)
    ("the hero" tidbit)
    (inigo_montoya fezzik friend-of)
    (prince_humperdinck enemy-of)
    (buttercup true-love-of)
    ("As you wish." quote))
  (buttercup
    (robin_wright played-by)
    ("the girl" tidbit)
    (westley true-love-of)
    ("Farm boy, fetch me that pitcher." quote))
  (inigo_montoya
    (mandy_patinkin played-by)
    ("outstanding swordsman" tidbit)
    (count_rugen killed)
    (fezzik westley friend-of)
    (count_rugen enemy-of)
    (domingo_montoya son-of)
    ("Hello, my name is Inigo Montoya. You killed my father. Prepare to die."
       quote))
  (fezzik
    (andre_the_giant played-by)
    ("the colossus" tidbit)
    (inigo_montoya westley friend-of)
    ("Anybody want a peanut?" quote))
  (prince_humperdinck
    (chris_sarandon played-by)
    ("the bad guy" tidbit)
    (the_king son-of)
    (the_impressive_clergyman employed)
    (westley miracle_max enemy-of)
    ("Please consider me as an alternative to suicide." quote))
  (count_rugen
    (christopher_guest played-by)
    (inigo_montoya killed-by)
    (inigo_montoya enemy-of)
    (domingo_montoya killed)
    (the_albino employed)
    ("the six-fingered man" tidbit)
    ("I swear it will be done." quote))
  (the_albino
    (mel_smith played-by)
    (count_rugen worked-for)
    ("Nobody withstands the machine." quote))
  (the_impressive_clergyman
    (peter_cook played-by)
    (prince_humperdinck worked-for)
    ("has a speech impediment" tidbit)
    ("Mawwiage is what bwings us togethaw today." quote))
  (the_grandson
    (fred_savage played-by)
    ("Is this a kissing book?" quote)
    ("a sick kid" tidbit))
  (the_grandfather
    (peter_falk played-by)
    ("the narrator" tidbit)
    ("That's right, when I was your age, television was called books." quote))
  (miracle_max
    (billy_crystal played-by)
    ("Have fun stormin' da castle!" quote)
    (valerie married-to)
    (prince_humperdinck enemy-of))
  (valerie
    (carol_kane played-by)
    (miracle_max married-to)
    ("The chocolate coating makes it go down easier." quote))
  (the_king
    (willoughby_gray played-by)
    ("She kissed me!" quote)
    (prince_humperdinck father-of))
  (domingo_montoya
    (inigo_montoya father-of)
    (count_rugen killed-by)))

Again, the hard part will be deleting the "backlinks" correctly.  Note
that after deleting VIZZINI, the node for WESTLEY, looks like

   (westley
       (cary_elwes played-by)
       ("the hero" tidbit)
       (inigo_montoya fezzik friend-of)
       (prince_humperdinck enemy-of)
       (buttercup true-love-of)
       ("As you wish" quote))

and _not_

   (westley
       (cary_elwes played-by)
       ("the hero" tidbit)
       (killed)                             ; nope
       (inigo_montoya fezzik friend-of)
       (prince_humperdinck enemy-of)
       (buttercup true-love-of)
       ("As you wish" quote))

and also _not_

   (westley
       (cary_elwes played-by)
       ("the hero" tidbit)
       (nil killed)                         ; nope
       (inigo_montoya fezzik friend-of)
       (prince_humperdinck enemy-of)
       (buttercup true-love-of)
       ("As you wish" quote))

In other words, if you delete a character who is another character's
only person for a relation, delete the whole entry.  If instead, we'd
deleted FEZZIK, then, among other changes, WESTLEY's node would contain
the attribute

       (inigo_montoya friend-of)            ; no more fezzik


 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

There will probably be a few things I forgot in this problem
description, so stay flexible.  Specifications will possibly change in
small ways, just like in the real world.  Check the newsgroup
frequently for updates.  Make sure that your program is the pinnacle of
good design, good documentation, and good abstraction.  Employing that
good abstraction will make it easier for you to adapt to specification
changes as they come up.  And when it all gets too frustrating, go take
a break and watch the movie.

(For more info on the movie, you can check out the IMDB info at
    http://us.imdb.com/Title?Princess+Bride,+The+(1987)
 or a movie script at
    http://www.d.umn.edu/~chouse/movierack/bridescript.html
 Have fun.)