SpEclAL sumid
`THE ROLE OF FRAME-BASED
`REPRESENTATION IN REASONING
`
`A frame-based representation facility contributes to a knowledge system’s
`ability to reason and can assist the system designer in determining strategies
`for controlling the system’s reasoning.
`
`RICHARD IFIKES and TOM KEHLER
`
`A fundamental observation arising from work in artifi-
`cial intelligence
`(AI) has been that expertise in a task
`domain requires substantial knowledge about that do-
`main. The effective representation of domain knowl-
`edge is therefore generally considered to be the key-
`stone to the success of AI programs [15] (see Figure 1).
`Domain knowledge typically has many forms, including
`descriptive definitions of domain-specific
`terms (e.g.,
`“power plant,” “pump, ” “flow,” “pressure”), descriptions
`of individual domain objects and their relationships
`to
`each other (‘e.g., “Pl is a pump whose pressure is 230
`psi”), and criteria for making decisions (e.g., “If the
`feedwater pump pressure exceeds 400 psi, then close
`the pump’s input value”). Because of this emphasis on
`representatbon and domain knowledge, systems that use
`AI techniqules to achieve expertise are often referred to
`as knowledge-based systems, or simply as knowledge
`systems.
`In order for a knowledge system to use domain-
`specific knowledge, it must have a language for repre-
`senting that knowledge. The basic criteria for a knowl-
`edge representation language are the following:
`l Expressive power-Can experts communicate their
`knowledge effectively
`to the system?
`l Understan(dability-Can experts understand what the
`system knows?
`. Accessibility-Can
`has been given?
`Experience has made it increasingly clear that none
`of the major knowledge representation languages is by
`itself able to satisfy all of these criteria. Early attempts
`at building
`intelligent systems used the first-order pred-
`
`the system use the information
`
`it
`
`@ 1985 ACM OOOl-0782/85/0900-0904
`
`756
`
`icate calculus as their representation language (e.g.,
`[lo]). The predicate calculus was appealing because of
`its very general expressive power and well-defined se-.
`mantics. However, because the language constructs are
`very fine grained and do not provide adequate facilities
`for defining more complex constructs, domain experts
`have difficulty using the predicate calculus or under-
`standing knowledge expressed in it. Also, the generalilty
`of the predicate calculus has been a significant barrier
`to the development of effective deduction facilities for
`using knowledge expressed in it.
`These difficulties helped motivate the development
`of “semantic networks” (e.g., [ll]), and various “object-
`oriented” representation languages based on frames (e.g.,
`[2,4]). Frame languages provide the knowledge-base
`builder with an easy means of describing the types of
`domain objects that the system must model. The de-
`scription of an object type can contain a prototype de-
`scription of individual objects of that type; these proto-
`types can be used to create a default description of an
`object when its type becomes known in the model.
`A frame provides a structured representation of an
`object or a class of objects. For example, one frame
`might represent an automobile, and another a whole
`class of automobiles (see Figure 2). Constructs are avail-
`able in a frame language for organizing frames that
`represent classes into taxonomies. These constructs al..
`low a knowledge-base designer to describe each class as
`(subclass) of other more generic classes.
`a specialization
`Thus, automobiles can be described as vehicles plus a
`set of properties that distinguish autos from other kinds
`of vehicles.
`The advantages of frame languages are considerable:
`They capture the way experts typically
`think about
`
`904
`
`Communications of the ACM
`
`September 1985 Volume 28 Number 9
`
`WTS PARADIGM LLC EXHIBIT 1007
`1 of 17
`
`

`
`Special Section
`
`much of their knowledge, provide a concise structural
`representation of useful relations, and support a concise
`definition-by-specialization
`technique that is easy
`for most domain experts to use. In addition, special-
`purpose deduction algorithms have been developed
`that exploit the structural characteristics of frames to
`rapidly perform a set of inferences commonly needed
`in knowledge-system applications,
`In addition to encoding and storing beliefs about a
`problem domain, a representation facility
`typically per-
`forms a set of inferences that extends the explicitly
`held set of beliefs to a larger, virtual set of beliefs. Thus,
`the representation facility participates in the system’s
`reasoning activities by providing these “automatic”
`in-
`ferences as part of each assertion and retrieval opera-
`tion. Frame languages are particularly powerful in this
`regard because the taxonomic relationships among
`frames enable descriptive information
`to be shared
`
`frames (via inheritance) and because the
`among multiple
`internal structure of frames enables semantic integrity
`constraints to be automatically maintained.
`One of the basic tenets of knowledge-system technol-
`ogy is that domain knowledge can be more effectively
`used by a system and more easily understood by a
`system’s users if it is represented in declarative rather
`than procedural form. Frame systems, however, pro-
`vide no direct facilities for declaratively describing how
`the knowledge stored in frames is to be used. Tradition-
`ally, the only way of associating domain-dependent be-
`havior with frames has been by attaching to them in
`various ways procedures written
`in the underlying pro-
`gramming language (e.g., LISP) (as in, for example,
`KL-ONE [4] and KRL [Z]). Additional
`facilities are
`needed in such systems for declaratively describing
`domain-dependent inference rules, analysis decision
`rules, actions that can be taken in the domain by
`
`Behavior
`descriptions
`
`Vocabulary
`definitions
`
`Objects
`and
`relationships
`
`I
`
`1
`
`I
`
`\.
`
`1
`
`I
`
`I
`
`/1
`
`Unce&ain
`
`I
`]
`
`Processes
`
`Knowledge
`base
`
`M
`
`Constraints
`
`A
`
`A
`
`I
`
`I
`
`Disjunctive
`facts
`
`Expertise in a task domain usually draws on many diierent
`kinds of knowledge about that domain. The representation and
`reasoning facilities in Al systems must be able to integrate
`
`different kinds of knowledge into a coherent knowledge base
`that can effectively support the system’s activities.
`
`FIGURE 1. The Kinds of Knowkdge That Can Go into a Knowledge Base
`
`September 1985 Volume 28 Number 9
`
`Communications of the ACM
`
`905
`
`WTS PARADIGM LLC EXHIBIT 1007
`2 of 17
`
`

`
`Special Section
`
`AGENTS
`
`--
`
`PEOPLE
`
`6
`
`PHYSICAL
`
`.DB.cECTS
`
`,hlEN-=:::I
`
`FE:
`
`-0DCTDRS
`\LAWYERS
`BUILDINGS
`STATUES
`JHlNGS.OWNED.BYJ'ALJL--,__
`
`-.__
`
`.
`
`PRODUCTS -
`
`VEHICLES
`
`AUTDMDBUmES
`
`e
`
`TRUCKS<
`
`\ BOATS
`
`SEDANS------CAR2
`-COUPES
`STATIDN.WAGGNS
`HUGE .GREY .TRUCKS
`- - - = = - TRUCK 1
`BlG.NDNJIED.TRUCKS
`
`ransportatiof~
`II .!:
`
`Superclasses
`Subclasses
`Member
`of:
`
`: WEHlCLES
`COUPES,
`: STATIDN.WAGGNS,
`(CLASSES in
`)1B GENERKXJNIJS)
`
`SEDANS
`
`emberslot:
`Inheritanlce:
`Cardinality.Wax:
`Values:
`Ulnknown
`
`from PHYSlCM.OBJECTS
`*COLOR
`DWERRlDE.WALlJES
`1
`
`emberslot:
`Inheritance:
`ValueClass:
`Cardinality.Min:
`Cardinalizy.Max:
`‘Height
`Conrent:
`Values
`: Ul?known
`
`from PHYSlCAL.DBJECJS
`*HEIGHT
`DWERRlDE.WMUES
`INTEGER
`1
`1
`in
`
`inches.’
`
`:
`
`SmberSlot
`Inheritance
`ValueClass:
`Cardinality.Yin:
`Cardinality.Wax:
`‘Length
`Cornrent:
`Unknown
`Values:
`
`f r on PHYSICAL.DB.fECTS
`“LENGTH
`: OWERRKlE.WALlJES
`RlTEGER
`1
`1
`in
`
`inches’
`
`?IrberSlot:
`Inheritance:
`Cardinality.Min:
`Cardinalizy.Max:
`Values
`: Unknown
`
`%OCATlON from PHYSIcM.UBJECTS
`OWERRlOE.WMlJES
`1
`1
`
`-
`
`iji trmsportation
`j$ Member
`of:
`SEDANS
`cam
`from PtwsIcM.cmscTs
`i tance
`: DWERRlDE.WALUES
`Unknown
`
`iii OwnSlot:
`:::
`I nher
`Values:
`
`HEIWIT
`OwnSlot:
`Inheritance
`ValueClass:
`Cardinality.Yin:
`Cardinality.lOax:
`Comment:
`‘Height
`Values:
`Unknown
`
`fron PHYSlCM.OBJECTS
`: OWERRlDE.WALUES
`NTEGER
`1
`1
`in
`
`inches.’
`
`from PHYSlCM.OBJECTS
`LENGTH
`OwnSlot:
`i tance
`: OWERRKXWALUES
`I nher
`ValueClass:
`NTEGER
`Cardinality.Win:
`1
`1
`Cardinality.Uax:
`Comment:
`‘Length
`in
`Values:
`Unknown
`
`inches’
`
`PHYSlCM.GBJECTS
`fror
`LOCATKIN
`OwnSlot:
`OWERRU3E.WMlJES
`Inheritance:
`1
`1
`
`Cardinality.Max:
`Values:
`Unknown
`
`$
`
`t:l Cardinality.Min:
`
`OWNER
`OwnSlot:
`Inheritance:
`ValueClass:
`
`from PHYSlCM.OBZCTS
`DWERRlDE.WMUES
`AGENTS
`
`of objects or
`representations
`Frames provide structured
`classes of objects. The AUTOMOBILES
`frame shown here
`(lower
`left) represents
`the class of all automobiles. and the
`CARP frame 8(lower right) represents a specific automobile
`that
`is a member of that class. Frames allow classes
`to be
`described as specializations
`of other more generic classes and
`for those descriptions
`to be organized
`into taxonomies. Thus,
`automobiles
`can be described as vehicles plus a set of
`
`from other kinds of vehicles.
`that distinguish autos
`properties
`The transportation
`taxonomy shown here (top) uses solid
`lines to represent class-subclass
`relationships and dashed
`lines to represent class-member
`relationships. For example,
`VEHICLES
`isa subclass ofboth PHYSICAL.•
`BJECTS and
`PRODUCTS, and TRUCK 1 is a member of both
`HUGE.GREY.TRUCKSalIdTHINGS.OWNED.BY.PAUL.
`
`FIGURE 2. A Frame Taxonomy
`
`906
`
`Communications of the ACM
`
`September 1985 Volume 28 Number 9
`
`WTS PARADIGM LLC EXHIBIT 1007
`3 of 17
`
`

`
`Special Section
`
`various agents, simulations of object behavior, etc.
`The most popular and effective representational
`form
`for declarative descriptions of domain-dependent be-
`havioral knowledge in knowledge systems has been
`pattern/action decision rules, called production rules
`(e.g., [6, 71). Production rules are, in effect, a subset of
`the predicate calculus with an added prescriptive com-
`ponent indicating how the information
`in the rules is to
`be used during reasoning. Production rules can be eas-
`ily understood by domain experts and have sufficient
`expressive power to represent a useful range of
`domain-dependent inference rules and behavior speci-
`fications. By themselves, however, production rules do
`not provide an effective representation facility
`for most
`knowledge-system applications. In particular,
`their ex-
`pressive power is inadequate for defining terms and for
`describing domain objects and static relationships
`among objects.
`The major inadequacies of production rules are in
`areas that are effectively handled by frames. A great
`deal of success, in fact, has been achieved by integrat-
`ing frame and production rule languages to form hybrid
`representation facilities that combine the advantages of
`both component representation techniques (e.g.,
`LOOPS8 [18], KEE” (Knowledge Engineering Environ-
`ment@) [12], and CENTAUR [l]). These systems have
`shown how a frame language can serve as a powerful
`foundation for a rule language. The frames provide a
`rich structural
`language for describing the objects re-
`ferred to in the rules and a supporting layer of generic
`deductive capability about those objects that does not
`need to be explicitly dealt with in the rules. Frame
`taxonomies can also be used to partition,
`index, and
`organize a system’s production rules. This capability
`makes it easier for the domain expert to construct and
`understand rules, and for the system designer to control
`when and for what purpose particular collections of
`rules are used by the system.
`for Minsky’s intro-
`Although a primary motivation
`duction of frames [a] was to semantically direct the
`reasoning of scene-analysis systems, most of the subse-
`quent work on frame-based systems (e.g., KRL [2],
`UNITS [Ii’], and KL-ONE [4]) has focused on structural
`representation issues rather than on the control of rea-
`soning. The information stored in frames has often been
`treated as the “database” of the knowledge system,
`whereas the control of reasoning has been left to other
`parts of the system. This focus on structural representa-
`tion issues has helped to elucidate the semantics of the
`common frame constructs and to demonstrate their
`usefulness for organizing and storing knowledge (e.g.,
`[5]). Little attention, however, has been paid to
`whether and how those constructs can be useful for
`controlling reasoning.
`Recent experience with frame-based representation
`facilities in complex application domains has shown
`that frames can play an important role throughout
`the
`LOOPS is a trademark of Xerox Corporation.
`KEE and Knowledge Engineering Environment are trademarks of IntelliCorp.
`
`in the control of reasoning compo-
`system, including
`nents. For example, the structural
`features of frame
`languages have proved to be very useful for organizing
`and controlling
`the behavior of large collections of pro-
`duction rules. These uses of frames are our central
`theme in this article. We elaborate the various ways in
`which a frame-based representation facility participates
`in a knowledge system’s reasoning functionality and
`can assist the system designer in determining strategies
`for controlling a system’s reasoning.
`
`COMPONENTS OF A FRAME-BASED
`REPRESENTATION
`FACILITY
`In this section we summarize the basic components of a
`typical frame-based representation facility
`in order to
`indicate the salient features of frame systems and to
`provide a context for the discussions in subsequent sec-
`tions. The facility described is a component of the KEE
`system [12]. In order to highlight
`the role that a frame-
`based representation facility plays in the reasoning of a
`knowledge system, our description explicitly distin-
`guishes between the semantic interpretation of frame
`language constructs (e.g., that a MemberOf link be-
`tween frames M and C denotes the proposition that the
`object represented by M is a member of the class repre-
`sented by C), and the reasoning services that are typi-
`cally provided by a frame-based representation facility
`(e.g., that when a MemberOf link is created between
`frames M and C, the default description in C of mem-
`bers of the class represented by C is added to M).
`
`Structural
`Features
`Taxonomy Descriptions. The frame-based representa-
`tion language included in the KEE system provides typ-
`ical frame language constructs for describing individu-
`als and classes of individuals
`in an application domain
`(see Figure 3). Each individual or class is represented
`by a frame.’ Frames can be organized into taxonomies
`using two constructs that represent relationships be-
`tween frames: member links, representing class member-
`ship, and subclass links, representing class containment
`or specialization. These links provide two standard in-
`terpretations of the meaning of “is-a” links, as in “A
`truck is a vehicle” and "TRUCK 1 is a truck.” (See [3] for
`a discussion of the variety of interpretations of “is-a” in
`frame systems.)
`Frames can incorporate sets of attribute descriptions
`called slots. A distinguishing characteristic of frame-
`based languages is that a frame representing a class can
`contain prototype descriptions of members of the class
`as well as descriptions of the class as a whole. In the
`KEE system, prototype descriptions are distinguished
`from other descriptive information by the use of two
`kinds of slots, own slots and member slots. Own slots can
`occur in any frame and are used to describe attributes
`of the object or class represented by the frame. Member
`‘Some systems use other terms for what we are calling frames. For example.
`frames are called units in the KEE system and concepts in KL-ONE. We use the
`single generic term “frame”
`in all cases here for consistency.
`
`September 1985 Volume 28 Number 9
`
`Communications of the ACM
`
`SO7
`
`WTS PARADIGM LLC EXHIBIT 1007
`4 of 17
`
`

`
`Special Section
`
`In knowledge base TRANSPORTATION
`Frame: TRUCKS
`Superclasses:
`VEHICLES
`Subclasses
`HUGE.GREY.TRUCKS
`: BIG.NON.RED.TRUCKS,
`MemberOf: CLASSES.OF.PHYSICAL.OBJECTS
`
`from PHYSICAL.OBJECTS
`MemberSlot : HEIGHT
`Val.ueClass:
`INTEGER
`Cardina1ity.MI.n:
`1
`Cardlnality.Max:
`1
`Units
`: INCHES
`*Height
`Comment
`:
`Val.ues: Unknown
`
`inches."
`
`in
`
`MemberSlot : LENGTH
`from PWSICAL.OBJECTS
`ValueClass:
`NUMBER
`Cardinality.Min:
`1
`Cardinallty.Max:
`1
`Units
`: METERS
`*Length
`Comment:
`Values: Unknown
`
`in meters*
`
`from CLASS.OF.PHYSICAL.OBJECTS
`LONGEST
`OwnSlot:
`ValueClass:
`TRUCKS
`Cardina1ity.MI.n:
`1
`Cardinallty.Max:
`1
`"The longest
`Comment:
`Values: Unknown
`
`known truck*
`
`from CLASS.OF.PHYSICAL.OBJECTS
`TALLEST
`OwnSlot:
`ValueClass:
`TRUCKS
`Cardinallty.Mln:
`1
`Cardinali.ty.Max:
`1
`Comment:
`"The tallest
`Values: Unknown
`
`known truck'
`
`This frame describes class TRUCKS as a subclass of class
`VEHICLES and as a member of class
`Memberslotsinthe
`CLASSES.• F.PHYSICAL.OUJECTS.
`TRUCKS framelike
`LENGTH and HEIGHT providea
`
`prototype description of each class member. Own slots like
`LONGEST and TALLEST describe attributes of the class as
`a whole.
`
`FIGURE 3. The TRUCKS Frame
`
`908
`
`Communications of the ACM
`
`September 1985 Volume 28 Number 9
`
`WTS PARADIGM LLC EXHIBIT 1007
`5 of 17
`
`

`
`Special Section
`
`slots can occur in frames that represent classes and are
`used to describe attributes of each member of the class,
`rather than of the class itself. For example, a frame
`representing the TRUCKS class might have own slots for
`LONGEST and HEAVIEST,
`and member slots for
`LENGTH and WEIGHT. Member slots allow class frames
`to play a role in knowledge bases similar to that of
`schemas in relational databases.
`Frames representing classes may have slots whose
`values specify collections of subclasses that form dis-
`joint decompositions or exhaustive decompositions of
`the class (e.g., to specify that a vehicle cannot be both a
`truck and a station wagon, or that all adults are either
`men or women). The semantics of these decomposition
`slots is considered to be part of the definition of the
`frame language. Thus, domain-independent methods
`can be included in a frame system for reasoning about
`decompositions.
`
`Attribute Descriptions. An important source of the ex-
`pressive power of frame-based languages is the facilities
`they provide for describing object attributes. For exam-
`ple, a frame representing a truck might include descrip-
`tions of the truck’s height, length, and owner. These
`facilities allow frames to include partial descriptions of
`attribute values, and help preserve the semantic integ-
`rity of a system’s knowledge base by constraining the
`number and range of allowable attribute values.
`Slots in most frame systems, including KEE, can have
`multiple values (to provide appropriate support for at-
`tributessuchas COUSIN, WHEEL, and VICEPRESI-
`DENT) and a set of properties, which we are calling
`facets. Several frame systems, including KEE, have
`built-in
`facets for representing constraints on the num-
`ber of possible values an attribute can have and for
`indicating
`the classes to which each value must belong.
`For example, the frame representing a person “John”
`could specify that John’s SISTER slot has three values,
`each of whom is a doctor, without
`identifying
`the
`sisters.
`In the KEE system, two facets, CardinalityMin
`and CardinalityMax,
`have been provided for con-
`straining the number of values for an attribute repre-
`sented by a slot. A CardinalityMin
`value of m indi-
`cates that the corresponding attribute has at least m
`distinct values; a CardinalityMax
`value of n indi-
`cates that the corresponding attribute has at most n
`distinct values.
`facet of a slot can be used to de-
`The ValueClass
`scribe the classes to which each value of the slot be-
`longs. The value of the ValueClass
`facet of a slot can
`be a Boolean combination of class descriptions; for in-
`stance,
`
`MEN
`(INTERSECTION
`(UNION DOCTORS LAWYERS)
`(NOT.ONE.OF
`FRED))
`
`designates a man who is either a doctor or a lawyer,
`but is not Fred (see Figure 4). The value-class specifica-
`tion is a generalization of a standard programming lan-
`
`guage data-type specification. The KEE system provides
`a knowledge base containing class frames for standard
`STRINGS). The class
`data types (e.g., INTEGERS,
`frames in that knowledge base are available for inclu-
`sion in value-class specifications. For example, one
`could specify that a value must be any integer in the
`range 0 to 100 except 23 or 36 with the value class
`
`(INTERSECTION
`(INTERVAL
`(NOT:ONE.OF
`
`INTEGERS
`0 100)
`23 36)).
`
`The system’s functions for adding slot values to a
`knowledge base use the slot’s value-class and cardinal-
`ity specifications as constraints that must be satisfied
`by any new value. Value-class and cardinality specifi-
`cations also provide effective partial descriptions of un-
`known slot values, including
`the representation of a
`useful class of disjunctions and negations. For example,
`the UNION and ONE. OF value-class constructs can be
`used to express disjunctive
`information about the val-
`ues of a slot, the NOT. IN and NOT. ONE. OF constructs
`can be used to express negative information, and a
`CardinalityMax
`value of 0 can be used to indicate
`that the slot has no values.
`
`Behavioral Properties
`Although
`frame languages provide no specific facilities
`for declaratively describing behavior, they do provide
`various ways of attaching procedural information ex-
`pressed in some other language (e.g., LISP) to frames
`(see Figure 5). This procedural attachment capability
`enables behavioral models of objects and expertise in
`an application domain to be built. It also provides a
`powerful form of object-oriented programming whereby
`objects represented by frames can respond to messages.
`The KEE system supports two standard forms of pro-
`cedural attachment: methods and active values. Methods
`are LISP procedures, attached to frames, that respond to
`messages sent to the frames. Methods are stored as the
`values of slots that have been identified as message re-
`sponders. Messages sent to frames specify the target
`message-responder slot and include any arguments
`needed by the method stored at the slot. Active values
`are procedures or collections of production rules at-
`tached to slots that are invoked when the slot’s values
`are accessed or stored. Thus, they behave like “de-
`mons,” monitoring changes and uses of the values.
`They can also be used to dynamically compute values
`on a “when-needed” basis. Methods and active values
`are typically written
`to apply to any member of a class
`of objects and are included by the knowledge-base de-
`signer in the class description as part of the prototype
`description of a class member.
`
`Reasoning Services
`A frame-based representation facility extends the sys-
`tem’s exnlicitlv held set of beliefs to a larger. virtual set
`Y
`.
`d
`of beliefs by automatically performing a set of infer-
`ences as part of its assertion and retrieval operations.
`These inferences, based on the structural properties of
`
`September 1985 Volume 28 Number 9
`
`Communications of the ACM
`
`909
`
`WTS PARADIGM LLC EXHIBIT 1007
`6 of 17
`
`

`
`Special Section
`
`Unit:
`base TRANSPORTATION
`in knowledge
`TRUCK1
`Member : THINGS.OWNED.BY.PAUL,
`HUGE.GREY.TRUCKS
`
`: OWNER
`ownsl.ot
`(UNION DOCTORS
`Valueclass:
`MEN
`(NOT. ONE. OF FRED)
`AGENTS
`1
`
`Cardlnallty.Max:
`Values : PAUL
`
`LAWYERS)
`
`ownSl.ot : WHEELS
`from HUGE.GREY.TRUCKS
`16
`Cardinallty.Min:
`‘The vehicle’s
`Comment:
`Values:
`Unknown
`
`wheels’
`
`The facilities provided by frame languages for describing object
`attributes help preserve the semantic integrity of a system’s
`knowledge base by constraining the number and range of
`allowable amibute values. For example, the frame shown here,
`which represents a truck, specifies (by means of the
`
`. Min facet of the WHEEL slot) that the truck
`Cardinality
`must have at least 16 wheels and (by means of the
`Valueclass
`facet of the OWNER slot) that its owner must
`be a man who is either a doctor or a lawyer and not Fred.
`
`FIGURE 4. The TRUCK 1 Frame
`
`frames and taxonomies, can often play a major role in
`the overall reasoning of a knowledge system. Because
`they are “wired in” to the representational machinery
`and have a limited scope, they are much faster than
`general deduction methods, such as logic theorem prov-
`ers or production rule interpreters.
`Some of these inference methods perform what is
`commonly known as inheritance. If the PHYSICAL.
`OBJECTS frame has a subclass link to the VEHICLES
`frame, for example, and the VEHICLES
`frame has a
`subclass link to the AUTOS frame, the representation
`facility will “retrieve”
`the belief that AUTOS is a sub-
`class of PHYEIICAL. OBJECTS without
`recourse to
`other reasoning mechanisms.
`Other automatic inference methods use constraints
`such as value-class and cardinality specifications to de-
`termine whether a given item could be a value of a
`given slot. For example, when a value is being added to
`a slot, the value is rejected if the slot already contains
`the maximum number of permitted values or if the
`value is not a member of the slot’s value class.
`
`The assertion and retrieval mechanisms
`Inheritance.
`for frame-based languages use the member links, sub-
`
`class links, and prototype descriptions of class members
`in a frame. Any
`to augment
`the descriptive
`information
`frame can have a member link to one or more class
`frames (e.g., to represent that TRUCKI
`is a member of
`both TRUCKS and THINGS.OWNED.BY.PAUL).A
`frame is said to inherit the member slots of the class
`frames to which it has member links. Those inherited
`slots become own slots of the member frame, since they
`represent attributes of the member object itself. For
`example, the TRUCKS frame would acquire two own
`slots, LENGTH and WEIGHT, from the frame for
`TRUCKS.
`Class frames (i.e., frames that represent classes) can
`also have subclass links to one or more other class
`frames (e.g., to represent that TRUCKS is a subclass of
`both VEHICLES and PRODUCTS). Since every member
`of a subclass is also a member of the superclass, a sub-
`class frame inherits the member slots of its superclass
`frames as additional member slots. For example, if the
`frame has member slots LENGTH
`PHYSICAL.OBJECTS
`and WEIGHT, and the VEHICLES
`frame has a subclass
`linktothe
`frame,then LENGTH
`PHYSICAL.OBJECTS
`and WEIGHT become member slots of the VEHICLES
`frame as well.
`
`910
`
`Communications of the ACM
`
`September 1985 Volume 28 Number 9
`
`WTS PARADIGM LLC EXHIBIT 1007
`7 of 17
`
`

`
`Special Section
`
`The KEE system also considers a class to be a describ-
`able object. Thus, the frame for a class can indicate the
`classes to which that class itself belongs. Like any other
`frame, a class frame inherits own slots from the frames
`that represent the “classes of classes” to which the
`class belongs. For example, VEHICLES might be a
`memberofclass PHYSICAL.~BJECT.TYPES.
`The
`framemightincludethe
`PHYSICAL.•
`BJECT.TYPES
`member slots LONGEST and HEAVIEST,
`which would
`thus become own slots of the VEHICLES
`frame.
`
`Value Class and Cardinality Reasoning. A frame system
`considers value-class and cardinality specifications as
`constraints on the legal values of a slot. The system
`provides constraint checking procedures for determin-
`
`ing whether a slot’s value-class and cardinality specifi-
`cations exclude a given item from being a value of the
`slot. An item is excluded if the slot already has its
`maximum number of allowable values or if the item is
`not a member of the slot’s value class. These proce-
`dures can be called directly by the user. They are
`called by the system whenever a slot’s values, value-
`class specifications, or cardinality specifications are
`changed. Calls by the system cause an error to be gen-
`erated if a constraint is violated.
`The value-class constraint checking procedures un-
`derstand the semantics of basic set theory operators and
`numerical intervals. The primitive
`test of whether a
`given item is in a class represented by a frame is per-
`formed by sending a message to the frame; thus each
`
`Unit:
`in knowledge base TRANSPORTATION
`TRUCKS
`VEHICLES
`Superclasses:
`Subclasses
`: BIG.NON.RED.TRUCKS,
`Member: CLASSES.OF.PHYSICAL.OBJECTS
`
`HUGE.GREY.TRUCKS
`
`from TRUCKS
`MemberSlot: DIAGNOSE
`Inheritance:
`METHOD
`ValueClass: METHODS
`Cardinality.Min:
`1
`Cardi.nality.Max:
`1
`Comment:
`'A method for diagnosing
`Values: TRUCK.DIAGNOSIS.FUNCTION
`
`electrical
`
`faults:
`
`from TRUCKS
`: ELECTRICAL.FAULTS
`MemberSlOt
`Comment:
`'Faults
`found by the DIAGNOSIS method"
`Values: Unknown
`
`from PHYSICAL.OBJECTS
`
`MemberSlot: LOCATION
`Cardina1ity.Ml.n:
`1
`Cardlnallty.Max:
`1
`Values: Unknown
`ActiveValues:
`UPDATE.LOCATION
`
`Procedural information can be attached to frames in various
`ways. For example, ti
`value of the DIAGNOSE slot in the
`TRUCKS frame is a method (i.e., function) for diagnosing
`electrical faults. The slot and method are inherited by the
`frames that represent individual trucks and enable each, of
`them to respond to DIAGNOSE messages by calling ths
`method. In addition, “demons” in ths form of functions or
`collections of production rules can be attached to slots so that
`
`they are automatically invoked when the slot’s values are
`accessed or stored. For example, a demon is attached to the
`LOCATION slot of the TRUCKS frame (by means of the
`facet) t0 Updab
`a geOgraphiCal map being
`ActiveValues
`displayed by the system whenever the slot’s value changes.
`The slot and its attached demon are inherited by the frames
`that represent individual trucks, so that the current location
`of every truck is displayed on the map.
`
`FIGURE 5. Procedural Information in the TRUCKS Frame
`
`September 1985 Volume 28 Number 9
`
`Communications of the ACM
`
`911
`
`WTS PARADIGM LLC EXHIBIT 1007
`8 of 17
`
`

`
`Special Section
`
`class in a knlowledge base can have its own member-
`ship test (e.g., for INTEGERS). The frame can respond
`yes, no, or unknown. A default method is supplied that
`looks at explicit membership links and decomposition
`specifications.
`
`FOR
`
`FRAMES A!; A FOUNDATION
`PRODUCTION-RULE
`SYSTEMS
`A frame-based representation facility can serve as an
`important component in the design of a production-rule
`language and the reasoning facilities that interpret
`rules. The frame facility supplies an expressively pow-
`erful language for describing the objects being reasoned
`about by the rules and automatically performs a useful
`set of inferences on those descriptions. In addition,
`frames can be used to represent the rules themselves.
`When each rule is represented as a frame, rules can
`easily be grouped into classes, and the description of
`a rule can include arbitrary attributes of the rule. For
`example, a frame representing a rule could have an
`EXTERNAL. FORM slot containing the rule as the user
`wrote it, and a PARSE method for converting the rule
`into an inter:nal form consisting of lists of expressions
`that are values of the slots CONDITIONS,
`CONCLU-
`SIONS , and ACTIONS. Other slots that provide descrip-
`tions, such as rationalizations
`for the rule, records of
`usage, and goals the rule is useful for achieving, could
`be included in the frame at the user’s or designer’s
`discretion.
`in the
`facility
`The architecture of the production-rule
`KEE system illustrates many of these points. Each rule
`is represented as a frame, and the facility uses a simple
`predicate logic language for representing a rule’s condi-
`tions and conclusions. The predicates of the language
`reflect the relationships
`that can be represented in the
`frame langualge; for instance, class membership
`(IN. CLASS)!. the minimum cardinality of an own slot
`(OWN. MIN. CARD), and being the value of an own slot
`(OWN. VALUE:). The rule designer therefore has full ac-
`cess to the frame language through these predicates. In
`addition, the language allows any LISP function
`to be a
`predicate, so that an arbitrary computation can be used
`to determine the truth value of a rule condition.
`Consider, for example, the KEE system production
`rule shown in Figure 6. This rule states that trucks
`weighing more than 10,000 pounds, having at least 10
`wheels, and having a color other than red are members
`of the class EIG. NON. RED. TRUCKS. The rule is rep-
`resented in the KEE system as a frame and is parsed by
`a method attached to the frame. The parser translates
`the rule’s conditions and conclusions into the logic lan-
`guage described above. The rule’s internal
`form corre-
`sponds to
`
`(IF
`
`(AND
`
`?X TRUCKS)
`(IN.CLASS
`(OWN-VALUE WEIGHT ?X ?WT)
`(GR