Intersection Search in CommonLisp
                          for Semantic Net Inference
                                  AI CSW4701

Here  we  represent  a  Semantic Net as a collection of symbols with associated
property lists. In CommonLisp, a symbol, s, may have a property, p, with value,
v, and is coded in CL as:

(setf (get s p) v)

A  Semantic  Net,  recall, links concept and instance nodes with labeled arcs.
The labels refer to relationships that exist between the  concepts  represented
by the nodes of the net. Each node will be represented in CL by a symbol, while
the labeled arc is represented by a property name. The fact that concept X has
relation R with concept Y, will thus be coded in CL as

the value of (get X R) is Y

Recall  that  the  ISA  relation  is  very  special.  It defines a hierarchy of
concepts taxonomically. It is frequently the case that during reasoning we wish
to  determine  how  two  concepts X, and Y are related.  One means of answering
this query is to compute the most specific general concept that both  X  and  Y
are  related  to  by  the  ISA  hierarchy.   The specialized inference function
sketched below, called Intersect-search, implements this inference task.   Note
the "reserved" symbol ANYTHING is the top most concept in our hierarchy.

    (defun  Intersect-search (ConceptX ConceptY)

       (setf *Marker* (+1 *Marker*)) ;*Marker* is taken to be a global 
                                     ;variable

       (trace-and-mark ConceptX *Marker*) ;defined below
       (trace-and-find ConceptY *Marker*) ;defined below
      )

    (defun trace-and-mark (c m)
       (cond ((eql c 'ANYTHING)  c)
             (t (setf (get c 'MARK) m)
                (trace-and-mark (get c 'ISA) m))))

    (defun trace-and-find (c m)
       (cond ((eql c 'ANYTHING) c)
             ((eql (get c 'MARK) m) c)
             (t (trace-and-find (get c 'ISA) m))))


    ;AND THAT's IT!

Recall that a  partial matcher over Semantic Nets implements another
specialized  inference  task relating concepts by their set of attribute
values. one needs to record along with each concept
(symbol) a list of all of its existing properties defined  in  the  net.  Then,
computing  the  partial  match of two Semantic Nets involves a computation over
these lists. Alternatively, one can retrieve ALL attribute values of a concept
including its generalizations in the taxonomic hierarchy (everything touched
along the ISA chain) and compare the two sets of attribute values. This
latter operation would be implemented in a fashion very similar to the logic
embedded in your first pattern matcher.