Power-Programmierung/CD1.mdf/magazine/aijournl/1986_11/pfl.art

Text File | 1986-10-06 | 23KB | 662 lines

Understanding Frame Languages, Part II

"The Implementation of PFL"

by Tim Finin


Knowledge representation is fundamental to AI. Over the past 25
years, many special purpose languages have been developed for
representing knowledge in AI systems. Frame-based representation
languages (FBRLs) form a class which has achieved wide
popularity. In part one of this article, we discussed the
concepts which underly frame-based represention languages and
introduced a particular language, PFL (Pedagogical Frame
Language). In part two we give a functional description of PFL,
discuss implementational issues and exhibit portions of the
Common Lisp code which implements PFL.

PFL is was written for pedagogical purposes - it does
not attempt to be very powerful, expressive or
efficient. Although PFL is quite simple (amounting to
less than 250 lines of commented Common Lisp code) it
is sufficiently powerful to support the
representational needs of many AI applications. The
purpose of PFL and this article is twofold: (1) to
describe in the most concrete terms possible (e.g.
code) some of the concepts and mechanisms which underly
frame-based representation languages and (2) to
demonstrate some of the features of Common Lisp in the
context of a complete, useful program.


A Functional Description of PFL

This section discusses PFL from a functional point of
view. The dozen major functions are presented and
briefly described. The primary PFL functions can be can
be classified by their use into those used to create,
access, modify and display frames.  This section will
describe each of them in turn.  As an overview, the
complete list is:

(fdefine F ...) define the frame F.

(fget Fr S F D) return data facet F of slot S of frame
                Fr.

(fvalue(s) F S) return data in the :value facet of slot
                S of frame F.

(fslots F)      returns names of slots in frame F.

(ffacets F S)   returns names of facets in slot S of
                frame F.è
(fput Fr S F D) adds datum D as a datum from slot S of
                frame Fr.

(fremove Fr S F D)
                removes D to facet F of slot S of frame
                Fr.

(ferase F)      removes all local information from
                frame F then deletes it.

(framep F)      true if F is the name of a frame.

(fsubsumes F1 F2)
                true if F1 subsumes F2.

(fshow F)       show definition of frame F.


Defining Frames

(fdefine frame-name parents &rest slots)

(fdefineq frame-name parents &rest slots)

