Dec 282017
 
Text file explaining the theory of OOP's programming.
File OPPSTEXT.ZIP from The Programmer’s Corner in
Category Miscellaneous Language Source Code
Text file explaining the theory of OOP’s programming.
File Name File Size Zip Size Zip Type
OOPS.TXT 116432 28273 deflated

Download File OPPSTEXT.ZIP Here

Contents of the OOPS.TXT file


This file was captured from a series of messages written by Gordon Lee and
uploaded to the OOPS conference on the Interlink network. Lee is the AI
conference moderator on that network. Unfortunately, a couple of messages
in the sequence were not posted for some reason.

The originating BBS for these messages was the following:

Rose Media - NSA Canada - 416-733-2285

--Bob Simanski
Herndon, VA
June 8, 1989

==============================================================================
Date: 06-02-89 (23:53)
To: ALL
From: GORDON LEE
Subj: OBJECTS/FRAMES
------------------------------------------------------------------------

An Example
In terms of the house-painting example, the COLOUR slot
might have a symbolic representation (e.g., "RED" rather than
"fire-engine red" or "colour 7329"), while the PRICE slot might
have a decimal representation. The SURFACES slot might be a
multivalued slot containing a number of terms on which the paint
could be applied. The INSTRUCTIONS slot might contain English
text describing the manner of application of the paint, while the
GLOSS slot might have a logical representation (e.g., "TRUE") as
in Figure 3.

