Note: Descriptions are shown in the official language in which they were submitted.
`` ~2~33~
70æ40-76
EXPERT SYSTEM APPARATUS AND M~THO~S
Cross-references to Related Applications
Background of the Invention
1. Field of the Invention
The present invention relates to expert systems
implemented by means of digital computers and more particularly to
the knowledge base and inference engine components of expert
systems, to apparatus for creatiny expert systems, and to
apparatus and methods for creating a definitional knowledge base.
Brief Description of Drawings
Figure 1 is a conceptual block diagram of a prior-art
expert system.
Figure lA is a conceptual block diayram of a prior-art
expert system shell.
Figure 2 is a conceptual block diagram of the expert
system shell and expert system of the present invention.
Figure 3 is a canceptual diagram of a hierarchy of
definitions as used in the present invention.
Figure 4 is a diagram of the terms and descrlptions used
`- to define the term FRAUD.
Figure 5 is a diagram of a hISP environment.
Figure 6 is an overvlew of a first pratotype emhodiment
~` of the present invention.
.`' ,
. .
,
,
~7~33~
70~40--76
Figure 7 is a diayram of TDEF 617 of the first prototype
embodiment.
Figure 8 is a detailed diagram of the function DEFINE of
the first prototype embodiment.
Figure 9 is a diagram of certain improvements in the
second prototype embodiment.
2. DescriPtion of_the Prior Art: Fi~. 1 and lA
In recent years, expert systems have become commercially
available. An expert system is a system which applies information
in a given field of expertise in the same fashion as ~70uld an
-la~
~7~3~3
expert in the field. Additionally, expert systerns resemble human
experts in that they are able to some degree to explain
themselves. Depending on its complexity, an expert system may
explain why it reached a given conclusion, explain why it wants a
given piece of information, and permit the user to change the
value of a given piece of information and see how that affects the
result. Expert systems have been built which perform tasks such
as configuring large computer systems, diagnosing bacterial
infections, or diagnosing why an oil drilling bit has become stuck
and suggesting a remedy.
Prior-art expert systems have generally been rule-based, i.e.,
they have functioned by applying rules obtained by questioning an
expert about his expertise to facts provided by the user of the
expert system. The rules are generally of the form
If A then B
In such a rule, A is termed the predicate for B, which is the
conclusion. ~hen A is true, then the conclusion may be inferred
to be true. For example, one rule in a medical diagnostic system
might be "If the patient has a fever and runny nose, he may have
the flu." According to this rule, if the symptoms are a fever and
runny nose, one possible inference is the Plu.
~ ~7~3~q~
Figure 1 is a block diagram of a prior-art rule-based expert
system 101. System 101 has three components, command processor
(CP) 103, rule inference engine (RIE) 105, and rule store (RS)
107. RS 107 contains the rules 109 for the area for which the
system is an expert. RIE 105 receives problem data from the user,
applies the rules in RS 107 to the data, and provides the result
of its application of the rules to the problem data to the user.
CP 103 controls RIE 105 by means of inference engine commands
(IEC). CP 103 produces the commands from command input provided
by the user. To continue with the flu example above, a person
using a medical diagnosis expert might input the command to the CP
"What disease?" CP 103 would then provide an inference engine
command to RIE 105, which would determine that its rules for
diseases required symptoms. RIE 105 would then requést problem
data from the user, perhaps by asking "What symptoms?'l The user
could then input the symptoms and RIE 105 could then find a rulé
109 for which the symptoms ~lere the predicate and return the
rule's conclusion as result data. For example, if the input
symptoms were "fever and runny nose", expert system 101 could
conclude from the rule 109 cited above that the disease might be
the flu. Of course, many other ailments have those symptoms, and
there would therefore be more than one rule 109 having the
symptoms as part of its predicate. Dependin~ on its
sophistication, expert system 101 could simply return as results
the conclusions of dll rules 109 having the symptoms ~s part of
~ , .
;:
'i
~2~
their predicate or could ask the user for more symptoms and use
the new symptoms to narro~ the number of rules ~Jhich ~JoulrJ apply.
In either case, expert system 101 can, at the request of the user,
show what rules 109 it used to reach its conclusion.
The first prior-art expert systems 101 ~ere custom-made and
required long and close cooperation between an expert, a knowledge
engineer, and computer system designers. The expert provided his
expertise; the knowledge engineer reduced the expertise to rules
109 and designed RIE 105 and the representation used to store the
rules 109 in RS 107. Computer system designers, finally, ~Jrote
the programs which implemented the kno~Jledge engineer's design.
The large inputs of professional time required to custom build
expert systems 101 made them very expensive and led the makers of
expert systems 101 to develop special tools, called expert system
shells, for making expert systems. Figure lA is a block diagram
of an expert system shell 110 for making rule-based experts. As
may be seen from that figure, the expert system shell has the
components of the rule-based expert of figure 1 and an additional
component, rule processor (RP) 111. Rule processor 111 is used to
produce rules 109 for storage in a RS 107 specific to the expert
system currently being built. RIE 105 is used in expert system
shell 110 to test the expert system being built as it is
constructed. When all of the rules 109 for the expert system
--4--
~2~
being developed have been written and the system has been fully
tested, users of the ne~J expert system are given access to ~IE 105
and to RS 107 for the new expert.
The usefulness of expert system shells 110 depends to a
considerable extent on the sophistication of RP 111. In some
systems, RP 111 requires rules 109 input in special forms. Thus,
these systems generally require a knowledge engineer and cannot be
used by the expert himself. In other systems, RP 111 constructs
its rules from examples provided by the expert, and thus does not
require a knowledge engineer.
Although rule-based expert systems 101 are becoming steadily more
powerful, more usable, and less expensive, their reliance on rules
has certain inherent disadvantages. First, most experts do not
think about their areas of expertise in terms of a set of rulés.
Because they do not, a knowledge engineer or a system which
constructs rules from examples must mediate between the expert and
expert system shell 110. In the first case, the development of
expert systems is more expensive than it would be otherwise, and
in the second case, the complexity of expert system shell 110 is
greater than it would be otherwise and the expert is still not
completely insulated from the rules, since he must still check the
rules produced by shell 110.
33~r3~J
Second, since RS 107 is a collection of rules 109 created
independently of each other, there is no guarantee that the
collection of rules 109 is complete or contains no contradictory
rules. If a set of rules 109 is incomplete, expert system 101 may
reach no result or a wrong result, if the set of rules 109
includes contradictory rules 109, expert system 101 may a~ain
reach no result or reach a result which depends on RIE lO5's
internal algorithm for resolving contradictions rather than the
rules.
The ability to operate with incomplete sets of rules 103 or ~lith
contradictory rules 109 is part of the power of rule-based systems
101 and is required in situations in which the expert is unable to
reduce his area of expertise to clear principles. However, expert
systems are employed in many situations where the expert can
reduce his expertise to clear principles, and in these situations,
the ability to deal with incomplete sets of rules 109 and
contradictory rules 109 makes detection of mistakes more
difficult, and when a mistake is made, makes the behavior of
system 101 dependent upon RIE 105's internal algorithms rather
than on the rules.
.
! Third, rule-based expert systems 101 are difficult to modify. The
behavior of a rule-based expert system depends on the totality of
its rules, and it is often difficult to determine what rules must
--6--
~L~7~33~3
be changed if the system's behavior is to be al-tered because it
has bugs or because the expert has changed his mi nd about how he
would deal with a given case.
Fourth, the power and complexity of rule-based expert systems 101
are not required for many situations in which expert systems are
useful. Generally speaking, that power and complexity is required
where the expert cannot fully define his expertise. Ho~lever,
there are many situations where the layman requires the guidance
of an expert but the expert can completely and easily define his
expertise. In such situations, useful expert systems and expert
system shells need not have the complexity inherent in rule-based
expert systems and expert system shells.
One such situation is that presented by complex forms such as tax
forms. In most cases, little judgment is required to fill out the
form, but the form is nevertheless so involved that many people
require the help of a tax preparer. Spread sheets have made it
mechanically easier to deal with the data involved in filling out
a tax form and permit a user to see how a change in one value
affects others, but they have not provided the kind of reasoned
guidance for the user which is possible in an expert system. What
is needed, therefore, and what is provided by the invention
described herein, is an expert system shell which is easier to use
than those typical of rule-based systems and expert systems which
.
~L~7 ~33~q~
are substantially simpler than rule-based expert systems, but
which provide reasoned expert advice in situations which do not
require the full power of rule-based systems.
Summary of the Invention
The present invention relates to digital data processing systems
and more specifically to expert systems and expert system shells
employed in digital data processing systems. Expert systems of
the present invention employ definitions instead of rules. An
expert defines his area of expertise as a set of terms with a
corresponding set of hierarchical definitions. The definition for
à term may include terms defined at a lower level of the
hierarchy, literal terms, constant values, and values obtained
from sources external to the expert system. The decisions which
the expert would reach regarding a term in the hierarchy are
expressed as values of the term. The defined terms make up the
knowledge base of the expert system of the present invention. The
inference engine determines what decision the expert would have
made regarding a given term by computing the term's value from its
definition. If the definition involves other terms~ the values of
those terms are computed from their definitions, and if the
' definition or the definitions of other terms involve values
obtained from external sources, those values are obtained as
i
i -8-
~27~33~
needed to compute the value of the given term. If the external
source is a terminal, the expert system asks the persc,n at the
terminal for a value and the person inputting the value may ask
why the value is needed. The inference engine determines from the
definition why the value is necessary and provides that
information to the person inputting the value.
Once the inference engine has determined what decision the expert
would have made, the user of the expert system may ask the expert
system how it came to its conclusion. The inference engine again
goes to the hierarchical definition of the term and works through
the definition to show how it arrived at its result.
Additionally, the user can ask the expert system to assume another
vàlue for one of the terms used in the definition of the term the
user originally asked about. The inference engine then
substitutes the new value for the old and determines anew what the
result is for the term the user originally asked about, thus
showing how the change in value of one of the subordinate terms
affected the value of the term originally asked about.
The techniques used in the expert system of the present invention
to determine why the expert system requested a given input, how
the expert system arrived at a conclusion, and to change the value
of a term and see the result are all applicable not only in the
~%7~
expert systems of the present lnvention, but also in other systems
employing hierarchicall~-defined sets of terrns.
Expert systems of the present invention are created using an
expert shell of the present invention. The expert shell contains
the inference engine and the definitional knowledge base just
described and additionally contains a definition processor for
creating the definitions in the definitional knowledge base. To
use the definitional knowledge base, the user of the shell
(generally the expert) inputs a define command followed by the
term he wishes to define. The definition processor then requests
a description of the term, and the expert describes the term. The
description indicates how the term's value is to be derived and
may contain other terms, constants, or a description of where an
external value is to be obtained. If the description contains no
further undefined terms, the definition processor creates the
term's definition from the description. If the description
contains further undefined terms, the definition processor
requests a description of each of the undefined terms and
processes the description as just described. The iterations
continue until no undefined terms remain. As a term is defined,
the term and its definition become part of the definitional
knowledge base. The definition processor further permits the
expert to redefine terms, remove a term and its definition from
the knowledge base, and see the definition for a term and for the
--10--
terms which enter into its definition. As may be seen from the
above description, the expert system shell of the present
invention permits an expert to provide information in the form of
definitions instead of rules, ensures that a set of definitions is
consistent, and makes it easy to determine what terms a given term
depends on.
The technique employed in the definition processor of the present
invention to create hierarchical definitions may be employed not
only in expert system shells of the present invention, but also in
any system which creates hierarchical systems of definitions.
It is thus an object of the invention to provide improved expert
systems and expert system shells.
It is another object of the invention to provide an expert system
having a definitional knowledge base and an inference engine which
employs the definitional knowledge base to reach conclusions.
It is a further object of the invention to provide an expert
system shell for producing expert systems having a definitional
knowledge base.
--1 1--
. .
~2~
70840-7
It is an additional ohject of the inventi.on to provide
apparatus and methods for creatiny sets of terms h~ving
hierarchical definitions.
It is yet another object of the inventior to provide
appara~us and methods for indicating to a user of a knowledge base
having hierarchical definitions how a conclusion was reached, why
certain information was requested, and how the conclusion wlll
change if one of the terms receives a di.fferent value.
It is a still further object of the invention to provide
apparatus and methods which guarantee that an expert system
knowledge base is complete and non-contradictory.
According to a broad aspect of the invention there is
provided a digital computer system operable as an expert system,
said computer system comprising: storage means to store a
knowledge base including hieràrchically defined terms and their
definitions, the corresponding dsfinition of each term defining
its respective term using the value of one or more terms, each of
whose definitions is at a lower level of the hierarchy, and/or
using one or more external values external to the knowledge base;
and processing means for receiving commands from a user of the
system, for producing inference commands in response to said user
commands, for interrogating said storage means in response to said
commands to obtain the definition of a given term, and for
computing the value of said glven term from its corresponding
definition by obtalning the value of any term and any e~ternal
value in the corresponding definition, said system employiny said
,
33,90
7084~-76
computed value to produ~e an expert response to said user.
Ac~ording to anokher broad aspect of the invention there
is provided a digital computer system operable to define a given
term for an expert system by creating a hierarchlcal definition of
the given term for storage with the term in a kno~,lledge base
employed in the expert system ~omprising: storage means for
storing the knowledge base; interactive input/outpu~ means for
providing output information to and receiving input informa-tion
from a user o~ the digital computer system who is the source of
the definition; and processing means coupled to the storage means
and to the interactive input/output means for receiviny the input
infoxmation and providing the output information and re~eiving
previously-defined terms and definitions and providing the given
term and the definition created therefor and for responding to the
given term received in the input information by providing output
information requesting a description of the given term from the
user, receiving input information containing the description from
the userr analyzing the description to determine whether there is
any term therein which does not have a definition in the knowledge
base, and if there is not, ending the analysis, forming the
definition for the given term from the description and the
definitions of the previously-defined terms used therein, and
storing the given term and the definition in the knowledge base,
and if there is, providing output information requesting a
description of the undefined term from the user and proceeding as
for the given term, and continuing thus until no undefined term
-13-
7~ 75
remains in the description of the given term or in any
descriptions requested in the course of defininy the given term.
Other objects and advantages of the present invention
will be understood by those of ordinary skill in the art after
referring to the detailed description of a first prototype
embodiment contained herein, to appendices containiny the LISP
code for the first prototype embodiment and a second prototype
embodiment, and to the drawings.
For ease of reference to figures, the reference numbers
used in the description of the preferred embodiment have three
digits. The two least-significant digits are reference numbers
within a drawing; the most significant digit is the drawiny
number. For example, the reference number 901 refers to an item
shown in figure 9.
~ESCRIPTION OF A P~EFE~R~D EMBODIMENT
The following description of a preferred embodiment
first presents a conceptual overview of the expert system and
expert system shell of the present invention and then presents a
detailed description of a first prototype implementation of the
invention. Certain improvements made in a second prototype
implementation are discussed. A copy of the program for the first
prototype is included in Appendix A and a copy of the program for
the second prototype is included in Appendix B.
-14-
.~ - . , , ., . ~
1. Conceptual Overview of the Expert System Shell and Ex~
System of the Present Invention: Figure 2
Figure 2 is a conceptual block diagram of expert system shell 201
and expert system 202 of the present invention. Expert system
shell 201 has four components: command processor (CP) 203,
definition processor (DP) 207, term store (TS) 215, and term
inference engine (TIE) 219. Expert systems 202 produced using
expert system shell 201 have all of these components but DP 207.
As will be explained in more detail below, CP 203 receives
commands from users of shell 201 and system 202 and provides them
to the other components; DP 207 processes definition.s; TS 215
stores defined terms and their definitions; TIE 219 uses a term's
definition from TS 215 to evaluate the term and perform other"
operations on it.
CP 203 converts commands from users of shell 201 and expert
systems 202 into definition processor commands (DPCs) 204 and
inference engine commands (IECs) 217. In the prototype, DPCs 204
permit the user of shell 201 to define a term, redefine a term,
undefine a defined term, view a term's definition, save a set of
definitions, and restore a set of definitions. IECs 217 permit
the user of shell 201 or an expert system 202 produced by shell
.
~.~;7~
201 ~o determine the current value of a term, find out ho~/l expert
system 202 reached that value, have expert system 202 ~ssume a
different value for a term and see how that affects the value of
other terms, reset the value of any one or all of the terms, and
when the determination of the current value of a term requires a
value to be supplied from outside the definition, to ask expert
system 202 why the value is required.
Definition processor 207 defines TERMs 206. When a TERM 206 has
been fully defined, TS 215 contains a defined term (DTERM) 211
corresponding to TERM 206 and a definition (DEF) 213 for DTERM
211. TERM 206 may be received either in a DPC 204 or from a
description (DESC) 205 DP 207 requested from the user of expert
system shell 201 in response to a TERM 206. DP 207 first
determines whether there is already a DTERM 211 corresponding to
TERM 206, i.e., whether TERM 206 is already defined. If it is, DP
207 retrieves DTERM 211 corresponding to TERM 206 from TS 215 and
prepares it for use in the definition DP 207 is currently
constructing. If it is not defined, DP 207 outputs a description
request (DESC REQ) to the user of shell 201. The user provides a
description (DESC) 205 of TERM 206 to DP 201, which then makes a
DEF 213 for TERM 206 using the information in DESC 205. As will
be described in more detail below, DESC 205 is written in a
definition language which permits the user to specify other TERMs
206, constant values, and that a value is to be obtained from
i
-16-
I ,,,, ,_,, , . , , , ,, ,_
~ ~7~
outside expert system 206 for which the definition is beiny
provided. The definition further specifies operations ~hich may
be performed on the values represented by TERM 206, constants, and
external values in the definition. If DESC 205 contains TERMs
206, DP 207 treats those TERMs 206 in the manner just described.
If there is a DTERM 211 corresponding to TERM 206, DTERM 211 is
used in DEF 213 being constructed; if there is not, DP 207
requests a DESC 205 defining TERM 206 and processes it as just
described. The repetitive operation of DP 207 is shown in Figure
2 by arrow 208 showing how UDESC 210, which contains at least one
TERM 206, is again processed by DP 207. Processing continues in
this fashion until the original DESC 205 and all of the TERMs 206
in any DESCs 205 produced for TERMs 206 required to define the
TERMs 206 in the original DESC 205 have been defined; i.e, have
corresponding DTERMs 211 and DEFs 213 in TS 215.
The DTERMs 211 and DEFs 213 resulting from operation of DP 207 are
placed in TS 215. DTERM 211 may be located in TS 215 by name.
DEF 213 corresponding to DTERM 211 is associated with DTERM 211,
and may thus be used once DTERM 211 is located. Included in DEF
213 is a modified version of DESC 205 from which DEF 213 is
derived.
The remaining operations specified by DPCs 204 are carried out in
DP 207 and TS 215 as follows: when a TERM 206 ~s undef~ned, DP
-17-
207 removes the corresponding DTERM 211 and DEF 213 froM TS 215;
~hen a TERM 206 is redefined, DP 207 removes DEF 213 corresponding
to TERM 206 and requests a ne~l DESC 205 for TERM 206 That DESC
205 is then processed in the manner just described. ~Ihen a DPC
requests that a TERM 206's definition be displayed, DP 207
displays the DESC 205 which was incorporated into the DEF 213 for
DTERM 211 corresponding to TERM 206. Finally, the saYe operation
saves the contents of a given TS 215 to a file for later use and
the restore operation restores the contents of the file to TS 215.
Term inference engine (TIE) 219 performs operations using the
DTERMs 211 and DEFs 213 in TS 215. The primary operation is the
what operation, which determines the value of a DTERM 211 from its
dèfinition and external values provided by the user of expert
systeln 202 or shell 201. TIE 219 performs the what operation in
response to an IEC 217 specifying the operation and a TERM 206
from CP 203. TIE 219 uses DTERM 211 corresponding to TERM 206 to
locate DTERM 211's DEF 213 in TS 215. It then performs the
operations specified in DEF 213 using the DTERMs 211, constants,
and external values specified in the definition and returns the
result, TRES 227, to the user of system 202 or shell 201.
The constants in DEF 213 are available for immediate use in
calculating the value of DTERM 211; in the case of the external
values, DTERM 211 contains a descriptlon of how the external value
-18-
~ 2~
is to be obtained. TIE 219 uses the description to make a request
for an externa1 value (EXVAL REQ) to the source of the external
value (EXVAL) 225 and receives EXVAL 225 from the source. In the
simplest case, the source is the terminal being used b~ the user
of system 202 or shell 201 and the information is obtained by
putting a question on the user's terminal screen and receiving his
input; in more complex cases, the source may be a fiie or a data
base.
In the case of a further DTERM 211 in DEF 213 for the DTERM 211
being evaluated. TIE 219 obtains the further DTERM 211's DEF 213
and computes that DTERM 211 's value from its DEF 213, evaluating
as it does so any DTERMs 211 in that DEF 213, and continuing thus
until all DTERMs 211 from which the DTERM 211 whose value is being
sought in the what operation is dependent have been evaluated.
The constants, external values, and DTERMs 211 specified in each
DEF 213 are dealt with in the manner just described. When all
DEFs 213 have been evaluated, the value of DTERM 211 whose value
is being sought is computed and returned as TRES 227.
In a preferred embodiment, EXVALs 225 which are obtained during
evaluation of a given DEF 213 become part of that DEF 213's
definition; thus, if the what operation is performed a second time
on DTERM 211, TIE 219 will not produce any EXVAL REQs, but will
simply use the stored EXVALs 225 to recompute the value of DTERM
--19-
:
~271~
211. A preferred embodime~t has two IECs 217 for rnodifying the
stored EXVALs 225. rhe first, reset, simply removes all of the
stored EXVALs 225 from the DEFs 213 for the DTERMs 211 specified
in the reset command. Thus, when what is again performed, a new
EXVAL 225 will be obtained as previously explained. The second,
assume, permits a new EXVAL 225 to be provided to DEF 213 for TERM
206 specified in the assume command. ~hen what is again performed
in this case, the specified EXVAL 225 is used to derive the value
of DTERM 211 for which the what operation is being performed.
If a user of shell 201 or system 202 wants to know why TIE 219 is
asking for a given EXVAL 225, he can respond to an EXVAL REQ with
the command for the why operation. In response to that command,
TIE 219 outputs DESC 205 from DEF 213 for the DTERM 211 whose
value was being computed when the EXVAL 225 was required, and the
user can determine from DESC 205 why the given EXVAL 225 is
important. The user can further use why to ask why any of the
DTERMs 211 whose values are required to obtain the value of the
DTERM 211 whose evaluation produced the EXVAL REQ are required,
and TIE 219 provides the DESCs 205 for those DTERMs 211.
-20-
3. T_e Hierarchy of Definit10ns. Fi~ 3
In defining any term, DP 207 produces a hlerarchy of DEFs 213. If
DEF 213 for the term being defined itself contains no terms, the
hierarchy has only one level. If DEF 213 for the term contains a
further term, that term must be deflned before the first term can
be defined, and the first term is the top term in a hierarchy with
two levels. If any of the DEFs 213 at the second level contains a
further term, that term must be defined, and the hierarchy has
three levels. The hierarchy thus continues to deepen until none
of the DEFs 213 for the terms upon which other terms depend
contains a further term, but is instead defined solely in terms of
operations on constants or external values. As is clear from the
above discussion, a DEF 213 is always the top DEF 213 in the
hierarchy of DEFs 213 required to define the DTERM 211 which DEF
213 defines, but may at the same time be at a lower level in the
hierarchy o~ DEFs 213 required to deflne some other DTERM 211.
Figure 3 is a conceptual illustration of one such hierarchy of
DEFs 213. Hierarchy 305 contains DEFs 213(A) through 213(E)
corresponding to DTERMS Zll(A) through 211(E) belonging to set of
, DTERMS 301. The topmost definition in hierarchy 305 is DEF
i 213(A), corresponding to DTERM 211(A). The notat~on OP(B,C) in
DEF 213(A) indicates that DEF 213(A) speci~ies that the value of
DTERM 211(A) is obtained by performing an operation on the values
-21-
,J . .
of DTERMs 211 (B) and (C). Similarly, DEF Z13 B specifies that
the value o~ DTERM 211(B) is obtained by performiny an operation
on the values of DTERMs 211(D) and (E). Consequently, hierarchy
305 for DEF 213(A) has three levels: level 1 307, containing only
DEF 213(A), level 2 309, containing DEF 213(B) and DEF 213(C), and
level 3 311, containing DEFs 213(D) and 213(E). DEFs 213(C),
213(D), and 213(E) do not define DTERMs 211 C, D, and E ~Jith other
DTERMs 211, and cannot give rise to lo~er levels. Such DEFs 213
are termed terminal definitions 312.
In constructing hierarchy 305, DP 207 begins with TERM 206(A)
corresponding to DTERM 211(A), which it receives from a DESC 205
from which a DEF 213 at a higher level is being constructed or
from a define or redefine DPC 204. DP 207 then requests a DESC
205 for DTERM 211~A). DESC 205 defines DTERM 211(A) in terms of
an operation on two TERMS 206, B and C. If DEF 213(8) and DEF
213(C) already exist, DP 207 can make DEF 213(A) and need go no
further. If either DEF 213(B) or DEF 213(C) does not exist, DP
207 must produce those DEFs 213 before it can make DEF 213A. DP
207 thus asks for a DESC 205 for TERM 206(B) and for TERM 206(C).
In the case of TERM 206(C), DESC 205 defines TERM 206(C) only in
terms of EXVAL(C) 225, and DEF 213(C) can be constructed
immediately. In the case of TERM 206(B), DESC 205 defines TERM
206(B) in terms of two additional TERMs 206, D and E;
consequently, DP 207 must descend another level an~ produce DEFs
-22-
~7~33~
213 for those TERMs 206. Ayain, DP 207 requests DESCs 206 For
those terms. In both cases, the TERMs 206 are defined in terms of
EXVALs 225, and consequently, both DEFs 213 can be constructed.
DEFs 213 for all TERMs Z06 involved in the definition oF TERM 206
A have now been constructed, DTERMs 211(B) through (E)
corresponding to TERMs 206 (B) through (E) exist, DEF 213(A) can
be constructed, and TERM 206(A) now has a DTERM 211(A)
corresponding to it.
Because hierarchy 305 is constructed repetitively beginning with
the top DEF 213 in hierarchy 305 and only TERMs 206 which have no
corresponding DTERM 211 are defined, no DTERM 211 can have two
DEFs 213 and no DEF 213 in hierarchy 305 can refer to a DEF 213
which is above it in hierarchy 305. Consequently, the DEFs 213 in
hierarchy 305 are necessarily complete and consistent with regard
to DEF 213(A) in hierarchy 305 or to the top DEF 213 in any
hierarchy incorporating DEF 213(A).
4. The Description Language for Descriptions 205
As previously indicated, DP 207 makes DEFs 213 from descriptions
j (DESCs~ 205. In the prototype, DESCs 205 are made using a
! description language. The descrlption language includes
I .
!
-23-
predefined terms specifying operations on terms, a case statement,
and operations for obtaining external values.
The operations include Boolean operations, arithmetic operations,
and text concatenation. The case statement is a list of boolean
expression-value pairs of the form:
(boolean_exp_l) value_l . . . (boolean_exp_n) value_n
(OTHER~ISE) otherwise_value
When DEF 213 containing a case statement is evaluated, the boolean
experessions 1 through n are evaluated in order until one of them
is true. The value corresponding to the true boolean expression
becomes the value of DTERM 211 defined by DEF 213. If none of the
boolean expressions is true, the value corresponding to OTHER~ISE
becomes the value of DTERM 211.
The description language of the prototype permits specification of
two classes of operations for obtaining external values. The
first class, the ASK operations, obtains values from the terminal
of the user of expert system 202. The first class, the ASK
operations, are used to obtain external values from the terminal.
The second class, the RECO~D operations, are used to obtain
external values from a data base system. In both cases, the
external values may be numbers, text strings, or boolean values,
-24-
ll
,
or they may select one of a set of alternative literal terms,
i.e., terms which represent nothing but themselves~
ASK to obtain a numeric value has the form:
ASK NUMBER "prompt string"
When the DEF 213 containing such an ASK operation is evaluated, DP
207 outputs the prompt string to the terminal and waits for a
number input from the terminal. That number is then used ln the
evaluation of DEF 213. The prompt string may itself contain a
previously-defined term, and consequently, a user's response may
be made to depend on the value of a previously-evaluated term.
the ASK operations for boolean and text string values are
specified in the same fashion as the ASK operation for numeric
values, except that NUMBER in the above operation is replaced by
YES-NO when a boolean value is sought and TEXT when a text string
is sought.
ASK which selects one of a number of literal terms has the form:
ASK CHOICE "prompt_string"
(literal_term_l . . literal_term_n)
,
-Z5-
When the DEF 213 containing ASK CHOICE is evaluated. the prompt
string is output and the user is asked to select one of the
literal terms. That literal term may then be used in DEF 213 to
compute the value of DTERM 211 defined by DEF 213.
The RECORD operations are generally analogous to the ASK
operations, except that the RECORD operation specifies how the
external value is to be located in the data base and the data base
supplies the value at the specified location.
Operation of Shell 201 and System 202: Figure 4
The operation of shell 201 will be explained in detail using a
hierarchy of definitions from which it may be determined whether
someone has been defrauded. The legal definition of fraud
requires that one party knowingly made a misrepresentation to the
other party and that the other party relied on the
misrepresentation to his detriment. Figure 4 shows a hierarchy of
DTERMs 211 which corresponds to that legal definition.
Creation of the hierarchy of Figure 4 begins when CP 203 receives
the DEFINE FRAUD command. CP 203 then passes TERM 206 FRAUD to DP
-26-
, . . .
.
207, which requests a DESC 206 from the expert making the
definition. The expert provides the DESC 206
KNO~ING_MISREPRESENTATION AND DETRIMENTAL_RELIANCE
This DESC 206 contains two further TERMs 206 and the boolean AND
operator. Thus, the value of FRAUD is to be computed by obtaining
the values of the DTERMs 211 corresponding to the TERMs 206 and
performing an AND operation on them.
Since the further TERMS 206 are undefined, DP 207 asks for their
definitions. The expert provides the DESC 205
MISREPRESENTATION AND DEFENDANT_KNEW_MISREPRESENTATION
for KNOWING_MISREPRESENTATION and the DESC 205 RELIANCE_BY
PLAINTIFF AND LOSS_BY_PLAINTIFF for DETRIMENTAL_RELIANCE. Again,
these further TERMs 206 are undefined, so DP 207 asks for their
definitions and the expert provides the definitions shown in
Figure 4. While DP 207 may ask for definitions in any order, a
preferred embodiment defines all TERMs 206 necessary to define a
given undefined TERM 206 before going on to the next undefined
TERM 206.
-27-
~%~
In the above example, the DESCs 205 for ~ISREP~ESENTATION,
DEFENDANT_KNEW MISREPRESENTATION, RELIANCE_BY PLAINTIFF, and LOSS
BY_PLAINTIFF all contain only the system-defined DTERMs 211 used
in the ASK YES-N0 operation, so DP 207 is now a~le to produce DEfs
213 for all of the terrns in the hierarchy. The values of all of
the DTERMs 211 in the hierarchy depend ultimately on the values
which the ASK YES-NO operation requests from the user of expert
system 202 which employs the FRAUD definition, and thus depends
ultimately on what the plaintiff says about what happened to him.
Use of the FRAUD definition hierarchy in expert system 202 begins
with the WHAT FRAUD command which the user o~ expert system 202
inputs to CP 203. CP 203 generates a corresponding ~HAT FRAUD IEC
217 for TIE 219. TIE 219 then determines the value of FRAUD by
evaluating its DEF 213. In order to do that, it must evaluate the
DEFs 213 for other DTERMs 211 in the hierarchy, beginning ~lith
KNO~ING_MISREPRESENTATION. The evaluation of KN0WING
MISREPRESENTATION requires the evaluation of MISREPRESENTATION.
The evaluation o~ that DTERM 211 results in the execution of the
WHAT YES-NO operation in its DEF 213, and TIE 219 outputs the
prompt "Did he tell you anything that ~asn't true?" If the user
answers "no", MISREPRESENTATION is false, KNO~ING
~lISREPRESENTATION is false, and FRAUD is false, so TIE 219 returns
TRES 227 to the user indicatin~ that there is no fraud. If the
user answers "yes", TIE 219 evaluates DEFENDANT_KNEW
-2~-
~L;~ 9 ~;3
MISREPRESENTATION, which again results in a question to the user
Depending on the answer to the question, evaluation continues or
is finished. TIE 219 proceeds in the above ~ashion until it has
computed a value for FRAUD.
As previously mentioned, a user of expert system 202 may use the
HOW user command to determine how expert system 202 arrived at its
value for FRAUD. Assuming that the user answered "no" when asked
"Did he tell you anything that wasn't true" (in the definition of
MISREPRESENTATION), TIE 219 in the prototype will respond to HOW
FRAUD by outputting
FRAUD is defined to be (KNOWING_MISREPRESENTATION AND
DETRIMENTAL_RELIANCE) where (KNOWING
MISREPRESENTATION) equals FALSE.
As previously mentioned, DP 207 places DESC 205 for a DTERM 211 in
the DTERM 211's DEF 213, and TIE 219 alsc. stores the external
values it receives in evaluating a DTERM 211's DEF 213 in DEF
213. In performing the HO~I operation, TIE 219 first fetches and
outputs DESC 205 from DEF 213 for the DTERM 211 being inquired
about and then evaluates the DTERMS 211 in DEF 213 as required to
obtain the value of DTERM 211 being inquired about. The DTERMs
211 are then output together with their values. If a user wishes
to inquire further, he need only repeat the HOW operatlon on the
-29-
"63~3
other DTERMS 211 specified in the DESC 205 output in the HOW
operation.
As also previously mentioned, a user may respond to a request for
an external value with the WHY command instead of a value. If a
user responds in the case of the FRAUD example with WHY ~hen TIE
219 asks "Did he tell you anything that wasn't true"; TIE 219
responds with:
MISREPRESENTATION is needed to determine the value of
KNOWING_MISREPRESENTATION, which is defined to be
MISREPRESENTATION AND SUBJECT_KNEW MISREPRESENTATION
a`nd repeats the question.
Again, the information used to respond to the WHY command comes
from the DESCs 205 stored in the DEFs 213 in the hierarchy used to
define FRAUD. If the user wants to know more at this point, he
can apply HGW to the DTERMs 211 mentioned in the response to the
NHY command.
-30-
~7~
6. The LISP Environment of the Prototype Embodiments: Fi~_5
Having thus provided a conceptual overview of the structure and
operation of shell 201 and system 202, the discussion proceeds to
a detailed description of the implementation of the first
prototype.
Both the first and second prototype embodiments are implemented in
the LISP programming language and execute in the LISP
environment. The LISP programming language and environment are
frequently used to implement prototype and production expert
systems and are well-known in the expert system art. The specific
LISP dialect used for the prototype embodiments is COMMON LISP,
which is described in Guy L. Steele, Jr., COMMON LISP, the
Lan~uage, Digital Press, 1984. Only so much of the LISP
environment and language are described here as is required for a
clear understanding of the mode of operation of the prototype
embodiments.
Beglnning with the LISP language, the language differs from
languages such as FORTRAN or PASCAL in that is is chiefly
concerned with the processing of symbols, as opposed to the
processing of data which i5 represented in a program by symbols.
The fundamental components of a LISP program are atoms. An atom
may be a symbol, such as ABC, or a constant. The components are
organized into programs b~ means of lists which may have no
members or members including atoms and other lists. A list is
made by enclosing its members in parentheses: (A~C) is a lisr with
one member, the symbol ABC. Functions appear in LISP as lists in
which the first symbol in the list represents the function and the
other atoms represent the function's arguments. For example, the
add function is represented in LISP by the symbol +, and the list
(+ 2 3) specifies that the + operation is to be applied to the
atoms 2 and 3. Any atom or list which has a value when evaluated
by a LISP interpreter is called a form. 5 and (~ 2 3) are forms,
and if the symbol ABC has a value, it is a form.
Functions are defined in LISP by means of the DEFUN function, in
which the remaining items of the list define the function's name,
its arguments, and the value it returns. For example, (defun five
() 5) defines a functlon which takes no arguments and always
returns the value 5.
Among the things LISP programs can do with symbols and lists is
make them. Since a function definition is only a kind of list, a
LISP program can provide a symbol to DEFUN as the name of the new
symbol being created by DEFUN and then use the symbol to execute
the newly-created function. Symbols may either represent
themselves as symbols or values. ~hen a symbol is representing
itself as a symbol in a LISP list, lt is preceded by a ' mark. In
9~
the case of symbols representing functions, the value of the
symbol is the function. However, if the function is placed in a
list with its arguments and the list evaluated, the result is the
value of that execution of the function. Thus, 'five represen'cs
the symbol five, ~Jhile five represents the function defined by
DEFUN above, and ~five) represents the value of an execution of
the function five, i.e., 5.
LISP programs are written and executed in a LISP environment.
That used for the prototype embodiments was made by Gold Hill
Computers, Inc. for the Professional Computer manufactured by Wang
Laboratories, Inc. Figure 5 is a conceptual block diagram of a
typical LISP environment 501. Environment 501 has two main
components, LISP interpreter 503, which evaluates LISP forms, and
LISP symbol space 505, which stores LISP symbols (S~M 501) and
their definitions (SYMDEF 509). DEFUN and certain other LISP -
functions create and define new LISP symbols or redefine
previously-existing LISP symbols when they are evaluated;
consequently, LISP interpreter 503 may be seen as not only an
evaluator of symbols, but also as a creator, definer, and
redefiner of symbols.
Operation of LISP environment SOl is as follows: when a user of
LISP environment 501 types a list containin~ a form such as
(five), LISP interpreter 503 evaluates the form by locating the
-33-
_ .. . ..
symbol five in symbol space 505, determining what its S~MDEF 509
is, and then interpreting SYMDEF 509 to compute the value of
five. In this case, SYMDEf 509 is the code for the function five
which was created by evaluation of the DEFUN expression, and its
interpretation produces the value ~, which the interpreter returns
to the user as the value of (five).
Because LISP interpreter 503 is able to create SYMs 507 and their
corresponding SYMDEFs 509, store them in symbol space 505, and
locate them in symbol space 505, LISP environment 501
automatically performs operations which are difficult to implement
in other languages and which are essential for the operation of
expert system shells and expert systems. For that reason~ LISP
environments 501 have been the preferred environments for the
creation of prototype expert systems and expert system shells. As
will be seen in the ensuing discussion, the prototypes of the
present invention take full advantage of the symbol creation,
definition, and location operations.
7 Overview of the First Prototype Embodiment: Fi~. 6
In the first prototype embodiment, the components of expert shell
201 and expert system 202 are implemented by means of L~SP
-34
~ 7B~
functions. Code for these ~unctions is contained in Appendi~ 1
Figure 6 gives an overview of that code and relates the LISP
functions of the first prototype embodirnent to the components of
Figure 2 and the inputs and outputs of those components. Thus,
the LISP functions making up CP 2Q3 are contained in the dashed
box with that label, the functions making Up DP 207 are in the
dashed box with that label, and those making up TIE 219 are in the
dashed box with that label. TS 215 is embodied in the first
prototype by LISP symbol space 505, which stores LISP symbols and
their definitions. The components of the first prototype
embodiment should also be understood to include LISP interpreter
503, which executes the LISP functions making up the components,
places the SYMs 507 and SYMDEFs 509 created by the components in
symbol space 50S, and manipulates the SYMs 507 and their SYMDEFs
509.
.,
Beginning with EXPERT 603, EXPERT 603 performs the functions of CP
203 in the prototype. Code for EXPERT 603 may be found on page 14
of Appendix 1. As can be seen from that code, EXPERT 603 receives
an input string, puts parentheses around it to produce a LISP form
termed CFORM 605 in Figure 6, and performs the EVAL operation on
it. ~hen LISP interpreter 503 evaluates the form, it treats the
first symbol in the form as a LISP function name and the remaining
items in the form as a list of arguments for the named function.
;
~35-
Expected input strings for EXPERT 603 are the commands for DP 207,
namely DEFINE, REDEFINE, UNDEFINE, and the commands for TIE 219,
namely WHAT, HOW, ASSUME, RESET, DEFINITION, SAVE, ~ , and
RESTORE. DEFINE, REDEFINE, and UNDEFINE correspond to the DPCs
204 of Figure 2 and the remaining strings correspond to the IECs
217 of that figure. In the first prototype embodiment, there is
no error detection in EXPERT 603; however, in a commercial
embodiment, EXPERT 603 would include code for detecting and
responding to improper input.
As may be seen from Figure 6, DP 207 is embodied in the first
prototype by the LISP functions DEFINE, on page 1 of Appendix 1,
REDEFINE, and UNDEFINE, both on page 3. When EXPERT 603 receives
the DEFINE command with a TERM 206 such as FRAUD, and presents it
to the LISP interpreter as (DEFINE FRAUD), LISP interpreter 503
invokes the function DEFINE with the argument FRAUD. DEFINE
requests a DESC 205 from the user and uses DESC 205 to produce the
DEF 213 for FRAUD. As will be explained in greater detail below,
the result of the invocation is a LISP function named FRAUD for
which the DEFUN would look like the following:
-36
33'~3
(defun FRAUD ()
(prog2
(push 'FRAUD arg-stack)
(AND (KNOWING_MISREPRESENTATION)
(DETRIMENTAL_RELIANCE))
(pop Arg-stack)
) ) ) )
In the course of defining FRAUD, KNOWING_MISREPRESENTATION and
DETRIMENTAL_RELIANCE and the DTERMs 211 required for their
definitions are all defined as LISP symbols representing LISP
functions. AND is a predefined LISP function which performs the
AND operation on its arguments. The value returned by the
function FRAUD is the result of the AND operation.
The DTERMs 211 which have been defined as LISP symbols
representing LISP functions are termed TSYMs 615 in the following
discussion, and their definitions, which are the prototype's
implementation of DEFs 213, are termed TDEFs 617. As the LISP
interpreter produces TSYMs 615 and TDEFs 617 in response to the
DEFINE function, it places them in symbol space 50S. fDEF 617 in
the first prototype is shown in Figure 7. As shol"n there, each
TDEF 617 contains TFUNC 701, the LISP function represented by TSYM
615, TDESC 705, a modified copy o~ DESC 205 which was the source
--37-
_. ._ ..
of TSYM 615 s definition and TEXVAL 703, which contains the last
EXVAL 703 specified by a user of expert 202 for TSYM 615.
The remaining functions in DP 207 are invoked in the same fashion
as DEFINE from EXPERT 603. REDEFINE first employs LISP operations
which remove TFUNC 701 and TDESC 705 from TDEF 617 for TSYM 615
being redefined and then invokes DEFINE to make new values for
TFUNC 701 and TDESC 705 in TDEF 617. UNDEFINE simply removes
TFUNC 701 and TDESC 705 without making a new definition of TSYM
615.
Continuing with the implementation of TIE 219 in first prototype
embodiment 601 when LISP interpreter 503 receives a CFORM 605
from EXPERT 603 which represents an IEC 217 it executes the
function in TIE 219 specified in CFORM 605. As the functions in
TIE 219 are executed they provide forms (TFORMS 639~ made from
TSYMS 615 to Interpreter 505 which evaluates them and returns the
results (TFORM RESULT) to the function being executed.
The functions in TIE 219 employ data structures in TIE 219
ARG-STACK 635 and TERMS-STACK 613 defined on page 1 of appendix
1 and SYM-BOUND-LIST defined on page lZ. Beginning with
ARG-STACK 635 ARG-STACK 635 is used to store a TSYM 615 while the
values of the TSYMs 615 with which it is defined are computed. As
may be seen in the code for the procedure FRAUD above the symbol
,~L2~
FRAUD is pushed -to ARC,-STACK before the AND operation ~/hich
defines FRAUD is executed and is popped from ARG-STACK
thereafter. TERMS-STACK 613 is a stack of TSYMs 615. The stack
is ordered by when a TSYM 615's TDEF 617 was created, wi-th the
first TSYM 615 to have its TDEF 617 created at the bottom and the
last at the top. As ~lill be explained in detail below, the last
TSYM 615 is normally the one whose TDEF 617 is at the top of the
hierarchy of definitions. SYM_BOUND_LIST 637 is a list of TSYMs
615 which currently have EXVALs 225 assigned to them.
Beginning the discussion of the LISP functions in TIE 219 with
WHAT function 619, that function is executed in response to the
WHAT command to EXPERT 603. That command has the form WHAT DTERM
611. For FRAUD, it would be WHAT FRAUD, which EXPERT 603 turns
into (WHAT FRAUD~. WHAT function 619 on page 5 of Appendix 1
first uses a LISP function to determine whether its argument is a
TSYM 615, and if it is, uses another LISP fùnction which takes a
symbol which is a function name as an argument and invokes the
function, in this case, FRAUD. The result is the execution of
TFUNC 701 in TDEF 617 for FRAUD. When that TFUNC 701 is executed,
the TFUNCs 701 for MISREPRESENTATION and DETRIMENTAL_RELIANCE are
executed until the value of FRAUD has been determined. When a
TFUNC 701 for a given TSYM 615 is executed, the TFUNCs 701 for
any TSYMs 615 required to find the value of the given TSYM 615 are
executed. ~hen all of the necessary TFUNCs 701 have been
-39-
,_ _ ,
~ L~7~3~3~
executed, the value resulting from those executions is returned to
the user of system 202 as TRES 227. If a TSYM 615 whose TFUNC 701
requires an EXVAL 225 already has such a value, the TSYM 615 is on
SYM-BOUND-LIST 637 and TFUNC 701 uses TEXVAL 703 in TDEF 617 for
TSYM 615; otherwise, TFUNC 701 generates an EXVAL REQ and obtains
EXVAL 225 from the user. Thus, the WHAT function, together with
LISP interpreter 503, operate as an inference engine for
determining the value of the TSYM 615 whose definition is at the
top level of the hierarchy as determined by external values.
Further, as long as a TFUNC 701 invoked as a conse~uence of the
WHAT operation is active, its corresponding TSYM 615 is on
ARG-STACK 635.
~0W function 623, on page 4 of Appendix 1, is executed in response
to the HOW command, which specifies a TSYM 615. HOW function 623
takes that TSYM 615 as an argument and uses another L1SP function,
SYMBOL-FUNCTION with the argument TSYM 615 to obtain the list used
with DEFUN to define TFUNC 701 corresponding to TSYM 615 and other
LISP functions to obtain the third element in the third list in
TFUNC 701. As may be seen from the FRAUD function above, that
element is the list defining the operation by which the function's
value is derived, i.e., in FRAUD, the list (AND ~KNOWING
MISREPRESENTATION) (DETRIMENTAL RELIANCE)). The HOW functlon
retrieves that list, uses TIE 219's DEFINITION function to display
TDESC 705 for TSYM 615 used in the HOW command, and then evaluates
-40-
~,. .. ~ . .
the TSYMs 615 in the list retrieved from TFUNC 701, and outputs
the results with suitable explanatory text.
The user of expert 202 may input the ~I~IY command either to EXPERT
603 or to TIE 219 in response to an EXVAI REQ output during
evaluation of a TSYM 615. The WHY function is on page 1-4 of
Appendix 1. The function may be invoked either with or without a
TSYM 615 as an argument. In the first case, the function works
with the TSYM 615 currently at the top of ARG-STACK 635, which is
the TSYM 615 corresponding to TFUNC 701 currently being evaluated
and whose evaluation produced the EXVAL REQ to which the user may
be responding, and in the second case, it works with TSYM 615
provided by the user. In either case, the next step is to locate
the preceding TSYM 615 in ARG-STACK 635, which is the TSYM 615
corresponding to the TFUNC 701 whose evaluation led to the
evaluation of the function corresponding to TSYM 615 being
processed by WHY. If there is no preceding TSYM 615, the WHY
command is meaningless, and a corresponding message is output to
the user; if there is a preceding TSYM 615, then DEFINITION is
used to output the definition for the preceding TSYM 615 together
with suitable explanatory text.
Contlnuing with the DEFINITION function, whose code ls on page 5
of Appendix 1, the command to EXPERT 603 whlch invokes the
functlon may have either a TSYM 615 as an argument or no
-41-
argument. In the first case, TDESC 705 in TDEF 617 is output; in
the second case, the TDESCs 705 for all TSYMs 615 on TERMS-STACK
613 are output.
The ASSUME function, whose code is on page 9 of Appendix 1 is
invoked with the ASSUME command, which specifies a TSYM 615 and a
value. The TSYM 615 must be one whose TFUNC 701 requests an EXVAL
225. ASSUME first empties ARG-STACK 635, so that the TSYM 615
will be reevaluated before a WHY command succeeds, then sets
TEXVAL 703 in TDEF 617 to the value received as an argument, and
puts TSYM 615 on SYM-BOUND-LIST 613 to indicate that it has a
TEXVAL 703.
The RESET function, whose code is on page 13 of Appendix 1, is
invoked with the RESET command, which may or may not specify a
TSYM 615. In the first case, only TEXVAL 703 in TDEF 617
corresponding to TSYM 615 is reset; in the second case, all
TEXVALs 703 are reset. The RESET function first empties ARG-STACK
635 for the reasons previously described. If a TSYM 615 is
specified, the RESET function unbinds TEXVAL 703 from TSYM 615,
effectively removing it from TDEF 617, and removes TSYM 615 from
SYM-BOUND-LIST 637. If no TSYM 615 is specified, RESET performs
the above operation for every TSYM 615 on SYM-BOUND-LIST 637.
-42-
~2~
The SAVE function, whose code is on page 5, makes a file ~JJhich
contains a DEFINE command for each TSYM 615 followed by TDESC 705
for the TSYM 615. The UEFINE commands occur in the order in which
TSYMs 615 occur in TERMS-STACK 613. SAVE works hy outputting the
following to the file for each TSYM 615 in TERMS-STACK 613: the
string DEFINE, a string representing TSYM 615, and a string
representing TDESC 705 for TSYM 615. The resulting file contains
the TDESCs 705 in the order in which the DESCs 205 upon which they
are based were input to DP 207.
The RESTORE function, whose code is also on page 5, restores the
TSYMS 615 which were previously saved. It does so by performing a
LISP load operation on the file. In the load operation, the LISP
symbols in the file are evaluated. In this case, thé result of
the evaluation is the production of the TSYMs 615 and their TDEFs
617 specified in the DEFINE commands in the resored file.
10. Detailed Description of DEFINE 607: Figure 8
Figure 8 shows how the DEFINE functions and functions invoked by
it recursively create the hierarchy of TDEFs 617 for a given set
of TSYMs 615. As previously mentioned, the manner in in which
DEFINE creates the hierarchy of TDEFs 617 guarantees that each
_~3_
.,,
~,~7~
TERM 206 is completely defined and that a given TERM 206 has only
a single definition
Figure 8 shows DEFINE, the major functions invoked by DEFIrJE, and
the manner in which the data from which TSYMs 615 and TDEFs 617
are created flows between the functions.
DEFINE 607 (page 1 of Appendix 1) produces DTERMs 211 from TERMs
206. When DEFINE returns DTERM 211, TSYM 615 and TDEF 617
corresponding to DTERM 211 have been created. DEFINE 607 is
invoked by EXPERT 603 and RESTORE 633; additionally, it is
recursively invoked by itself and by PROCESS-FUNCTION 811. EXPERT
603 provides CFORM 605 containing the DEFINE symbol and a TERM 206
to be defined; RESTORE 633 provides a CFORM 605 containing the
DEFINE symbol and a TERM 206 which is a copy of a previously-saved
DTERM 211 and a copy of TDESC 705 for that DTERM 211. When DÉFINE
607 is recursively invoked, its input is a TERM 206 which is is
used in the DESC 205 of another TERM 206 being defined.
Generally speaking, TERM 206 is a single symbol; however, when
DESC 205 includes a case statement, TERM 206 may be a list; in
that case, DEFINE invokes CONVERT 809 to convert the list to a
LISP form and then recursively invokes itself to define each of
the undefined TERMs 206 in the LISP form. Next, DEFINE 607
determines whether TERM 206 is a LISP symbol; if it is not, DEFINE
_44_
~ 2~
607 simply returns TERM 206 unchanged. If it is, DEFINE 607
determines whether TERM 206 was provided by RESTORE 633; if it
was, DEFINE 607 provides TERM 206 and the copy of TDESC 705 to
GETDEF 805 and returns the value returned by GETDEF 805, namely a
list whose element is TERM 206. If TERM 206 was not provided by
RESTORE 603, DEFINE 607 determines whether there is already a TSYM
615 for TERM 206 or if TERM 206 is a literal ~i.e, there was no
copy of TDESC 705). If either is the case, DEFINE returns a list
whose element is TERM 206. If none of the other cases was true,
GETDEF 805 is invoked by DEFINE 607 without a copy of T~ESC 705.
GETDEF 805 (page 2 of Appendix 1) receives an undefined term
(UTERM) 803 from DEFINE 607 and may also receive a copy of TDESC
705 for the term. In the first case, GETDEF obtains DESC 205 from
the user; in the second case, it simply uses TDESC 705. Next it
invokes CONVERT 809 to convert it to CDESC 807, which is a LISP
form. Next, UTERM 803 and CDESC 807 are provided to
PROCESS-FUNCTION 811, which returns TFUNC 701 for UTERM 811.
Finally, GETDEF 805 places TSYM 615 on TERMS-STACK 613, and
returns a list consisting of DTERM 211 corresponding to UTERM 803
to DEFINE 607.
CONVERT 809 (page 7 of Appendix 1) is invoked by DEFINE 607 or
GETDEF 805. It receives a DESC 205 from its invoker and converts
it to a LISP form, CDESC 807, which it returns to the ~nvoker.
-~5-
,
~ 27~
PROCESS-FUNCTION 811 (page Z of Appendix 1) receives UTERM 803 and
CDESC 807, passes UTERM 803 to DEFINE-FUNCTI0N 813, receives TFUNC
701 from DEFINE-FUNCTION 811, returns TFUNC 701 to GETDEF 805, and
produces UTERML 815, which is a list of the UTERMs 803 from CDESC
807 which have not yet been defined. PROCESS-FUNCTION then
invokes DEFINE 607 for each UTERM 803 on UTERML 815
DEFINE-FUNCTION 803 (page 2 of appendix 1), finally, creates and
evaluates a DEFUN for TFUNC 701, thereby creating TFUNC 701, which
it returns to PROCESS-FUNCTION 811, which in turn returns it to
GETDEF 805.
As can be seen from the above description, recursive invocations
of DEFINE 607 continue until all of the TERMs 206 required to
define the TERM 206 for which DEFINE was invoked have been
defined; only at tnat point, DEFINE 606 returns DTERM 211
corresponding to TERM 206. Since the user of Shell 201 must
define all of the TERMs 206 required to define a given TERM 206
and can give TERM 206 only a single der^inition, DEFINE 606
guarantees that a set of definitions for a term 206 is complete
and consistent.
-46~
. ~ ..
~27~
_1 Prototvpe Embodiment 2: FigLre 9
Appendix 2 contains the LISP code for prototype embodiment 2 of
the present invention~ As will be clear to one skllled in the art
upon examining appendix 2 prototype embodiment 2 contains many
improvements over prototype embodiment 1 including a better
interface to the user and more robust recovery from user errors.
Among the most important improvements included in prototype
embodiment 2 are the alternate embodiments of TDEF 617 and ~IHAT
shown in overview in Figure 9.
TDEF 901 contains TDESC 705 and tEXVAL 703 as did TDEF 617; it
does not contain TFUNC 701 and contains two new fields: TFORM 903
ànd TTYPE 90S. The change was made to eliminate a difficulty with
prototype embodiment 1: namely that the TERM 206 to be defined
might correspond to some other LISP symbol already in symbol space
505. In that case the definition produced by DEFINE 607 for TERM
206 would supersede the previously-existing definition of the
symbol. The problem is solved in prototype embodiment 2 by
replacing TFUNC 701 with TFORM 903 a LISP form which is not
itself executable as a function but may be executed by an
EVALUATOR function 911 in TIE 219. TTYPE 905 contains information
about the kind of value returned when TFORM 905 is executed by
EVALUATOR 911.
-47-
.. ., ~. ,
The remaining portion of Figure 9 shows the relationship between
WHAT function 907 and EVALUATOR 911 in prototype embodiment 2.
~HAT 907 receives the WHAT CFORM ~05 from EXPERT 603 as before
but instead of simply performing a LISP eval operation on TSYM 615
prc,vided as an argument to WHAT it provides TFORM 903 from TDEF
901 for TSYM 615 to evaluator 911 which in turn produces LISP
forms to perform the operations specified in TFORM 903 and
provides them to LISP interpreter 503. LISP interpreter 503
returns the results of the evaluation of the LISP forms to
evaluator 911 which then makes these results into TRES 227 which
it returns to WHAT 907 which in turn returns it to the user.
12. Conclusion
The preceding Description of a Preferred Embodiment and the
appendices attached thereto have disclosed the best manner
presently known to the inventors of implementing a novel expert
shell and novel expert systems. The expert systems though not as
powerful as those produced in the prior art have many of the most
important advantages oF pior-art expert systems and are
particularly well-adapted to situations where what is sought from
the expert system is detailed knowledge o~ complicated
procedures. The expert system shell is easier to use than expert
system shells oF the prior art and guarantees that the definitlons
-48-
making up the knowledge base oF an expert system are complete and
consistent.
The advantages of the expert system shell and expert systems
disclosed herein stem from the fact that the knowledge base used
by the expert system consists of terms defined with a hierarchy of
definitions in which a given definition depends only on
definitions lower than itself in the hierarchy and on external
values obtained from a source external to the knowledge base. The
expert system makes an inference concerning a term by requesting
the user to supply one or more external values and then
determining what value is produced for the term using the external
values and the hierarchy of definitions. The hierarchy of
definitions is produced in the expert system shell by requesting
definitions of terms used to define a given term until all of
those terms are completely defined, thereby guaranteeing that the
definitions from which the definition of a given term depends are
complete and consistent.
~hile the embodiments disclosed herein were implemented in LISP,
implementat~ons of the invention are in no way restricted to
LISP. It is further to be emphasized that the embodiments
disclosed herein, though the best known to the inventors at the
present time, are prototypes and intended to be purely exemplary.
Thus, the disclosed embodiments are to be considered in all
i
: , -49-
~27~
respects as illustrative and not restric-tive, the scope of the
invention being indicated by the appended claims rather than the
foregoing description, and all changes which come within the
meaning and range of equivalency of the claims are intended to be
embraced therein.
,
-50-
!
.. _ . _ . - . . ...
, . . .
