CS 2360
Spring 1998
Homework Assignment 4
Due no later than 8:00am, Monday, May 4, 1998
The universe comes to an end in three weeks. The Seinfeld universe,
that is. As a tribute to one of TV's all-time classic shows as well as
what future historians will look back on as the defining cultural artifact
of the good ol' USA in the 1990s, this weeks homework focuses on the
show about nothing.
The series isn't really dead, however. It already lives on in syndication,
and in Atlanta as well as other cities the Seinfeld reruns compete favorably
against first-run shows on the big three (or three and a half, if you count
Fox) networks. And as the show continues to attract new viewers through
these reruns, the viewers may need a "road map" to figure out who's
related to whom, especially if they haven't been able to see the
episodes in their original order.
Your contribution to the Seinfeld legacy will be to provide these
new viewers with appropriate database software for keeping track
of an ever-expanding group of superficial characters. I've already
encoded some of the basic knowledge for the prototype system below.
Now I want you to construct, in Common LISP of course, three functions
which will comprise the backbone software for this system. But let's
get back to the database, which actually consists of three parts. The
first part is a relational network (encoded as a big association list)
in which each node is a brief description of a character from the TV show.
Each description contains the name of the character, some attributes of
that character, and some relationships between that character and others
in the relational network. Here's what this first part looks like:
(defvar *database*
'((person01
(name jerry_seinfeld)
(gender male)
(occupation comedian)
(tidbit "loves breakfast cereal")
(has-friend kramer george_costanza elaine_benes)
(has-enemy newman)
(has-parent helen_seinfeld morty_seinfeld))
(person02
(name george_costanza)
(gender male)
(occupation former_baseball_executive)
(tidbit "jerry's high school chum")
(has-friend jerry_seinfeld elaine_benes kramer)
(engaged-to susan_ross)
(has-parent estelle_costanza frank_costanza))
(person03
(name elaine_benes)
(gender female)
(occupation editor)
(tidbit "dancing fool")
(has-friend jerry_seinfeld george_costanza kramer))
(person04
(name kramer)
(gender male)
(occupation entrepreneur)
(tidbit "first name is Cosmo")
(has-parent babs_kramer)
(has-friend george_costanza newman jerry_seinfeld elaine_benes))
(person05
(name helen_seinfeld)
(gender female)
(occupation retired)
(has-child jerry_seinfeld)
(married-to morty_seinfeld))
(person06
(name morty_seinfeld)
(gender male)
(occupation retired)
(has-child jerry_seinfeld)
(married-to helen_seinfeld))
(person07
(name susan_ross)
(gender female)
(occupation NBC_executive)
(tidbit "died of envelope poisoning")
(engaged-to george_costanza))
(person08
(name estelle_costanza)
(gender female)
(occupation retired)
(has-child george_costanza)
(married-to frank_costanza))
(person09
(name frank_costanza)
(gender male)
(occupation retired)
(tidbit "co-inventor of 'the bro'")
(has-child george_costanza)
(married-to estelle_costanza))
(person10
(name babs_kramer)
(gender female)
(tidbit "drunken stumblebum")
(has-child kramer))
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-friend kramer)
(has-enemy jerry_seinfeld))
)
)
In the data structure above, the characters may not appear in the order
given, so don't assume that order. And the stuff "defines" a character
may not appear as it does above. For example, the entry for Kramer
might appear as it does above, or it could look like this:
(person04
(has-parent babs_kramer)
(gender male)
(name kramer)
(tidbit "first name is Cosmo")
(occupation entrepreneur)
(has-friend elaine_benes jerry_seinfeld newman george-costanza))
Both versions mean exactly the same thing, and your programs must
be able to deal with this variability.
The second component of the database is also an association list,
but this one contains the names of relationships which may exist
between any two characters in this "Seinfeld" universe. Associated
with each of the relationships which may lead from character A
to character B is the corresponding relationship which must lead
from character B to character A. For example, the relationship
"has-parent" leads from "george_costanza" to "estelle_costanza", so
there must be a "has-child" relationship leading from "estelle_costanza"
to "george_costanza".
(defvar *relations* '((has-parent has-child)
(has-child has-parent)
(has-friend has-friend)
(married-to married-to)
(engaged-to engaged-to)
(has-enemy has-enemy)))
The third and final component of the database is yet another a-list
that maps the names of people to their corresponding node numbers:
(defvar *names*
'((jerry_seinfeld person01)
(newman person11)
(elaine_benes person03)
:
:
))
One LISP program you'll have to write is one which searches for a
relationship, however distant, between any two characters in "Seinfeld".
The top-level function here will be called "find-relationship", and
this function takes five (count 'em, five) arguments. The first two
arguments are the names of two characters who may be somehow related.
The third argument is the relational network, the fourth argument is the
a-list of relationships, and the fifth argument is the a-list of names
and corresponding node identifiers.
For example,
(find-relationship
'jerry_seinfeld 'susan_ross *database* *relations* *names*))
should return something that looks like this
(JERRY_SEINFELD HAS-FRIEND KRAMER HAS-FRIEND GEORGE_COSTANZA
ENGAGED-TO SUSAN_ROSS)
If no relationship can be found, simply return NIL. If more than one
chain of relations can be found, then just return the first one found.
To implement this, use a depth-first search algorithm. You've already
had some exposure to depth-first search: it's the same as a preorder
traversal. However, there are a few wrinkles which make this problem
more complex than just plain old vanilla preorder traversal. First,
this data structure isn't a tree. That is, this data structure has
cycles, which means you have to figure out how to keep your program from
searching around and around through the same cycle. Second, it won't be
enough to just return T when you find a relationship between two
"Seinfeld" characters--you'll have to return a list of the labels on the
"nodes" and "links" joining the two characters. If it's not immediately
obvious how to do this, we'll talk more about depth-first search on
Thursday. In the meantime, you can work on the other programs you have
to write....
As the new "Seinfeld" viewer watches more and more reruns, that
viewer will undoubtedly want to add new characters to the database,
so you'll have to construct the appropriate function, which you'll
call "add-character". This function will take four arguments: the
properly constructed "node" to be added to the network, the relational
network, the a-list of relations, and the a-list of names and nodes. This
function will return the updated relational network with the new node
added in somewhere (the order of the characters in the network doesn't
matter) and with the appropriate links to the new node inserted in
the correct neighboring nodes (your function will have to construct
these from the information passed to it; the order of the links within
a character's node doesn't matter either). For example, let's assume
the existence of a test node:
(defconstant *test-node*
'(person42
(name bob_sacamano)
(gender male)
(tidbit "never seen")
(has-friend kramer)))
Then a call to "add-character" like this:
(add-character *test-node* *database* *relations* *names*)
would return this updated network:
((person42 ;;here's the new bob_sacamano node
(name bob_sacamano)
(gender male)
(tidbit "never seen") ;;make sure you see the change to the
(has-friend kramer)) ;;kramer node below
(person01
(name jerry_seinfeld)
(gender male)
(occupation comedian)
(tidbit "loves breakfast cereal")
(has-friend kramer george_costanza elaine_benes)
(has-enemy newman)
(has-parent helen_seinfeld morty_seinfeld))
(person02
(name george_costanza)
(gender male)
(occupation former_baseball_executive)
(tidbit "jerry's high school chum")
(has-friend jerry_seinfeld elaine_benes kramer)
(engaged-to susan_ross)
(has-parent estelle_costanza frank_costanza))
(person03
(name elaine_benes)
(gender female)
(occupation editor)
(tidbit "dancing fool")
(has-friend jerry_seinfeld george_costanza kramer))
(person04
(name kramer)
(gender male)
(occupation entrepreneur)
(tidbit "first name is Cosmo")
(has-parent babs_kramer)
(has-friend bob_sacamano george_costanza newman ;;new pointer from
jerry_seinfeld elaine_benes)) ;;kramer to
(person05 ;;bob_sacamano
(name helen_seinfeld)
(gender female)
(occupation retired)
(has-child jerry_seinfeld)
(married-to morty_seinfeld))
(person06
(name morty_seinfeld)
(gender male)
(occupation retired)
(has-child jerry_seinfeld)
(married-to helen_seinfeld))
(person07
(name susan_ross)
(gender female)
(occupation NBC_executive)
(tidbit "died of envelope poisoning")
(engaged-to george_costanza))
(person08
(name estelle_costanza)
(gender female)
(occupation retired)
(has-child george_costanza)
(married-to frank_costanza))
(person09
(name frank_costanza)
(gender male)
(occupation retired)
(tidbit "co-inventor of 'the bro'")
(has-child george_costanza)
(married-to estelle_costanza))
(person10
(name babs_kramer)
(gender female)
(tidbit "drunken stumblebum")
(has-child kramer))
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-friend kramer)
(has-enemy jerry_seinfeld))
)
Similarly, I want those new viewers to be able to get rid of characters
from the database as necessary. Thus, if we wanted to delete George's
fiancee who died from licking tainted glue while sealing her wedding
invitations, we'd invoke the "delete-character" function you're going
to write. This function also takes four arguments: the name of the
character to be deleted, the network, the a-list of relations, and
the a-list of names and nodes. This function returns the relational
network with the designated character's node deleted. Also missing will
be any links from other nodes to the deleted character. For example:
(delete-character 'susan_ross *database* *relations* *names*)
will return
((person01
(name jerry_seinfeld)
(gender male)
(occupation comedian)
(tidbit "loves breakfast cereal")
(has-friend kramer george_costanza elaine_benes)
(has-enemy newman)
(has-parent helen_seinfeld morty_seinfeld))
(person02
(name george_costanza)
(gender male)
(occupation former_baseball_executive)
(tidbit "jerry's high school chum")
(has-friend jerry_seinfeld elaine_benes kramer) ;;the link to susan_ross
(has-parent estelle_costanza frank_costanza)) ;;is gone
(person03
(name elaine_benes)
(gender female)
(occupation editor)
(tidbit "dancing fool")
(has-friend jerry_seinfeld george_costanza kramer))
(person04
(name kramer)
(gender male)
(occupation entrepreneur)
(tidbit "first name is Cosmo")
(has-parent babs_kramer)
(has-friend george_costanza newman jerry_seinfeld elaine_benes))
(person05
(name helen_seinfeld)
(gender female)
(occupation retired)
(has-child jerry_seinfeld)
(married-to morty_seinfeld))
(person06
(name morty_seinfeld)
(gender male)
(occupation retired)
(has-child jerry_seinfeld)
(married-to helen_seinfeld))
(person08 ;;susan_ross is no longer here
(name estelle_costanza)
(gender female)
(occupation retired)
(has-child george_costanza)
(married-to frank_costanza))
(person09
(name frank_costanza)
(gender male)
(occupation retired)
(tidbit "co-inventor of 'the bro'")
(has-child george_costanza)
(married-to estelle_costanza))
(person10
(name babs_kramer)
(gender female)
(tidbit "drunken stumblebum")
(has-child kramer))
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-friend kramer)
(has-enemy jerry_seinfeld))
)
The hard part in these latter two functions is dealing with the links
from the related nodes to the node being added or deleted. These
"backlinks" will either have to be constructed from given information
and inserted in the right places (when using "add-character") or
located from given information and deleted (when using "delete-
character"). A simple way to delete all backlinks in the example
above would be to do a more-or-less linear search through *database*
and remove any link that ended with susan_ross. Don't do that. One
of the goals of this assignment is to give you experience in tearing
apart and putting together complex list structures in just the right
places, so use the information passed to the add and delete functions
to locate the right places to add stuff and the right things to be
deleted.
Note that we're still in the functional programming paradigm. Your
add and delete functions don't make destructive changes to a database
stored in some global variable. They take the database as input via
the argument list and RETURN a modified copy of the database.
And let me answer a couple of anticipated questions. Say the newman
node looks like this:
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-friend kramer)
(has-enemy jerry_seinfeld))
And then you add to the database the node for the soup_nazi who is a
friend of newman. The newman node should end up looking like this:
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-friend soup_nazi kramer) ;; or (has-friend kramer soup_nazi)
(has-enemy jerry_seinfeld))
but not like this:
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-friend kramer)
(has-friend soup_nazi)
(has-enemy jerry_seinfeld))
That is, we won't duplicate attribute names (e.g., name, gender) or
relationship names (e.g., has-friend, has-enemy) within one character's
node, and neither should you.
Now if the newman node in the database looks like this,
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-friend soup_nazi kramer)
(has-enemy jerry_seinfeld))
and you delete the kramer node, then the newman node would have to be
updated accordingly, because it contains a pointer to kramer. Without
that pointer, the node now looks like this:
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-friend soup_nazi)
(has-enemy jerry_seinfeld))
So if you now delete the soup-nazi from the database, and the newman
node is as shown immediately above, the updated newman node should
now look like this:
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-enemy jerry_seinfeld))
not this:
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-friend )
(has-enemy jerry_seinfeld))
and not this:
(person11
(name newman)
(gender male)
(occupation postal_worker)
(tidbit "slimy schemer")
(has-friend nil)
(has-enemy jerry_seinfeld))
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,
remember: you can never watch too much TV.
Copyright 1998 by Kurt Eiselt. All rights reserved.
Last revised: April 28, 1998