Homework Assignment 4

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

Today in class we introduced the notion of an inheritance network.
One 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, 
make it all very understandable, provide appropriate commenting, 
and remember that we're still living in a functional programming world.



Copyright 1998 by Kurt Eiselt.  All rights reserved.