_____________________________________________
| OUTSIDE-PAINT |
|_____________________________________________|
| COLOUR | RED |
|_______________|_____________________________|
| PRICE | 12.99 |
|_______________|_____________________________|
| SURFACES | (Wood, Stucco, Concrete |
|_______________|_____________________________|
| INSTRUCTIONS | Prepare surface by removing |
| | any loose paint, dirt, or |
| | grease. Apply primer..... |
| | dry for 12 hours. |
|_______________|_____________________________|
| TYPE | Latex |
|_______________|_____________________________|
| GLOSS | TRUE |
|_______________|_____________________________|

Figure 3: Frame with Slots and Values


Value Forms
As the example illustrates, many different forms might
appropriately be used to represent values. An application
developer would typically employ some of the following types of
representation in a system:

* Numerical
- integer
- decimal
- floating point (engineering notation)
* Logical
* Symbolic
* Text
* Graphical or pictorial


Restrictions
So far, no restrictions have been placed on the possible
contents of a particular slot. Thus, while a decimal value might
logically be expected in the price slot (e.g., 12.99), nothing
would prevent an entry of TWELVE DOLLARS AND NINETY NINE CENTS
from being made. Even worse, a nonprice value could be stored in
the slot (e.g., LATEX). Since such values would not be very
meaningful, certain restrictions on slot contents must often be
applied. Although several types of restrictions might be
applied, only three are discussed at this point:

1. Restrictions on the form of the representations (e.g.,
only decimal values permitted)
2. Restrictions on the value that can be stored (e.g.,
only prices between 9.99 and 19.99 permitted)
3. Restrictions that are independent of specific values
(e.g., no more than three values in the slot.


Representation Restrictions
To be able to process knowledge contained in the slots of
frames, the reasoning system must be able to interpret the values
in a slot unambiguously; it must know (and be able to understand)
the form of representation of the knowledge in the slot.
Consider the COLOUR slot, for example, containing the value RED.
For the term to be meaningful, the inferencing mechanism must
interpret RED as a symbol (from which the meaning "fire-engine
red" might be inferred) rather than as text (i.e., the three
letters R, E, and D).

To accomplish this the knowledge engineer can attach a
restriction to a slot, limiting the form of the value(s) that can
be stored in it. In the case of the COLOUR slot, for example,
the following restriction could be applied:

RESTRICTION: (VALUE-TYPE:SYMBOL)

Similarly, the PRICE slot might be restricted to hold
decimal values, the GLOSS slot logical values, and so forth.


Value Restrictions
Ensuring that a slot's value has the proper form of
representation only solves part of the problem, for the value
itself, when interpreted correctly, must also be meaningful.
Assume for the moment that there are only four colours of outside
paint - fire-engine red (with symbol RED), chocolate brown (with
symbol BROWN), creamy pearl (with symbol WHITE), and forest moss
(with symbol GREEN). Under these circumstances, the symbol
MAGENTA in the COLOUR slot would be in error, just as a value of
$ or % would be in error. Yet, both MAGENTA and $ are valid
symbols. Thus, a further restriction must be attached to the
slot, limiting the specific symbols that can be stored in it to
only those that represent valid paint colors. In the case of the
COLOUR slot, for example, the following restriction could be
applied:

RESTRICTION: (CONTENT-ONE-OF: RED BROWN WHITE GREEN)

This restriction would exclude values that represented paint
colours not offered (e.g., MAGENTA) as well as values that do not
represent a paint colour (e.g., $).

A variety of similar restrictions might be placed on other
slots. For example, values in the PRICE slot might be
constrained to fall within a range of numbers or to exclude
certain numbers (e.g., even dollar amounts). Consider, for
example, a slot containing the floor on which a particular office
is located in a 50-story building. The restriction placed on
such a slot might contain a mixture of ranges and specific
values, such as:

RESTRICTION: (CONTENT-ONE-OF: G B LL M 2:12 14:48 P R)

On the other hand, because of the variety of floor names
that might be possible (e.g., garage, basement, lower-level,
mezzanine, penthouse, roof), the developer may need to specify
only what may not be used as a floor name (e.g., the 13th floor).

RESTRICTION: (CONTENT-NOT-ONE-OF: 13)


Other Types of Restrictions
The developer might wish to apply several other types of
restrictions in appropriate situations. For example, the maximum
(or minimum) number of values that could be placed in a slot at
any one time might be specified. Consider the house painting
example again. If the mixing of paint colours is to prevented,
the COLOUR slot could be constrained to holding a single colour
as follows:

RESTRICTION: (MAX-NUMBER-OF-VALUES: 1)

Similarly, the relation that the frame might bear to other frames
can be constrained.


An Example
Taking restrictions into consideration, the OUTSIDE-PAINT
frame might be set up as shown in Figure 4.
__________________________________________________________
| OUTSIDE-PAINT |
|__________________________________________________________|
| COLOUR | RED |
| |__________________________________________|
| | RESTRICTION: (VALUE-TYPE: SYMBOL) |
| |__________________________________________|
| | RESTRICTION: (CONTENT-ONE-OF RED |
| | BROWN WHITE GREEN) |
| |__________________________________________|
| | RESTRICTION: (MAX-NUMBER-OF-VALUES: 1) |
|_______________|__________________________________________|
| PRICE | 12.99 |
| |__________________________________________|
| | RESTRICTION: (VALUE-TYPE: DECIMAL) |
| |__________________________________________|
| | RESTRICTION: (CONTENT-ONE-OF 9.99 12.99) |
|_______________|__________________________________________|
| SURFACES | (Wood, Stucco, (Nonporous Concrete)) |
| |__________________________________________|
| | RESTRICTION: (MAX-NUMBER-OF-VALUES 10) |
|_______________|__________________________________________|
| INSTRUCTIONS | Prepare surface by removing any loose |
| | paint, dirt, or grease. Apply primer... |
| | dry for 12 hours. |
|_______________|__________________________________________|
| TYPE | Latex |
| |__________________________________________|
| | RESTRICTION: (CONTENT-NOT-ONE-OF: |
| | Water-Based) |
|_______________|__________________________________________|
| GLOSS | TRUE |
| |__________________________________________|
| | RESTRICTION: (VALUE-TYPE: LOGICAL) |
| |__________________________________________|
| | RESTRICTION: (CONTENT-ONE-OF TRUE FALSE |
| | UNKNOWN) |
| |__________________________________________|
| | RESTRICTION: (MAX-NUMBER-OF-VALUES: 1) |
|_______________|__________________________________________|

Figure 4: Frame with Slots, Values, and Restrictions


What Controls How a Slot Is Treated?
The previous subsection described some of the types of
restrictions that a developer might wish to place on the contents
of a slot, but such restrictions are not the only type of
specification that might be used to control particular aspects of
slot value processing. For example, the developer might like to
specify the type font and point size with which a value should be
displayed. Thus, some mechanism is needed by which a value
should be displayed. Thus, some mechanism is needed by which
such control information can be attached to slots in a frame.


Facets
This mechanism is the "facet." Facets contain certain types
of information that are related to a slot. A variety of
different facets may be attached to the same slot, each providing
a different type of control parameter or characteristic. The
contents of the appropriate facet are checked whenever a
particular type of action is to be performed (e.g., fetch, store,
display, query) in connection with a slot value.


Standard Facets
A knowledge-based application development tool (shell)
offering frame-based representations will likely provide a number
of standard facets. That is, any application generated using the
tool would contain the necessary program code or instructions to
perform the required processing of any values contained in one of
these standard facets. The application developer need only
provide the appropriate contents of a facet in order for that
facet to be effective in providing its intended function.

Adding a facet structure to a frame, then, provides a
mechanism for representing the various types of slot value
restrictions discussed previously as well as for representing
other characteristics such as display format. Some of the
standard facets that a knowledge-based application development
tool (shell) might provide for each slot in a frame include:

* Permitted representational form(s) for the values in
the slot
* Permitted values for the slot
* Maximum number of values permitted in the slot
* Minimum number of values permitted in the slot
* Display format for the slot's value
* Explanation about the purpose or meaning of the slot
* Text of question to be asked in the event that the user
is requested to provide a value for the slot
* Text of response to be provided should the user
question the purpose of the request for a slot value.

A variety of other facets that relate to inheritance and class
structure relationships might also be made available.


Active Values
Facets can be used to support a number of special-purpose
capabilities. Since access to a slot value in a frame takes
place only after the system refers to the relevant facets
controlling access, setting up a facet to indicate that a slot
value is active is relatively easy. That is, any access to an
active slot turns control over to an "active value" routine
before access is made.

Frame-based systems commonly provide a number of standard
active value routines that will plot, graph, or signal the value
each time the slot's contents change. However, the knowledge
engineer can also use active values as a monitoring capability by
specifying a routine to be given control each time access is to
be made to a slot. Access may be intercepted just prior to a
data store or immediately after a data fetch. The routine
receiving control may then modify or substitute values, log the
access, or turn control over to the user to browse the knowledge
base. This mechanism provides the knowledge engineer with an
easily created filter, enabling values to be range- and type-
checked either before they are stored or before they are returned
to the requesting program or rule.

Active values can be used as a regular part of the knowledge
representation. Thus, the storage of a particular value in a
state slot can be used as the trigger to initiate the processing
of a specified rule-set. However, active values also offer the
knowledge engineer a handy debugging mechanism. An active value
can readily be attached to a slot, with control being turned over
to the knowledge engineer (or his/her debugging routine) when
activated. Various system values can be examined and displayed
before regular execution of the application is resumed. This
capability is perhaps the most valuable testing and debugging
tool provided by a frame-based system.


Developer-Specified Facets
Generally speaking, a knowledge-based application
development tool cannot provide all of the facets that a
developer might wish to attach to a particular slot. The ones
described in the previous subsection could be viewed as generic
facets, facets that are related to the reasoning process in
general and that are unrelated to any particular application.
Because additional problem-dependent facets are also needed,
however, the development tool should offer a mechanism that will
enable the developer to define and add facets that are related to
the particular application. Of course, the developer will also
have to provide the necessary programming to implement handling
of the facet!

Consider the following example of a developer-specified or
application-dependent facet, in which the developer wants to use
the facet to record the source from which the current value of a
slot was obtained (e.g., input by the user, initialized default
value using Rule 7 of Rule-Set 3). This facet would be analogous
to the "why" facet. Instead of containing the text of an
explanation, however, the facet would contain the source from
which the current slot value was obtained. Specifying a new
facet is generally quite easy with tools (shells) that permit
developer-specified facets. In addition to creating the facet,
however, the developer must also provide the mechanism to
implement the facet's intent. In the case of the "how" facet,
the developer would have to create a mechanism to trap any store
into the slot, backtrack to determine the appropriate source
designation for that value, store that designator in the facet,
and complete the trapped store (i.e., putting the value in the
slot as originally attempted).


Where Are Frames Useful?
Frames are useful in categorizing knowledge when that
knowledge has some underlying structure. If the knowledge can be
related to a set of objects or concepts, then at least a portion
of the facts contained in the knowledge base can be clustered
around those objects or concepts.

To illustrate, consider a knowledge base dealing with
automobiles. By clustering the knowledge around each type of
automobile, a user could obtain information on Chevrolets without
having to search through all the knowledge about automobiles.
This type of retrieval would take advantage of the frame
structure, referring only to the slots in a particular frame.
Similarly, the user could obtain information on tire types
without having to search through all the knowledge in the
knowledge base, looking at a particular slot in a number of
frames. This type of retrieval would take advantage of the slot
structure. These two types of access to the knowledge are
illustrated in Figure 5. The frame structure permits the
knowledge engineer and the domain expert to view the contents and
structure of the knowledge base in a way that facilitates greater
understanding as well as a greater ability to detect inconsistent
or incomplete data.

__________________ __________________ __________________
| CHEVROLETS | | CHRYSLER | | FORD |
|__________________| |__________________| |__________________|
|BODY-TYPE | | |BODY-TYPE | | |BODY-TYPE | |
|_____________|____| |_____________|____| |_____________|____|
|TIRES | | |TIRES | | |TIRES | |
|_____________|____| |_____________|____| |_____________|____|
|ENGINE-TYPE | | |ENGINE-TYPE | | |ENGINE-TYPE | |
|_____________|____| |_____________|____| |_____________|____|
|FUEL-REQUIRED| | |FUEL-REQUIRED| | |FUEL-REQUIRED| |
|_____________|____| |_____________|____| |_____________|____|
|BATTERY-TYPES| | |BATTERY-TYPES| | |BATTERY-TYPES| |
|_____________|____| |_____________|____| |_____________|____|

Figure 5: Knowledge Access by Frame and by Slot


Thus, in the rough design portion of the feasibility study,
the knowledge engineer should be looking at the characteristics
of the knowledge that is expected to be placed in the knowledge
base, identify whether it will likely consist of a loose
collection of unrelated facts or whether it will likely consist
of a number of clusters of related facts. The knowledge engineer
should search to identify not only what objects or concepts
(around which knowledge can be clustered) but also how many such
objects and concepts might exist. The larger the number, the
greater the advantage a frame-based representation can provide.


STRUCTURE

Thus far, frames have not been related to each other in any
way. The illustrations have just shown frames without any
connection among them. In practical applications, however, the
objects or concepts represented by frames often do bear some
relationship to each other. Part of the power of a frame-based
representation is its ability to capture such relationships and
to represent this structure in the knowledge base.

One way to view such relationships is with the concept of
refinement. That is, as attention shifts systematically from one
frame to the next in a collection of related frames, the idea or
object represented by each frame becomes progressively either
more general or more specific. The description in the following
subsections moves in what is commonly viewed as the downward
direction, from general to specific. (Related frames are
generally displayed as a two-dimensional hierarchy, with the more
general frames at the top of the display and the more specific
frames at the bottom. Hence, traversing frames from general to
specific implies movement down the page.)


Classes
The term "class" is used to denote a frame containing the
knowledge about a set or class of objects of a given type. Thus,
a frame might be established for the class AUTOMOBILE. All other
clusters of knowledge about particular aspects of automobiles
would be associated with subordinate frames. However, knowledge
about unrelated concepts would be associated with frames in
different classes. Thus, the knowledge base might contain the
classes AUTOMOBILE, KITCHEN-UTENSILS, and SHOES, as shown in
Figure 6.

_______________ _______________ _______________
| AUTOMOBILES | |KITCHEN-UTENSIL| | SHOES |
|_______________| |_______________| |_______________|
| | | | | |
| | | | | |
|_______________| |_______________| |_______________|

Figure 6: Three Class Frames


Subclasses
The frames in a "subclass" represent a particularization or
a specialization of the class to which they relate. Thus, the
class AUTOMOBILES might have the subclasses of DOMESTIC and
IMPORTED, as shown in Figure 7. The frames representing these
two subclasses would have more specialized information that
pertains to one of the two types of automobiles (i.e., domestic
cars or imported cars) but that does not pertain to the class of
automobiles as a whole. The subclass provides additional
knowledge beyond what is available at the class level. The
subclass is thus different from a mathematical subclass; it
represents a narrowing of the concept but also an expansion of
the information about the concept.
_____________________
| AUTOMOBILES |
|_____________________|
______|______
__________________|___ ___|_________________
| DOMESTIC | | IMPORTED |
|______________________| |_____________________|

Figure 7: Two Subclasses of Automobiles

Note that subclasses are themselves classes, for they in
turn can have subclasses. To avoid confusion, we shall refer to
classes and subclasses alike as classes. Since classes deriving
from another class can give rise to further derivative classes,
the concept specialization process can continue iteratively.
Each lower class in the hierarchy represents a further
specialization of the concept. (Or, looking at the hierarchy the
other way, each class represents a generalization of a
subordinate class.) Thus, the class DOMESTIC might have three
subclasses representing automobiles manufactured by three
companies: CHEVROLET, FORD, and CHRYSLER. The class FORD might
in turn have two subclasses representing two different models
manufactured: RANCHERO and LTD. This process could continue on
to body type (e.g., sedan, station wagon) and other features.
This class hierarchy is shown in Figure 8.

_____________________
| AUTOMOBILES |
|_____________________|
______|______
__________________|___ ___|_________________
| IMPORTED | | DOMESTIC |
|______________________| |_____________________|
___________________________________|_______
________|_________ ________|_________ ________|_________
| CHEVROLET | | FORD | | CHRYSLER |
|__________________| |__________________| |__________________|
______|______
__________________|___ ___|_________________
| RANCHERO | | LTD |
|______________________| |_____________________|

Figure 8: Class Structure of Automobiles

Although not shown in Figure 8, each of the other domestic
automobile classes (e.g., CHEVROLET) could be broken down into
model based subclasses, and the IMPORTED class could have a
similar class graph attached to it.

This class structure serves to structure the knowledge, and
the resulting class hierarchy is often referred to as a
"taxonomy." Thus, the structure in Figure 8 would be referred to
as the automobile taxonomy.


Instances
Sooner or later no further subdivisions are possible without
losing the concept of a class that represents multiple objects.
At this point, the next further specialization would be a
particular "instance." Each such instance would represent a
specific case of instantiation of the general concept. Thus, as
shown in Figure 9, the class RANCHERO might have three instances,
with frames representing MY-FORD, JIM'S-FORD, and SUSAN'S-FORD.
By convention, the dotted line represents a class-instance
relationship while the solid line represents a class-subclass
relationship. Each instance frame represents a particular
automobile having a specific owner, colour, registration number,
and so forth.
_____________________
| AUTOMOBILES |
|_____________________|
______|______
__________________|___ ___|_________________
| IMPORTED | | DOMESTIC |
|______________________| |_____________________|
___________________________________|_______
________|_________ ________|_________ ________|_________
| CHEVROLET | | FORD | | CHRYSLER |
|__________________| |__________________| |__________________|
| |
__________________|___ ___|_________________
| RANCHERO | | LTD |
|__________.___________| |_____________________|
.......:.....................................
________:_________ ________:_________ ________:_________
| MY-FORD | | JIM'S-FORD | | SUSAN'S-FORD |
|__________________| |__________________| |__________________|

Figure 9: Automobile Taxonomy with Instances

The graph of the class hierarchy can be viewed as an upside-
down tree. The class at the top represents the root of the tree,
while the instance at the bottom represents the leaves. Just as
nothing grows from the leaves of a real tree, so does nothing
grow from the leaves of the frame tree. There is no
categorization more specialized than the instance.


Intersecting Hierarchies
The automobile taxonomy illustrated in Figure 9 was created
as an isolated knowledge structure, but this need not be the
case. Classes and instances can be related between taxonomies.
Consider two other taxonomies about trucks and the other the
knowledge about engines.

Figure 10a shows the class TRUCKS broken down into two
subclasses, SPECIAL-PURPOSE and CARGO. The SPECIAL-PURPOSE class
is further broken down into two subclasses, FIRE-TRUCK and TOW-
TRUCK, while the CARGO class is broken down into GENERAL-GOODS,
TANK, and CATTLE. The general goods class is broken down into
1/2-TON, 1-TON, and 2-TON subclasses, and the 1/2-ton class has
two instances. A much broader taxonomy could be developed, but
this brief one will serve to illustrate a point.

_____________________
| TRUCKS |
|_____________________|
______|______
__________________|___ ___|_________________
| SPECIAL-PURPOSE | | CARGO |
|______________________| |_____________________|
_______| ___________________________________|_______
| ________|_________ ________|_________ ________|________
| | TANK | | CATTLE | | GENERAL-GOODS |
| |__________________| |__________________| |_________________|
|________________ |
__________|___________ _____________________ |
| FIRE-ENGINE |_____| TOW-TRUCK | |

|______________________| |_____________________| |
__________________________________________________|
________|_________ ________|_________ ________|_________
| 1/2-TON | | 1-TON | | 2-TON |
|________._________| |__________________| |__________________|
:............................
__________________:___ ___:_________________
| MARY'S-TRUCK | | GEORGE'S-TRUCK |
|______________________| |_____________________|

Figure 10a: The Truck Taxonomy

The Ranchero is an interesting vehicle in this context.
Because it consists of the front half of a passenger car and the
rear half of a truck, the RANCHERO class (or any instance of that
class) relates to concepts in both hierarchies. This
relationship is represented in Figure 10b by the dotted line
connecting the instance MY-FORD to the class RANCHERO (making it
a member of AUTOMOBILES) and to the class 1/2-TON (making it a
member of TRUCKS), which means that MY-FORD is an instance of
both classes and has all the properties of a Ranchero automobile
and all the properties of a 1/2-ton truck. Such a passing of
properties from class to class or instance and from multiple
classes to another class or instance illustrates the
"inheritance" of properties down through the knowledge taxonomy.
The concept of inheritance is discussed later.
______________________ _____________________
| AUTOMOBILES | | TRUCKS |
|______________________| |_____________________|
| |
__________|___________ __________|__________
| DOMESTIC | | CARGO |
|______________________| |_____________________|
| |
__________|___________ __________|__________
| FORD | | GENERAL-GOODS |
|______________________| |_____________________|
| |
__________|___________ __________|__________
| RANCHERO | | 1/2-TON |
|______________________| |__________.__________|
: :
__________:___________ :
| MY-FORD |................:
|______________________| :

Figure 10b: Skeleton of Two Taxonomies

Connections can also be made higher up in the taxonomy
(i.e., between classes). For example, the class RANCHERO could
be related as a subclass of both the FORD and GENERAL-GOODS
classes, as shown in Figure 10c.

______________________ _____________________
| AUTOMOBILES | | TRUCKS |
|______________________| |_____________________|
| |
__________|___________ __________|__________
| DOMESTIC | | CARGO |
|______________________| |_____________________|
| |
__________|___________ __________|__________
| FORD | | GENERAL-GOODS |
|______________________| |_____________________|
|____________________________|
__________|___________ __________|__________
| RANCHERO | | 1/2-TON |
|______________________| |__________.__________|
: :
__________:___________ :
| MY-FORD | :
|______________________| :

Figure 10c: Skeleton Taxonomies with More Abstract Connection

This relationship would imply that all Ranchero were domestic
Ford automobiles and that they were all general-goods carrying
trucks (no cattle trucks or fire engines), but it would not imply
anything about the load-carrying capacity of the Ranchero. Thus,
the connection between RANCHERO and GENERAL-GOODS implies that
the RANCHERO automobiles are a particularization of the class
FORD (and all classes above it). However, none of the knowledge
in the tree extending below GENERAL-GOODS has any fixed relation
to RANCHERO automobiles. Thus, RANCHERO vehicles are potentially
eligible to have either 1/2-TON, 1-TON, or 2-TON capacities.

Now consider the engine taxonomy. As shown in Figure 11a,
the class ENGINES is broken down into the subclasses DIESEL and
GASOLINE. The GASOLINE class is further broken down into
CARBURETED and FUEL-INJECTED subclasses. The FUEL-INJECTED class
is further divided into cylinder-based subclasses. Although not
shown in Figure 11a, similar subtrees would extend down from the
CARBURETED and DIESEL classes.

_____________________
| ENGINES |
|_____________________|
______|______
__________________|___ ___|_________________
| DIESEL | | GASOLINE |
|______________________| |_____________________|
_____________________|
__________________|___ ___|_________________
| CARBURETED | | FUEL-INJECTED |
|______________________| |_____________________|
___________________________________|_______
________|_________ ________|_________ ________|________
| 4-CYLINDER | | 6-CYLINDER | | 8-CYLINDER |
|__________________| |__________________| |_________________|

Figure 11a: The Engine Taxonomy

Assume for the moment that MY-FORD has an 8-cylinder, fuel-
injected, gasoline engine. The novice knowledge engineer might
be tempted to establish a relation similar to the one shown in
Figure 11b, making MY-FORD a subclass of both RANCHERO and 8-
CYLINDER. After all, MY-FORD does have an 8-cylinder engine with
all the properties indicated in the 8-CYLINDER, FUEL-INJECTED,
GASOLINE, and ENGINES classes. However, while MY-FORD is a
particularization of the classes RANCHERO, FORD, DOMESTIC, and
AUTOMOBILES, it is not a particularization of any of the classes
8-CYLINDER, FUEL-INJECTED, GASOLINE, or ENGINES. The car I am
driving has an engine, but it is "not" an example or instance of
an engine. Therefore, a different type of connection is needed.

The proper relationship is of the form "contains" or
"has-a." Thus, the knowledge engineer could specify that all
Rancheros contain fuel-injected engines by using the relation:

RELATION: RANCHERO HAS-A FUEL-INJECTED

This relation is indicated by the solid line connecting the
sides of the RANCHERO and FUEL-INJECTED class boxes in Figure
11c. Such a relation indicates that every Ranchero vehicle has a
fuel-injected, gasoline-powered engine. All of the
characteristics of such an engine are available to the RANCHERO
frame, but there is no implication that the RANCHERO is an
instance of FUEL-INJECTED. Relations are discussed in greater
detail in the section of relationship knowledge.

______________________ _____________________
| AUTOMOBILES | | ENGINES |
|______________________| |_____________________|
| |
__________|___________ __________|__________
| DOMESTIC | | GASOLINE |
|______________________| |_____________________|
| |
__________|___________ __________|__________
| FORD | | FUEL-INJECTED |
|______________________| |_____________________|
| |
__________|___________ __________|__________
| RANCHERO | | 8-CYLINDER |
|__________.___________| |__________.__________|
: :
__________:___________ :
| MY-FORD |................:
|______________________| :

Figure 11b: An Improper Relationship

______________________ _____________________
| AUTOMOBILES | | ENGINES |
|______________________| |_____________________|
| |
__________|___________ __________|__________
| DOMESTIC | | GASOLINE |
|______________________| |_____________________|
| |
__________|___________ __________|__________
| FORD | __| FUEL-INJECTED |
|______________________| | |_____________________|
| | |
__________|___________ | __________|__________
| RANCHERO |__| | 8-CYLINDER |
|______________________| |__________.__________|
: :
__________:___________ :
| MY-FORD | :
|______________________| :

Figure 11b: An Proper Relationship


Where Are Structures Useful?
The arrangement of frames in a structural relationship
offers several advantages. Most importantly, the visual
representation of the relationships between frames aids the
knowledge engineer in understanding the underlying structure of
the knowledge, thereby facilitating the development of the
application. Not only does it aid in determining where to place
knowledge in the knowledge base, but it can guide the knowledge
acquisition process. By viewing the structure and considering
the areas in which knowledge has and has not been acquired, the
knowledge engineer can determine where further acquisition
efforts might appropriately be directed.

The structured relationship of frames in a taxonomy is also
a means of storing knowledge. The fact that MY-FORD is a
RANCHERO provides additional knowledge about MY-FORD. Similarly,
additional knowledge is provided by the linkages indicating that
the car is manufactured by Ford, that it is a domestic vehicle,
that it is a general-goods carrying truck, and so forth. This
knowledge is available not only to the knowledge engineer but to
inference mechanisms as well.


Frame-Based Reasoning
Because the knowledge contained in a frame's slots is
available to inference mechanisms, a rule could reason about the
characteristics of a frame by referring to its slot values.
Assume that the application involves planning a route to be
driven and that a rickety bridge is to be avoided if the vehicle
is too heavy. A rule such as the following might be placed in
the knowledge base:

RULE 1: IF WEIGHT of MY-FORD >3000 pounds
THEN take detour around rickety bridge

If the value of the WEIGHT slot of the frame MY-FORD is greater
than 3000 pounds, then the plan should include a detour around
the rickety bridge.

Similarly, rules can be used to process the structural
knowledge contained in a taxonomy. The following rule, which
might be one of a set determining at what type of service station
the driver should stop to refuel his car, is illustrative.

RULE 2: IF ?VEHICLE is MEMBER-OF AUTOMOBILES
AND ?VEHICLE HAS-A ?ENGINE
AND ?ENGINE is MEMBER-OF DIESEL
THEN set REFUEL of ?VEHICLE to TRUCKSTOP

Rule 2 is a bit more complicated that it looks. On the
first line the inference engine attempts to "instantiate" the
variable ?VEHICLE with every frame, but only those instantiations
that are members of the class AUTOMOBILES are kept. At this
point several vehicles might qualify, so several instances of the
rule would be established (e.g., with vehicle-1, vehicle-2). The
second line instantiates the variable ?ENGINE with any frame that
?VEHICLE points to with a HAS-A relation. Thus, if vehicle-1 had
an engine and, say, a fuel-tank, the rule would be instantiated
twice - once with ?VEHICLE = vehicle-1 and ?ENGINE = ENGINES and
once with ?VEHICLE = vehicle-1 and ?ENGINE = FUEL-TANK.

The third line of the rule then throws out any instantiation
of the rule for which ?ENGINE is not a member of the class
DIESEL. Thus, only those rule instantiations for which the
specified conditions are satisfied will be left at the end of
line three. The fourth line then sets the slot REFUEL of the
associated vehicle to the value TRUCKSTOP. If there were five
automobiles with diesel engines, Rule 2 would be instantiated
five times and would fire five times, once with each eligible
automobile.


(End of Message 12 - continued next message)
---
==============================================================================
Date: 06-02-89 (23:53) Number: 11 Data Bit
To: ALL Refer#: NONE
From: GORDON LEE Read: YES
Subj: OBJECTS/FRAMES Conf: (89) OOPS
------------------------------------------------------------------------
(Message 13 of 31)

Similarly, rules can be developed that create structure in
the taxonomy, associating one class with another. Reasoning with
a knowledge taxonomy is not the exclusive province of rules,
although many frame-based systems use rule-based knowledge
extensively. However, procedural knowledge of the type found in
"blackboard" systems can process frame-based knowledge quite
efficiently.


Hierarchical Reasoning
The arrangement of knowledge from general to specific within
a knowledge taxonomy matches the type of reasoning that is used
in many types of applications. For example, consider the problem
of classifying a truck by its purpose or function. Usually the
truck is categorized more by eliminating all of the functions
that is cannot serve than by identifying its purpose. This
elimination can take place at various levels in the hierarchy,
depending on the type of knowledge known about the candidate
truck. Thus, at one level there might be a rule:

RULE: IF MANUFACTURER of ?TRUCK is CHRYSLER
THEN ?TRUCK is NOT MEMBER-OF FIRE-TRUCK

Assuming Chrysler does not manufacture any fire trucks, a single
rule at this level can eliminate a number of class and subclass
possibilities.

Another method of elimination can be illustrated at another
level. For example, assume that the capacity of the truck could
be identified as 1/2-TON. Then a rule as the following would
serve to put the identified function of any frame having a 1/2-
ton capacity in the slot POSSIBLE-FUNCTIONS:

RULE: IF CAPACITY of ?TRUCK is 1/2-TON
AND CAPACITY of ?POSSIBILITY is 1/2-TON
AND ?TRUCK NOT ?POSSIBILITY
THEN ADD FUNCTION of ?POSSIBILITY to
POSSIBLE-FUNCTIONS of ?TRUCK

Because of the tree structure of the knowledge taxonomy,
fewer frames need be considered at a higher level than at a lower
level. Thus, the reasoning can take place more efficiently at a
higher level if data availability and desired output permit. For
example, consider the problem of identifying the type of truck to
use to satisfy a particular requirement such as carrying a
liquid. In this case, the inference engine might be able to
select a tank truck as belonging to a class of trucks that would
satisfy the requirement without ever considering the type or
volume of liquid to be carried.

Planning can be carried out on multiple levels. For
example, at the first level the reasoning goal would be to
determine whether a type of truck equipped to transport a liquid
cargo existed. Having determined this, the inference mechanism
might then focus on a narrower problem, namely, checking the cost
and availability of each qualifying tank truck.

Should no tank truck satisfying the cost and availability
requirements exist, the inference mechanism might go back up a
level to consider another type of truck that might be able to
transport a liquid cargo (e.g., a general-cargo carrier with a
portable tank placed in the cargo area).

The hierarchical structuring of frame-based representations
is consistent with this type of reasoning. Even if the
application does not involve a sequence of objects or concepts at
progressively greater levels of detail, it may well involve
multilevel reasoning, using completely different sets of objects
at each level. Such reasoning can be greatly facilitated by
having a compatibly structured knowledge representation.

At the time of the feasibility study and during the early
design phases of the project, the knowledge engineer should
therefore be looking at the characteristics of the expertise that
is to be captured about the application domain. Questions such
as the following should be asked:

* Do the objects and concepts of the domain bear a
relationship to each other?
* Are there large numbers of related frames?
* Does the reasoning process involve multiple levels of
detail about particular types of objects?

Affirmative answers tend to indicate an appropriate situation for
the use of a frame-based representation.


INHERITANCE

The previous section indicated that frames at lower levels
of a taxonomy could obtain properties from frames at higher
levels in the taxonomy. Knowing that FORD is a subclass of
DOMESTIC automobiles and of AUTOMOBILES permits certain
additional information about Fords to be inferred, namely, that
they had the general properties of automobiles (e.g., four
wheels) as well as the additional properties of domestic cars
(e.g., English rather than metric dimensions). The mechanism for
passing such knowledge from frame to frame down through the
taxonomy from general to specific is known as "inheritance."


Passing Properties
Each subclass can be given certain properties of its parent
class. Thus, the general knowledge about automobiles would be
inherited (made available) in every frame at the DOMESTIC class
level. This knowledge would further be inherited by each frame
at the manufacturer class level (e.g., FORD), by the frames
representing all the models of a manufacturer (e.g., the LTD
class), as well as by each instance frame (e.g., MY-FORD).
Similarly, the additional knowledge provided by the DOMESTIC
class (i.e., the additional knowledge that is not contained in
the class AUTOMOBILES) would also be inherited downward to all
frames at the manufacturer, model, and instance levels of the
hierarchy.

The discussion thus far has focused on the inheritance of
slot values from a parent frame to a child or offspring frame in
an iterative manner throughout a structured hierarchy. However,
a frame can inherit many types of properties from its parents.
No individual development tool (shell) may provide the full range
of inheritance capabilites, but the discussion in the next
subsection is intended to show the types of inheritance that a
knowledge engineer might find useful for a particular
application.


Types of Inheritance
A slot in a frame might inherit a variety of properties,
ranging from specific values to structural characteristics, as
illustrated by the four types of inheritance described below.


Types of Inheritance: Slot
"Slot inheritance" takes place when the slot itself, but not
its value, is inherited from a parent frame. Thus, in Figure
12a, the WHEELS slot would be inherited by every descendant
subclass from the class AUTOMOBILES, but the slot value would not
be inherited. That is, the classes DOMESTIC and IMPORTED would
have a property called WHEELS, but there would be no implication
about how many wheels a domestic or imported automobile might
have. The (3 4) values of the WHEELS slot of AUTOMOBILES would
not be inherited.

Further, the WHEELS slot of DOMESTIC might be given a value
of 4, since no 3-wheeled automobiles are made domestically. As
shown in Figure 12b, this assignment would not affect the values
of the WHEELS slot of any other frame in the hierarchy.

___________________________
| AUTOMOBILES |
|___________________________|
| WHEELS | (3 4) |
|_____________|_____________|
______|______
_______________________|___ ___|_______________________
| DOMESTIC | | IMPORTED |
|___________________________| |___________________________|
| WHEELS | | | WHEELS | |
|_____________|_____________| |______________|____________|

Figure 12a: Slot Inheritance


___________________________
| AUTOMOBILES |
|___________________________|
| WHEELS | (3 4) |
|_____________|_____________|
______|______
_______________________|___ ___|_______________________
| DOMESTIC | | IMPORTED |
|___________________________| |___________________________|
| WHEELS | 4 | | WHEELS | |
|_____________|_____________| |______________|____________|

Figure 12b: Noninheritance of Slot Values


Types of Inheritance: Value
"Value inheritance" takes place when the value of a slot in
a frame is inherited from the corresponding slot of the parent.
Thus, if the AUTOMOBILE frame had a slot called CARRIES with a
value of (PASSENGERS, CARG0), the corresponding slot in the
DOMESTIC and IMPORTED frames would be given the value
(PASSENGERS, CARGO), indicating that those vehicles similarly can
carry both passengers and cargo. Similarly, this value would
automatically appear in the CARRIES slot of each descendant frame
in the hierarchy as shown in Figure 13a.

If the CARRIES slot of CORVETTE were then to be set to
passengers (since the sports car has no room for cargo), this
value would appear in the CARRIES slot for all descendant frames.
However, this change would not be inherited upward to any parent
frame, nor would it affect the slot values in any other unrelated
branch of the tree (e.g., the IMPORTED frame), as illustrated in
Figure 13b.
___________________________
| AUTOMOBILES |
|___________________________|
| CARRIES | (PASSENGERS, |
| | CARGO) |
|_________|_________________|
______|______
_______________________|___ ___|_______________________
| DOMESTIC | | IMPORTED |
|___________________________| |___________________________|
| CARRIES | (PASSENGERS, | | CARRIES | (PASSENGERS, |
| | CARGO | | | CARGO |
|_________|_________________| |_________|_________________|
|__________________________________
____________|______________ _____________|_____________
| CHEVROLET | | FORD |
|___________________________| |___________________________|
| CARRIES | (PASSENGERS, | | CARRIES | (PASSENGERS, |
| | CARGO | | | CARGO |
|_________|_________________| |_________|_________________|
|
____________|______________
| CORVETTE |
|___________________________|
| CARRIES | (PASSENGERS, |
| | CARGO |
|_________|__.______________|
:
____________:______________
| MY-CORVETTE |
|___________________________|
| CARRIES | (PASSENGERS, |
| | CARGO |
|_________|_________________|

Figure 13A: Value Inheritance

|
____________|______________
| CORVETTE |
|___________________________|
| CARRIES | (PASSENGERS) |
| | |
|_________|__.______________|
:
____________:______________
| MY-CORVETTE |
|___________________________|
| CARRIES | (PASSENGERS) |
| | |
|_________|_________________|

Figure 13b: Downward Only Inheritance of Values


Types of Inheritance: Restriction
"Restriction inheritance" takes place when it is the
restrictions on values, rather than the values themselves, that
are inherited. Thus, a constraint on the WHEELS slot of
AUTOMOBILES to permit only 3- and 4-wheeled vehicles would be
binding on all subclasses and instances of AUTOMOBILES, but no
specific value would be implied (see Figure 14).

___________________________
| AUTOMOBILES |
|___________________________|
| WHEELS |_________________|
| | RESTRICTION: |
| | (VALUE-ONE-OF: |
| | 3 4) |
|_________|_________________|
______|______
_______________________|___ ___|_______________________
| DOMESTIC | | IMPORTED |
|___________________________| |___________________________|
| WHEELS |_________________| | WHEELS |_________________|
| | RESTRICTION: | | | RESTRICTION: |
| | (VALUE-ONE-OF: | | | (VALUE-ONE-OF: |
| | 3 4) | | | 3 4) |
|_________|_________________| |_________|_________________|

Figure 14: Restriction Inheritance


___________________________
| FORD |
|___________________________|
| WHEELS | 4 |
|_____________|_____________|
| FLEET-MPG | 26 |
|_____________|_____________|
______|
_______________________|___
| RANCHERO |
|___________________________|
| WHEELS | 4 |
|_________|__.______________|
:
____________:______________
| MY-FORD |
|___________________________|
| WHEELS | 4 |
|_________|_________________|

Figure 15: Noninheritance


Types of Inheritance: Null
In some cases inheritance is not desirable, and all of its
forms should be inhibited. Thus, for example, the FORD frame
shown in Figure 15 might have a slot named FLEET-MPG, containing
the average miles-per-gallon rating of all the cars produced by
the manufacture. This rating is a property of the class FORD; it
is not a description of any class or instance properties. Thus,
neither the slot FLEET-MPG nor its value should be inherited
downward from the manufacturer frames.


Multiple Inheritance
Figures 10b and 10c showed how a given frame (whether
instance or class) might derive from more than one parent. In
the latter figure, the RANCHERO class was shown to be a
particularization of the class FORD as well as of the class
GENERAL-GOODS. Conceptually, it is easy to see that the RANCHERO
automobile has properties of Ford automobiles and also of
general-goods carrying trucks. As long as the parents share no
common slots, inheritance from multiple parents is a simple
matter. The difficulty arises when the parents have common slots
(potentially with different values). How should inheritance be
handled in such a circumstance? Two common types of inheritance
might be used to deal with this situation: union and
intersection.

___________________________ ___________________________
| FORD | | GENERAL-GOODS |
|___________________________| |___________________________|
| CARRIES | PASSENGERS | | CARRIES | CARGO |
|___________|_______________| |___________|_______________|
| COLOURS | (RED, WHITE, | | COLOURS | (RED, BLUE, |
| | BLUE, BROWN, | | | BLACK, BROWN) |
| | GREEN) | | | |
|___________|_______________| |___________|_______________|
| CYLINDERS | 6 | | CYLINDERS | 8 |
|___________|_______________| |___________|_______________|
|________________ ________________|
_____________|_____________
| RANCHERO |
|___________________________|
| CARRIES | (PASSENGERS, |
| | CARGO) |
|___________|_______________|
| COLOURS | (RED, BLUE, |
| | BROWN) |
|___________|_______________|
| CYLINDERS | 6 |
|___________|_______________|


Figure 16: Union and Intersection Inheritance


Multiple Inheritance: Union
"Union inheritance" takes place when a frame's slot receives
the union of the values in each of the parent's slots bearing the
same name. Thus, in Figure 16, the CARRIES slot of RANCHERO
receives the value PASSENGERS from FORD and the value CARGO from
GENERAL-GOODS.


Multiple Inheritance: Intersection
"Intersection inheritance" takes place when a frames's slot
receives the intersection of the values in each of the parent's
slots bearing the same name. The COLOURS slot reflects the
colours that the vehicle can be painted. If Fords can be painted
red, white, blue, brown, and green and if goods-carrying trucks
can be painted red, blue, black, and brown, then intersection
inheritance would provide red, blue, and brown as the possible
colours for Ranchero. This intersection inheritance is
illustrated in Figure 16.

A variety of other inheritance methods is also possible.
For example a slot value might be inherited from only the first
(last) of the listed parents. Thus, Fords might have 6 cylinders
and trucks might have 8. Rather then ending up with a
combination (e.g., 7 cylinders), the Ranchero will end up with
either 6 or 8 cylinders. (The CYLINDERS slot for RANCHERO in
Figure 16 has a value of 6, reflecting inheritance from the FORD
frame.)

When multiple values are involved, further inheritance
possibilities arise. For example, a developer might like values
to be inherited in the same order (reverse order) as they appear
in the parent's slots or to be combined in the same (reverse)
order in which the parents are listed. Depending on the
facilities of the particular knowledge-based application
development tool (shell) being used, these and other inheritance
mechanisms may or may not be available. The knowledge engineer
should investigate the inheritance needs of the form of knowledge
representation being selected and compare those needs with the
capabilities of the available tools (shells) when selecting a
tool (shell).


RELATIONSHIP KNOWLEDGE

The preceding subsections have focused on the storage of
values in slots and the association of various types of
restrictions with those slots. Knowledge about relationships can
also be stored in slots. Consider, for example, a knowledge base
with the classes AUTOMOBILES, ENGINES, and SPARK-PLUGS. A
section of the AUTOMOBILE taxonomy that was displayed in Figure 9
consists of the classes DOMESTIC, FORD, and RANCHERO, and the
instance MY-FORD. A section of the ENGINES taxonomy that was
displayed in Figure 11a has classes GASOLINE, FUEL-INJECTED, and
8-CYLINDER. An additional taxonomy on SPARK-PLUGS is shown with
a single subclass, CERAMIC. These three structures are
illustrated in Figure 17a.

_________________ _________________ _________________
| AUTOMOBILES | | ENGINES | | SPARK-PLUGS |
|_________________| |_________________| |_________________|
| | |
________|________ ________|________ ________|________
| DOMESTIC | _| GASOLINE |___| CERAMIC |
|_________________| | |_________________| |_________________|
| | |
________|________ | ________|________
| FORD | | | FUEL-INJECTED |
|_________________| | |_________________|
| | |
________|________ | ________|________
| RANCHERO |_| | 8-CYLINDER |
|________.________| |_________________|
:
________:________
| MY-FORD |
|_________________|

Figure 17a: Relations Between Taxonomies

Some specific relations have been defined between these
classes, relating RANCHERO to GASOLINE and relating GASOLINE and
CERAMIC. The basic relation is the HAS-A relation, so that
RANCHERO HAS-A GASOLINE engine and GASOLINE engine HAS-A CERAMIC
set of spark-plugs. HAS-A is what is termed a complementary
relation; its complement is CONTAINED-IN. If RANCHERO HAS-A
GASOLINE, then GASOLINE CONTAINED-IN RANCHERO. When either
relation of a complementary pair is defined, the other can be
defined automatically. One way to implement such relations is to
store them in appropriate slots in the relevant frames. The four
relations shown in Figure 17a are:

RELATION: RANCHERO HAS-A GASOLINE
GASOLINE CONTAINED-IN RANCHERO
RELATION: GASOLINE HAS-A CERAMIC
CERAMIC CONTAINED-IN GASOLINE


Instances
The frame representation for part of a knowledge base will
often remain static during analysis. Thus, the knowledge
engineer would create relationships such as those shown in Figure
17a during development of the application system, and these
frames and relationships would not be changed. However, because
other parts of the knowledge base will change dynamically during
an analysis, the inference engine must be able to create (or
destroy) frames and relationships programmatically during
execution of the application.

Consider the case of Susan buying a new Ranchero. Her
acquisition will necessitate creating a new instance of RANCHERO,
SUSAN'S FORD, as well as other relationships. Because RANCHERO
HAS-A GASOLINE, an instance of GASOLINE will need to be created
and SUSAN'S-FORD given a HAS-A relation to it. Similarly,
because GASOLINE is linked to CERAMIC with a HAS-A relation, an
instance of CERAMIC will need to be created and a HAS-A relation
established from the GASOLINE instance to the CERAMIC instance.
These relationships are depicted in Figure 17b, which is
identical to Figure 17a except for the addition of all the frames
and relations implied by the addition of the instance, SUSAN'S
FORD.

_________________ _________________ _________________
| AUTOMOBILES | | ENGINES | | SPARK-PLUGS |
|_________________| |_________________| |_________________|
| | |
________|________ ________|________ ________|________
| DOMESTIC | _| GASOLINE |___| CERAMIC |
|_________________| | |_______________._| |________.________|
| | | :... :
________|________ | ________|________ : :
| FORD | | | FUEL-INJECTED |: :
|_________________| | |_________________|: :
| | | : :
________|________ | ________|________ : :
| RANCHERO |_| | 8-CYLINDER |: :
|________.________| |_________________|: :
:.......... : :
________:________ : : :
| MY-FORD |: : :
|_________________|: : :
..........: ..........: :
________:________ ________:________ ________:________
| SUSAN'S FORD |___|SUSAN'S GASOLINE |___| SUSAN'S CERAMIC |
|_________________| |_________________| |_________________|

Figure 17b: Relations Between Taxonomies With a New Instance

Rather than having to create each frame individually and to
establish each relationship within the family, some knowledge-
based development tools (shells) will automatically create all
referenced frames (that do not already exist) and all of the
relationships between those frames whenever a new frame is
created. Thus, the creation of SUSAN'S-FORD would trigger the
following:

* Creation of an instance, SUSAN'S-GASOLINE, of GASOLINE
* Linking the instance to the parent (SUSAN'S-GASOLINE to
GASOLINE)
* Establishing a HAS-A relation between SUSAN'S-FORD and
SUSAN'S-GASOLINE
* Establishing a CONTAINED-IN relation between SUSAN'S-
GASOLINE and SUSAN'S-FORD
* Creation of an instance, SUSAN'S-CERAMIC, of CERAMIC
* Linking the instance to the parent (SUSAN'S-CERAMIC to
CERAMIC)
* Establishing a HAS-A relation between SUSAN'S-GASOLINE
and SUSAN'S-CERAMIC
* Establishing a CONTAINED-IN relation between SUSAN'S-
CERAMIC and SUSAN'S-GASOLINE.

This ability to create a full subtree simply by creating an
instance of a class is a very powerful capability.


Facets Revisited
In view of the class relationships that can exist between
frames, additional facets can be created to constrain slot
contents in terms of these relationships. Thus, the possible
values that might be placed in a slot might be restricted to the
name of a frame that is an instance of a particular class or the
name of a class that is derived from another class. In terms of
the automobile example, the following restriction would restrict
the possible values for a slot to instances of DOMESTIC:

RESTRICTION: (INSTANCE-OF: DOMESTIC)

Thus, any instance of one of the domestic manufactures
(e.g., CHRYSLER) or of any of the domestic manufacturer's car
models (e.g., LTD) would be permitted. However, one of the
manufacturers (e.g., the class CHRYSLER) or one of the car model
classes (e.g., LTD) would not be permitted. Likewise, no
instances deriving from the IMPORTED side of the taxonomy would
be permitted.

Similarly, restrictions such as DERIVES-FROM, NOT-MEMBER-OF,
INHERITANCE-TYPE, INSTANCE, and EXCLUSIVE-MEMBERSHIP can be used
to control the use of and reasoning with relations. Again, this
area offers considerable additional power to a representational
form, but different knowledge-based application development tools
(shells) provide these types of capabilities in different ways,
if at all.


Where Is Inheritance Useful?
Inheritance is particularly useful when the reasoning
process involves creating new instances, modifying relationships,
or adding new relationships. A change made to a slot in a
subclass frame as a result of the reasoning process will be
inherited down to all subordinate subclasses and instances. The
knowledge engineer need not worry about, and the knowledge base
need not make provision for, finding every instance and making
the corresponding change.

Thus, if the application domain seems well-suited for frame-
based representation, the knowledge engineer should examine the
degree to which that structure may change or be filled out during
the reasoning process. The more dynamic the knowledge base, the
more important an inheritance mechanism may become. Even for
static knowledge bases, inheritance can be valuable during the
development process. (Although the ultimate knowledge base may
be static, the knowledge base during the engineering process is
likely to be anything but static.)


Order Out of Chaos
For example, one system that was examined involved the
checking of equipment configurations for completeness and
consistency. This type of problem is a common one for a fairly
broad range of manufacturing industries. This system was
entirely rule-based and involved an extensive set of rules, each
checking some aspect of the configuration. Understanding some of
the relationships between rules was difficult because or the
number of rules to be examined.

A small version of this system was assembled using a frame-
based representation (as well as a rule-based representation),
which permitted the rules to be categorized and their numbers
reduced. By taking advantage of the ability to reason about
structures and relationships of equipment components, it was
possible to substitute a smaller number of rules operating at a
more abstract level for a larger number of the original rules.
Not only did this change provide an efficiency in representation,
but it made the system less complex logically. This latter
characteristic facilitated the developer's modification of the
knowledge base.

Thus, the combination of a frame-based knowledge base
structure with a rule-based reasoning mechanism can provide an
application system structure that is far more powerful and
efficient than the system that might be built using either
representational form alone. In this case, the whole is
definitely greater than the sum of the parts.


OTHER TYPES OF SLOT CONTENTS

The preceding subsections have discussed two types of
knowledge that can be stored in a slot - basic facts or values,
and frame relationships. Additional types of knowledge can be
placed in a slot, however. For example, rules or even entire
rule-sets might be placed in a slot. Similarly, procedural or
behavioral knowledge can be accommodated by placing a function in
a slot. As a practical matter, however, rules are likely to be
gathered in a rule taxonomy, with just a reference to the
appropriate rule class contained in the slot. In this manner the
categorization power of a frame-based representation can be
brought to bear on rule-based and procedural-based knowledge.
The association of functions with a frame also provides the
mechanism for implementing object-oriented programming, a concept
that is discussed later in this brief.


Rule-Sets
In some knowledge-based development systems (shells) an
entire rule-set may be stored in a slot, permitting rule-based
knowledge as well as facts and relationship knowledge to be
structured in the knowledge taxonomy. At the other extreme, each
rule could be placed in a single frame, with a parent frame
representing the entire rule-set. The inclusion of rules within
a frame permits an application's rule-based knowledge to be
structured in the same manner as the factual knowledge. Rules
can thus be organized in a taxonomy and referenced from slots of
other frames. Such rule references can be inherited downward in
knowledge hierarchies from classes through subclasses to specific
instances.

___________________________
| DIAGNOSTIC-RULES |
|___________________________|
_________________|_________________
____________|______________ | ______________|____________
| CARBURETOR- | | | ELECTRICAL-SYSTEM- |
| DIAGNOSTICS | | | DIAGNOSTICS |
|___________________________| | |___________________________|
| RULE-C-1 | | | | RULE-E-1 | |
|___________|_______________| | |___________|_______________|
| RULE-C-2 | | | | RULE-E-2 | |
|___________|_______________| | |___________|_______________|
| | | | | | |
|___________|_______________| | |___________|_______________|
| RULE-C-n | | | | RULE-E-n | |
|___________|_______________| | |___________|_______________|
|
_____________|_____________
| BRAKE-SYSTEM- |
| DIAGNOSTICS |
|___________________________|
| RULE-B-1 | |
|___________|_______________|
| RULE-B-2 | |
|___________|_______________|
| | |
|___________|_______________|
| RULE-B-n | |
|___________|_______________|

Figure 18: Rule-Based Knowledge Taxonomy

To illustrate, consider a frame-based taxonomy of rules
relating to automobiles failure diagnostics. The knowledge
taxonomy has a root class called DIAGNOSTIC-RULES. This class
contains no rules but represents the class of all diagnostic
rules. It serves as the parent to three subclasses that
respectively contain the individual rule-sets for each type of
diagnostic: CARBURETOR-DIAGNOSTICS, ELECTRICAL-SYSTEM-
DIAGNOSTICS, and BRAKE-SYSTEM-DIAGNOSTICS. As shown in Figure
18, the rules are distributed one rule per slot within those
frames. Alternatively, each of these three frames could serve as
classes representing the rule-set, with the rules contained
individually in instances of those classes. Thus, not only does
the frame representation provide a mechanism for decomposing the
rule-sets and for referencing them, but it also provides a
mechanism for structuring the relationship between the rule-sets.

This structure permits not only a better understanding of
the rule-based knowledge, but also a more efficient application
of the rules, since only the rules in the relevant rule-set need
be considered at any one time. Further, the frame-based
structuring of rules permits relevant rules to be inherited from
classes through subclasses to specific instances of rules.

Similarly, references to rules or rule classes can be
inherited down through nonrule knowledge taxonomies. Consider
the CARBURETOR-DIAGNOSTICS rule-set in Figure 18 to determine
whether a carburetor is working properly. A reference to these
rules might be contained in a slot within the AUTOMOBILES frame,
representing the class of automobiles. These rules would then be
inherited by all subclasses of AUTOMOBILES (e.g., CHEVROLET and
CHRYSLER) as well as by specific instances of classes (e.g., MY-
FORD). Thus, the carburetor diagnostic rule-set would be
available to every class and instance for use as needed.

The inheritance of rule-sets (or reference to rule-set)
offers a number of advantages. Assume that the carburetor
diagnostic for Chevrolet and Chrysler are basically similar but
differ slightly with respect to certain details. Thus, a basic
set of diagnostic rules could be referenced at the level of
AUTOMOBILES, and this set would automatically be made available
to every subclass of AUTOMOBILES, as well as to any specific
instance of AUTOMOBILES. The inherited rule-set could be
slightly modified at a subclass level (e.g., CHEVROLET) by adding
and deleting rules to reflect considerations unique to a
particular brand of automobile.

Then each specific instance of an automobile (e.g., MY-FORD)
would inherit references to an appropriate set of carburetor
diagnostic rules. Given any instance of AUTOMOBILES, the
inference mechanism could reference that frame's carburetor
diagnostic rules without having to determine which rules might be
applicable to that particular vehicle. Any general changes in
diagnostic procedures could be reflected in the basic rules, and
these changes would automatically be available to derivative
classes and instances in the knowledge taxonomy.

Similarly, a change to the rules pertaining to Ford
automobiles could be made to the FORD frame. These changes would
be reflected not only in FORD, but also in all frames descendent
from the class FORD (e.g., LTD, MY-FORD). However, these changes
would not be reflected in the frames for any other type of car
(e.g., CHRYSLER) or in frames representing more general
subclasses of automobiles in the hierarchy (e.g., DOMESTIC). The
benefits that can be gained from this representational form are
enormous.

An alternative way of organizing the carburetor rules is
reflected in Figure 19. The individual rules can be represented
as instances, as shown in the right-hand side of the diagram.
These are gathered together into classes (e.g., CHEVY-GENERAL,
CHEVY-SPECIFIC). Because many of the general rules are common to
several types of vehicles, they are related to more than one
class.

_________________
GC= BOTH, GENERAL-RULES & GC| RULE GR-1 |
CHEVY-GENERAL || |_________________|
G= ONLY, GENERAL-RULES ||
|| _________________
||G| RULE GR-2 |
|| |_________________|
||
_________________ || _________________
| GENERAL-RULES |_|GC| RULE GR-3 |
|_________________| || |_________________|
||
|| _________________
|GC| RULE GR-4 |
|| |_________________|
||
_________________ || _________________
_| CHEVY-GENERAL |_||G| RULE GR-5 |
| |_________________| |_________________|
|
_________________ | _________________
| CHEVY-RULES |_| __| RULE C-1 |
|_________________| | | |_________________|
| |
| _________________ | _________________
|_| CHEVY-SPECIFIC |_|__| RULE C-2 |
|_________________| | |_________________|
|
| _________________
|__| RULE C-3 |
|_________________|

Figure 19: Alternative Rule Structure

The DIAGNOSTIC slot of the class AUTOMOBILES would then
contain a reference to the GENERAL-RULES class, which in turn
would provide access to the individual diagnostic rules.
However, the reference to these rules would not be inherited;
only the slot would pass down through the hierarchy. At the
level of the CHEVROLET class, a reference would be placed in the
DIAGNOSTICS slot to the CHEVY-RULES. These in turn would provide
access to the CHEVY-GENERAL rules (which are a subset of the
general rules) and the CHEVY-SPECIFIC rules, which are unique to
chevrolets. CHEVY-GENERAL and CHEVY-SPECIFIC then provide access
to the specific rules that are to be used for diagnosing a
problem in a Chevrolet.


Procedures (Methods)
Slots may also contain functions, permitting procedural
knowledge to be incorporated within the frame representation.
(Such functions, when used to support object-oriented
programming, are often referred to as "methods.") Analogous to
the inclusion of rules within a slot, the inclusion of a function
or method provides a very powerful way to structure the
distribution of procedural or behavioral knowledge within an
application.

The automobile example of the previous subsection can easily
be adapted to this case. Just substitute the term "function" for
the term "rule-set" to create an appropriate example. All of the
arguments made above with respect to rule-sets and inheritance
apply equally well for functions and procedural knowledge
representations.

In the case of functions, however, some specialized types of
inheritance are provided by various knowledge-based system
development tools (shells). These inheritance mechanisms permit
some procedural code at a subordinate level to be combined with a
function inherited from a parent frame rather than being replaced
by it. Thus, instead of making local changes to the inherited
diagnostic function at the manufacture class level (e.g.,
CHEVROLET) to reflect differences in procedures between different
automobiles, those changes can be placed directly in the slots of
the descendant frames. Then, instead of replacing the inherited
function (as would customarily be the case), the modifications
would be applied to that function. This technique permits local
changes to be made to a function automatically at each level in
the knowledge taxonomy. The knowledge engineer need not worry
about whether all changes were made or whether they were made
correctly in every frame.


Method Inheritance
Function or procedural knowledge can be inherited from
parent to descendant frame in the usual ways. However, some
special types of inheritance are desirable for procedural
knowledge. The following two forms illustrate some of the
possibilities.


Method Inheritance: Before
"Before inheritance" is so named because the function stored
in the child's slot is applied "before" the inherited function
from the parent has been applied. The top portion of Figure 20
shows a function in each of two frames (DOMESTIC and CHRYSLER)
when those two frames are unrelated. One references a general
diagnostic function. The lower portion of the figure shows the
resultant function in the CHRYSLER frame, named "modified
diagnostic function" for clarity, after inheritance has taken
place (after CHRYSLER has been made a child of DOMESTIC).

Prior to Inheritance
______________________________________________________
| DOMESTIC |
|______________________________________________________|
| CARBURETOR-DIAGNOSTIC | (General-Diagnostic-Function |
| | (Parameters-1)) |
|_______________________|______________________________|

_______________________________________________________
| CHRYSLER |
|_______________________________________________________|
| CARBURETOR-DIAGNOSTIC | (Special-Chrysler-Diagnostic- |
| | Function (Parameters-2)) |
|_______________________|_______________________________|


=================================================================

Post-Inheritance Combination
______________________________________________________
| DOMESTIC |
|______________________________________________________|
| CARBURETOR-DIAGNOSTIC | (General-Diagnostic-Function |
| | (Parameters-1)) |
|_______________________|______________________________|
|
__________________________|_____________________________
| CHRYSLER |
|_______________________________________________________|
| | (Modified-Diagnostic-Function-|
| CARBURETOR-DIAGNOSTIC | for-Chrysler (Parameters-2) |
| | (Parameters-1)) |
|_______________________|_______________________________|

Figure 20: Before-Type Inheritance

Figures 21a and 21b show the respective skeletons of the
"code" for the two original functions, while Figure 21c shows the
skeleton of the combined function. Note that the functions are
combined; they are not just called one after the other. Thus,
the before-function call can actually exit, in which case the
inherited function would not be performed at all.

General-Diagnostic-Function (Parameters-1);
General Function Code;
Return;
End;
Figure 21a: Skeleton of the General
Diagnostic Function


Special-Chrysler-Diagnostic-Function (Parameters-2);
Special Function Code;
Return;
End;
Figure 21b: Skeleton of the Special Chrysler
Diagnostic Function


Modified-Diagnostic-Function (Parameters-2,
Parameters-1);
Special Function Code;
Call General-Diagnostic-Function (Parameters-1);
Return;
End;
Figure 21c: Skeleton of the Modified Diagnostic
Function with Before Inheritance

Before inheritance can be used for several purposes. The
child function can serve as a monitor, reporting or recording
data whenever the function is called. It can serve as a filter,
checking whether the conditions are such that the general routine
should be skipped. It can also serve as a preprocessor,
modifying or adjusting values before supplying them to the
general routine. Two different parameters sets were used for the
two functions in the example for the sake of clarity; however, in
practice a common set is often used.


Method Inheritance: After
"After inheritance" is so named because the function stored
in the child's slot is applied "after" the inherited function
from the parent has been applied. The situation is the same as
depicted in Figure 20 and Figures 21a and 21b, but the functions
are combined differently, as shown in Figure 21d.

Modified-Diagnostic-Function (Parameters-2,
Parameters-1);
Call General-Diagnostic-Function (Parameters-1);
Special Function Code;
Return;
End;
Figure 21d: Skeleton of the Modified Diagnostic
Function with After Inheritance

After inheritance can also be used for several purposes.
Again, the child function can serve as a monitor, reporting or
recording the effects of the application of the parent routine.
It can also serve as a post-processor, modifying or adjusting
values before they are returned from the function. Again, two
different parameter sets were shown, but the child function
usually uses the parent function's parameters.


Method Inheritance: Other
Inheritance can be defined and implemented in many other
ways. For example, the parent function could be inherited into
the "middle" of the child code. Rather than combining the
functions to form a new function associated with the child, the
knowledge engineer could achieve the equivalent processing by
sending the child function up to be processed with the parent
function.


OBJECT-ORIENTED PROGRAMMING

The development of programs on the basis of associating all
data and programmed behaviour (e.g., functions) with each object
in the application system is known as "object-oriented
programming." Messages are sent to objects requesting that
particular functions or services be performed. The object
responds, relying on methods (functions) to provide the requested
action. Necessary data are obtained from the requesting message,
from data stored with the object, and from other objects as

necessary.

Such message passing may appear similar to function or
subroutine calls, and well it should. However, it differs in
that the definition of the function is taken from the object
"receiving" the message, not the object sending the message.

Each object can be represented as a frame, with the data
about that object stored in slots in its frame. The various
behaviours of the object are provided by methods that are also
stored in the frame's slots. Messages are then exchanged between
objects to provide a collection of behaviours that represent the
purpose of the entire system.

Many people have concluded that object-oriented programming
is nothing more than the development of programs using subroutine
calls to a core set of subroutines. While technically true, that
opinion misses the point that object-oriented programming
represents a methodology for thinking about a problem, an
approach to structuring a computer program. The modularization
and the association of data with each object provides a number of
benefits including error reduction and comparatively easy
maintenance.


Example
Consider a knowledge-based application dealing with failure
diagnostics for automobiles. Objects would be constructed
representing various kinds of automobiles. A frame-based
representation, such as shown in Figure 9, would be a typical
means for representing such a system. As was discussed
previously in the subsection on procedures and function
inheritance, various diagnostic routines could be provided at
various levels of the knowledge taxonomy, with local
modifications made to reflect differences between manufactures'
products, differences between models, and so forth.

The diagnostic routines would be called into play by a set
of rules that analyzed symptoms exhibited by a car. A message to
a particular automobile (object) would trigger the performance of
the requested diagnostic function for that car. The inference
mechanism would not need to perform tests to isolate which
procedures should be applied given the identity of the particular
car being examined. The appropriate diagnostic routines would
already be associated with that car. The inference mechanism
would only need to execute the function (perform the method).

Thus, in developing the diagnostic logic of the system, the
knowledge engineer need not be concerned about providing the
necessary tailoring each time a particular diagnostic procedure
is to be used to produce additional information about the failure
in the automobile. All such specialization will already be
reflected in the methods for the diagnostics associated with each
given automobile.

Obviously, this approach has several benefits in terms of
development efficiency, ease of modification, simpler application
logic, clarity of documentation, and reduction in number of
errors. Further, development of a complete set of methods for
"every" object is not as formidable a task as it might at first
appear. Because of the hierarchical structure of the objects and
the inheritance capabilities, much of the method development of
individual objects (frames) is provided implicitly through
inheritance rather than explicitly through separate coding.

The key observation to be made about object-oriented
programming is how the benefits are derived from the integration
of the approach with the various facilities of a frame-based
representation.


Method Inheritance: Other
Inheritance can be defined and implemented in many other
ways. For example, the parent function could be inherited into
the "middle" of the child code. Rather than combining the
functions to form a new function associated with the child, the
knowledge engineer could achieve the equivalent processing by
sending the child function up to be processed with the parent
function.


OBJECT-ORIENTED PROGRAMMING

The development of programs on the basis of associating all
data and programmed behaviour (e.g., functions) with each object
in the application system is known as "object-oriented
programming." Messages are sent to objects requesting that
particular functions or services be performed. The object
responds, relying on methods (functions) to provide the requested
action. Necessary data are obtained from the requesting message,
from data stored with the object, and from other objects as
necessary.

Such message passing may appear similar to function or
subroutine calls, and well it should. However, it differs in
that the definition of the function is taken from the object
"receiving" the message, not the object sending the message.

Each object can be represented as a frame, with the data
about that object stored in slots in its frame. The various
behaviours of the object are provided by methods that are also
stored in the frame's slots. Messages are then exchanged between
objects to provide a collection of behaviours that represent the
purpose of the entire system.

Many people have concluded that object-oriented programming
is nothing more than the development of programs using subroutine
calls to a core set of subroutines. While technically true, that
opinion misses the point that object-oriented programming
represents a methodology for thinking about a problem, an
approach to structuring a computer program. The modularization
and the association of data with each object provides a number of
benefits including error reduction and comparatively easy
maintenance.


Example
Consider a knowledge-based application dealing with failure
diagnostics for automobiles. Objects would be constructed
representing various kinds of automobiles. A frame-based
representation, such as shown in Figure 9, would be a typical
means for representing such a system. As was discussed
previously in the subsection on procedures and function
inheritance, various diagnostic routines could be provided at
various levels of the knowledge taxonomy, with local
modifications made to reflect differences between manufactures'
products, differences between models, and so forth.

The diagnostic routines would be called into play by a set
of rules that analyzed symptoms exhibited by a car. A message to
a particular automobile (object) would trigger the performance of
the requested diagnostic function for that car. The inference
mechanism would not need to perform tests to isolate which
procedures should be applied given the identity of the particular
car being examined. The appropriate diagnostic routines would
already be associated with that car. The inference mechanism
would only need to execute the function (perform the method).

Thus, in developing the diagnostic logic of the system, the
knowledge engineer need not be concerned about providing the
necessary tailoring each time a particular diagnostic procedure
is to be used to produce additional information about the failure
in the automobile. All such specialization will already be
reflected in the methods for the diagnostics associated with each
given automobile.

Obviously, this approach has several benefits in terms of
development efficiency, ease of modification, simpler application
logic, clarity of documentation, and reduction in number of
errors. Further, development of a complete set of methods for
"every" object is not as formidable a task as it might at first
appear. Because of the hierarchical structure of the objects and
the inheritance capabilities, much of the method development of
individual objects (frames) is provided implicitly through
inheritance rather than explicitly through separate coding.

The key observation to be made about object-oriented
programming is how the benefits are derived from the integration
of the approach with the various facilities of a frame-based
representation.


Example Continued
Assume that the critical facts associated with a particular
automobile undergoing a diagnostic test are to be printed out.
This request may arise from the execution of a rule-set, or from
a knowledge engineer or a user browsing the knowledge base and
seeking certain information.

In this case, however, an extensive set of programs is not
needed. A single message to the frame containing the automobile
of interest, requesting that its critical data be displayed on
the screen, will suffice. The "critical data" method for that
particular automobile will assemble the necessary data for that
car directly; an extensive set of tests to determine which types
of data are considered critical for particular brands and models
of automobiles is not needed. Next, this method sends a message
to an "output" object that has routines for displaying a set of
data on the screen. (If the data were to be sent to a printer or
disk file, the process would be similar except that the message
would be sent to a different method. No local program code is
involved in determining the way to package and transfer that data
to any particular device.)

The benefits from such modularization are striking. A
change in the diagnostic procedure for a particular model of
automobile can be made directly to the appropriate method
associated with that automobile. All changes would be localized
to a single method. The knowledge engineer would not need to
search for all sections of the entire program that referenced or
were in some way involved with that particular diagnostic. Even
scattered revisions can often be made in a single place, since
the revision would be inherited downward in the representation
hierarchy to all descendants.

If a developer modifies a printer driver (e.g., as a result
of a change to the printer actually attached to the computer
system), only the one method that is responsible for displaying
data on that printer need be changed. No other code fragments
would be involved with the printer, eliminating the need for the
knowledge engineer to search through the application looking for
code fragments and then to examine that code to determine whether
modifications would be required to reflect the change made to the
equipment.


Where Is Object-Oriented Programming Useful?
The preceding paragraphs have focused on the maintenance
advantages of object-oriented programming; however, the
representational benefits are available in a wide variety of
applications. Any time the application involves the behavioral
representation of a set of objects, object-oriented programming
is a candidate development style or approach. Similarly, the
object-oriented approach should be considered any time the
application logic involves such behavioral performance or
triggering of a behaviour from several locations. Keep in mind
that the benefit of this means of structuring and applying
knowledge derives from the structural characteristics of the
application, not the particular domain knowledge to be associated
with the system.

As a practical matter, object-oriented programming is
inextricably intertwined with a frame-based representation and
the organization of the knowledge base. Many of the benefits of
the object-oriented approach will be lost if a frame-based
representation is not used. This provides two hints for use
during the design process:

* Any time a frame-based representation appears to be
appropriate, an object-oriented programming approach
should be considered.
* Any time an object-oriented approach appears to be
appropriate, based on the expected behavioral
characteristics of the application, employing a frame-
based representation should be considered (though
perhaps in conjunction with other representational
forms as well).

Interestingly, despite the close relationship between frame-
based organizations, rule-based systems, and object-oriented
programming, a rule-based system operating with a frame-based
representation generally represents a violation of object-
oriented programming principles. Technically, in a pure object-
oriented approach, data from a frame (e.g., slot definitions and
values) must be kept within the object itself and are not
accessible from outside. Only the functions operating within the
object have free access to the data. This restriction enforces
the modularity and independence required to achieve the benefits
of object-oriented programming. However, this requirement, if
enforced, would prevent a rule-based knowledge representation
from accessing the information contained in a companion frame-
based representation!


ADVANTAGES OF FRAME-BASED REASONING

The chief advantage of frame-based reasoning is that it
provides a means for structuring a variety of types of data in
the knowledge base and a framework whereby not only the data but
also the structure of those data can be reasoned about. Thus, a
frame-based representation:

* Greatly aids in structuring the design for a
knowledge-based application
* Enables rules and procedures in an application to be
more generic, thereby reducing rule-set or procedure
size and making the knowledge base easier to understand
and test
* Compartmentalizes the data in the knowledge base,
oftentimes reducing the complexity so that an
application can be built and tested in less time
* Permits greater understanding of knowledge structure
and relationships through graphical displays of the
structure
* Enhances the maintainability of the knowledge base
* Provides many of the essential characteristics of an
object once that type of object has been identified,
ousting the need to derive these aspects individually.


Engineering a Knowledge-Bases Application Using
a Frame-Based Representation
An early step in studying frame-based reasoning is to
examine various information taxonomies. Such taxonomies are
interesting to manipulate. Soon the student knowledge engineer
has an opportunity to relate a taxonomy to a rule-set and to
relate taxonomies to one another. Making these relations can
also be enjoyable, but soon interest turns toward developing such
taxonomies.

In a rule-based reasoning system, where rules or rule-sets
are the only medium for representing and storing knowledge,
getting started is (supposedly) easy. The student knowledge
engineer just starts "writing rules."

In a frame-based reasoning system many more issues need to
be considered. First, the type of reasoning that will be
necessary must be planned. Then the tasks to be performed by the
rules have to be specified and the requirements to accomplish
that processing must be determined. Only then can the developer
start to sketch out a few rules, identify a small hierarchy of
frames, and actually test that the structural concept performs as
expected.

It has been found that, in developing the beginnings of a
frames-based representation for an application, blackboard and
paper sessions held among the knowledge engineering team members
are best interspersed with sessions at the workstation to test
the ideas. Frame-based application development systems are
typically implemented for use with AI workstations and
incorporate a considerable number of graphical aids for creating
and testing the application. This hardware-software combination
offers remarkable efficiency early in the development cycle;
teams can often sketch out an implementation for two hours' worth
of designing at the blackboard in about one hour at a
workstation.

The consequences of this efficiency are significant. First,
developers are much less reluctant to throw away a design that is
only partially correct; second, it does not take very long to get
the design correct. In addition, the success or failure of a
given design can be determined in rather short order so that
developers can usually find an opportunity to test and measure a
pet design.


PROBLEMS WITH FRAME-BASED REASONING

Perhaps the most detrimental aspect of frame-based reasoning
systems are that frame-based and object-oriented programming
techniques are not yet commonplace in the computer world and
people need time and patience to master the techniques and use
them both fluently and properly. These techniques are
fundamentally simple, although at first they seem complex. It is
well worth the several months' time that it might take for a
knowledge engineer to become highly proficient in their use.


Efficiency Considerations
One of the major dissatisfactions expressed with frame-based
reasoning concerns efficiency. The structures and capabilites
that have been described in this brief offer a wide variety of
benefits, but these benefits are achieved only at a price. The
dynamic ability to modify the knowledge structure or to modify
the facets associated with a slot during execution of the
application system requires that a considerable amount of
checking be performed at execution time. The computer cannot
store a fact in a frame with the execution of a single store
instruction. Instead, the various facets governing the slot must
be references to verify that storage of this particular value is
permitted, to check whether this action is to be trapped, and so
forth. A simple store command that would involve a single
computer instruction in systems using other forms of knowledge
representation can easily explode into the tens and hundreds of
instructions. This expansion, of course, is accompanied by a
concomitant degradation in the application's execution speed.


Abuse of Frame-Based Reasoning
This brief has focused on the advantages that a developer
can gain using a frame-based approach for representing certain
aspects of an application's knowledge base, but the process can
also be abused. In a desire to build taxonomies, a new knowledge
engineer can easily become overly enthusiastic and create
inappropriate taxonomies. Such mistakes can lead to severe
difficulties subsequently when the knowledge engineer must reason
about the knowledge. Person having this difficulty are labeled
as having contracted "taxonomic fever."


"Taxonomic Fever"
A novice can easily succumb to taxonomic fever, which causes
a taxonomy to be devised to represent every phenomena in sight.
While most of the outward signs of this disease disappear after
the first few days of exposure to object-oriented programming or
frame-based reasoning, the inward vestiges of the disease can
linger, with a wayward taxonomy creeping into a design every now
and then. Therefore, a certain litmus test needs to be applied
to each taxonomy in the design, namely:

* How does this taxonomy support the reasoning process?
* Does the taxonomy refine the reasoning concept, that
is, does each unit of the taxonomy in the direction of
the leaves represent a specialization of the root (most
general) unit?

If the knowledge engineer has difficulty verifying these tests,
the taxonomy and the results that use it may not be well-
designed.


An Example
Consider the automotive diagnostic application, for example.
In such an application, the taxonomy and the rules should
represent the order and structure of the automotive diagnostic
process, which could easily have several taxonomies (with some,
perhaps, containing only rules). Among these taxonomies,
however, it would be surprising to find a car parts taxonomy that
starts with the car as a whole and goes down through all the
various assemblies and subassemblies to the final nuts and bolts.
Why? Because the complete parts structure of a car is not used
to diagnose an automotive malfunction; the mechanic does not
selectively test each nut, bolt, and washer. He does not reason
over the whole car, and his underlying reasoning in isolating a
problem and diagnosing it is quite different from that described
by the parts taxonomy.


A Taxonomic Mistake
One of the mistakes frequently made by novice knowledge
engineers is the construction of an inconsistent taxonomy. If,
for example, AUTOMOBILES is the top frame in a taxonomy and if 4-
CYLINDER is a leaf frame at the bottom of the taxonomy, then 4-
CYLINDER should be a specialization of AUTOMOBILES. Although
representing a more specialized object, 4-CYLINDER should still
characterize something that would be known as an automobile.
Since 4-CYLINDER is a more specialized engine rather than a more
specialized automobile, the taxonomy is at least mislabeled if
not in error. Such mislabeling can really confuse and obfuscate
knowledge in a frame-based representation.

Unfortunately, the knowledge engineer can fairly easily fall
into this type of trap. An example was shown in connection with
Figure 11b, in which MY-FORD as depicted as an instance of both
AUTOMOBILES and ENGINES. Another example is shown in Figure 22.
The taxonomy is consistent until the class FORD is reached. At
this point rather than the class being broken down into different
types of Ford automobiles, the class is broken down by components
that go into a car. The fact that the remainder of the hierarchy
is consistent with those components does not eliminate the
problem. The switch in logical progression has already been
made. The best procedure to test for such representational
errors is to ask at each level whether those objects represent
types of objects belonging to parent classes.

Fortunately, these problems diminish greatly as people
become more accustomed to and familiar with frame-based reasoning
and its capabilities.
_________________
| AUTOMOBILES |
|_________________|
_____________________|_____________________
________|________ ________|________
| DOMESTIC | | IMPORTED |
|_________________| |_________________|
|_____________________ _____________________
________|________ ________|________ ________|________
| CHEVROLET | | FORD | | CHRYSLER |
|_________________| |_________________| |_________________|
_____________________|_____________________
________|________ ________|________ ________|________
| FUEL-SYSTEM | | ENGINE | | BRAKES |
|_________________| |_________________| |_________________|
_____________________|_____________________
________|________ ________|________
| DIESEL | | GASOLINE |
|_________________| |_________________|
_____________________ _____________________|
________|________ ________|________ ________|________
| 4-CYLINDER | | 6-CYLINDER | | 8-CYLINDER |
|_________________| |_________________| |_________________|

Figure 22: An Erroneous Taxonomy


SUMMARY

Frame-based reasoning offers an attractive range of
techniques for structuring a knowledge-based application and for
supporting very rapid prototype development. It can provide
enormous benefits in knowledge representation and system
modification. However, these tools do not replace the detailed
analysis of the application necessary for it to be a success, and
blind application of these tools can lead to problems.


A Warning
The rather broad range of frame-based capabilites described
in this brief does not imply that any particular knowledge-based
application development tool (shell) has all these capabilites.
Some tools, of course, do not offer any frame-based
representational capabilities; others offer subsets of the
capabilities described herein. Part of the feasibility study and
the early design work involves examining the problem's natural
knowledge representations, comparing these requirements with the
representational capabilities of eligible tools, and finally
selecting a development tool (shell) and organizing the knowledge
to fit within the representations available.


Rule of Thumb
Frame-based reasoning is in many ways like physics. In that
domain, the behaviour of the physical world generally has a
simple explanation. Thus, if the researcher finds that the
explanation of a particular phenomenon (or the solution of a
particular problem) is becoming difficult or "messy," the
difficulty is an indication that a different approach should be
taken, that a different representation of the problem should be
considered.

Similarly, reasoning with frame-based knowledge is generally
a relatively straightforward process. If the knowledge engineer
finds that working with a particular representation is becoming
increasingly difficult, that difficultly is usually an indication
that the representation is wrong. It has been found that
stopping at this point and trying a different structure for the
knowledge usually significantly reduces the logical complexity of
the problem.

Because frame-based reasoning development tools are large
and normally require large, specialized workstations,
applications developed using them are difficult to move into
environments where delivery versions of these tools may not
exist. More and more delivery environments are being supported
by the manufactures of these software tools; as time progresses,
this problem should become less critical. Also, new personal
computer systems built around the Intel 80386 chip may provide a
cost effective delivery vehicle for many application using frame-
based reasoning tools.


------------


 December 28, 2017  Add comments

Leave a Reply