Homework Assignment 4

CS 2360
Winter 1997
Homework Assignment 4
Due no later than 8:00am, Monday, February 10, 1997 

So, you've been busting your butt trying to get a handle on all this
functional programming and recursion, and you're falling behind in
your other classes, and maybe you still have a midterm or two yet to
go this week.  Here's your chance to catch up.  Assignment 4 is
optional.  Yes, that's right, this assignment is completely optional.
That is, you already have a perfect score on this assignment, no matter
what you do.  If you're feeling harried right now and need some time
to work on something other than CS 2360, this is an opportunity
to do so.  But if you'd like to continue to hone your abstracting-
functional-programming-Lisp-hacking edge, go ahead and practice on
this one, and turn it in by the date and time above, and you'll get
feedback on how you did.  This is not, however, an opportunity for
*extra credit*.  If you want the practice and the feedback, and you
can afford the time, do the assignment.  If not, don't do the assignment.
Either way, you'll get full credit.  Now, here's the optional assignment:

Today in class we introduced the notion of an inheritance network.
An abstraction of an inheritance network is a tree, or more accurately, a
directed acyclic graph, which includes trees but also includes structures that
aren't strictly trees.  Here's an example of a simple inheritance network:

                                 animal
                                  ^ ^
                                 /   \
                                /     \
                               /       \
                         is-a /         \ is-a
              blood          /           \          blood
       cold {-------\       /             \       /-------} warm
                     \     /               \     /
                      -dinosaur             bird-
               move  / ^^                     ^^ \  move
       walk {-------/ /  \                   /  \ \-------} fly
                     /    \                 /    \
               is-a /      \ is-a     is-a /      \ is-a
                   /        \             /        \
       move       /          \           /          \    move
fly {-------pterodactyl  brontosaurus  canary    ostrich-------} walk

What does this thing mean?  (Other than that my knowledge of zoology is
severely impaired.)  This inheritance network says that dinosaurs and birds
are both subclasses of the class of animals.  Those relationships are denoted
by the is-a link pointing upwards, as in "a dinosaur is-a animal".  Birds have
two properties: they are warm-blooded, and the move primarily by flight.
Dinosaurs have two properties too: they are cold-blooded (depending on
whose theory you like), and they move primarily by walking.  Pterodactyls 
and bronotosaurs are both dinosaurs, but pterodactyls don't walk most of 
the time, they fly.  Canaries and ostriches are both birds, but ostriches 
don't fly, they walk.

Your task for this assignment is to implement the structure shown above using
Common LISP's a-list abstract data type.  Then you are to write four functions
called RETRIEVE?, CONFIRM?, COMMON?, and ALL-ATTRIBUTES? which use the 
inheritance network to answer questions posed in the following way:

RETRIEVE? takes three arguments, the name of a class, a relationship (e.g.,
is-a, move, blood), and an inheritance hierarchy, and returns the first class
(i.e., the class that's lowest in the hierarchy) it can find that completes the
relation.  For example (assuming the association list representing the
inheritance hierarchy is bound to the variable named HIERARCHY):

(retrieve? 'brontosaurus 'is-a hierarchy) => dinosaur
(retrieve? 'canary 'move hierarchy) => fly
(retrieve? 'ostrich 'move hierarchy) => walk
(retrieve? 'bird 'is-a hierarchy) => animal
(retrieve? 'bird 'eats hierarchy) => nil

CONFIRM? takes four arguments: a class name, a relationship, another class 
name, and an inheritance hierarchy, and returns a value indicating whether 
that relationship holds, either directly or indirectly through any number 
of levels of inheritance.  For example:

(confirm? 'brontosaurus 'is-a 'dinosaur hierarchy) => T
(confirm? 'dinosaur 'is-a 'brontosaurus hierarchy) => nil
(confirm? 'brontosaurus 'is-a 'animal hierarchy) => T
(confirm? 'canary 'is-a 'dinosaur hierarchy) => nil
(confirm? 'canary 'move 'fly hierarchy) => T
(confirm? 'ostrich 'move 'fly hierarchy) => nil

COMMON? takes two class names and an inheritance hierarchy as arguments and
returns the lowest class in the hierarchy which contains both named classes:

(common? 'brontosaurus 'pterodactyl hierarchy) => dinosaur
(common? 'brontosaurus 'ostrich hierarchy) => animal

ALL-ATTRIBUTES? takes two arguments: a class name and an inheritance hierarchy.
The function returns a list of all attributes (including inherited attributes)
associated with that class name.  For example:

(all-attributes? 'ostrich hierarchy) => ((move walk) (blood warm))
(all-attributes? 'bird hierarchy) => ((move fly) (blood warm))
(all-attributes? 'animal hierarchy) => nil
(all-attributes? 'chihuahua hierarchy) => nil

Note that ALL-ATTRIBUTES? did not include both (move walk) and
(move fly) in the list of attributes for the ostrich class.  Also, the 
order in which the attributes are shown in the list is not important.  
Thus, if your version of ALL-ATTRIBUTES? returns ((blood warm) (move walk)) 
for the ostrich class, that's ok too.

That's it.  Make sure you use procedural and data abstractions effectively, 
and remember that we're still living in a functional programming world.
And however you spend your time this week, please spend it wisely.



Copyright 1997 by Kurt Eiselt.  All rights reserved.