Homework Assignment 4

CS 2360
Spring 1996
Homework Assignment 4
Due no later than 8:00am, Monday, April 29, 1996

Many of you are probably not aware that Atlanta is home to the 
highly-respected Institute for Television Research.  (Their motto?  
"You can never watch too much TV.")  The folks at ITR have asked us 
to help them with their on-line knowledge base (KB) of animal TV 
stars.  They know what the knowledge base is going to look like, but 
they need some help constructing the functions to let them access the
information.  More about that later.  First, let's look at a sample 
knowledge base that ITR has provided us (oh, "defconstant" is sort of
like "setf", and you should read about it in your book):

  (defconstant *animals*
    '((mammal (is-a nil)
              (prototype dog))
      (cat (is-a mammal))
      (dog (is-a mammal)
           (prototype collie)
           (legs 4)
           (speak bark))
      (collie (is-a dog)
              (color brown)
              (prototype lassie))
      (lassie (is-a collie)
              (instance? T)
              (tv-star T))
      (dolphin (is-a mammal)
               (prototype flipper)
               (speak click-whistle))
    )
  )

Note that this database is actually a relational network with 
inheritance, implemented as an association list, just like we 
discussed in class today.  (Gee Mr. Science, what a coincidence!)  
Now note that links are not only oriented "upward" (i.e., the "is-a" 
relations) but also "downward" (i.e., check out the "prototype" 
links).

What ITR needs now is some functions to help them navigate and 
retrieve information from what will someday become a very large 
knowledge base.  That's where you come in...you get to write those 
functions.  The functions can be broken into two different 
categories: those that work on a single node in the knowledge base 
(e.g., "(collie (is-a dog) (color brown) (prototype lassie))") and 
those that work on the whole knowledge base (e.g., see the data 
structure bound to *animals*).

You are to write two functions to extract information from a node.  
They're both very straightforward.  The first, called "node-id", 
takes one argument, a node, and merely returns the name or identifier 
of that node:

? (node-id '(collie (is-a dog)(color brown)(prototype lassie))) 
COLLIE

The other function, called "node-get-attribute", takes two arguments, 
a node and an attribute name, and returns the attribute if found and 
returns nil if the attribute is not found:

? (node-get-attribute '(collie (is-a dog)(color brown)(prototype lassie)) 
   'color)
BROWN
? (node-get-attribute '(collie (is-a dog)(color brown)(prototype lassie)) 
   'foo)
NIL

So much for the easy ones.  Now you can write four more functions to 
search the knowledge base for some node and then return some 
information about that node.  If you do these right, you should be 
able to use the functions "node-id" and "node-get-attribute" to your 
advantage.

The first of these functions is called "kb-find-node" and it takes 
two arguments.  The first argument is the knowledge base itself, and 
the second argument is a node name or identifier.  The function 
returns the node with that name if found in the knowledge base, or it 
returns nil if the node isn't found:

? (kb-find-node *animals* 'collie)
(COLLIE (IS-A DOG)(COLOR BROWN)(PROTOTYPE LASSIE))
? (kb-find-node *animals* 'rin-tin-tin)
NIL

The next function is called "kb-find-attr-using" and takes four (!) 
arguments.  The first is the knowledge base, the second is a node 
name, the third is an attribute name, and the fourth is the name of a
relationship to another node.  You can think of the behavior of this 
function as follows:  find a given node in the knowledge base and 
then look for the named attribute; if the attribute is found, then 
return the value associated with that attribute, but if the attribute 
is not found then repeatedly follow the named relationship link until 
the attribute is found (or until there are no more links to follow).  
Here are some examples:

? (kb-find-attr-using *animals* 'lassie 'legs 'is-a)
4
? (kb-find-attr-using *animals* 'lassie 'legs 'prototype)
NIL
? (kb-find-attr-using *animals* 'dog 'tv-star 'prototype)
T

The third function, called "kb-find-instance", takes two arguments.  
The first of these arguments is the knowledge base, and the second is 
a node name.  The function finds the named node in the knowledge base 
and then follows the "prototype" relationship links to find a node 
which is related to the given node and which is also an "instance" of 
the given node (i.e., the value associated with the "instance" 
attribute is T).  You'll want to study these examples:

? (kb-find-instance *animals* 'dog)
LASSIE
? (kb-find-instance *animals* 'flipper)
NIL
? (kb-find-instance *animals* 'cat)
NIL

The last function is a little bit different.  The folks at ITR want 
to store sound bites associated with TV animals in their knowledge 
base.  However, in the absence of sophisticated sound technology on 
ITR computers, they're going to simulate the sound bites by just 
storing the names of functions which, when evaluated, print text 
versions of the sounds that the various TV animals make.  The 
function is called "kb-perform" and it takes three arguments.  The 
first argument, naturally, is the knowledge base.  The second is the 
name of a node.  The third argument is an attribute name (which in 
this case will be the name of some behavior), but this function 
expects that it won't find a value associated with that attribute to 
be returned---instead, it expects to find the name of a function to 
be evaluated, and the result of that evaluation is what "kb-perform" 
returns.  If the function can't find the given behavior, it will 
print "Message not understoood".  Examples of these sound simulator 
functions in the sample knowledge base above are "bark" and "click-
whistle", which are defined as follows:

(defun bark ()
  (print "Woof Woof"))

(defun click-whistle ()
  (print "Click Click Whistle Click Click"))

Here are some examples of "kb-perform" in action:

? (kb-perform *animals* 'dog 'speak)
"Woof Woof"
"Woof Woof"
? (kb-perform *animals* 'lassie 'speak)
"Woof Woof"
"Woof Woof"
? (kb-perform *animals* 'cat 'speak)
"Message not understood"
"Message not understood"

Why do the simulated sound bites always appear twice?  That's a good 
question, and we have no doubt that you'll figure out the answer.

That's it.  Make sure you use procedural and data abstractions 
effectively, as some bonehead may come along and want to change the 
knowledge base sometime before the quarter is over.



Copyright 1996 by Kurt Eiselt.  All rights reserved.