The easiest way to create a frame is just to refer to
it!  For example, saying (fget 'john 'age ':value) has
the side effect of establishing john as a frame if it
is not one already.  Two functions are provided for
explicitly creating a frame and giving it some
information: fdefine and fdefineq.  The function
fdefineq is just like fdefine except that it does not
evaluate its arguments.  A typical call to fdefineq
looks like this:

 (fdefineq cs-student student
   (major (:value computer-science)))

This expression defines cs-student to be a kind of student whose
major is "computer-science". The first argument provides the
frame's name, the second its immediate subsumers in the taxonomy
and its remaining arguments (if any) its slots. The slot
specifying arguments are lists which have the structure:

 (slot-name facet1 facet2 ... facetn)

where a facet looks like:

 (facet-name datum1 datum2 ... datumn)

A more elaborate example of a frame definitions is:

 (fdefineq course university-thing
   (name (:type string)(:min 1)(:max 1))
   (number (:min 1) (:max 1))è   (department (:type dept) (:min 1))
   (prerequisits (:type course))
   (lecturer (:type instructor)(:min 1))
   (teaching-assistant (:type ta))
   (students
     (:type student)
     (:min 1)
     (:if-added check-prerequisites)))

Note that re-defining a frame will cause the old
definition to be overwritten.


Accessing parts of Frames

Four basic functions are provided to extract
information from a frame.  The functions fget and
fvalues extract data stored in the facets of the slots
of frames.  Fget retrieves data from arbitrary facets
of a frames slot and fvalues from the :value facet.
The functions fslots and ffacets operate on a more
schematic level, retrieving the slots of a frame, and
the facets of a slot, respectively. Whether or not
inheritance is done (and the use of defaults and
demons) is controlled through the use of optional
keyword parameters.

(fget frame slot facet &key inherit)

The main frame accessing function is fget.  It takes
three required arguments which specify a frame, slot
and facet and an optional keyword parameter inherit.
It returns the data in the specified frame, slot and
facet.  Examples are:

 (fget 'john 'advisor :if-needed)
 (fget 'john 'advisor :type
     :inherit t)
 (fget 'john 'advisor :type
     :inherit nil)

The optional keyword parameter inherit controls whetheror not inheritance is used.  If it is not specified,
then tits value defaults to that of the global variable
*finherit*.

(fvalues frame slot &key inherit default demons)

The function fvalues is used to get the data in a
slot's :value facet.  It is distinct from fget because
the data in this facet can be represented explicitly or
computed from the :default or :if-needed facets.  This
function takes two required parameters which specify
the frame and slot and up to three optional keyword
parameters which control inheritance, the use of
default values and the use of if-needed demons.èExamples are:

 (fvalues stud 'courses)
 (fvalues stud 'courses :inherit nil)
 (fvalues stud 'courses
      :inherit t
      :default nil
      :if-needed nil)

The optional keyword parameters are as follows:

   - inherit - If non-nil then data can be
     inherited from any of the frame's parents if
     there are no local values, default values or
     if-needed demons.

   - default - If non-nil then a default value
     will be sought if there is no local explicit
     value.

   - demons - If non-nil than if-needed demons can
     be invoked to compute values there are no
     local values or default values.

If any of these optional keyword variables are not
specified, then their values are provided by the global
variables *finherit*, *fdefault* and *fdemons*.  These
are initially all set to T.

(fslots frame &key inherit)

This function returns a list of the names of the slots
in the frame frame.  If the keyword parameter inherit
is nil then these will include only the local slots,
otherwise the list will include all local and inherited
slots.

(ffacets frame slot &key inherit)

This function returns a list of the names of all of the facets in
frame frame and slot slot. As with the function fslots, the
keyword parameter inherit determines whether just the local or
the local and inherited slots are returned.

These last two functions, fslots and ffacets are useful
in writing functions which operate on arbitrary frame
structures.  Writing a function to display the
information in a frame, for example, requires iterating
over all of the slots in the frame and then iterating
over all of the facets in each slot:

 (defun fshow (frame)
   "displays a frame"
   (format t "~%frame ~S" frame)
   (foreach slot in (fslots frame)è     (format t "~%  slot ~S:" slot)
     (foreach facet in (ffacets frame slot)
       (format t "~%  ~S = " facet)
       (foreach datum in
         (fget frame slot facet)
         (format t "~S "  datum))))
   frame)


Adding Information

(fput frame slot facet datum &key type demons inherit
number)

This function adds a new datum to a given frame, slot
and facet after checking any appropriate type and
cardinality constraints.  If the datum is already a
local value in the facet, then nothing is done.  If the
facet is :value and if the keyword parameter :type is
non-nil, then the datum is checked for proper type.
The datum is then added to the facet and, if the facet
is :value and the keyword parameter :demons is non-nil,
any demons are run.  The :inherit keyword parameter
controls whether or not inheritance is used in
gathering the demons and type information.  The :number
keyword parameter controls the application of any
cardinality constraints (i.e. those specified by the
:min and :max facets.


Removing Information

Two primitive functions are provided for removing
information from the frame system: fremove, which
removes a given datum from the facet of a frames's slot
and ferase which erases an entire frame.

(fremove frame slot facet datum &key demons inherit
number)

This function removes the datum from the frame and slot and
facet, after checking any appropriate cardinality constraint. If
we are removing a value (e.g. the facet is :value) then any
appropriate :min constraints are checked before the value is
removed and any if-removed demons are run (provided the :demons
parameter is non-nil). The keyword parameter :inherit controls
whether or not these demons and min constraints will be
inherited.

(ferase frame &key demons inherit)

The :ferase function removes all local data in all
local facets of all local slots of the frame frame via
calls to fremove.  This may, of course, trigger
if-removed demons.  After the data have been removed,èthe frame itself is deleted. The optional keyword
parameters demons and inherit are simply passed on to
fremove.


Miscellaneous

(framep expr)

This predicate returns T if its argument is the name of
a frame.

(fsubsumes expr1 expr2)

This function returns T if expr1 can be shown to
subsume expr2. One of the two arguments must be a
frame.  Expression E1 subsumes E2 if one of the
following is true:

   - both are frames and they are equal or there
     is a chain of AKO links from E2 to E1

   - E1 is a frame and there is a predicate in its
     subsumes-if slot which is true of E2.

   - E2 is a frame and there is a predicate in its
     subsumed-if slot which is true of E1.

The last two methods are provided in order to compare
frames with other, non-frame, objects.  For example, we
can define a frame number which subsumes all lisp
numbers and a frame ageValue which subsumes numbers
between 0 and 120 as follows:

 (fdefineq number thing
   (subsumes-if (:value numberp)))

 (fdefineq ageValue number
   (subsumes-if (:value validAgeP)))

 (defun validAgeP (X)
   (and (numberp X)
        (<= 0 X 120)))


Displaying Frames

Two simple functions are provided for displaying the
definition of a frame:  fshow displays all information
in a frame and fshow-values shows just the slot values.
Again, the use of inheritance, default values and
demons is controlled by optional keyword parameters.

(fshow frame &key inherit)
èThis function displays the specified frame, including
all of its slots, facets and data.  In the keyword
parameter inherit in nil, only the local information
will be displayed.

(fshow-values frame &key inherit demons default)

This function displays the values for all of the slots
in the specified frame.  The keyword parameters are
similar to those for fvalues.


Global Variables

PFL has a small number of global variables which
control its operation.  These include:

   - *frames* - This variable is bound to a list
     of the names of all of the frames in
     existence.  Its initial value is NIL.

   - *finherit* - The default value for the
     keyword parameter inherit.  Initially
     T. Determines whether or not inheritance is
     used in seeking data from facets in a slot.

   - *fdemons* - The default value for the keyword
     parameter demons.  Initially T. Determines
     wheter or not IF-NEEDED, IF-ADDED and
     IF-REMOVED demons are invoked when seeking,
     adding or removing values from a slot,
     respectively.

   - *ftype* - The default value for the keyword
     parameter type.  Initially T. Determines
     wheter or not type checking is done when
     values are added to a slot.

   - *fdefault* - The default value for the
     keyword parameter default.  Initially
     T. Determines whether or not the :DEFAULT
     facet is used when looking for a value for a
     slot and none is found.

   - *fnumber* - The default value for the keyword
     parameter number.  Initially T. Determines
     whether or not the :MIN and :MAX constraints
     are checked when adding and removing values
     from slots.


Implementation Issues

This section describes some of the details of the
Common Lisp implementation. A listing of the code canèbe found at the end of this article. We will first
describe the overall organization of the program and
then the representation used for frames the basic
functions used to create, access and modify frames are
described.

Organization of the Program

Good programming practice dictates that any large
system should be broken up into smaller modules.
I have followed this practice and decomposed it into the
files listed below.  (Editor's note:  the following files have
been merged into the one file PFL.LSP and can be obtained by
downloading from any AI EXPERT Bulletin Board node (see page ??)
or from AI EXPERT's account on CompuServe.)

PFL.LISP        defines the PFL system

PFLVARIABLES.LISP
                global variables

PFLMACROS.LISP  macros and small utilities

PFLBASE.LISP    basic functions

PFLDISPLAY.LISP functions to display frames

PFLTHING.LISP   standard top of all taxonomies

The file PFL.LISP defines the PFL system and can be
used to load PFL.  Note the use of the "readtime
conditionals" (e.g. #+ symbolics) to customize PFL to
run on different systems. The file PFLVARIABLES.LISP
defines and intializes all of the global variables used
in PFL.  We follow the popular Lisp convention that the
names of global variables begin and end with the "*"
character. The file PFLMACROS.LISP contains the
definitions of macros and general utilities that are
used throughout the system. It is important to have these
organized into a separate file since the macro definitions are
needed whenever any other module is compiled. The main body of
the system is contained in PFLBASE.LISP. This is the largest and
most important file. Several functions for displaying frames are
found in PFLDISPLAY.LISP. Finally, some standard frames that are
to be included in every taxonomy are defined in the file
PFLTHING.LISP


Representing a Frame

In PFL a frame is represented as a list containing the
frame's name and a sublist to represent each of its
local slots. Each slot list has a name and any number
of facets.  Each facet has a name and any number of
data.  Here is the structure schematically:è
 (frame-name
    (slot1-name ...)
    (slot2-name ...)
    (slot3-name
      (facet1-name ...)
      (facet2-name datum1
                   datum2
                   ...)
        ...)
     ...)

And here is an example of a list structure for a frame
used to represent a person:

 (person
   (ako (:value animal))
   (gender (:type gender-term)
           (:min 1)
           (:max 1))
   (spouse (:type person)
           (:if-added add-inverse)))

The current implementation stores a structure which
represents a frame under the frame property of the
frame's name.  In addition, the global variable
*frames* is bound to a list of the names of all current
frames.  Thus the function which creates a frame is
relatively straightforward:

 (defun fcreate (f)
   "creates a frame with name F"
   (setq *frames* (adjoin f *frames*))
   (setf (get f 'frame) (list f)))

Indexing the frames in this way has the advantages of being very
easy to implement and allowing for extremely fact access. The
chief disadvantage is that it only allows a single, global frame
system to exist since Common Lisp's property list system is
global. This makes it impossible, for example, to maintain two
seperate knowledge bases and to quickly switch between them. A
typical alternative to this scheme is to maintain a hash-table
into which all current frames are placed, indexed by their names.
This enables one to have multiple frame systems by creating
several hash-tables.


Accessing Data in Frames

One of the most basic operations on such a frame
structure is one which gets the data associated with a
particular frame, slot and facet.  This can be
accomplished very easily by the internal PFL function
fget-local:
è (defun fget-local (frame slot facet)
   ;; returns the data in a facet w/o
   ;; inheritance or demons.
   (cdr (assoc
         facet
         (cdr (assoc
               slot
               (cdr (frame frame)))))))

where the function frame returns the structure which
represents the specified frame, creating the frame if
neccessary:

 (defun frame (f)
   (or (get f 'frame)
       (fcreate f)))

Since the CDR of NIL is defined to be NIL in Common
Lisp, this process will work even if the frame does not
have the slot or facet in question.

Of course, attempting to get data may in general
require that it be inherited from the frame's
ancestors.  If the facet in question is the :value
facet, then we may have to look for corresponding
:default or :if-needed facets.  The fget function takes
three required arguments specifying a frame, slot and
facet and returns a list of the data found.  Whether or
not inheritance is done is controlled by the optional
keyword parameter :inherit.  If the facet in question
is the :value facet, then we can control whether or not
demons can be invoked to compute the values and whether
or not default values will be accepted through the use
of the optional keyword parameters :demons and default.
Note that fget simply passes the job onto fget-value or
fget1, depending on whether or not the facet sought is
the :value facet.

 (defun fget
        (frame slot facet
          &key (inherit *finherit*)
               (demons *fdemons*)
               (default *fdefault*))
   (if (equal facet :value)
       (fvalues frame slot facet
          :inherit inherit
          :demons demons
          :default default)
       (fget1 frame slot facet inherit)))

 (defun fget1 (frame slot facet inherit?)
    "returns data in frame, slot and facet"
    (or (fget-local frame slot facet)
        (if inherit?
          (forsome parent in (fparents frame)è              (fget1 parent slot facet t)))))

 (defun fvalues (f s
                 &key (inherit *finherit*)
                      (demons *fdemons*)
                      (default *fdefault*)
                      (finitial f))
    "returns values from frame F slot S"
    (or (fget-local f s :value)
        (and default
             (fget-local f s :default))
        (and demons
             (forsome demon in
               (fget-local f s :if-needed)
               (listify (funcall demon finitial s))))
        (and inherit
             (forsome parent in (fparents f)
               (fvalues parent s
                  :inherit t
                  :demons demons
                  :default default
                  :finitial finitial)))))


Adding Data to a Slot

New data is added to a facet of a slot using rplacd to
modify the list representation the facet, appending the
new datum to the end of the list. The ffacet function
is used to get this facet structure, creating it if
neccessary.

 (defun fput-add (frame slot facet datum)
    ;; adds datum to given (frame,slot,facet)
    (rplacd (last (ffacet frame slot facet))
            (list datum)))

 (defun ffacet (frame slot facet)
    ;; returns the expression representing
    ;; given (frame, slot,facet), creating
    ;; it if neccessary.
    (extend facet (extend slot (frame frame))))

 (defun extend (key alist)
    ;; like assoc, but adds key KEY if
    ;; its not in the alist AlIST.
    (or (assoc key (cdr alist))
        (cadr (rplacd (last alist)
                      (list (list key))))))

In general, putting a value into a facet of a slot is
somewhat more complex.  If the value is already
present, then nothing need be done. if the facet in
question is the :value facet, then we must check to see
if the candidate value satisfies all of the typesèassociated with the slot (as specified in the :type
facet), ensure that the slot is still open to receiving
additional values (checking the :min facet), and
finally, triggering any if-added demons associated with
the slot. The following functions accomplishes this
process:

 (defun fput (frame slot facet datum
              &key (demons *fdemons*)
                   (type *ftype*)
                   (inherit *finherit*)
                   (number *fnumber*))
   ;; adds a datum to a slot.
   (cond ((member datum (fget-local frame slot facet))
          datum)
         ((equal facet :value)
          (fput-value frame slot datum
             demons type inherit number))
         (t
          (fput-add frame slot facet datum)
          datum)))

 (defun fput-value (frame slot datum demons?
                    type? inherit? number?)
    ;; adds value to slot if the types are ok
    ;; & slot isn't full, then runs demons
    (unless
      (and type? (not (fcheck-types frame slot datum)))
      (unless (and number?
                   (not (fcheck-max frame slot)))
        (fput-add frame slot :value datum)
        (if demons?
            (foreach demon in
              (fget frame slot :if-added
                    :inherit inherit?)
              (funcall demon frame slot datum)))
        datum)))


Removing Values

Removing data from a facet of a frame's slot is
relatively easy.  We first must ensure that the datum
is indeed a locally stored one.  Then, if the facet in
question is the :value facet, we must verify that the
datum's removal will not leave too few data in the
facet.  The actual removal can then be done with a
simple call to delete.  Finally, if we are removing a
value, we must run any if-removed demons associated
with the slot.

 (defun fremove (frame slot facet datum
                 &key (demons *fdemons*)
                      (inherit *finherit*)
                      (number *fnumber*))è    ;; removes datum from frame's slot's facet
    (when (and (member datum
                       (fget-local frame slot facet))
               (or (not (eq facet :value))
                   (fcheck-min frame slot)))
          (delete datum (ffacet frame slot facet))
          (if (and (eq facet :value) demons)
              (foreach demon in
                (fget frame slot :if-removed
                      :inherit inherit)
                (funcall demon frame slot datum)))))