Home
Patent Search
IMT Blog
REGISTER
|
SIGN IN
United States Patent
4914590
Loatman , ; et al.
April 3, 1990
Title
Natural language understanding system
Abstract
A hybrid natural language understanding (NLU) system which is particularly designed for processing natural language text. Primary functional components of the NLU system include a preprocessor; a word look-up and morphology module which communicates with a lexicon and a learning module; a syntactic parser which interfaces with an augmented transition network (ATN) grammar; a case frame applier, which converts the syntactic structure into canonical, semantic "case frames"; and a discourse analysis component which integrates explicit and implied information in the text into a conceptual structure which represents its meaning. This structure may be passed on to a knowledge based system, data base, to interested analysts or decision makers, etc. Significant feedback points are provided, e.g., the case frame applier may notify the syntactic parser of a semantically incorrect parse, or the syntactic parser may seek a semantic judgment based on a fragmentary parse. This system incorporates a novel semantic analysis approach based largely on case grammar.
Inventors:
Loatman; Robert B.
(Vienna,
VA
)
, Post; Stephen D.
(McLean,
VA
)
, Yang; Chih-King
(Rockville,
MD
)
, Hermansen; John C.
(Catharpin,
VA
)
Assignee:
Emhart Industries, Inc.
(Indianapolis,
IN
)
Appl. No.:
195237
Filed:
May 18, 1988
Current U.S. Class:
704/8
Field of Search:
364/200,900,274.8,419,917.92
Claims
We claim:
1. A method of processing natural language text, comprising
providing electronically encoded data representative of the natural language text,
lexically processing the electronically encoded data with reference to a lexicon data base, said lexicon data base being comprised of lexical entries all including syntactic category data and semantically significant lexical entries including one or more concepts, to produce lexical specifications,
interpreting the lexical specifications with reference to an electronic representation of an Augmented Transition Network to produce configuration data, said configuration data including one or more concepts obtained from the lexical specifications, and
semantically processing the configuration data with reference to case frame templates each identified with a respective concept, to produce case frames in accordance with the concepts included in said configuration data.
2. A method as defined in claim 1 wherein the semantically significant lexical entries are comprised of entries representing verbs.
3. A method as defined in claim 1 wherein the semantically significant lexical entries are comprised of entries representing adjectives.
4. A method as defined in claim 1 wherein the semantically significant lexical entries are comprised of entries representing nouns which suggest verbs.
5. A method as defined in claim 1 wherein said configuration data assigns said syntactic category data to syntactic registers.
6. A method as defined in claim 1 wherein each of the case frame templates includes one or more roles associated with the case frame template's concept.
7. A method as defined in claim 6 wherein the roles may include propositional roles and modal roles.
8. A method as defined in claim 6, wherein each of the case frame templates identifies propositional roles which can participate in the case frame, a mapping between the roles and syntactic data to identify roles sources in configuration data, and restrictions on which roles may participate in the case frame.
9. A method as defined in claim 6 wherein at least some of said lexical entries are further comprised of semantic features, and said semantic features are used to restrict the participation of roles in a case frame.
10. A method as defined in claim 1 wherein the providing, lexically processing, interpreting, and semantically processing steps are effected in sequence.
11. A method as defined in claim 1 further comprising the step of semantically analyzing case frames in accordance with configuration data corresponding to a partial interpretation of a sentence of said natural language text.
12. A method as defined in claim 11 further comprising the step in the event said case frames are semantically unacceptable of returning to a prior, semantically acceptable partial interpretation of the sentence.
13. A method as defined in claim 1 further comprising the step of looking ahead in the lexical specifications after partially completing the interpreting step to control the further conduct of the interpreting step.
14. A method as defined in claim 13 wherein the step of looking ahead includes a semantic analysis of the lexical specifications.
15. A method as defined in claim 1 further comprising the step after said semantic processing step of conceptually integrating information from the case frames.
16. A method as defined in claim 15 wherein the conceptually integrating step comprises filling in domain knowledge templates.
17. A method as defined in claim 1, wherein at least some of the lexical entries are further comprised of syntactic features, said syntactic features being used in the interpreting step.
18. A method as defined in claim 1 wherein at least some of the lexical entries are further comprised of semantic features, said semantic features being used in said semantic processing step to instantiate case frames.
19. A method as defined in claim 1 wherein the case frames are conceptually integrated by filling in domain knowledge templates, further comprising the step of adding to or modifying the domain knowledge templates.
20. A method for developing natural language processing systems of the type wherein the following steps are effected:
providing electronically encoded data representative of the natural language text,
lexically processing the electronically encoded data with reference to a lexicon, said lexicon being comprised of lexical entries wherein semantically significant lexical entries include one or more concepts, to produce lexical specifications,
interpreting the lexical specifications with reference to an electronic representation of an ATN grammar specification to produce configuration data, said configuration data including concepts obtained from the lexical specifications, and
semantically processing the configuration data with reference to case frame data base containing case frame templates each identified with a respective concept, to produce case frames in accordance with the concepts included in said configuration data;
said method comprising the step of modifying one or more of the lexicon data base, ATN grammar specification, and case frame data base.
21. A method as defined in claim 20 wherein the modifying step comprises adding a further entry to the lexicon data base in response to user input.
22. A method as defined in claim 20 wherein the modifying step comprises learning a new word from the natural language text from context, without human intervention.
23. A method as defined in claim 22 wherein the modifying step comprises recognizing inflected forms of a known root word.
24. A method as defined in claim 22 wherein the modifying step comprises morphologically analyzing the word, and may be followed by a human verification of the morphological analysis.
25. A method of processing natural language text, comprising
providing electronically encoded data representative of the natural language text,
lexically processing the electronically encoded data with reference to a lexicon data base, said lexicon data base being comprised of lexical entries all including syntactic category data and semantically significant lexical entries including one or more concepts, to produce lexical specifications,
interpreting the lexical specifications with reference to an electronic representation of a grammar specification to produce output data representative of a grammatical parse of the natural language text, said output data including concepts obtained from the lexical specifications, and
semantically processing the output data with reference to case frame templates each identified with a respective concept and including one or more roles associated with such concept, to produce case frames in accordance with the concepts included in said configuration data.
26. A method as defined in claim 25 wherein the semantically significant lexical entries are comprised of entries representing verbs.
27. A method as defined in claim 25 wherein the semantically significant lexical entries are comprised of entries representing adjectives.
28. A method as defined in claim 25 wherein the semantically significant lexical entries are comprised of entries representing nouns which suggest verbs.
29. A method as defined in claim 25 Wherein said configuration data assigns said syntactic category data to syntactic registers.
30. A method as defined in claim 25 wherein the roles may include propositional roles and modal roles.
31. A method as defined in claim 25, wherein each of the case frame templates identifies propositional roles which can participate in the concept, a mapping between the roles and syntactic data to identify roles sources in output data, and restrictions on which roles may participate in the concept.
32. A method as defined in claim 25, wherein at least some of the lexical entries are further comprised of syntactic features, said syntactic features being used in the interpreting step.
33. A method as defined in claim 25 wherein at least some of said lexical entries are further comprised of semantic features, and said semantic features are used to restrict the participation of roles in a case frame.
34. A method as defined in claim 25 wherein the providing, lexically processing, interpreting, and semantically processing steps are effected in sequence.
35. A method as defined in claim 25 further comprising the step of semantically analyzing case frames in accordance with configuration data corresponding to a partial interpretation of a sentence of said natural language text.
36. A method as defined in claim 25 further comprising the step of semantically analyzing case frames in accordance with configuration data corresponding to a partial interpretation of a sentence of said natural language text.
37. A method as defined in claim 25 further comprising the step of looking ahead in the lexical specifications after partially completing the interpreting step to control the further conduct of the interpreting step.
38. A method as defined in claim 25 further comprising the step after said semantic processing step of conceptually integrating information from the case frames.
39. Apparatus for processing natural language text, comprising
means for providing electronically encoded data representative of the natural language text;
lexicon data base means comprising a plurality of lexical entries, wherein said lexical entries are comprised of syntactic category data and semantically significant lexical entries are also comprised of one or more concepts;
means for lexically processing the electronically encoded data by reference to the lexicon data base means to produce lexical specifications;
parser means for interpreting the lexical specifications with reference to an Augmented Transition Network grammar specification to produce configuration data, said configuration data including concept data obtained from the lexical specifications;
case frame means for providing a plurality of case frame templates each identified with a respective concept; and
means for semantically processing the configuration data by reference to the case frame means to produce case frames in accordance with the concepts included in the configuration data.
40. Apparatus as defined in claim 39 wherein the semantically significant lexical entries are comprised of entries representing verbs.
41. Apparatus as defined in claim 39, wherein the semantically significant lexical entries are comprised of entries representing adjectives.
42. Apparatus as defined in claim 39, wherein the semantically significant lexical entries are comprised of entries representing nouns which suggest verbs.
43. Apparatus as defined in claim 39 wherein said configuration data assigns said syntactic category data to syntactic registers.
44. Apparatus as defined in claim 39 wherein each of the case frame templates includes one or more roles associated with the case frame template's concept.
45. Apparatus as defined in claim 44 wherein the roles may include propositional roles and modal roles.
46. Apparatus as defined in claim 44, wherein each of the case frame templates identifies propositional roles Which can participate in the concept, a mapping between the roles and syntactic data to identify roles sources in configuration data, and restrictions on which roles may participate in the concept.
47. Apparatus as defined in claim 44 wherein at least some of the lexical entries are further comprised of semantic features, and said semantic features are used to restrict the participation of roles in a case frame.
48. Apparatus as defined in claim 39 wherein at least some of the lexical entries are further comprised of semantic features, said semantic features being used by said semantic processing means to instantiate case frames.
49. Apparatus as defined in claim 39 wherein at least some of the lexical entries are further comprised of syntactic features, said syntactic features being used by said parser means.
50. Apparatus as defined in claim 39 wherein the lexical processing, parser, and semantically processing means operate in sequence.
51. Apparatus as defined in claim 39 wherein the parser means includes means for looking ahead in the lexical specifications after partially completing the parse of a sentence to control the further course of the parse.
52. Apparatus as defined in claim 39 further comprising means for conceptually integrating the case frames.
53. Apparatus as defined in claim 52 wherein the conceptually integrating means is comprised of domain knowledge templates.
54. Apparatus as defined in claim 39 wherein said case frame means comprises a concept network, and means for retrieving information from the concept network and lexicon to constitute case frame templates.
55. Apparatus for processing natural language text, comprising
means for providing electronically encoded data representative of the natural language text;
lexicon data base means comprising a plurality of lexical entries, wherein said lexical entries are comprised of syntactic category data and semantically significant lexical entries are also comprised of one or more concepts;
means for lexically processing the electronically encoded data by reference to the lexicon data base means to produce lexical specifications;
parser means for interpreting the lexical specifications with reference to an electronically encoded grammar specification to produce output data representative of a grammatical parse of the natural language text, said output data including concepts obtained from the lexical specifications;
case frame means for providing a plurality of case frame templates each identified with a respective concept and including one or more roles; and
means for semantically processing the configuration data by reference to the case frame means to produce case frames in accordance with the concepts included in the configuration data.
56. Apparatus as defined in claim 55 wherein the semantically significant lexical entries are comprised of entries representing verbs.
57. Apparatus as defined in claim 55 wherein the roles may include propositional roles and modal roles.
58. Apparatus as defined in claim 55, wherein each of the case frame templates identifies propositional roles which can participate in the concept, a mapping between the roles and syntactic data to identify roles sources in configuration data, and restrictions on which roles may participate in the concept.
59. Apparatus as defined in claim 55 further comprising means for conceptually integrating the case frames.
60. Apparatus as defined in claim 55 wherein the conceptually integrating means is comprised of domain knowledge templates.
61. Apparatus as defined in claim 55 wherein at least some of the lexical entries are further comprised of semantic features, and said semantic features are used to restrict the participation of roles in a case frame.
62. Apparatus as defined in claim 55 wherein at least some of the lexical entries are further comprised of syntactic features, said syntactic features being used by said parser means.
63. Apparatus as defined in claim 55 wherein the lexicon data base means, parser means, and case frame means are data structures comprised of objects.
64. Apparatus as defined in claim 63 wherein said object based data structures are distributed between permanent memory and virtual memory.
65. Apparatus as define in claim 63 wherein the objects comprise frames.
Description
BACKGROUND OF THE INVENTION
The present invention relates to natural language understanding (NLU) systems, and more particularly to systems for understanding natural language
Reference is made herein to various prior art references:
(1) Bates, M. 1978. "The Theory and Practice of Augmented Transition Network Grammars". In L. Bolc (ed.), Natural Language Communication with Computers. New York: Springer.
(2) Boguracv, B. 1983. "Recognizing Conjunctions within the ATN Framework. In K. Sparck Jones and Y. Wilks (Eds.), Automatic Natural Language Parsing. New York: Halsted Press
(3) Cook, W. 1979. Case Grammar: Development of the Matrix Model. Washington DC: Georgetown University Press
(4) Cruse, D. A. 1986. Lexical Semantics. Cambridge University Press, Cambridge, England.
(5) Dyer, M. 1983. In-Depth Understanding. Cambridge, MA: MIT Press
(6) Jespersen, O. 1964. Essentials of English Grammar. University, AL: University of Alabama Press
(7) Laffal, J. 1973. A Concept Dictionary of English. Essex, CT: Gallery Press
(8) Lebowitz, M. 1983. "Memory-Based Parsing", Artificial Intelligence, Vol. 21, pp 363-404.
(9) Marcus, M. 1980. Theory of Syntactic Recognition for Natural Language. Cambridge, MA: MIT Press.
(10) Quirk, R., Greenbaum, S., Leech, G., and Svartvik, J. l985. A Comprehensive Grammar of the English Language. New York: Seminar Press
(11) Sager, N. 1981. Natural Language Information Processing: A Computer Grammar of English and Its Applications. Reading, MA: Addison-Wesley
(12) Schank, R. 1975. Conceptual Information Processing. New York: North-Holland.
(13) Wilks, V., Huang, X., and Fass, D. 1985. "Syntax, Preference, and Right Attachment", Proceedings of the Ninth IJCAI.
(14) Winograd, T. 1983. Language as a Cognitive Process, vol. 1: Syntax. Reading, MA: Addison-Wesley.
(15) Winston, Morton E.; Chaffin, Roger; and Herrmann, Douglas. 1987. "A Taxonomy of Part-Whole Relations" in Cognitive Science, Vol. 11, pp. 417-444.
(16) Winston, P. and Horn, B. 1984. LISP. 2nd ed. Reading, MA: Addison-Wesley.
(17) Woods, W. 1970. "Transition Network Grammars for Natural Language Analysis". Communications of the ACM, Vol. 13, No. 10, pp. 591-606.
(18) Woods, W., Kaplan, R. and Nash-Weber, B. 1972. The Lunar Sciences Natural Language Information System: Final Report. Cambridge, MA: Bolt Beranek and Newman, Inc.
(19) Xerox Corporation 1986. Interlisp-D Reference Manual. Pasadena, CA: Xerox Artificial Intelligence Systems Division.
In the last decade, some headway has been made in the area of data bases to provide information online. This allows for the easy application of statistical and other algorithmic aids to the data. Much of the current work to enhance the usefulness of these systems, to make them more "user friendly", is being performed under the broad heading of Artificial Intelligence. A subdomain of this technology is the area of Natural Language Understanding (NLU). The assumption is that communication with machines would be much easier if only one could use natural language in accessing information. This field is called data base retrieval (or data base query) and is the area to which most NLU work is being applied.
However, there is another NLU application that is less publicized but much more important. Even if the information in a data base is readily accessible, how accurate and timely is that information For example, in message processing applications, many messages arrive at an intelligence center in an unformatted, "free text" form (i.e., natural language). No present NLU system can account for all of English, and in order to accomplish any useful work with such a system, it is built with a specific, limited task in mind. The linguistic structures and vocabulary that a system can handle are specifically targeted to an application domain and expected text input format. A special use of language peculiar to a domain is often referred to as a "sublanguage", a term encompassing dialects and jargons. A significant part of an NLU developer's job is to discover the characteristics of a sublanguage and specify them for the requirements of an NLU development system.
Various NLU methodologies have been proposed. Many of these center on one particular aspect of a problem, such as conceptual analysis, syntax, or knowledge about specific words. The present invention involves a hybrid approach incorporating all of these aspects.
Quirk et al. 1985 contains a useful discussion of word morphology. This reference, Jespersen 1964 and Sager 1981 all provide significant information concerning grammar specification in natural language processing. Particularly pertinent to the technique of using augmented transition networks (ATN) for grammar specification are Bates (1978) and Winograd (1983). Neither reference, however, discloses a methodology for adapting ATNs to a graphical programming environment.
Prior art references dealing with conceptual analysis include Schank 1975 and Lebowitz 1983 (which discuss conceptual dependency); Cook 1979 (dealing with case grammar); Wilks et al. 1985 (semantic preferences); and Laffal 1973 (psychology). Dyer 1983 discloses domain-specific pattern matchers for NLU systems.
Accordingly, it is a principal object of the invention to provide an improved approach to the development of NLU systems, particularly as applied to text processing. Such approach should be adaptable to a broad range of linguistic domains, as well as to a variety of applications such as monitoring and sorting electronic mail.
SUMMARY OF THE INVENTION
In fulfilling the above and additional objects, the invention provides a hybrid natural language understanding system combining grammar development and application tools embodied in Augmented Transition Networks (ATNs), and novel semantic processing techniques. In the underlying process, a series of "words" (in the preferred embodiment, from a source text) are examined with reference to a lexicon, the entries of which include syntactic and semantic information. Then, an ATN grammar specification is used to attempt a syntactic parse. The syntactic structure thus derived is converted to "case frames" (by a case frame applier) which are canonical, language-independent semantic structures. These case frames are then submitted to discourse analysis, to derive domain-specific knowledge.
In accordance with one aspect of the invention, the process flow described above is not always followed sequentially. The case frame applier may notify the parser that a proposed parse is semantically incorrect. "Look ahead" capabilities in the ATNs permit the syntactic parser to ask the case frame applier for a semantic judgment based upon a fragmentary parse, when confronted with two computationally expensive paths.
Another aspect of the invention is the novel semantic technique utilizing a concept network of "case frame templates". A case frame represents a proposition about the world, i.e., a state, process, or action. Each case frame points at the fillers of propositional (intrinsic) and modal (extrinsic) roles. Case frame templates in the concept network store essential information about roles, including: which propositional roles may participate in a concept; which role fillers occur in a syntactic structure (mapping from syntactic registers to case roles); and restrictions on participation of candidate role fillers on a concept.
The NLU system of the invention incorporates a powerful, novel learning module. New words may be learned by context or from interaction with a dictionary officer. This system acquires templates for new case frames via menus and user prompting, and organizes the concepts into a coherent network. New words may be recognized as an inflected form of a known root word, may be obtained by regular morphological derivation, or in the most difficult cases, may be acquired through mixed-initiative interaction with a dictionary officer.
A preferred discourse analysis component uses domain knowledge templates to spawn demons which specify pattern matches based upon knowledge of the specific domain. Thus, both explicit and implied information in the text under analysis is integrated into conceptual structures to represent its meaning. These structures may be sent to a knowledge based system, used to update a database, or forwarded to appropriate analysts or decision makers .
BRIEF DESCRIPTION OF THE DRAWINGS
The above and additional aspects of the invention are illustrated in the following detailed description of the preferred embodiment, which should be taken together with the drawings in which:
FIG. 1 is a block schematic diagram of the PAKTUS architecture (i.e., of a preferred NLU system in accordance with the invention);
FIG. 2 is a screen image of an object in the PIKS object-oriented programming system;
FIG. 3 is a screen image of a fragment of the AKO network;
FIGS. 4 and 4B show a screen image of a PIKS browser network window;
FIGS. 5A and 5B show a screen image of a template for RULES;
FIGS. 6A through 6C show a screen image of the PIKS Agenda and certain associated objects;
FIGS. 7A and 7B illustrate a screen image of a non-grammar Rule;
FIGS. 8A and 8B show a screen image obtained during a graphic program trace;
FIGS. 9A and 9B show the interaction with a graphic program trace;
FIGS. 10A and 10B show a graphic program for a simple ATN grammar of English;
FIGS. 11A and 11B are interactive windows displaying a state, an arc, and a non-grammar rule;
FIGS. 12A through 12H are screen images of the primary PAKTUS grammar networks; FIGS. 12A through 12C show the left, middle and right sides, respectively, of the top level (sentence) network, FIGS. 12D and 12E show the left and right sides, respectively, of the noun phrase network while FIGS. 12F through 12H show four further networks;
FIG. 13 shows the addition of new mode to an ATN graph;
FIG. 14 illustrates the establishment of a transition path from slate t.uparw.through Arc Jump, for the ATN graph of FIG. 13;
FIGS. 15A and 15B show the addition of a label and a rule to the ATN graph of FIG. 14;
FIGS. 16A and 16B show the interactive generation of a rule for Arc Jump;
FIGS. 17A and 17B show an illustrative set of nominal categories;
FIG. 18 shows a set of verb categories;
FIG. 19 is a screen image of a PAKTUS request for user verification of its analysis of a new word;
FIGS. 20A through 20D show various screen images illustrating the acquisition of two senses of the word "general";
FIGS. 21A and 21B show a screen image showing the acquisition of an irregular word;
FIGS. 22A and 22B show a fragment of a concept network in accordance with the preferred embodiment;
FIG. 23 is a screen image showing the CauseBe Concept Object;
FIG. 24 is a screen image of the damage concept;
FIG. 25 is two windows showing a specific case role over-riding the mapping default of its category;
FIG. 26 is three windows showing case role mappings over-ridden in a specific concept and then in a specific verb;
FIG. 27 is a screen image illustrating the initial interaction in learning a new verb;
FIG. 28 is a screen image of a case frame specification for "explore";
FIG. 29 illustrates role source and constraint specification for the verb "explore";
FIGS. 30A and 30B show various screen images illustrating the entry of a new sense of the verb "burn";
FIG. 31 is a screen image of a domain template master;
FIG. 32 shows a pattern specification for a message sender; and
FIG. 33 shows an instance of a domain knowledge template;
FIG. 34 is a window image of a major syntactic registers (top panel) and conceptual frame (bottom panel) for example text;
FIGS. 35A and 35B show a window image corresponding to that of FIG. 34, for a second sentence;
FIG. 36 is a window image corresponding to that of FIG. 34, for a third sentence;
FIG. 37 is a data structure computed from the messages of FIGS. 34 through 36;
FIG. 38 illustrates the structure and operation of the PAKTUS lexicon;
FIG. 39 is a flow chart schematic diagram of the routing for compiling Lisp code from Rules objects;
FIGS. 40A and 40B show a flow chart schematic diagram of the RuleComp subroutine of the routine of FIG. 39;
FIGS. 41A and 41B show a flow chart schematic diagram of compilation of the Predicate code in the subroutine of FIGS. 40A and 40B;
FIG. 42 is a flow chart schematic diagram of the construction of the initiation code in the routine of FIG. 39;
FIGS. 43A through 43D show a flow chart schematic diagram of the parse routine, for parsing natural language sentences;
FIGS. 44A through 44C show a flow chart schematic diagram of a first part of the ATNMatch routine for interpreting natural language input;
FIGS. 45A through 45C show a flow chart schematic diagram of the remainder of the ATNMatch routine of FIGS. 44A through 44C;
FIG. 46 is a perspective view of an illustrative configuration of hardware devices for PAKTUS;
FIG. 47 is a schematic diagram of some PAKTUS semantic relations;
FIGS. 48A and 48B show a flow chart schematic diagram of the CaseFrame function;
FIGS. 49A through 49F show a flow chart schematic diagram of the FillRole function;
FIG. 50 is a flow chart schematic diagram of the ATN Compiler for compiling ATN graphs into Lisp code;
FIGS. 51A through 51C show a flow chart schematic diagram of first part of the ATNGEN function;
FIGS. 52A and 52B show a flow chart schematic diagram of the remainder of the ATNGEN function of FIGS. 51A through 51C.
FIGS. 53A and 53B show a flow chart schematic diagram of the AddNodeFn function;
FIGS. 54A and 54B show a flow chart schematic diagram of the AddLinkFn function;
FIGS. 55A and 55B show a flow chart schematic diagram of the DeleteLinkFn function;
FIGS. 56A through 56C show a flow chart schematic diagram of a look-ahead test for the presence of a relative clause with a relative pronoun or noun phrase; and
FIG. 57 is a schematic diagram of a network of case roles.
DETAILED DESCRIPTION
The following detailed description of a natural language text understanding system according to a preferred embodiment of the invention is organized according to the following major sections:
(1) An overview of the system architecture;
(2) The object-oriented programming language underlying the preferred embodiment of this NLU system;
(3) The ATN-based grammar specification used in this system, and the graphic programming techniques used to develop this;
(4) The system lexicon, i.e., data base for lexical information about words;
(5) The semantic analysis and use of conceptual case frames in this analysis;
(6) Conceptual integration to produce domain-specific output; and
(7) Examples of the processing of a message by this NLU system.
1. SYSTEM OVERVIEW
The NLU system of the preferred embodiment is often referred to in this patent specification as PAKTUS (PRC Adaptive Knowledge-based Text Understanding System). PAKTUS is a hybrid system. It integrates syntactic and semantic NLU methods that have had partial success in the prior art, and augments these with novel semantic processing and powerful new programming tools for building grammars. The PAKTUS architecture is summarized in FIG. 1. Its primary functional components are represented within the large box, with interfaces to the external environment indicated by arrows into and out of the box. Processing begins with the arrival of an electronic stream of text, indicated at 20. Such a stream might be produced by a speech recognition device or an optical character scanner, but more likely would be a pre-existing message stream. In any case, the first function performed, by the preprocessor 30, is the decomposition of the stream of characters into individual words, sentences, and messages (at 40).
The "words" identified by the preprocessor 30 are actually just "tokens" that suggest entries in a lexicon 60 which contain information about the meaning and usage of actual words. Often, words are encountered that have never been seen previously by PAKTUS. It tries to analyze these morphologically, with frequent success. If this fails, it deduces as much as it can from the current context, later verifying its deductions through mixed initiative interaction of the learning module 70
with a dictionary officer 78 (a person with substantial linguistic knowledge and an understanding of the structure and function of the PAKTUS lexicon).
The next step in processing the text is for module 80 to parse the sentences syntactically, according to a grammar specification 90 embodied in PAKTUS as an Augmented Transition Network (ATN). This parse identifies the subject, main verb, direct and indirect objects (if any), prepositional phrases, relative clauses, adverbials, etc. for each sentence. Then the syntactic structure 100 is converted to canonical, language-independent semantic structures called "case frames". A case frame 105
represents a proposition about the world (a state, process, or action) and points at the fillers of its "propositional" (intrinsic) and "modal" (extrinsic) "roles". Modal roles include time, place, etc., and are independent of all but a few concepts. They are optional in almost any sentence and represent "metapropositions" that predicate something about the basic sentential proposition.
If the parse cannot be put into any case frame, it is rejected and the syntactic parser tries alternatives. In some situations, the syntactic parser may fail, in which case alternative methods for handling ill-formed input are tried. Such methods tend to be application specific. The case frames are collected by a discourse analysis component 130, which applies knowledge (templates 135) about the particular domain of the application system to integrate all the information, both explicit and implied, of the message into conceptual structures 140 representing its meaning. These structures 140 may be passed to a knowledge based system (at 160, 165) which will act according to its goals. Alternatively, they might be matched against analysts' and decision makers' interest profiles cast in terms of conceptual templates, and routed accordingly (at 150, 155); or they might be reformatted into a data base update (at 170, 175).
The above discussion was framed as though processing proceeded sequentially from preprocessor through morphology, syntactic parse, case frame application, discourse analysis, and final transmission to the intended person or system. While that does represent the basic flow of control, there are important feedback points. For example, the case frame applier 120 may notify the syntactic parser that a proposed parse is semantically incorrect, so an alternative parse should be attempted. This may happen at the end of a clause or even within a clause; the system saves prior successful configurations and may return to such a configuration in the event that further parsing leads to a semantically unacceptable configuration. In addition, when confronted with two computationally expensive paths, the syntactic parser 80 may ask the case frame applier 120 to make a semantic judgment based on a fragmentary parse, before deciding which to try first.
The learning module 70 of PAKTUS is quite powerful, although it is not designed for an untrained user. In addition to learning new words either from context or from interaction with a dictionary officer, it acquires templates for new case frames via menus and user prompting, and it organizes the concepts into a coherent network. Words and conceptual case frames are not entered into PAKTUS in advance. PAKTUS was designed to acquire new words as encountered, as a human child does. It can learn words in a variety of ways and with varying confidence. The simplest consists of recognizing an inflected form of a known root word; for example, recognizing "symbols" as the plural form of "symbol" or "shaking" as the present participle of "shake". This type of word recognition is so simple, reliable, and efficient that PAKTUS need not even both to ask the dictionary officer for confirmation, nor does it clutter the lexicon 60 with a permanent record of the inflected form. At the next level is regular morphological derivation such as recognizing "symbolize" as meaning "to be a symbol for something". Such derivations are less reliable, due to the ever changes nature of natural languages (e.g., what was once a regularly derived word may later take on a new meaning), so PAKTUS preferably asks for verification of these by the dictionary officer 78.
The most difficult case, and the most interesting, occurs when a word is encountered that cannot be morphologically decomposed, either because its root is unknown or it is irregularly derived. The invention provides different modes of operation wherein PAKTUS will either ask to be taught the definition (including any associated case frame) immediately, acquiring it through mixed-initiative interaction with the dictionary officer; or it will "guess" as much as it can from the context in which the word is used, and proceed with its task. In the latter case, it stores its guesses in a special list. Periodically, the dictionary officer asks to see these lists and verifies, supplements, and corrects them through mixed-initiative interaction, after which PAKTUS stores the results permanently. As an NLU system's capabilities are developed, it may become increasingly more active in this learning process.
2. PIKS OBJECT PROGRAMMING SYSTEM
2.1 Introduction
The following discussion comprising Section 2 of this application describes a shell for developing and using knowledge-based systems, known by applicants and referred to herein as PIKS (PRC Integrated Knowledge-Programming System). It supports a variety of programming techniques which are utilized in the interactive graphic natural language programming system of the invention. The PIKS embodiment discussed in Section 2 of this application was implemented in Common Lisp and Interlisp D, the latter being used to support graphics functions.
2.2 Summary
Subsection 2.3 discusses object programming in PIKS. PIKS incorporates a network of frame data structures, in which objects may inherit attributes and behavior along any path. Subsection 2.4 explains a system browser facility in PIKS which provides intelligent interactive windows into objects and the knowledge network. Subsection 2.5 discusses the use of PIKS for rule-based programming to support inferencing. Subsection 2.6 discusses the PIKS object-oriented data base.
2.3 Object Programming ln PIKS
2.3.1 Introduction
PIKS supports object-oriented programming. this programming style, objects serve to organize information about the application domain. Objects are data structures with associated procedures. The basic structure of objects in PIKS is similar to that described by Winston and Horn (1984), and the term "frame" as used in this application is used in the same sense as in that prior art reference. Each object has a name and a set of slots. Each slot has an associated value and a set of other facets. The names of non-value facets appear within the object. The fillers of the value or other facets are lists of arbitrary LISP objects, including the names of other PIKS objects; therefore, the equivalent of any data structure can be constructed from these objects. An example of an object as displayed in a PIKS Browser window (see section 2.4) is shown in FIG. 2; note that this is an example of an object used for an expert systems application rather than natural language processing.
The facets other than the value of a slot may represent anything the user chooses, but PIKS supports certain facets that, in effect, monitor the value facet. These are often referred to as demons. In FIG. 2, the Report and Status slots have IF-ADDED demons, which monitor the addition of values to these slots. Other non-value facets recognized by PIKS are methods, which name procedures that are invoked in response to messages to objects; defaults and if-needed facets, which are used in retrieving information from objects; and modes, which associate properties with objects. These are explained in detail in the following sections.
2.3.2 Accessing and Modifying Objects
The user may interact directly with objects using the System Browser described in section 2.4. Programs, however, will normally use the primitive access functions described in this section.
(Note on notation: All function specifications in Section A of the present application consist of a "." followed by the function name in boldface, the arguments in square brackets, and an explanation of the function. All functions are Lambda expressions (i.e., they evaluate their arguments), unless otherwise noted.)
2.3.2.1 Basic Functions for Putting Information in an Object
FRAMEPUT [Frame Slot Facet Value Nomark Noaudit]
Adds Value at the end of the Facet facet of the Slot slot of Frame, if it is not already there. Notifies the PIKS database system or the Interlisp file package that Frame is changed unless Nomark is non-NIL. Stores audit information (date, time, manner of creation or update) in Frame unless Noaudit is non-NIL or the globalvar PIKSAUDIT is NIL. If (EQ Facet 'VALUE) and Slot has an inverse, Slot', then also stores Frame in VALUE facet of Slot' of Value, notifies the PIKS database system or the Interlisp file package that Value is changed unless Nomark is non-NIL, and stores audit information (date, time, manner of creation or update) in Value unless Noaudit is non-NIL or the globalvar PIKSAUDIT is NIL. Nomark and Noaudit have these same effects in all the functions below that use them. FRAMEPUT returns Value if it was stored, NIL otherwise.
Note: Frame must be an atom. Slot and Facet should also be atoms, although FRAMEPUT will still create the specified structure if they are not. However, if Slot of Facet is not an atom, the PIKS functions that fetch information (FRAMEGET, etc.) will not recognize it. Value may be any LISP expression unless it is being put in the VALUE facet of a slot that has an inverse (see subsection 2.3.3), in which case it must be an atom.
FRAMEPUT! [Frame Slot Facet Value Nomark Noaudit]
Like FRAMEPUT, but first removes any existing value(s) from Frame Slot Facet. This is for use when Facet should have a unique value. If (EQ Facet 'VALUE) and Slot has an inverse, Slot', then Frame is removed from the Slot'VALUE of each element of Frame Slot's VALUE. Returns Value.
2.3.2.2 Basic Functions for Getting Information from an Object
FRAMEGET [Frame Slot Facet]
Returns the list of values stored on the Facet facet of the Slot slot of Frame. If Facet is not specified (or NIL), the VALUE facet is returned. Note that (a pointer to) the actual list within the frame is returned, not a copy. If surgery is performed (e.g., by NCONC, join, etc.), then the frame itself is changed.
FRAMEGET! [Frame Slot Facet]
Returns the same value as (CAR (FRAMEGET Frame Slot Facet)) but is slightly more efficient.
FRAMEGET.V.D [Frame Slot]
Returns the list of values stored on the VALUE facet of the Slot slot of Frame, if any; otherwise, returns list of values on the DE639 FAULT facet of the Slot slot of Frame.
FRAMEP [Object]
Returns Object's FRAME property, if any; otherwise NIL.
GETFACETS [Frame Slot]
Returns list of facets for Slot slot of Frame.
GETSLOTS [Frame]
Returns list of slots defined for Frame.
HasSlot [Frame Slot]
Returns the tail of Frame's slot list beginning with Slot if Frame has Slot; otherwise NIL.
IsRoot [Frame]
Returns (Frame) if Frame has an AKO value (see Subsection 2.3.3.2 below); otherwise NIL.
@[Frame Slot Facet Value Nomark Noaudit]
Behaves like FRAMEPUT if the first four arguments are non-NIL or like FRAMEGET if only the first three are non-NIL. If only Frame and Slot are given, returns the contents of Slot. If only Frame is given, returns its contents.
2.3.2.3 Functions for Removing Information from Objects
FRAMERMOVE [Frame Slot Facet Value Nomark Noaudit Noinv]
Deletes Value from Facet of Slot of Frame (inverse of FRAMEPUT). If (EQ Facet 'VALUE) and Slot has an inverse, Slot', and Noinv is NIL. removes Frame from Slot' VALUE of Value. Returns Value if it wad deleted, NIL otherwise (i.e., Value was not there).
FREVALS [Frame Slot Facet Nomark Noaudit]
Deletes entire Facet from Slot of Frame. Returns Facet if it was deleted, NIL otherwise. If (EQ Facet 'VALUE) and Slot has an inverse, Slot', then Frame is removed from the Slot' VALUE of each element of Frame Slot's VALUE.
FRESLOT [Frame Slot Nomark Noaudit]
Deletes entire Slot from Frame. Returns Slot if it was deleted, NIL otherwise. If Slot has an inverse, Slot', then Frame is removed from the Slot' VALUE of each element of Frame Slot's VALUE.
KillNode [Frame Nomark Noaudit Noprompt]
First sends an AboutToBeDestroyed message to Frame. Certain objects (e.g., CONCEPT) will not permit their destruction, and they will so inform the user and return "DONT" to KillNode, which will refuse to proceed. Otherwise, if Noprompt is NIL (the default), first asks for confirmation in a pop-up window. If the user confirms, KillNode destroys Frame and removes any links to it from other objects if the links (slot-VALUES) have INVERSEs. If this results in the other objects being "orphaned" (see section 3.3.3), the user is asked to supply a new parent but may respond NIL. Returns NIL.
2.3.3 Relationships among Objects
2.3.3.1 Slots Viewed as Assertions about Relationships
When the value of a slot of an object contains the name of another object, the two objects are in a relationship named by the slot. Formally: for any slot S, the set R.sub.s, of all pairs (O.sub.1, O.sub.2) of objects such that O.sub.2 is a member of the value of slot S of object O.sub.1, is a relation. Since relations may be ewed as predicates, links between objects often represent assertions about the things being represented. Furthermore, following links from object to object is a form of deduction, so that from one point of view, object networks together with the inheritance mechanisms to be described below provide a significant part of predicate calculus. PIKS also provides for non-monotonic reasoning, using inheritance with exceptions, as explained in section 2.3.7.
Although the user is free to associate any interpretation to the relations implicit in slot linkages, PIKS was designed under the assumption that all predicates of the form R.sub.s above are uniformly true, that is, allowing no exceptions. when exceptions are desired, property inheritance, as explained in section 2.3.7, should be used. Nothing in PIKS forces the user to accept this convention, but Certain design details of the inheritance mechanisms will be better understood if this is kept in mind.
2.3.3.2 The AKO Network
The AKO slot is treated specially by PIKS. It specifies subclass and instance relationships between objects. As such, it is the default link used for inheritance (see section 2.3.3.5). Every object should have a value for its AKO slot. PIKS does not prevent the creation of objects that lack this slot, but it will refuse to perform certain operations on them. In addition, it is probably a good idea to ensure that all objects are descended from the OBJECT object.
Of course, many objects may be linked to the same parent by their AKO slot. It is also permissible for an object to have more than one AKO value. In other words, the relation defined by AKO links is a network; it need not be a hierarchy. The only restriction on the structure of the network is that there should be no AKO cycles (e.g., X is AKO Y, Y is AKO Z, and Z is AKO X). The user must enforce this restriction; PIKS does not (for efficiency). (Actually, cycles Will not necessarily cause problems; see the discussion of FRAMEGET-Z in section 2.3.3.5.)
It is often necessary to use the inverse of the AKO relation. In PIKS this inverse relation is called KINDSOF (if BOY is AKO (i.e., A Kind Of) PERSON, then KINDSOF PERSON includes BOY). Because this inverse relation must be known so frequently, it is explicitly and automatically stored by PIKS. (It could be computed whenever needed, but at great cost in computation time.) Whenever PIKS establishes an AKO link from object X to object Y, it immediately establishes a KINDSOF link from Y to X. Conversely, if a KINDSOF link is added from Z to W, then PIKS immediately establishes an AKO link from W to Z. In addition, if an AKO or a KINDSOF link is deleted, the inverse link is also deleted by PIKS.
2.3.3.3 Other Special Links
There are several additional object links treated specially by PIKS. Each of these has an inverse which is automatically maintained. These links and their respective inverses are: Parts and PartOf; Instances and AIO; Location and IsHere; and INVERSE and INVERSE. One other special PIKS link is Has. It does not have an inverse. Objects representing each of these slots exist as KINDSOF the object SLOT.
Note that the Instances and AIO slots are provided for the convenience of users who want to distinguish between classes and instances. Many knowledge representation systems do this. PIKS does not itself recognize this distinction, however, since its users have not found any compelling reason to do so in their applications to date.
2.3.3.4 User-Defined Links
Users may define any links (or slots in general) they desire. PIKS supports user-defined inverse link pairs. To cause PIKS to maintain such bi-directional links, one defines objects for each link as KINDSOF the object SLOT and lists each link object as the INVERSE value of the other. For example, suppose one wants PIKS to recognize the Parent and Child relations as inverses. One can do this with the Browser (see section 2.4), or directly, by the function calls:
(FRAMEPUT 'SLOT 'KINDSOF 'VALUE 'PARENT)(*makes Parent AKO SLOT)
FRAMEPUT 'SLOT 'KINDSOF 'VALUE 'Child)(*makes Child AKO SLOT)
(FRAMEPUT 'Parent 'INVERSE 'VALUE 'Child)(*makes Parent and Child inverses of each other)
Certain links may be considered essential. That is, one may want all objects of a certain type to have these links. PIKS has a facility for identifying links that should normally be maintained. If an object that had such links subsequently loses all of them as a result of a KillNode operation, PIKS will prompt the user to supply new links, unless the Noprompt option to KillNode is non-NIL. This link monitoring is established by storing the atom MAINTAIN in the MODE facet of the INVERSE slot of the link object. In the example of the preceding paragraph, (FRAMEPUT 'Parent 'INVERSE 'MODE 'MAINTAIN)(*maintain the Parent link) will cause PIKS to prompt for new Parent(s) whenever a node becomes "orphaned" by KillNode (unless Noprompt is non-NIL). The PIKS links AKO and Location have the MAINTAIN mode.
2.3.3.5 Inheritance of Slot-Facet Values
Slot-facet values may be inherited through object relations. The basic information fetching functions described in section 2.3.2.2 access only the specified object. sometimes, however, information may be common to many objects. In that case, rather than redundantly storing the information in each object, it may be stored in a common ancestor (i.e., an object that can be reached by traversing links of some relation) and inherited by its progeny (i.e., all objects that can be reached from ancestor by traversing links of the inverse relation).
PIKS provides an alternative fetching function, FRAMEGET-Z, that implements this inheritance. Thus inheritance will occur only where the PIKS user wants it. It would be slightly simpler to always look for inherited values, but this search incurs great computational cost, and in practical applications, the system developer almost always knows in advance whether or not a value should be found in the object accessed, or inherited. Nevertheless, if one feels that simplicity outweighs efficiency, one has the option of always using FRAMEGET-Z instead of FRAMEGET for information fetching.
The default relation for inheritance is AKO, but the user may supply any path. The PIKS implementation of this inheritance takes the information from the first object encountered in the depth-first search along the specified path that has it. If no slot-facet value is found in this search, it is retrieved, if available, from the object that represents the slot. The information may be inherited as a specified value, or, alternatively, a procedure may be invoked to compute the result. The procedure must be defined by the PIKS user and stored in the appropriate place. The details are as follows:
FRAMEGET.Z [Frame Slot Facet Path Focus]
Returns same list as FRAMEGET, unless Frame has no Slot-Facet values, in which case a depth-first search is made along the Path relation (default Path is AKO) from Frame until Slot-Facet values are found and these are returned. If Facet is NIL, searches for VALUE, DEFAULT, or IF-NEEDED facet of Slot, in that order; if IF-NEEDED values are found first, they are APPLIED to (Frame Slot), and the list of results is returned. Each IF-NEEDED function should return a list. If more than one is present, the resulting lists are joined together. If this search does not result in any value, then another search for a VALUE, DEFAULT, or IF-NEEDED facet is initiated, beginning with the Facet slot of the Slot object and following AKO paths. Note that (FRAMEGET-Z Frame Slot 'VALUE) may not return the same value as (FRAMEGET-Z Frame Slot). The former will not notice any DEFAULT or IF-NEEDED facets; the latter will.
2.3.4 Some Useful Functions Based on Object Relations
Is [It Thing Path BlockCat]
Thing may be an atom or a list. Returns non-NIL if, following Path links, It is a descendant of Thing, if thing is an atom, or of a member of Thing if thing is a list. The default path is AKO. The search along Paths will ignore BlockCat. For example, in the PAKTUS natural language application, which includes the AKO relationships depicted in FIG. 3, it is sometimes necessary to know whether a word is a substantive (i.e., a common noun which is not also an adjective). One can use, for example, (Is 'BIG "Common NIL 'Adj) which returns NIL since there is no AKO path from BIG to Common that does not pass through the Adj category. As another example, (Is 'HUMAN 'Common NIL 'Adj) returns non-NIL since there is a path to Common that does not pass through the blocked Adj category.
Note: Do not write programs that use the value returned by Is. Is should be used only as a predicate (the value returned is either NIL or tru (non-NIL)). The specific non-NIL value returned may change in the future. (It has changed several times in the past.) If there is a compelling reason to return some particular value, that may be implemented later. (Currently, Is returns the parent of It which is at the start of the path to Thing, assuming that It is not itself a Thing; e.g., (Is 'HUMAN 'Common NIL 'Adj) returns Person.)
Has [It Thing Path]
Returns the first member of It's Has value that Is Thing, if any; otherwise the first member of It's Parts slot that Has Thing, if any; otherwise NIL. Path is passed to Is (the default is AKO). For example, in one application (Has 'UR5thAirReconRgt 'Tactical Aircraft) returns UR8thReconSqdn because UR8thReconSqdn is one of UR5thAirReconRgt's Parts, and it Has BREWER-D, which Is a TacticalAircraft.
Contains [It Thing Path]
Returns the first object in It's Has value that Is Thing, if any; otherwise NIL. Path is passed to Is (the default is AKO). For example, in the application just mentioned (Contains 'KyzlArvat 'TacticalAircraft) returns UR8thReconSqdn because UR8thReconSqdn is in KyzlArvat's IsHere Value, and it Has BREWER-D, which Is a TacticalAircraft.
InvSlot [Slot]
Returns the inverse of Slot, if any; otherwise NIL.
2.3.5 Active Values (Demons)
Active values are slots that trigger attached procedures (i.e., demons) when their value is accessed. The procedures that maintain inverse link relationships, for example, are demons. These are deeply embedded, within the object-access functions, however, and are not associated with particular objects. The demons that monitor active values are stored in objects, and different (classes of) objects may have different demons for the sale slot. The IF-NEEDED functions discussed in section 2.3.3.5 are such demons. They are an integral part of the PIKS inheritance mechanism. This section describes the PIKS support for other demons.
PIKS provides demons that monitor the addition, deletion, or fetching of values. The demons are invoked by the functions FRAMEPUT+, FRAMEREMOVE+, and FRAMEGET+. These return the same values and have the same effects as FRAMEPUT, FRAMEREMOVE, and FRAMEGET, respectively, if no demons are associated with the object and slot being accessed.
Section 3 of this application describes the definition and storage of demons for the ATN-based NLU interactive programming technique of the invention. Demons for monitoring the addition of values are normally put on the IF-ADDED facet of the slot being monitored; those monitoring value deletion are on the IF-REMOVED facet; and those monitoring value fetching are on the IF-FETCHED facet. Demons are inherited through the AKO network and are not usually stored on leaf nodes. Unlike inheritance of other facets, all inherited demons are invoked, not just the first one found. Also, if no demons are found on AKO ancestors, PIKS will invoke any demons found on the slot object instead. These should be stored on the IF-ADDED, IF-REMOVED, and IF-FETCHED facets of the appropriate slot (as defined belo)) of the slot objects. Demons may also monitor non-VALUE facets of slots, but these are limited to global demons on the slot object. (They are global in the sense that a single demon monitors the slot-facet value of all objects.)
FRAMEPUT+ [Frame Slot Facet Value DupFlg Nomark Noaudit]
Same as FRAMEPUT, but if Facet is VALUE and Value is a new value or DupFlg is non-NIL, also searches along AKO links for IF-ADDED facets; values in IF-ADDED facets are APPLIED to the list (Frame Value Slot Facet). If Facet is not VALUE or no IF-ADDED facets were found, any values in the IF-ADDED facet of the Facet slot of Slot are used instead. Returns value if it was added or DupFlg is non-NIL, NIL otherwise. The demons are invoked after the Value is stored in Slot. Note that the demons are not invoked if Value was already there, unless DupF1g is non-NIL.
FRAMEREMOVE+ [Frame Slot Facet Value Nomark Noaudit Noinv]
Same as FRAMEREMOVE, but if Facet is VALUE, also searches along AKO links for IF-REMOVED facets; values in IF-REMOVED facets are APPLIED to the list (Frame value Slot Facet). If Facet is not VALUE or no IF-REMOVED facets were found, any values in the IF-REMOVED facet of the Facet slot of Slot are used instead. Returns Value if it was deleted, NIL otherwise. Noinv is passed on to FRAMEREMOVE. The demons are invoked before the Value is deleted from Slot.
FRAMEGET+ [Frame Slot Facet]
Same as FRAMEGET, except that if Facet is NIL or VALUE, also searches along AKO links for IF-FETCHED facets; values in IF-FETCHED facets are APPLYed to the list (Frame Slot Facet). If Facet is not NIL or VALUE or no IF-FETCHED facets were found, any values in the IF-FETCHED facet of the Facet slot of Slot are used instead. Returns the result of (FRAMEGET Frame Slot Facet). The demons are invoked before the Value is fetched from Slot.
2.3.6 Messages to Objects
Another way to evoke action from an object is to send it a message. This is somewhat like the use of demons in that procedures are attached to objects. However, it is different in that the procedures are explicitly invoked, and they may take any number of arguments in addition to the name of the object receiving the message. The functions that are invoked in response to messages are called methods. They are usually stored on the METHOD facet of the slot whose name is the same as the message (thus, messages must be atoms). They are inherited through the AKO network (they are fetched with FRAMEGET-Z). Alternatively, a method may be stored on an object whose name is the same as the message, on its METHOD slot, VALUE or DEFAULT facet. Another alternative is that an object may have a private method, which it uses but does not pass on to its progeny. These are stored on the MyMETHOD facet. The message passing function is ".rarw." (left arrow). The calling syntax is as follows:
.rarw. [Frame Message Arg.sub.1 . . . Arg.sub.n ]
The method is the first element of the MyMETHOD facet of the Message slot of Frame, if any; otherwise (CAR (FRAMEGET-Z Frame Message 'METHOD)) . Raises an error if the method is not function. APPLYs the method to the list (Frame Arg.sub.1 . . . Arg.sub.n) and returns the result.
As with demons, the PIKS user must define the methods and install them in the appropriate places. The PIKS kernel recognizes three messages Default methods for responding to these messages are stored in the message objects These messages and their associated methods are described below. For examples of how methods are installed, the user is advised to use the PIKS Browser (see section 2.4) to look at the object's SLOT (which holds a method that is inherited by its progeny), CONCEPT (which has a private method), and AboutToBeDestroyed (which holds a global default method).
AboutToBeDestroyed
This message is sent to an object by KillNode (see section 2.3.2.3). The default method for objects descended from CONCEPT via AKO links is the function ProtestIfNot Gensym, which warns the user if the object does not appear to have been created by a GENSYM (i.e., it does not look like a temporary object). The default method (stored in the AboutToBeDestroyed object) for other objects is the function ProtestIfOldEnough, which informs the user if the object is more than 30 minutes old, assuming that PIKS object auditing was on when the object was created (see section 2.3.2.1). Most of the PIKS kernel objects have the function No as their method for this message. It prints (and speaks, if a Votrax is active) a message, inverts the screen a few times, and returns the atom DONT to the calling function.
AboutToBeRenamed
This is sent to an object by RenameNode (see section 2.3.5). The default method permits renaming. (It simply returns T.)
DescribeYourself
This is used by the Browser (see section 2.4). The default response is to print (and speak, if a Votrax is active) a description of the object. This description consists of lists of the values of each slot that has an inverse (these are assumed to contain the most interesting data), preceded by whatever is stored in the Meaning facet of the My slot of the slot object. For example, the current value of AKO'S My Meaning is the string "I am a kind of". Thus, if X is AKO Z and W, part of its response to the DescribeYourself message is "I am a kind of (Z W)", unless, of course, the default method is overridden by another one stored in X or one of its ancestors.
2.3.7 Properties and PropertyInheritance with Exceptions
Several forms of inheritance are discussed above: inheritance of slot-facet values, of demons that monitor values, and of methods for responding to messages. The property inheritance discussed in this section is different. An object generally inherits values, demons, and methods from the first ancestor found possessing the attribute, in a depth-first search. This is sufficiently flexible for most applications. However, occasionally it is necessary to consider alternatives. PIKS provides a more powerful form of inheritance with exceptions. The attributes to be inherited in this way are called properties to distinguish them from others.
In PIKS, property values must be stored on a special facet, called MODE, of the AKO slot. Normally, progeny of an object with such a property will inherit the property bust as they inherit demons and methods. When appropriate, however, property inheritance can be explicitly blocked. This is done in a way that specifies both the ancestor and the property whose inheritance is blocked. For example, in the natural language system of the invention, there is a class of objects called Agent, which has the properties Animate and Concrete. One subclass of Agent is Person, which inherits these properties. Another descendant of Agent is the object PIKS, which inherits the Concrete property but not the Animate property. This is accomplished by storing the atom-Agent animate on the AKO MODE of the object System. This prevents progeny of System, such as PIKS, from inheriting the Animate property from Agent. Note that progeny of System may still inherit the Animate property from some other object. This provides for exceptions to exceptions, etc.
This inheritance with exceptions is incorporated into the function HasProp.
HasProp [Frame Property]
Returns the first ancestor, Source, found in a depth-first search from Frame along AKO links, which includes property in its AKO MODE and for which no AKO ancestor of Frame as -SourceProperty (the result of packing together the symbol "-", Source, and the value bound to Property) in its AKOMODE. In addition, Frame must not have -Property in its own AKO MODE.
2.4 The System Browser
The PIKS System Browser is an interactive graphic database interface. It was implemented using certain functions of the Interlisp-D Graphic package (Node Create, Layout Graph, Show Graph, Flip Node, Dump Graph, and Read Graph) as well as certain additional features designed by applicants. With it, one can examine, create, modify, destroy, and find things. Interaction is normally through the mouse in PIKS windows, but there may be occasion for a program to invoke the Browser functions directly. Section 2.4.1 explains the interactions that take place in the Browser windows, and section 2.4.2 and 2.4.3 describe the underlying functions that might be useful in other programs.
2.4.1 Using Browser Windows
PIKS Browser windows act as menus in which one selects any displayed node to be operated on. There are two types of Browser windows: network windows, which show the graph of part of the network defined by slot relations; and frame windows, which graph the internal structure of individual objects. A frame window was shown FIG. 2. A network window is shown in FIGS. 4A and 4B. (Note: This window was generated for an expert systems application rather than natural language processing.) The nodes in Browser windows usually are the names of PIKS objects but, in frame windows, may be any LISP expression. When a node is selected with the left or middle mouse button, a submenu of operations relevant to that node pops up. Generally, the left button menus relate to examining and modifying things, whereas the middle button menus provide database search functions. In addition, when depressed anywhere in the window, the right button brings up a menu for editing the window's graph, with corresponding changes being made to the PIKS database automatically.
2.4.1.1 Left Button Menu
Selecting a node with the left button causes the Browser to examine the item to determine whether it has a frame, a function definition, and a binding, and also whether it is a root node of the window. Depending on which of these characteristics are different actions on the item are meaningful. A list of all such actions is constructed. If it has only one element, that action is taken immediately; otherwise the list is displayed in a pop-up menu for the user to select one. The possible actions are as follows.
Display Frame displays the selected node's frame.
SEDIT It calls SEDIT on the selected node's frame.
Edit Prompt prompts for changes to the object. First a menu of the object's slots is displayed, then when a slot is selected a menu of its facets will pop up; when one of these is selected (or if none is selected then the VALUE facet is assumed) a menu of its values will appear. Selecting one of these will cause it to be deleted and a new value will be prompted for in the mouse process window. To delete the old value without a replacement, enter NIL (or "]"); otherwise, type the new value. The slot, facet, and value menus contain entries for NEWSLOT, NEWFACET, and NEWDATA, respectively, in case one wants to add rather than change something. This prompting will cycle until nothing is selected from the slot or the value menu (i.e., the mouse is clocked with the cursor outside the menu window).
Fillin stores values of items as specified by the node's Template, which may be inherited from an AKO ancestor. If the selected node did not have any AKO VALUE, the user is first prompted to supply one. Fillin will not proceed further without this information. When it is filled in, the frame is displayed in another Browser window. If the node has no Template, Fillin is equivalent to Display Frame. Template definition and application are explained in section 2.4.1.1.1.
Instantiate prompts for the name of a new instance of the selected node and stores the name of the node in the AKO VALUE of the new instance, creating the new frame in this process. However, if the selected node did not itself have any AKO VALUE, the user is first prompted to supply one. Instantiate will not proceed further without this information. It will also refuse to proceed if the new instance already has an AKO VALUE. After the new instance is created, each item in its inherited Template, if any, is filled in as described in section 2.4.1.1.1. Finally, the new frame is displayed in a Browser window.
Make Template instantiates the object Template and installs the resulting object as the value of the selected node's Template slot.
Rename first sends an AboutToBeRenamed message to the selected node. If the response is DONT, the Browser will not proceed further. Otherwise, the user is prompted for a new name. If the name given is already that of a frame, the user is so advised and processing halts. Otherwise, the frame is renamed, and for each object named as a VALUE of any slot in the frame that has an inverse, the old name of the frame is replaced by the new name in the inverse slot VALUE in that object. Finally, the node's frame is displayed in a Browser window.
Destroy performs (KillNode Node) on the selected node (see section 2.3.2.3).
Recompute Graph recomputes the graph (which may have become invalid because of changes made by a user program) in the window and then redisplays it. This option appears only for root nodes.
Recomp&Preserve recomputes the graph and redisplays it, preserving the positions of any nodes that were in the original graph. This is useful for complex graphs whose topology has been modified by manual interaction.
Edit Fn appears in the menu if the node has a function definition. Selecting this item brings up a DEDIT window on the function. (Functions will typically appear in windows that display rule frames or frames holding demons or methods.)
Value appears if the node has a binding. Selecting this item causes the bound value to be printed in a TTY window.
Shift Selection is not a menu entry; it refers to selecting a node while the left shift key is down. This causes the name of the node to be unread into the current TTY buffer.
2.4.1.1.1 Template Definition and Application
Templates are used in the Instantiate and Fillin actions. They specify the normal slots and facets for descendants of an object along KINDSOF paths. A template may be created by selecting Make Template from the left button menu, or by instantiating the object Template (which is its own template) or any of its KINDSOF progeny. A template may contain two items of information for each facet of each slot: (1) the source of the value(s) and (2) tests (predicates) that each value must satisfy. The default source for any slot and facet is the function AskUserForVals, which prompts the user. There are no default restrictions, except that when instantiating a Template, any tests must be lists or the atom "!". An example of a template is given in FIG. 5. This is the default template for PIKS rules (see section 2.5).
A template is applied to an object Frame by Instantiate or Fillin as follows. First, the template is fetched (using FRAMEGET-Z) from Frame. Then information is fetched from Frame by FRAMEGET-Z, following AKO paths and with the template as Focus. This implies that object-specific information will override that in a template, and also that the information need not all come from one template. There may be a network of templates having information of varying degrees of specificity and for different slots and facets; some information may even be inherited from the slot objects.
The information fetched is: (1) a list of slots for Frame, in the case of Fillin, or for instances of Frame, in the case of Instantiate; (2) for each Slot, a list of facets; (3) for each Slot-Facet thus specified, a list of sources; and (4) a list of tests to be run to determine whether a candidate filler of the Slot-Facet is acceptable. All information will have been stored in the template when it was created via Make Template or Instantiate, or else inherited from an ancestor of the template or from the slot objects. The list of slots is stored in the Slots slot; the list of facets for a slot is stored in its Facets facet; potential sources are in the .fwdarw. (left arrow) facet of the Slot (in case of VALUE facets) or SlotFacet (the concatenation of the particular slot and facet names, in case of non-VALUE facets) slot; and tests are in the @ facet of the Slot or SlotFacet slot.
The list of fillers of Slot-Facet is generated from the sources and tests until a non-NIL result is produced. That result becomes the filler, and no further sources are tried. The process operates as follows. Each candidate source is in one of four forms: an atom, a quoted atom, a list of the form (=Slot.sub.2 Facet.sub.2), or a list of the form (Gx.sub.1 . . . x.sub.n). If the source is an atom its current binding is considered and if a quoted atom, then that atom; if that passes all tests, it is stored (using FRAMEPUT!) as the only value. This is intended for initialization of a facet with a single value whose name is stored in the template. If it is not a quoted atom, the source should be a strong, number, or variable whose binding can be found in the current stack context (i.e., a globalvar or specvar). If the filler is a list of the form (=Slot.sub.2 Facet.sub.2) then Slot.sub.2 and Facet.sub.2 are assumed to be the names of another slot-facet (if Facet is NIL, VALUE is assumed) which is to be filled first, and whose value is to be shared. If the source is of the form (Gx.sub.1 . . . x.sub.n), G is APPLIED to the list (Frame Slot Facet v.sub.1 . . . v.sub.n), where v.sub.1 . . . v.sub.n are the values bound to x.sub.1 . . . x.sub.n. It is APPLIED as a generator so that the tests may be run on each candidate value. Candidates that pass all tests are added to the slot-facet's list of values. This process loops until the generator Fn terminates, or until one of the tests indicates that there is to be a unique filler. A test may be the atom "!", which means that there is to be only one value, or a list, which is passed along with the candidate filler to TrueP. Fillers of the Slot-Facet value are accepted if TrueP returns non-NIL for all tests. A special case is a list whose first element is the atom Pattern (or Pat). In this case the CDR is assumed to be an Interlisp pattern, and a pattern match function is constructed Its name will be of the form "FramePat1234". Assigning this function to a file (e.g., during a CLEANUP) will result in its compilation (which makes it more efficient). As described in this section, templates are used by the Browser for interacting with the user to create or fill in an object. They may also be invoked by user-defined functions for automatic instantiation.
2.4.1.2 Middle Button Menu
Selecting a node with the middle button causes the Browser to examine the item to determine whether it has a frame, whether it has or inherits any demons, methods or properties, and whether any explanatory information is associated with it. Depending on which of these characteristics are true, different actions on the item are meaningful. A list of all such actions is constructed. If it has only one element, that motion is taken immediately; otherwise the list is displayed in a pop-up menu for the user to select one. The possible actions are described below.
Show Messages produces a menu of messages to which the object can respond. Selecting an item in this menu with the middle button causes the Browser to search for the frame from which its method is inherited. If that frame is in an active window, the window is brought to the top and the frame blinks; otherwise, the name of the frame is printed in the prompt window. If the item is selected with the left button and it has a method with a function definition, the name of its method is displayed in another menu titled "Edit Fn?". If the user selects the method in this menu, its definition is put in a DEDIT window. In any case, its name is printed in a TTY window. The method also blinks (about twice as fast as the middle button blinking) if it happens to be in any Browser network window or is the root of any Browser frame window.
Show Active Puts produces a menu of slots that have demons monitoring additions of values (via FRAMEPUT+). Left and middle buttoning in this menu have the same effects as for Show Messages, operating on demons instead of methods.
Show Active Dels produces a menu of slots that have demons monitoring deletions of values (via FRAMEREMOVE+). Left and middle buttoning in this menu have the same effects as for Show Messages, operating on demons instead of methods.
Show Active Fetch produces a menu of slots that have demons monitoring fetches of values (via FRAMEGET+). Left and middle buttoning in this menu have the same effects as for Show Messages, operating on demons instead of methods.
Show Variables produces a menu of all slot-facet pairs, including those that are inherits along AKO paths, but excluding methods, demons, and all facts on ancestors+ My, KINDSOF, and INVERSE slots. Left and middle buttoning in this menu have the same effects as for Show Messages, operating on the list of values of the selected slot-facet instead of methods.
Show Properties produces a menu of all properties, including property blockages (see section 2.3.8). The middle button functions as for Show Messages in this menu, operating on properties instead of methods. The left button has no effect.
Show Paths is used to create new Browser network windows. It puts up a menu of the selected node's slots. Any number of slots may be selected. Selecting OK from this menu notifies the Browser that the selection is complete. The user is then prompted for a restriction, which may be a number, an atom, a list, or NIL (equivalently: "]"). A window is then generated which contains the graph of all progeny along the selected slot links that satisfy the restriction, starting from the selected node. Nodes that lie on the path to such progeny but which do not themselves satisfy the restriction are also displayed, with "@" packed in front of their name. If the restriction was a number, n, then the first n generations of progeny of the node are graphed; if it was an atom, P, only progeny that (HasProp P) pass (P is not evaluated); if it was a list, (F a.sub.1 . . . a.sub.j), only progeny, p, for which (F p a.sub.1 . . . a.sub.j) returns non-NIL pass (a.sub.1 . . . a.sub.j are not evaluated).
Description sends a Describe yourself message to the selected node (see section 2.3.7).
Explain will appear only if the node is in an AuditSlot window and it was changed during rule application while rule auditing was on (see section 2.5.4). It produces a menu of two items: What and Why. Selecting What causes the node's Title (or AKO value if there is no Title) to be printed. Selecting Why produces an explanation of why the node was put where it is, assuming that the user has set up rules properly, as described in section 2.5.4.
2.4.1.3 Right Button Menu
Pressing the right button anywhere in the interior (i.e., not on the border or title bar) of a PIKS Browser window brings up a menu of graph editing options. These are as described in the Interlisp Grapher package documentation (Xerox Corporation 1985), but in addition, adding and deleting links and deleting nodes in the graph have been integrated with the PIKS database system (see Section 2.4.2 below). When a link in the graph is added or deleted, the corresponding frame structures are changed. When a node is deleted, all links to or from it in the graph are deleted, and all frames involved are changed accordingly.
When adding or deleting a link one first specifies the "from" node and then the "to" node (FIG. 14). In addition, if the window's graph represents more than one type of link, a menu will pop up with each link type; one must be selected (FIG.
14). When adding links in a frame window, the corresponding frame structure is not changed until a path of length 2 or 3 is established. All such path must originate from the root (i.e., the frame name) or no structural change occurs. A path of length
3, say from A to B to C to D, causes D to be stored in the C facet of slot B of frame A. For a path of length 2, say from A to B to C, the user is asked whether C is to be a VALUE or some other Facet of slot B; if a value, then the structure is changed; otherwise, no structural change is made until the next link is added.
Note that PIKS permits arbitrary structures as values of facets. To handle these properly when adding and deleting links through the right button menu, the global variable ShowParens should be set to T. Also note that when adding a node, the label entered is not EVALed.
2.4.1.4 Right Button Background Commands
Occasionally, one wants to display a frame or graph whose root does not appear in any window. Two PIKS items have been added to the Interlisp background menu to provide for such situations. These are SpawnFrameW and SpawnPIKSW. The former has the same effect as Show Frame from the left button menu, except that the user is first prompted for the root node, which must be an atom, and also for the font, format, and label (see section 2.4.2) if global variable FontFmtPrompt is non-NIL. SpawnPIKSW is like Shot Paths from the middle button menu, but the user is prompted for the roots (there may be more than one; enter NIL or "]" to terminate prompting), the paths and, if FontFmtPrompt is non-NIL, the font, format, and label.
2.4.2 PAKTUS Graphic Programming Functions
FIGS. 53A through 55B give flow chart schematic diagrams of various graphic programming functions used in the PAKTUS ATN grammar development (Section 3 of the application). The AddNodeFn function 845 (FIGS. 53A and 53B) adds a node (855) or an entire subnet (863) to a PAKTUS Browser window. A single node can be copied from any existing Browser window by selecting it with the mouse (849), or its label can be typed in (861). An entire subnet can be added (863) by mouse-selecting the subnet root in an existing window (869) and then selecting the node in the original window (877) to which the subnet is to be appended (881, 885, or 889). Tests (879, 883, 887) restrict the resulting structures to be valid PAKTUS frames.
The AddLinkFn function 899 (FIGS. 54A and 54B) adds a link between two nodes in a Browser window. The user is prompted to select the From and To nodes (901) for the link. For the present purpose, there are two types of Browser window (905): a Frame window (915) and a graph window (907). Graph windows hold their linkage path names on a property; if there is more than one path displayed in the window, then the user is prompted to select from a menu the type of link desired (909). In either case, the link is then established (911) in the PAKTUS objects represented by the nodes. For a Frame window, it must be determined whether the from node is a Facet (915), a slot (921), or the frame (937) to determine (923, 927, 931, 941, 945, 949) what paths are valid, and how to add the link (917, 925, 933, 943, 951).
The DeleteLinkFn function 955 (FIGS. 55A and 55B) prompts (957) for the From and To nodes from which to delete the link. If the window holds a graph, the type of link it displays is removed from the nodes (967) after first asking the user which type of path (965) if the window displays more than one (963). For a Frame window, the type of structural change to the frame depends on the type of From node (971, 977, 987) and To node (979).
2.5. Rule-Based Programming in PIKS
2.5.1 Introduction
Rules in PIKS are objects that specify actions to be taken or conclusions to be drawn in a given context. The PIKS kernel contains the object RULE and its template RuleTem. Particular rules can be created as instances of RULE or of any user-defined subclass (i.e., KINDSOF progeny) of RULE. The two most important slots of a rule are Context and Then. context specifies when a rule is relevant. It may be thought of as the "if" part of a rule. A rule can be applied only when every element of its Context value is true. The Then slot specifies what is to be concluded or done when a rule's Context is true and the rule is applied, or "fired".
2.5.2 Rule Base Structure and Rule Invocation
Rules are invoked by being passed to the function TRYRULE, which tests a rule's conditions and executes its actions if all conditions are true. the calling syntax is: TRYRULE [Requestor Rule]. Requestor is an object associated with the rule. The assumption is that rules are partitioned into small sets, each representing expertise about a very specific domain. Requestor is the domain specialist object that holds and processes information about the current state of affairs in that domain. PIKS does not force one to organize rules in this way (one may call TRYRULE [NIL Rule]), but it is often useful to do so.
There are basically two ways to cause a rule to be tested: user programs can invoke TRYRULE directly; or a domain specialist object can be initialized on the PIKS Agenda by invoking SetPriority [Object Weight]. Weight is a numerical index intended as a measure of the relative importance of the reason for putting Object on the Agenda. If the Agenda is to be used, PIKS provides the function ScheduleAgenda, which is a simple algorithm for scheduling the domain specialists on the Agenda based on their intrinsic importance and on how long ago they were last serviced. ScheduleAgenda should be run as a separate process.
The operation of the scheduler and Agenda may besl be expIained by reference to an example. FIG. 6 shows the Agenda and a domain specialist object (UR3140, which is a specialist on augmentation of tactical air forces operational structure) and an associated rule from a PIKS application. Items on the Agenda were put there by application specific routines via calls to SetPriority. The scheduler continually cycles through the Agenda items, recomputing their Priority.
On each cycle, the item of highest Priority is selected and its Status Evaluation rules are tested. If none of these rules fire, the item's Priority is lowered by multiplying its current value by its Weight, as a percentage. For example, suppose UR3l40's Priority of 0.6495191 is the highest of any item on the agenda in the current cycle. then its Status Evaluation rule, ER3140#1, is tested by the scheduler by calling TRYRULE [UR3140 ER3140#1]. (Note that UR3140 is A Kind Of XX3140, from which it inherits information, and that it is passed to TRYRULE along with the rule; this gives the rule access to all information in UR3140 and its ancestors.) If the rule's conditions are not true, then UR3140's Priority will be lowered to
0.4221874 (=0.6495191 * 65%). Whenever a Status Evaluation rule's conditions are all true, the rule fires (its Then are executed), but the scheduler does nothing else to its associated specialist. In particular, it does not change the priority of the specialist or remove it from the Agenda. It is the responsibility of the rule to do these things, if appropriate. In the example, ER3140's last action is to remove its specialist from the Agenda.
In summary, one may either have PIKS manage rule processing or write programs that call TRYRULE directly. In the former case, the rules must be stored in the Evaluation rules facet of the Status slot of some specialist objects, and user-defined functions must put some of these specialists on the Agenda, using SetPriority.
2.5.3 Internal Structure of Rules and Rule Application
FIG. 6 included the rule ER3140#1, which illustrates the major constituents of a rule. FIG. 7 shows another rule from the same application. The two most important slots of any rule are Context and Then. Weight and Priority are application dependent and not necessary in the basic PIKS rule processing. (They could be used in a rule that is to be put on the Agenda and that has Status Evaluation rules, thus providing the capability for rule activations through a network.) LocalVars should be specified if bindings are to be passed among constituents of the rule (see below) or if rule explanations are desired, in which case the Text facet of the Context should also be supplied (see section 2.5.4). The Then slot has two facets: Facts and Actions, which are explained below (The rules in FIGS. 6A through 7B have only Actions.) Other slots may be added for particular applications (e.g., Essential data in the rule in FIGS. 7A and 7B). The most convenient way to create a rule, ensuring that its components are in the proper format, is to instantiate the object RULE or any of its KINDSOF progeny.
A rule is applied by passing each element of its Context VALUE to the function TrueP, along with the TRYRULE Requestor; if all are true (testing them returns non-NIL) the rule's Then are applied. A test specified in the Context can be in one of the following forms:
(a) (GlobalRecall F.sub.1 . . . F.sub.n)
(b) (LocalRecall F.sub.1 . . . F.sub.n)
(c) (F x.sub.1 . . . x.sub.j)
(d) (OR (Test.sub.1) . . . (Test.sub.i))
(e) (NOT Test)
In case (a), for each F a Recall message is sent to th global object CONTEXT, which contains the Agenda and list of facts deduced or told to the system by the user. CONTEXT has a default method for this message, which is to fetch the DEDUCED and TOLD slots of CONTEXT and APPLY F to each such fact until the result is non-NIL or the lists are exhausted. PIKS was designed on the assumption that each F is an Interlisp pattern function, but any user-defined function may also be Supplied. In case (b), for each F, A Recall message is sent to the TRYRULE Requestor (see section 2.5.2) with F as an argument. The user must define and install Recall methods on objects that are to receive Recall messages In case (c), F is APPLIED to the list (Requestor x.sub.1 . . . x.sub.j) where Requestor is the first argument passed to TRYRULE. In (d) and (e), each Test is one of the forms a) through e) (without the extra parentheses; for example, (OR (LocalRecal F) (NOT G x y z))). The result is true in (d) if any Test is true; and in (e) if Test is not true.
Typically, the LocalRecalls and GlobalRecalls will be stored first in a rule and will be pattern-matching functions that bind variables (which should be listed in the rule's LocalVars if previous bindings are to be restored). The resulting bindings will then be available to other predicates. For example, when the rule RAR3561#1 shown in FIG. 7 is tested, it first applies two pattern matches which bind variables PLACE Combat aircraft, etc. Then the other functions in its Context may use these bindings, such as the predicate TensionAreaP, which is passed the value bound to PLACE.
If all tests in the rule's Context are satisfied, its Then are applied. Items in its Then Facts facet are stored in the DEDUCED facet of CONTEXT (from which they may be retrieved later by a rule's GlobalRecall). Items in the Then Actions facet must be lists in one of the following forms:
(a) (F x.sub.1 . . . x.sub.n)
(b) (.rarw.Self M x.sub.1 . . . x.sub.n) or
(c) (.rarw.Object M x.sub.1 . . . x.sub.n).
2.6 Object-Oriented Database System
PIKS provides for automatic swapping of objects between virtual memory and random access files. The PIKS user must specify (e.g., in the user INIT file) the databases that contain the objects and must initialize the files. The PIKS Browser will then swap objects into virtual memory as needed. PIKS provides user-selectable menu items to write out changed objects PIKS notices changes to database objects if made by PIKS functions. PIKS maintains past instances of objects in such a way that one can roll back to a previous version of a database. One may also browse through different versions of a particular object and reset it to any one of these. A PIKS database requires a hash file for storing objects on disk.
3. INTERACTIVE GRAPHIC PROGRAMMING ENVIRONMENT
3.1 Introduction
In the present invention, applicants have utilized the PIKS programming functions and techniques discussed above to create an interactive graphic programming environment. This programming environment is the subject of commonly assigned U.S. Pat. Application, Ser. No. 195744 filed May 18,1988,R. Bruce Loatman and Chin-King Yang, entitled "INTERACTIVE GRAPHIC NATURAL LANGUAGE PROGRAMMING SYSTEM", filed of even date herewith. Such graphic programming environment comprises an important part of PAKTUS. In such programming environment, nodes represent states and transitions in an augmented transition network ("ATN"). Transition nodes specify stat transitions and can contain arbitrary production rules. They can be created, modified, deleted, and moved through direct user interaction. The internal structure of nodes can also be viewed graphically. An interpreter reads the graph and applies the production rules to the input.
The ATN-based environment of the invention comprises a program, considering both the graph (which defines the overall logical structure) and the information in the nodes. In the ATN application of the preferred embodiment for NLU applications, such programs may be considered a grammar and the interpreter may be called a passer. The ATN programming environment of this invention, however, is a general purpose programming language which may be used for other than NLU applications.
In an operative embodiment of the invention as illustrated in FIG. 46, the hardware elements of this ATN programming environment included computer 990 (Xerox 1186 of Xerox Corporation, with 3.5 megabytes RAM and 16 megabytes virtual memory), keyboard 988, and optical mouse pointing device 992 with left button 994, middle button 996, and right button 998.
3.2. ATN Grammar
3.2.1 Basic Elements of ATNs
The ATN grammar consists of several networks. Each is a directed graph with labeled states and arcs, including distinguished initial and final states. The states are represented as PIKS objects and have"InArcs" and"OutArcs" slots. The InArcs slot lists the transition arcs that go to the state, and the OutArcs slot lists those that lead out from the state. Some states do not have an InArcs slot. These are entry points into the network containing them. The final state is labeled as"*FIN" for all networks. It as no OutArcs. By convention, the name of a state usually either starts or ends with the symbol".uparw." except the initial and final states and a few other exceptions. (This convention is purely for the convenience of the grammar writer.) Each arc is also represented as a PIKS object and must have ToState, FromState, and label slots. It may also have Rule and Init slots. The Label slot of each arc indicates its type as explained below. The Rule slot contains a PIKS object which holds conditions and actions associated with the arc. The name of an arc is not used by PAKTUS.
3.2.1.1 Classification of Arcs
The ATN grammar can contain four different types of arcs, each of which is described below. Reference may be had to Winograd (1983) for a prior art discussion of these arc categories.
Category arcs: If the value of a Label slot is a lexical category or a function, then the arc is a category arc. When a category arc is encountered in parsing with a network, a single input word is matched against the specified category. The match consists of checking that the word is related to the category through AKO (A Kind Of) links or, if the Label is a function, it is APPLIED to the word and the match is successful if the result is non-NIL. In the PAKTUS system, this matching process returns just those senses of the word that match, and this subset replaces the definition of the word for the remainder of the parse. If parsing backs up to this point again, the previous definition is restored. This word definition is typically assigned to an appropriate syntactic register by the actions associated with the arc, and the transition is made to the next state. The input pointer then moves to the next word.
Seek arcs: If the Label is a state, then the arc is a seek arc. When a seek arc is encountered, the register list is pushed onto a stack, a new register configuration is set up, and any initializations in the Init slot are passed to PIKS function TrueP. If no initializations return NIL, the parser branches to the specified state, which may be in the current network or another one. If that network is traversed successfully, Rules on the seek arc are then tested (by TrueP), and if none returns NIL the register list is restored (the stack is popped) and the parser advances to the state to which the seek arc leads.
Send arcs: A send arc is labeled with the symbol "Send". When a send arc is encountered, it means that the network has been traversed successfully. The parser branches back to the seek arc that called the current network. `Jump arcs: The jump arcs are labeled with the symbol"Jump" and are taken without consuming any elements of the input. The rules associated with the arc must hold. These arcs usually correspond to branches around optional syntactic constituents. Some jump arcs, however, consume the current Hold register or copy some register from the current network or from one that invoked it with a seek arc.
3.2.1.2 The Use of Registers in ATN Grammars During sentence parsing, the register list is an association list of syntactic name/value pairs such as Subject/NP.sub.1 where NP.sub.1 is the noun phrase filling the Subject register. The register list is the major data structure holding the information about the parse. The value of a register will normally be a dotted pair of the form (Lex . WordDef.sub.j) where WordDef.sub.j is the PAKTUS definition of the word consumed by a category arc, or another register list which was built when traversing a seek arc. Thus, the register list is a network whose topology maps the successful paths taken so far in the parse. The top level, or"root" register is the distinguished symbol"S" and its value is the list of registers for the primary clause of the sentence. Register lists returned by seek arcs are assigned to appropriate registers at the upper level during the pop action. The paths from the leaves to the roots or from the roots to the leaves are available at all times. This provides ready access to any register from any arc during the parse. This facility, which Boguraev (1983) calls"cross-level communication", is a major improvement of the ATN programming technique of the present invention over the prior art (beyond the major advantage, graphic programming capability). It gives great power to the grammar writer to solve difficult syntactical problems like gapping in coordinate conjunctions; see section C3. below.
The functions which are used to manipulate the register list are designed in a space-conserving and efficient manner. The detailed descriptions are as follows:
GETR [RegList Register] returns the value of the indicated Register from the specified RegList. RegList can be a register list or an atom bound to a register list. The function GETR searches the list from front to back for the most recent occurrence of the named Register and returns the associated value. (The same register may have been set many times, since the grammar is invoked recursively as, for example, when a relative clause is embedded in an NP that is embedded in a PP that is in a clause, etc.) If the register has never been set, it returns the value NIL but does not cause an error.
SETR [RegList Register Value] sets a register. RegList must be an atom bound to a register list; otherwise, SETR causes an error. The function SETR does not change the name/value pair in the register list but instead adds to the front a new name/value pair. The new pair will effectively hide from the function GETR any old pair with the same name. Only the pointer to the current front of the list needs to be used at any given time, and look-up time is minimized. Subsequent seek arcs can freely change register settings without confusing the previous network if backup should later be required.
ADDR [RegList Register Value] is the same as SETR except that it takes the previous contents of Register, adds Value to it, and puts the result at the front of RegList. This is provided for registers that may hold more than one value, such as auxiliary verbs, adjectives, prepositional phrases, etc.
3.2.1.3 Conditions and Actions
The conditions and actions are presented in the form of PIKS rule objects (see Section A5 above) and stored under the Rule slot of an arc. In order for the arc to be taken, its conditions must hold for the current state of the parse. When this happens, the associated actions are carried out, usually causing the current network's registers to be filled with structures representing syntactic constituents of the clause recognized by the network. Most conditions and actions are register access functions. These functions are automatically generated by PAKTUS if they are put into a rule by the Instantiate and Fillin options of the PIKS Browser and the rule is descended from the object"RULE" through KINDSOF links (the inverse of AKO links). Alternatively, they may be produced by invoking code generation functions as follows:
LexT.RTM.st [STR] is a function generator which generates LISP code. Illustratively, this uses the notation adapted from Winograd (1983). STR is a string of symbols separated by periods. the leftmost symbol must be either"*" or".uparw.". The rightmost symbol must be a function. LexTest generates a function which takes two arguments. The first argument is a register list. The second is a value. The function retrieves a value from the register list through a series of calls to GETR according to the registers specified in STR (e.g., if STR = '*.Subject.Head.Num.Fn, the value of the Num register of the Head register of the Subject register of the current network's register list is fetched), then APPLYs the rightmost symbol of STR (which must be a function) to the list consisting of the retrieved register value and the second argument. Some of the special notations are explained as follows:
* is a global variable called STAR. It will be bound to a CONS cell of the form (Lex.WordDef) for a category arc, and to the register list of the containing network for other arcs.
.uparw. refers to the register list which is a level above the * register list (i.e., to the network containing the seek arc that invoked the STAR net). .uparw...uparw. refers to the register list a level above the .vertline. register list, .uparw...uparw...uparw. to the next level, etc.
The symbol"Lex" may be included in STR. In the PAKTUS system, it is a special register that can only be at the second or third position from the right of STR, and it holds the subset of the definition of an input word meeting the contextual specifications of the arc that accepted it. (For example, if the word"saw" was accepted by a Verb arc, its Noun sense is ignored henceforth in the parse unless it backs up to this point later. This helps eliminate ambiguity and prevents inconsistent decisions.) While at the second position from the right, it simply retrieves the word definition. While at the third position from the right, it applies GetForm to the retrieved definition plus the second element from the right, and then passes the result to the function at the rightmost position of STR.
GetForm [WordParse Dim] fetches the value of the Dim feature (or"dimension") of the word whose senses are listed in WordParse.
LexSet [STR] is a function generator which generates LISP code in a manner like LexTest, but it is intended for functions that set registers. STR is a string of notations separated by periods. The symbol third from the left is either a SETR sign".rarw." or an ADDR sign".rarw..rarw.". The symbols on the left hand side of the .rarw. must start with either"*" or".uparw." and be followed by a period and a register name. LexSet generates a function which takes a register list as argument. The function retrieves the value from the register list specified on the right of the .rarw. and applies SETR or ADDR to the register specified on the left hand side, storing the retrieved value there. For example, LexSet [.uparw..Subject.rarw.*.PrepObj] constructs a function that sets the Subject register of the parent network to the PrepObj register of the current network.
3.2.1.4 Initializations; Look-Ahead Tests
The seek arcs are the only arcs which have a Init slot. Initializations which are stored in this slot can provide actions and tests. When seek arcs are encountered, the forms on the Init slot are evaluated first. If any of the actions returns NIL, then the seek arc is not taken. Therefore any look ahead actions are always specified on the Init slot. These actions typically look two or three words ahead, or at the context in which the current clause is embedded, to decide whether or not the seek arc is feasible. In the PAKTUS grammar, such look-ahead actions greatly reduce the need for backing up, and almost make the parser deterministic for sentences that can be recognized by the grammar at all. (That is, sentences that are not parsed in linear time usually can not be parsed at all.) Initializations can also be used to set up initial register settings for the network about to be entered.
FIGS. 56A through 56C is a flow chart schematic diagram of a look-ahead test invoked by PAKTUS to determine whether the parser should consider whether a relative clause is present. The test 993 of FIG. 56 is invoked in parsing a noun phrase after the parser has encountered the head of the phrase. (Another relative clause look-ahead test, for participle relative clauses, is discussed below.) Routine 993 evaluates one or more subsequent words of the text (unlike the look-ahead test discussed in Marcus (1980), it is capable of handling any number of words) to determine whether (primarily) syntactic features of the text point to the possibility of a relative clause. A positive result,"return T", permits the parser to continue to look for such a clause while a negative result,"NIL", avoids a continued search for a relative clause potentially resulting in a considerable saving of processing time. This routine retrieves the next word of input ("WD") and returns T if WD is a relative pronoun, at
997, 999. At 1001, 1003, 1005, this test returns NIL if WD is a pronoun (not a relative pronoun) or a unit of time. At 1007, the parser looks at the configuration of the phrase in which the noun phrase is embedded and returns T if the tests shown are passed. At 1011, PAKTUS evaluates whether the next word is the beginning of a noun phrase that is followed by a verb, possibly with intervening adverbs, and returns NIL if this test fails.
If the test at 1011 succeeds, the remainder of the routine beginning at 1015 looks at the entire sentence to determine if there are enough verbs remaining for a relative clause to be present (i.e., without consuming the main verb of the sentence). If the MainVerb register of the top-level (sentence) network is filled, clause is set equal to the configuration of the parent clause (at 1037) and one or more of the tests shown at 1039, 1041, and 1043 are effected resulting in either a return T or return NIL decision.
If the test at 1015 fails, the loop at 1017, 1019, 1023, and 1025 tests successively higher level clauses repeating the loop if the MainVerb register of the clause is filled (and test 1019 fails). In these tests, if the clause is NIL or conjunctive (at 1019) the program flow jumps at A to the steps at 1037 and following, discussed above. Otherwise, if the main verb of a clause is not filled, the routine looks for the next verb or conjunction in the sentence, carries out one or more of the tests shown at 1029, 1031, and 1033, and either returns NIL (1045) or jumps at A to the previously discussed branch at steps 1037 and following.
The look-ahead test routine discussed above has only a minor degree of semantic content. PAKTUS also incorporates look-ahead tests embodying significant semantic features, another point of novelty over Marcus (1980). For example, in the test for the presence of a participle relative clause, when a past participle follows a noun, the system evaluates whether it may be part of a participle relative clause. The system considers each concept associated with the verb. For each such concept, PAKTUS carries out a partial instantiation of case frames of the relative clause that would be produced to see whether the noun could play a role which will be appropriate to its inclusion in the case frames for that concept. (See section 5, below, for a discussion of case frames.)
3.2.1.5 Some Useful Context-testing Functions
The following functions are frequently used in context tests on the grammar arcs.
HasFeature [WordParse Feature Clause] returns the senses in WordParse that have Feature, if any; otherwise NIL. Feature is intended to be a list of two elements: a word category (or list of categories) and a complement type (or list thereof). Senses not satisfying the Feature specification are discarded (e.g., a verb may be both monotransitive and bitransitive; if an arc requires a bitransitive verb then the monotransitive sense is"forgotten" for the remainder of the parse to prevent inconsistent decisions later). See arc dS/ze while using PAKTUS for an example of its usage.
IsLexCat [WordParse, CAT CLAUSE BlockCat] is used for matching a specified CAT, which is a lexical category (or list thereof), with WordParse which is the senses for a particular word. It returns a dotted pair whose CAR is the senses which belong to CAT, and whose CDR is the access path to the CAT, if a match is found; NIL otherwise. Paths through BlockCat are not considered.
3.3 The ATN Interpreter
3.3.1 PAKTUS Interpreter
The preferred embodiment of this invention utilizes a top-down, left-to-right, depth-first ATN interpreter or "parser". The interpreter applies the grammar to an input string (a list of words). It keeps a pointer to the current position in the input list, and current context (register configuration). As stated above, each network consists of a set of states and arcs. The arcs specify allowable transitions between states. Each arc has a label indicating the type of transition. Category arcs name (in their Label slot) the category to which the next Word in the input string must belong. When they are traversed, the position pointer is advanced to the next word. Seek arcs specify a recursive call to one of the transition nets, entering at the state indicated in the Label. If that net can be traversed, then processing resumes back in the net containing the seek arc. Jump arcs specify a transition to another state without consuming any input. Finally, the send arcs specify an exit from the net, returning to the net from which the current one was called, if any, or else to the top level. In the latter case, if all input has been consumed, the interpreter returns with successful completion.
Any arc can have rules stored in it. These are run after the arc is traversed (i.e., after a word has been tested for a category arc, or a net has been traversed for a seek arc). The transition to the next state will be completed only if the rules succeed. Each rule can specify context that must be true and actions to be taken in that case. The context specifications and the actions generally test and set registers associated with the current network (in such a way that old settings can be restored if necessary). See Section 2.5 above for further details of rule application.
In general, a state can have several arcs leading out of it to other states (or looping back to itself). When an arc is traversed, the PAKTUS interpreter maintains a stack of alternatives leading out of the same state that have not yet been tried. This stack contains all the information necessary to restart the parser at the point at which the alternative was created. This enables it to back up to this state and restore context if it is unable to successfully process the input along the attempted path. It can back up to this state even if it subsequently exits the current net (i.e., if this net were invoked by a seek arc).
The current interpreter returns as soon as it finds a path through the top-level net that consumes all input. (In an alternative embodiment for other applications, this may be modified to return all acceptable paths.) It returns the register configuration that was built in the cours