Open Collections will be undergoing maintenance Monday June 8th, 2020 11:00 – 13:00 PT. No downtime is expected, but site performance may be temporarily impacted.

Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A frame system model of the representation of knowledge for understanding natural language McDonald, David Blair 1975

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1975_A6_7 M32_2.pdf [ 6.44MB ]
Metadata
JSON: 831-1.0051778.json
JSON-LD: 831-1.0051778-ld.json
RDF/XML (Pretty): 831-1.0051778-rdf.xml
RDF/JSON: 831-1.0051778-rdf.json
Turtle: 831-1.0051778-turtle.txt
N-Triples: 831-1.0051778-rdf-ntriples.txt
Original Record: 831-1.0051778-source.json
Full Text
831-1.0051778-fulltext.txt
Citation
831-1.0051778.ris

Full Text

A FRAME SYSTEM MODEL OF THE REPRESENTATION OF KNOWLEDGE FOR UNDERSTANDING NATURAL LANGUAGE by DAVID BLAIR MCDONALD B . S c , U n i v e r s i t y of B r i t i s h Columbia, 1974. A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n the Department of Computer Science We accept t h i s t h e s i s as conforming to the re q u i r e d standard The U n i v e r s i t y of B r i t i s h Columbia August, 1975 In present ing th is thes is in p a r t i a l fu l f i lment of the requirements for an advanced degree at the Un ivers i ty of B r i t i s h Columbia, I agree that the L ibrary sha l l make it f r ee ly ava i l ab le for reference and study. I fur ther agree that permission for extensive copying of th is thes is for scho la r ly purposes may be granted by the Head of my Department or by h is representa t ives . It is understood that copying or p u b l i c a t i o n of th is thes is for f i n a n c i a l gain sha l l not be allowed without my wri t ten permission. Department of fa ftp'//T£/Q SC/gstt£ The Univers i ty of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date Z£m /??<T A Frame System Model f o r Understanding Natural Language i Abstract A model f o r the representation of knowledge i s described. I t was developed i n the domain of teaching a student how to draw simple f i g u r e s on a graphic terminal's screen. The student should not need to know anything about computers or graphics and should i n t e r a c t with the computer using a subset of E n g l i s h . The model was designed to represent the knowledge needed to understand sentences encountered i n t h i s domain. The model i s based on the ideas i n Minsky's frame systems, Hewitt's a c t o r formalism and semantic network theory. The basic components of the model and how they are used to represent knowledge i s presented. A d e t a i l e d example i s described, g i v i n g some d e t a i l s of how the system performs i n f e r e n c e s and how i t responds to various i n p u t s . F i n a l l y some conclusions are drawn about the design of t h i s r e p r e s e n t a t i o n f o r knowledge. A Frame System Model f o r Understanding Natural Language i i Table of Contents Chapter 1: I n t r o d u c t i o n ... ........ .............. 1 1. D e s c r i p t i o n of the Problem Domain ..................... 3 Chapter 2: A B r i e f Survey of Relevant Work 8 1. Minsky's Frame Systems 8 2. Hewitt's Actor Formalism ............................. 11 3. Semantic Networks 13 4. Fahlman's Work on Frames ............................. 15 Chapter 3: The Basic Components of the Model ................ 18 1. The Str u c t u r e of Frames .............................. 18 2. D e f i n i t i o n of Frames .................................... 20 3. Error Processing ..................................... 27 4. Infe r e n c i n g and Demon Processing 29 5. Context and Focus .................................... 33 6. Representation of Nouns .............................. 37 7. Representation of P r o p e r t i e s 42 8. Representation of R e l a t i o n s .......................... 46 9. Representation of Actions or Verbs ................... 51 Chapter 4: The Model i n Use ................. ............ 55 1. S p e c i f i c a t i o n of Top Level Frames ..................... 55 2. A D e t a i l e d Example 59 3. Comments on the Example 95 Chapter 5: Conclusions .......................-............. 101 Bibli o g r a p h y ................................................ 107 Appendix 1: A B r i e f D e s c r i p t i o n of Conniver ........ ...... 109 1. The Conniver Pat t e r n Matcher ........................ 109 2. The Conniver C o n t r o l Structure ......«.,............. . 112 Frame System Model f o r Understanding Natural Language 3. The Conniver Data Base A Frame System Model f o r Understanding Natural Language i v Table of Figures Figure 1 .................... .. ............................ .. 62 Figure 2 ....................................................... 67 Figure 3 ..................................................... 68 Figure 4 ....,,..,,........................<....... . .......... 71 Figure 5 ...................................................... 73 Figure 6 ..................................................... 75 Figure 7 .................................................... 77 Figure 8 81 Figure 9 ....... ... ... 82 Figure 10 .................. ....... . ............... 84 Figure 11 ....... .--,....»......-..... 87 Figure 12 ..... 89 Figure 13 ................................................... 91 Figure 14 ..................................................... 93 Figure 15 ........... .... ................ .......... 94 A Frame System Model f o r Understanding Natural Language v A£KH2wiS^5[sment The f i n a n c i a l a s s i s t a n c e of the Department of Communications and the National Research C o u n c i l of Canada i s g r a t e f u l l y acknowledged. A Frame System Model f o r Understanding Natural Language 1 Chapter _1. I n t r o d u c t i o n This t h e s i s describes a model of the rep r e s e n t a t i o n of knowledge f o r understanding n a t u r a l language. The f i r s t chapter gives a b r i e f i n t r o d u c t i o n to the problem domain. The second chapter contains a b r i e f survey of the more important papers t h a t i n f l u e n c e d t h i s t h e s i s . The t h i r d chapter describes the basic components of the model and some of the b u i l t i n f u n c t i o n s that the system uses. The f o u r t h chapter goes i n t o the d e t a i l s of the frames that are necessary to process n a t u r a l language and al s o goes i n t o a d e t a i l e d example of how the frames i n t e r a c t to understand E n g l i s h sentences. F i n a l l y some conclusions about frames and t h i s system are presented. In a r t i f i c i a l I n t e l l i g e n c e there has been a great deal of e f f o r t to develop a r e p r e s e n t a t i o n f o r knowledge. Considerable e f f o r t has been devoted to the problem of developing a method to handle l a r g e amounts of both procedural and d e c l a r a t i v e knowledge. The l a c k of a d e f i n i t e model f o r representing knowledge has been a major stumbling block f o r A r t i f i c i a l I n t e l l i g e n c e over the past few years. There have been some s u c c e s s f u l p r o j e c t s c a r r i e d out which s a t i s f a c t o r i l y handle a very s m a l l subset of knowledge possessed and used every day by a human being. These systems have not been e x t e n s i b l e to any great degree beyond the domain f o r which they were designed. So f a r there has been no model which can adequately represent and A Frame System Model f o r Understanding Natural Language 2 process information at the l e v e l of competence of a person. Computers have been used to g r e a t l y speed up the amount of computation that people can do i n a given time period. However, t h i s great speed can only be used to solve s p e c i f i c w e l l defined problems with a w e l l defined s o l u t i o n i n a given domain. Programs can be w r i t t e n which can solve many d i f f e r e n t problems i n a domain. However, once any input from outside t h i s domain i s given, the program i s completely l o s t and w i l l e i t h e r give an aknowledgement of i t s l o s s f o r a s o l u t i o n ( i f the programmer has foreseen t h i s problem), give i n c o r r e c t r e s u l t s or may even produce a program i n t e r r u p t . Computers have allowed p h y s i c a l and s o c i a l s c i e n t i s t s to perform tasks which would otherwise be impossible- However, there i s no room f o r e r r o r i n the input. I f i n c o r r e c t input i s given t o a program, then the program w i l l produce i n c o r r e c t answers ( i . e . garbage i n , garbage o u t ) . Humans on the other hand are " i n t e l l i g e n t " i n the sense th a t i f presented with i n c o r r e c t i n p u t , they w i l l normally n o t i c e t h i s and e i t h e r complain or make some assumption about why the input i s i n c o r r e c t and c a r r y on from there. In the domain of computational l i n g u i s t i c s when a parser i s presented with a s y n t a c t i c a l l y i n c o r r e c t sentence and i s unable to parse the sentence, then normally the program w i l l j u s t f a i l and say something l i k e " I couldn't understand t h a t , please t r y again". People, however, i n most cases seem to have the a b i l i t y t o d i g e s t s y n t a c t i c a l l y i n c o r r e c t sentences and s t i l l understand t h e i r underlying meaning. This i s more of a c r i t i c i s m of the A Frame System Model f o r Understanding Natural Language 3 standard approach to the s o l u t i o n of problems i n Computational L i n g u i s t i c s than a statement that computers w i l l never be able to understand n a t u r a l language. what must be done i s to take a approach which uses semantics at the same time as the operation of parsing i s performed and p o s s i b l y suspend the parsing of the whole sentence and j u s t parse c o n s t i t u e n t s such as noun phrases, p r e p o s i t i o n a l phrases, verbs, e t c . In t h i s t h e s i s a model f o r representing knowledge i s proposed. This model i s not f u l l y developed yet and s t i l l needs much work. The model was developed from problems associated with teaching a person who knew nothing about computers how to use a graphics t e r m i n a l . A b r i e f d e s c r i p t i o n of t h i s problem domain and some of the problems associated with i t w i l l now be described. 1.1. D e s c r i p t i o n of the Problem Domain The motivation f o r t h i s t h e s i s arose from a p r o j e c t c a r r i e d out at the U n i v e r s i t y of B r i t i s h Columbia t o develop a computer program which would be able to teach a person who knew nothing about computer graphics how to use a graphics t e r m i n a l . The computer was to i n t e r a c t with the student using a subset of E n g l i s h , so that the student would be more at ease. The idea was to d i s p l a y a scene or f i g u r e such as a simple house and then have the student reconstruct t h i s f i g u r e , by asking the computer (in English) to draw subcomponents, to move subcomponents about the graphics screen, e t c . This was meant to A Frame System Model f o r Understanding Natural Language 4 give the student a f e e l f o r the c a p a b i l i t i e s of a graphics t e r m i n a l . Hhen the student had f i n i s h e d t h i s phase, he would be shown how to use the hardware features of the graphics t e r m i n a l to perform the same tasks much more e f f i c i e n t l y and e a s i l y . As f a r as n a t u r a l language understanding was concerned the f i r s t phase of the teaching session would be by f a r the most d i f f i c u l t . In the second phase, the student would most l i k e l y be asking only f o r new components to be drawn and then manipulate them using the graphics hardware. The student at t h i s point might want to ask questions about how to do something using the graphics hardware f e a t u r e s . This s o r t of dialogue has been handled very w e l l by such systems as SCHOLAR [ 3 , 5 ] and SOPHIE[2 ] using semantic networks. The f i r s t phase must be able to understand and respond to f a r more d i f f i c u l t utterances. The f o l l o w i n g sample sentences could a r i s e when the student i s asked to draw a simple house. < ! J Sentence J Action J 1 + 1 |Draw a b i g j T h i s sentence i s easy to handle and a j \square. l b i g square w i l l be d i s p l a y e d on the I i j graphics screen. I I ^ 1 |Hake i t bigger. JThe anaphoric reference " i t " must be 1 } I disambiguated. In t h i s case there i s I | |only one p o s s i b l e candidate and so the | | \square w i l l be made bigger. J I -j 1 (Draw a t r i a n g l e , 1 This sentence i s easy to handle. The | 1 |knowledge that the t r i a n g l e w i l l | | |eventually form part of the house may I 3 \be used to perform i n f e r e n c e s on the I | ] f o l l o w i n g sentences. I i j A Frame System Model f o r Understanding Natural Language j Make i t big. The knowledge that the t r i a n g l e i s part of the house must now be used t o decide how b i g to make the t r i a n g l e . The act u a l s i z e should be such that the base of the t r i a n g l e i s the same width as the top of the square. |Move i t up a b i t , Again the word " i t " must be disambiguated. Also, the system must decide what amount "a b i t " i s . j Higher. This i s a sentence fragment which must be handled by the system. The system must r e a l i z e that t h i s fragment i s asking f o r the square to be moved even higher. I JMove i t up an J i n c h . J This sentence i s again easy to handle. The system should use i t s knowledge to make the bottom of the t r i a n g l e l e v e l with the top of the square and move i t up about an inch but not n e c e s s a r i l y e x a c t l y one i n c h . At t h i s point the system must r e a l i z e t h a t the main s t r u c t u r e of the house has been drawn. This w i l l allow the student to r e f e r to the s t r u c t u r e as "the house". JDraw an upright 3 r e c t a n g l e . This i s again a simple sentence t o handle. The system w i l l assume that the rec t a n g l e i s to be the main body of the door of the house. |Make i t smaller. 1 The rect a n g l e w i l l be made sm a l l e r . The knowledge that the door must f i t i n s i d e the square may be used to determine how small to make the r e c t a n g l e . ]Thinner. I i iMove i t down. I Another sentence fragment which the system must be able to handle. In t h i s case the door w i l l be made th i n n e r with the amount obtained from the f a c t that a door i s supposed to be about h a l f as wide as i t i s high. The system should r e a l i z e that the bottom of the rectangle must be equal to the bottom of the square. Thus the rectangle may be moved down to s a t i s f y t h i s r e l a t i o n . A Frame System Model f o r Understanding Natural Language 6 JDraw a very s m a l l |This sentence w i l l cause a very s m a l l j c i r c l e . I c i r c l e t o be drawn. The system w i l l J Jassume that i t i s meant to represent | jthe door knob f o r the door. The student J | w i l l have to move the c i r c l e around | \ u n t i l i t i s i n the c o r r e c t p o s i t i o n | 1 r e l a t i v e to the other components. j ^ JDraw a small IThis sentence i s easy to handle, j square i n s i d e the 1 except there i s no f i g u r e on the ( f r o n t . jscreen with the name " f r o n t " . The | |system must be able t o recognize when a I | f r o n t of a house has come i n t o | |existence. This w i l l allow the student I |to reference components of a f i g u r e by i Jname rather than a phrase such as "the j |big sguare under the t r i a n g l e " , i 1 As can be seen from the examples, people tend not to u t t e r complete s y n t a c t i c a l l y w e l l formed sentences, e s p e c i a l l y when they must type everything at a computer t e r m i n a l . These examples begin to show that the system would have to be able to understand sentence fragments as w e l l as s y n t a c t i c a l l y w e l l formed sentences. Some of the sentences are easy to handle using standard techniques, but, some of the fragments are extremely d i f f i c u l t . Also anaphoric references are used very h e a v i l y . An a ssociated problem i s to decide on an i n t e r n a l s t r u c t u r e which w i l l allow a f l e x i b l e method of representing the c u r r e n t s t a t e of the c o n v ersation, together with the current s t a t e of the f i g u r e being drawn. This information could then be used to help understand the utterances of the student. Also, s u f f i c i e n t i n f o r m a t i o n should be kept so that the system w i l l have some expectation of what the student i s going to do next. This w i l l help the program to disambiguate utterances which would not a Frame System Model f o r Understanding Natural Language 7 normally be understood. A Frame System Model for Understanding Natural Language 8 Chapter 2-Jk Brief Survey of Relevant Work Several d i f f e r e n t and diverse areas of A r t i f i c i a l I ntelligence have influenced the dire c t i o n t h i s thesis has taken. Minsky's frame systems [17] and Hewitt's actor formalisms [11,12,23] are the two most important ideas used. Semantic networks [2,3,18] have also played a s i g n i f i c a n t r o l e . 2.1. Minsky'_s Frame Systems The most important aspects of t h i s thesis are involved with the use of Minsky's frame systems to represent knowledge f o r understanding natural language. Minsky's frame systems paper [17] suggests an approach for the representation of knowledge. The idea behind frames i s that when one encounters a new sit u a t i o n (or makes a substantial change i n one's view of the current situation) a frame i s selected from memory. This i s a remembered structure which should very cl o s e l y match the current s i t u a t i o n . This frame may need to be adapted to f i t the current s i t u a t i o n . A frame i s a structure for representing a stereotype s i t u a t i o n , such as what a graphical house should look l i k e or what a graphical tree should look l i k e , etc. Attached to each frame are several pieces of di f f e r e n t information. Some of t h i s information w i l l consist of how the frame i s to be used, some A Frame System Model f o r Understanding Natural Language 9 expectation of what should happen next, what to do next i f these expectations are not met, e t c . A frame can be considered as a network of nodes and r e l a t i o n s between the nodes. In each frame some information i s a b s o l u t e l y f i x e d and must be true f o r the supposed s i t u a t i o n , no matter what. The frame also contains t e r m i n a l s which are s l o t s which may be f i l l e d with s p e c i f i c instances or data. The s l o t s may have associated with them c o n d i t i o n s which must be met f o r the assignment to t h i s s l o t to be allowed. The assignments to the s l o t s are u s u a l l y a l s o frames (or subframes). Conditions may c o n s i s t of a property which a subframe must have, such as i t must be a sguare or i t must be blue, e t c . More complex c o n d i t i o n s may be s p e c i f i e d by r e l a t i o n s h i p s between the s l o t concerned and other s l o t s of the frame. C o l l e c t i o n s of r e l a t e d frames are gathered together i n t o frame systems. Minsky i s mainly concerned with problems of re p r e s e n t a t i o n of knowledge necessary f o r v i s u a l image processing, even though he mentions other a p p l i c a t i o n s f o r h i s theory. In v i s i o n processing the d i f f e r e n t frames of the system w i l l s p e c i f y the scene from d i f f e r e n t points of view. This w i l l mean that d i f f e r e n t frames of the system may share the same t e r m i n a l s l o t assignment. Much of the power of the theory hinges on the i n c l u s i o n of expectation and other in f o r m a t i o n i n the frame. A frame's te r m i n a l s l o t s are normally f i l l e d with d e f a u l t values. In t h i s way a frame may contain many assumptions not n e c e s s a r i l y provided by the a c t u a l s i t u a t i o n . In the same way that a person A Frame System Model f o r Understanding Natural Language 10 may have a f a v o u r i t e g r a p h i c a l object (e.g. a c i r c l e ) , frames may have t h i s property a l s o . For example, the frame f o r a g r a p h i c a l object could have a d e f a u l t value of a c i r c l e . When i t i s asked to draw an object on a graphics t e r m i n a l screen ra t h e r than drawing a randomly chosen o b j e c t , i t could draw i t s f a v o u r i t e o b j e c t , i . e . a c i r c l e . The person who o r i g i n a l l y designed and wrote the frame would most l i k e l y pick h i s own f a v o u r i t e object. Frame systems are l i n k e d by an information r e t r i e v a l net so th a t when the curre n t frame does not s u c c e s s f u l l y f i t the curren t s i t u a t i o n , a new frame may be provided by the r e t r i e v a l net. Once a frame i s proposed t o represent the current s i t u a t i o n , a matching process must be performed so t h a t the t e r m i n a l s l o t s of a frame are c o r r e c t l y assigned according to the c u r r e n t s i t u a t i o n . The frame i t s e l f w i l l d i r e c t the pattern matching process according to the current goals of the system and w i l l i n c l u d e information about how to handle s u r p r i s e s or anomalies. The frames i n my system are s i m i l a r to but not the same as Minsky's. For one t h i n g mine are designed s p e c i f i c a l l y f o r processing n a t u r a l language, rather than v i s u a l images. They must be able t o perform some pattern r e c o g n i t i o n to be able to understand the sentences described i n the I n t r o d u c t i o n . The frames i n t h i s system are meant to be s p e c i a l i s t s which know everything about one s i n g l e concept. Anything which has to do with a concept must pass through t h i s one frame. The concept cannot be used i n any other way except through i t s frame. I f a A Frame System Model f o r Understanding Natural Language 11 word has more than one meaning then there must be frames defined f o r each of these meanings and these would be subsets of the frame f o r the word i t s e l f . The frames themselves are defined i n the Conniver programming language using some of the ideas of Hewitt's a c t o r formalism. Thus i n t h i s case a frame i s not a data s t r u c t u r e , but a procedure or an a c t o r (using Hewitt's terminology) . 2.2. He wit t j_s Actor Formalism Hewitt has developed from h i s o r i g i n a l Planner language [10] a new formalism f o r A r t i f i c i a l I n t e l l i g e n c e programming languages [11,12,23]. This formalism c o n s i s t s of what he c a l l s a c t o r s . An a c t o r i s sent a message (by another actor) and c a r r i e s out some a c t i o n according to i t s " s c r i p t " or body. The message i s pattern matched against a p a t t e r n which i s s p e c i f i e d i n the d e f i n i t i o n of the a c t o r . I f t h i s pattern match f a i l s then the actor i s not a p p l i c a b l e to the message and thus w i l l not be a c t i v a t e d . The s c r i p t f o r an actor may cause messages to be sent to other actors or even to i t s e l f (recursion i s immediately p o s s i b l e ) . Sending and r e c e i v i n g messages by a c t o r s i s the only p o s s i b l e form of communication. When a message i s sent to an a c t o r the message may contain both a c o n t i n u a t i o n point (CP) and a complaint department (CD). These two parts of the message are o p t i o n a l and i f they are not s p e c i f i e d then the a c t o r r e c e i v i n g the message must continue the computation on i t s own. The CP s p e c i f i e s where the r e s u l t of A Frame System Model f o r Understanding Natural Language 12 the computation i s to be sent when the a c t o r has completed i t s processing of the message. The CD i s where an e r r o r message i s to be sent when the a c t o r detects an e r r o r c o n d i t i o n . Both the CP and the CD are a c t o r s i n t h e i r own r i g h t and w i l l behave ac c o r d i n g l y . An actor can e a s i l y simulate a procedure by having the actor which represents the c a l l i n g procedure send a message to the a c t o r d e f i n i n g the procedure, s p e c i f y i n g the parameters to i t . The a c t o r d e f i n i n g the procedure would have a pattern i n i t s d e f i n i t i o n which would assign the values of the parameters to v a r i a b l e s . The CP of the parameter message to the actor d e f i n i n g the procedure could be made to r e t u r n c o n t r o l to the c a l l i n g a c t o r i n much the same way t h a t a procedure returns c o n t r o l to i t s c a l l e r . Hewitt claims that the a c t o r formalism accounts f o r a l l p o s s i b l e data and c o n t r o l s t r u c t u r e s , i n c l u d i n g : semaphores, monitors, ports, d e s c r i p t i o n s , semantic nets, l o g i c a l formulae, numbers, i d e n t i f i e r s , demons, processes, contexts and data bases. That i s a l l the above are s p e c i a l cases of the a c t o r formalism which i s supposed to be a general formalism f o r current programming language s t r u c t u r e s . As such i t i s a powerful concept u s e f u l f o r g i v i n g the programmer f u l l c o n t r o l over the computation as i t i s c a r r i e d out. A very important f e a t u r e about the a c t o r formalism i s that the way an actor a c t u a l l y performs i t s computation i s hidden from the user who has no access to i t . The only information a v a i l a b l e about an a c t o r i s what Hewitt c a l l s a c o n t r a c t . A c o n t r a c t i s a s p e c i f i c a t i o n of what an actor does and what i t r e t u r n s A Frame System Model f o r Understanding Natural Language 13 according to the message sent t o i t - This does not s p e c i f y how the actor performs t h i s a c t i o n . Thus an acto r may be replaced by another actor which behaves e x a c t l y the same as the o r i g i n a l ( e x t e r n a l l y at le a s t ) even though, i t may perform the computation i n a* d i f f e r e n t manner. For example, an actor which uses r e c u r s i o n to perform i t s computation may be replaced by another a c t o r which uses i t e r a t i o n to achieve the same r e s u l t . The system should then perform as i t p r e v i o u s l y d i d without changing any s p e c i f i c a t i o n s of the other a c t o r s i n the system. Hewitt's actor formalism has been used i n t h i s t h e s i s to implement a frame system i n the s p i r i t of Minsky's frame systems paper £17]. Changes have been made to the way that a c t o r s work even though they are s i m i l a r to Hewitt's a c t o r s . The actor formalism i s embedded i n Conniver f u n c t i o n s and thus are he a v i l y i dependent on the Conniver c o n t r o l and data base f a c i l i t i e s . The ba s i c idea i s that a c t o r s can only i n t e r a c t with other actors through sending and r e c e i v i n g messages. Routines are provided to send and receive messages much i n the same way that actors send and r e c e i v e messages, except that the user u s u a l l y has to e x p l i c i t l y s t a t e when to send and when to r e c e i v e a message, 2.3. Semantic Networks Semantic networks have been designed as a method f o r representing knowledge. They have been s u c c e s s f u l l y used to represent knowledge f o r understanding n a t u r a l language i n both SOPHIE [ 2 ] and i n SCHOLAR £3,5]. In both systems the problem A Frame System Model f o r Understanding Natural Language 14 domain has been a very l i m i t e d one. SOPHIE i s l i m i t e d to e l e c t r o n i c c i r c u i t diagrams and SCHOLAR was o r i g i n a l l y designed f o r computer aided teaching of South American geography. SCHOLAR has been adapted to handle "how t o " questions f o r teaching information about the ARPA network £5]. In a l l cases these systems have been very s u c c e s s f u l -Semantic networks c o n s i s t s of nodes and l i n k s . The nodes u s u a l l y denote words that the system knows about and the l i n k s s p e c i f y r e l a t i o n s h i p s between the nodes. Some of the r e l a t i o n s h i p s which are often used i n semantic networks are: superset, subset, i s - a , synonym, has-part, e t c . The r e l a t i o n s h i p s a c t u a l l y used i n any one system depend h e a v i l y on what the domain of the system i s . Most systems based on semantic networks use e i t h e r the superset or i s - a r e l a t i o n s h i p . These r e l a t i o n s h i p s are used to s p e c i f y h i e r a r c h i e s such as: a dog i s a mammal i s an animal, or a dog has superset mammal has superset animal. The problem with semantic networks i s that they can become very ad hoc. That i s the types of l i n k s between nodes are not w e l l defined and tend to be created as they are needed by the designer of the system. However, i f the r e l a t i o n s h i p s are w e l l defined such as superset, subset and others then semantic networks can g r e a t l y improve the e f f i c i e n c y and i n f e r e n c i n g power of a system. This i s so because there i s no need to repeat redundant i n f o r m a t i o n , s i n c e by using superset or i s - a l i n k s , the more general nodes can be used to represent general information about a concept. For example, i f there i s a A Frame System Model f o r Understanding Natural Language 15 hierarchy of the form a parrot has superset b i r d , then the in f o r m a t i o n that a parrot has feathers does not need to be a s s o c i a t e d with the node f o r p a r r o t , but may be i n h e r i t e d from the node f o r b i r d (since a l l b i r d s have f e a t h e r s ) . Semantic networks are used i n t h i s t h e s i s i n a very l i m i t e d way. Only the more w e l l defined r e l a t i o n s h i p s are used, such as superset, subset (the i n v e r s e of superset) and synonym l i n k s . The superset l i n k s are used i n the system so that redundant information i s not associated with many d i f f e r e n t nodes. More general i n f o r m a t i o n w i l l be kept i n a node and a l l the nodes which need access to t h i s i n f o r m a t i o n w i l l be subsets of t h i s general node. Synonym l i n k s w i l l point from one node to another node which has the same meaning as the f i r s t node so that synonyms can be used without a c t u a l l y having to keep m u l t i p l e copies of the same information around. For example, the a d j e c t i v e s l a r g e and b i g are to a l l i n t e n t s and purposes synonyms. Thus rather than having the same i n f o r m a t i o n f o r both, there w i l l be one piece of i n f o r m a t i o n , say a s s o c i a t e d with the node f o r b i g . 2.4. Fahlman 1s Work on Frames Since Minsky's frame systems paper, Fahlman has produced a t h e s i s proposal [ 7 ] and a t h e s i s progress report [ 8 ] on the implementation of frames. The t h e s i s proposal suggested an implementation method f o r r e c o g n i t i o n tasks by s p e c i f y i n g packets of demons which would be l o o k i n g f o r expected f e a t u r e s A Frame System Model f o r Understanding Natural Language 16 of the object under c o n s i d e r a t i o n - These packets of demons could b r i n g i n more packets of demons when they considered i t necessary. In h i s prpgress r e p o r t , Fahlman repudiates the approach described i n h i s proposal and completely r e v i s e s h i s r e c o g n i t i o n mechanisms. He i s now proposing a system based on a network very s i m i l a r to semantic networks. His system has nodes and l i n k s much i n the same way that semantic networks do. He proposes a set of f a i r l y r i g i d o r g a n i z a t i o n a l p r i n c i p l e s (such as a hierarchy of i s - a r e l a t i o n s ) . The system w i l l use p a r a l l e l marking of nodes f o r r e c o g n i t i o n . Trees can be marked very e f f i c i e n t l y by sending commands i n p a r a l l e l to the nodes v i a the l i n k s . The i s - a hierarchy i s e f f i c i e n t l y implemented. Members of a c l a s s i n h e r i t a l l the p r o p e r t i e s of a c l a s s and a l l i t s super-classes. Access to these p r o p e r t i e s i s very f a s t - The system i s capable of handling any number of orthogonal i s - a h i e r a r c h i e s . These i s - a h i e r a r c h i e s may be tangled to any desired extent. This system makes i t p o s s i b l e to very e a s i l y f i n d the i n t e r s e c t i o n of two or more c l a s s e s . These c l a s s e s can be e x p l i c i t groupings represented i n the i s - a hierarchy or they can be i m p l i c i t groupings based on some common property of the members. Each piece of informa t i o n i n the system w i l l e x i s t i n some context and i s only v i s i b l e when th a t context i s a c t i v e . This allows the system t o maintain many d i s t i n c t world models. Information not i n an a c t i v e context i s completely out of the A Frame System Model f o r Understanding Natural Language 17 way and does not slow down the accessing machinery- Contexts form tangled h i e r a r c h i e s with d i f f e r e n t l e v e l s of g e n e r a l i t y . One can operate i n a very general context with a l o t of information a v a i l a b l e or i n a very s p e c i a l i z e d context with much l e s s p o t e n t i a l f o r ambiguity and confusion- The system may focus i t s a t t e n t i o n by moving up or down t h i s h i e r a r c h y . A major point of h i s work i s that h i s system w i l l need v i r t u a l l y u n limited p a r a l l e l processing c a p a b i l i t i e s i f the system i s going to perform up to h i s expectations i n a very l a r g e domain of knowledge. A Frame System Model f o r Understanding Natural Language 18 Chapter 3. The Basic Components of the Model This chapter describes the basic components of a prototype model f o r the r e p r e s e n t a t i o n of knowledge used to so l v e some of the problems described i n the In t r o d u c t i o n - The s t r u c t u r e of frames, how frames communicate with one another and how inferenc e s are performed w i l l be given. These components and how they work are not complete yet, at l e a s t f o r a general r e p r e s e n t a t i o n f o r knowledge, but seem to work w e l l f o r the present domain. 3.1. The S t r u c t u r e of Frames The f i r s t important step i s to define what i s meant by a frame. A frame i s a node i n a network. Each such node contains a packet of knowledge that i s s p e c i f i c t o that node. These nodes may be l i n k e d together i n three d i f f e r e n t ways, by i m p l i c i t , e x p l i c i t and dynamic l i n k s . E x p l i c i t l i n k s are p h y s i c a l l i n k s between two frames. That i s there are p h y s i c a l p o i n t e r s between the two frames. This i s us e f u l f o r d e f i n i n g superset - subset, synonym, and other such r e l a t i o n s h i p s . Thus the frame w i l l have some method of accessing frames pointed to by such l i n k s , but w i l l not need to know the name of the frames at the time of the d e f i n i t i o n of the o r i g i n a l frame. A Frame System Model for Understanding Natural Language 19 Implicit l i n k s do not consist of physical l i n k s between two frames, These l i n k s are dependent on what i s contained i n the two frames. An i m p l i c i t l i n k exists between two frames i f one of the frames knows of the existence of the other frame. Then the f i r s t frame may communicate with the second. However, there need not be a reverse l i n k from the second frame to the f i r s t . A dynamic l i n k i s formed when one frame t e l l s another frame about i t s e l f . Then the second may communicate with the f i r s t . This i s in e f f e c t a method of forming a reverse l i n k to an i m p l i c i t or e x p l i c i t l i n k . The frames themselves behave very much l i k e Hewitt's actors [11,12,23], i . e . to activate a frame, a message must be sent to i t . Optional CP and CD frames may also be sent with the message. When a frame receives a message, i t w i l l perform a pattern match on the message to determine what i t i s meant to do. If the match succeeds the frame may do one of two things; 1.) return control to the CP frame by sending a message to i t (via the CP passed to the current frame) . or 2.) i t may activate a new frame by sending a message to another frame. This new frame would then control what happens next. Thus the external structure of a frame consists of a declaration of e x p l i c i t l i n k s , such as superset, subset, synonym and other relationships in which i t takes part with other frames. The external structure w i l l also be spe c i f i e d by the messages that the frame knows about and how i t responds to these messages. A Frame System Model f o r Understanding Natural Language 20 The i n t e r n a l s t r u c t u r e of a frame, on the other hand, c o n s i s t s of i m p l i c i t l i n k s to other frames and the decoding of messages that are sent to the frame. The frame w i l l then do whatever i s necessary according to the message re c e i v e d . Thus the i n t e r n a l s t r u c t u r e of a frame w i l l c ontain i n f o r m a t i o n about how to perform a c t i o n s which may be needed. The i n t e r n a l s t r u c t u r e also c o n s i s t s of what Minsky [17] c a l l s s l o t s . These s l o t s w i l l almost always be f i l l e d by a subframe of the current frame. For example, the frame f o r the f r o n t of a house which i s to be drawn on a graphics t e r m i n a l screen w i l l have s l o t s f o r a f r o n t body (the big sguare that i s the major part of a g r a p h i c a l house) , a door and a window,. Also there are c e r t a i n r e l a t i o n s h i p s that must be f u l f i l l e d by these subframes. The geometric r e l a t i o n s h i p s between the objects representing the f r o n t body, the door and the window may a l s o be considered as s l o t s i n s i d e the f r o n t frame which must a l s o be f i l l e d before a f r o n t can be recognized by the system. Some or a l l of these s l o t s may be o p t i o n a l . 3.2. D e f i n i t i o n of Frames In t h i s s e c t i o n , some fu n c t i o n s which are u s e f u l f o r d e f i n i n g frames are described. 1.) (FRDEFUN NAME (BFRAME (LOCAL VARS) BODY) (EFRAME (LOCAL VARS) BODY)) FRDEFUN defines a frame. NAME i s the name of the frame. BFRAME i n d i c a t e s that t h i s frame i s the b a s i c frame (BF) and ft Frame System Model f o r Understanding Natural Language 21 contains the more general information about the concept to be represented by the frame. This form w i l l always be present i n a frame d e f i n i t i o n . EFRAME, which i s o p t i o n a l , i n d i c a t e s that t h i s frame i s an extension frame (EF) and contains i n f o r m a t i o n about a s p e c i f i c i n s t a n c e of the concept to be represented by the frame. A copy of the EF w i l l be made to represent a s p e c i f i c object of t h i s type when a new instance i s to be created. This type of frame w i l l have the same name as the BFRAME above with an i n t e g e r concatenated on to the end of the name. This allows access to the EF by the BF. LOCAL VARS are Conniver l o c a l v a r i a b l e s which may be used i n s i d e the body of the frame without having to worry about t h e i r being destroyed by other procedures or frames which may be defined using the same l o c a l v a r i a b l e s . BODY c o n s i s t s of the body of the frame, i . e . Conniver code f o r decoding any messages received and performing any a c t i o n s d e s i r e d . This may c o n s i s t of any Conniver code which i s needed, as long as communication between frames i s done only by the f u n c t i o n SEND. FRDEFUN may be used to define two frames at the same time. This i s so that inf o r m a t i o n about a concept can be s p l i t i n t o two d i s t i n c t frames. For example, the concept square i s d i v i d e d i n t o two d i s t i n c t frames. One frame (BF) c o n s i s t s of more general information about squares. For example, i t would s p e c i f y that the lengths of a l l the sides are equal. The other, more s p e c i f i c , frame (EF) w i l l describe a s p e c i f i c square. For A Frame System Model f o r Understanding Natural Language 22 example, i t w i l l c o n t a i n information about the lengths of the sides of the sguare, the l o c a t i o n of the square on the screen i f i t i s being d i s p l a y e d , where the top of the square i s , e t c . FRDEFUN generates code i n f r o n t of BODY i n order t o rec e i v e a message when the frame i s sent one. Thus the user need not e x p l i c i t l y w r i t e code to re c e i v e a message. The v a r i a b l e s FRMESS AGE, FRCONTINUE and FRCOMPLAINT are assigned the message, the CP and the CD r e s p e c t i v e l y . These v a r i a b l e s can then be accessed by the user i f he so wishes. Other v a r i a b l e s which are a v a i l a b l e when d e f i n i n g frames are: HISTORY-LIST, CURRENT-FRAME and PREVIOUS-FRAME. The v a r i a b l e HISTORY-LIST i s a stack of a l l the messages sent t o frames. Each element i n t h i s l i s t c o n tains the name of the frame sent the message, the message i t s e l f , the CP and the CD-This h i s t o r y l i s t i s used by the input frame f o r disambiguating sentences. This v a r i a b l e i s a l s o used by the superset processing routine to decide when the unwinding process of the superset processing should be terminated. CURRENT-FRAME i s always bound to the name of the c u r r e n t l y a c t i v e frame. PREVIOUS-FRAME i s always bound t o the name of the frame which a c t i v a t e d the c u r r e n t l y a c t i v e frame. This v a r i a b l e i s often used by the input frame to help i n disambiguating sentences. 2.) (CREATE FRAME) Where FRAME i s the name of a frame which has an EF. This f u n c t i o n w i l l create a copy of t h i s EF and retu r n the name of t h i s new inst a n c e . A Frame System Model for Understanding Natural Language 23 3. ) (CASES VARIABLE (PATTERN 1 BODY 1) (PATTERN 2 BODY 2) (PATTERNS BODY 3) » <* • *» (PATTERNn BODYn) where VARIABLE contains a message or some value to be used i n pattern matching against the patterns PATTERN 1, PATTERN2, ... , PATTERNn- If VARIABLE i s not sp e c i f i e d , then the variable FRMESSAGE w i l l be used. PATTERN 1, PATTERN2, ... , PATTERNn are patterns to be matched against the value of VARIABLE (see Appendix 1 for a brief description of the Conniver pattern matcher). If a pattern i s the single atom ELSE:, then no matter what the value of VARIABLE i s the pattern match w i l l succeed. BODYi are pieces of Conniver code which are executed when PATTERNi i s successfully matched against the value of VARIABLE. Only the f i r s t successful match w i l l count, i . e . CASES acts very much l i k e a SELECT clause in LISP. 4. ) (EXPECT (PATTERN1 BODY 1) (PATTERN2 BODY 2) (PATTERNS BODY3) m m (PATTERNn BODYn) where PATTERN 1, PATTERN2, ... , PATTERNn and BODY 1, B0DY2, ... , BODYn have the same meaning as for CASES above. EXPECT causes a message to be received by the currently active frame. The variables EXPECT-MESSAGE, EXPECT-CONTINOE and EXPECT-COMPLAINT are assigned the values of the message, the CP and the CD sent to the current frame respectively. These variables are defined A Frame System Model f o r Understanding Natural Language 24 only w i t h i n an EXPECT clause. EXPECT i s normally used immediately a f t e r a message i s sent to another frame. EXPECT i s used to check that when a re t u r n i s made v i a the CP with some message, t h i s message i s one of the expected ones. 5. ) (SEND FRAME MESSAGE CONTINUATION COMPLAINT) SEND sends the message MESSAGE to the frame s p e c i f i e d by FRAME. MESSAGE i s a Conniver s t r u c t u r e which w i l l be evaluated. CONTINUATION i s o p t i o n a l , and i f s p e c i f i e d should evaluate to the frame to which c o n t r o l should return a f t e r FRAME has f i n i s h e d i t s processing. I f CONTINUATION i s not s p e c i f i e d , then the frame sent the message must not attempt to return c o n t r o l v i a the CP. COMPLAINT i s a l s o o p t i o n a l , and i f s p e c i f i e d should evaluate to a Conniver l a b e l i n the current frame. This l a b e l w i l l be made to look l i k e a frame and w i l l be sent to FRAME. I f FRAME or p o s s i b l y some of the frames i t a c t i v a t e s detect an e r r o r then c o n t r o l may be returned to t h i s CD and the CD must decide what to do depending on what e r r o r message i s returned. A l l t h i s i nformation i s put i n a s p e c i a l Conniver context used s o l e l y f o r messages. This g l o b a l context i s a v a i l a b l e to a l l frames. At t h i s point the current frame i s suspended and the frame being sent the message i s a c t i v a t e d or r e a c t i v a t e d depending on whether or not i t has been used i n the c u r r e n t computation. A l l the information concerning the a c t i v a t i o n of a frame i s contained on the property l i s t of the name of the frame. 6. ) (RECEIVE MESSAGE CONTINUATION COMPLAINT) RECEIVE i s used to r e c e i v e a message sent to the c u r r e n t l y A Frame System Model f o r 'Understanding N a t u r a l language 25 a c t i v e frame. MESSAGE i s a v a r i a b l e which w i l l be a s s i g n e d t h e a c t u a l message s e n t t o the c u r r e n t frame. CONTINUATION i s o p t i o n a l , and i f p r e s e n t w i l l be a s s i g n e d the CP i f one was s p e c i f i e d when the message was s e n t . I f no CP was s p e c i f i e d when t h e message was s e n t , then CONTINUATION w i l l be s e t t o NIL. I f CONTINUATION i s not s p e c i f i e d , the CP s e n t w i t h t h e message w i l l be i g n o r e d . COMPLAINT i s a l s o o p t i o n a l , and i f p r e s e n t w i l l be a s s i g n e d the CD i f one was s p e c i f i e d when t h e message was s e n t . I f no CD was s p e c i f i e d when the message was s e n t , then COMPLAINT w i l l be s e t t o NIL. I f COMPLAINT i s not s p e c i f i e d , t h e CD i n f o r m a t i o n s e n t w i t h t h e message w i l l be i g n o r e d . 7.) {DEF-SUBSET (FRAME 1 SUB 11, 5UB12, ... , SUBin) (FBAME2 SUB21, SUB22, ... , SUB2n) (FRAMEm SUBml, SUBm2, , SUBmn) T h i s w i l l d e f i n e the frame FSAMEi t o have as su b s e t frames th e frames S U B i l , SUBi2, ... , SUBin and t h e i n v e r s e , t h e frames S U B i l , SUBi2, ... , SUBin have as s u p e r s e t frame FRAMEi. A frame may have an a r b i t r a r y number o f s u p e r s e t s . When a frame r e c e i v e s a message which does not match any of the e xpected p a t t e r n s , the frame may send t h i s message t o i t s s u p e r s e t s , t o see i f they know what the message means.- I f one of the s u p e r s e t frames does a c c e p t t h e message, then i t w i l l r e t u r n c o n t r o l t o the CP w i t h some message, s p e c i f y i n g what happened. I f a s u p e r s e t frame i s unable t o understand a message, then i t w i l l send a message t o the CD s e n t w i t h t h e message i t r e c e i v e d , a f t e r making a l l e f f o r t s t o un d e r s t a n d t h e A Frame System Model f o r U n d e r s t a n d i n g N a t u r a l Language 26 message. When an i n v a l i d message i s en c o u n t e r e d s u p e r s e t frames may be i n v o k e d t o as h i g h a l e v e l as p o s s i b l e . E v e n t u a l l y c o n t r o l w i l l r e t u r n ( v i a the C'D,s) t o the o r i g i n a l frame and i t w i l send an e r r o r message to i t s CD. I f a l l p o s s i b l e s u p e r s e t paths have been t r a c e d w i t h t h e message, w i t h o u t s u c c e s s , then an e r r o r message w i l l be s e n t t o the CD c o r r e s p o n d i n g to the message c a u s i n g a l l the problems. The f o l l o w i n g C o n n i v e r f u n c t i o n p e r forms t h i s t a s k . 8. ) (SUPERSET-PROCESSOR MESSAGE) where MESSAGE i s t h e message which so f a r has not been u n d e r s t o o d by t h e c u r r e n t frame. T h i s r o u t i n e a l s o g e n e r a t e s t h e a p p r o p r i a t e e r r o r message and sends i t t o the CD i f t h e s u p e r s e t p r o c e s s i n g f a i l s . The main purpose o f h a v i n g s u p e r s e t p r o c e s s i n g i s t o reduce the amount of i n f o r m a t i o n t h a t must be c o n t a i n e d i n a frame. There are o f t e n many f a c t s a s s o c i a t e d w i t h a frame which a r e not s p e c i f i c t o t h a t one frame. U s i n g t h e n o t i o n o f s u p e r s e t s from s e m a n t i c network t h e o r y [ 2 , 3 , 1 8 ] , i t i s p o s s i b l e t o a s s o c i a t e more g e n e r a l i n f o r m a t i o n about a frame w i t h t h e s u p e r s e t of t h a t frame. Thus i n s t e a d o f p u t t i n g as much as p o s s i b l e i n t o a frame, t h e more g e n e r a l i n f o r m a t i o n w i l l be put i n t o i t s s u p e r s e t frame. The s u p e r s e t o f a frame has t h a t frame as a s u b s e t , so t h a t p r o c e s s i n g may go i n e i t h e r d i r e c t i o n , i f n e c e s s a r y . 9. ) (DEF-SYNONYM (FRAME1 SYN11, SYN12, ... , SYN 1n) (FRAME2 SYN21, SYN22, ... , SYN2n) (FRAME3 SYN31, SYN32, ... , SYN3n) =* » (FRAM Em SYNml, SYNm2, ... , SYNmn)) A Frame System Model f o r Understanding Natural Language 27 This f u n c t i o n d e f i n e s FRAMEi to be the ca n o n i c a l frame f o r a word and SY Ni 1, SYNi2, ... , SYNin t o be synonyms f o r the word. When a message i s sent to one of the synonyms f o r a* frame, the procedure SEND checks to see i f the frame being sent the message i s defined. I f i t i s not then SEND checks to see i f i t i s defined as a synonym. I f i t i s then rather than generating an e r r o r message, SEND sends the message to the ca n o n i c a l frame which defines the meaning of a l l the synonyms f o r that concept-3.3. E r r o r Processing E r r o r processing c a p a b i l i t i e s are very important f o r a system to be able to react c o r r e c t l y to an erroneous message passed to a frame or an erroneous assumption made by a frame., Erroneous assumptions by a frame are the most d i f f i c u l t e r r o r s to handle. Such e r r o r s must be handled s p e c i a l l y and i n v o l v e a great deal of e f f o r t to return the system to a s t a t e which c o n s i s t s of the c o r r e c t assignments to the s l o t s of the frames. The d e t e c t i o n of erroneous assumptions i s a l s o a major concern. I t means that there must be demons present to check f o r c e r t a i n c o n d i t i o n s which cannot normally occur a f t e r a d e c i s i o n has been made. For example, i f the student i s i n the process of drawing a house and the system suddenly disco v e r s that the square i t thought t o be the f r o n t body i s i n s i d e the square i t thought to be the window, the system must take some c o r r e c t i v e a c t i o n . This i n v o l v e s reassigning s l o t s i n the f r o n t A Frame System Model f o r Understanding Natural Language 28 body frame and the window frame to the c o r r e c t squares. I n v a l i d messages sent to frames, on the other hand, are r e l a t i v e l y easy to handle. When such a message i s f i r s t detected, supersets of the frame d e t e c t i n g the e r r o r are f i r s t checked to see i f any of them can comprehend what the message means. I f the superset processing succeeds i n understanding the message, then the frame that was o r i g i n a l l y sent the message w i l l remain i n c o n t r o l of the computation. I f superset processing f a i l s , then an e r r o r message i s sent to the CD f o r the frame. When an e r r o r occurs a message of the form: (•ERROR TYPE E.REOR-MESSAGE) i s sent to the CD, where TYPE s p e c i f i e s the type of the e r r o r . Some of the types that are pr e s e n t l y i n use are: 1. )*MESSAGE - This s i g n i f i e s that the e r r o r was caused by a message which d i d not match any of the patterns a s s o c i a t e d with the frame and th a t none of the superset frames of the frame could decode the message. ERROR-MESSAGE i s j u s t the erroneous message that caused the e r r o r . 2. ) *FATAL - This i s a message, which may only be sent to the top l e v e l frame. This message w i l l be sent when a frame has detected an i n t e r n a l system e r r o r . At t h i s point the system has no idea of what has gone wrong or what to do next. Such e r r o r s a r i s e when a frame i s a c t i v a t e d , but no message was sent f o r i t to r e c e i v e , or a message i s sent to an i n v a l i d frame, or p o s s i b l y when a frame sends a message to a frame and r e c e i v e s back an unexpected message. At present these are the only times A Frame System Model f o r Understanding Natural Language 29 that a f a t a l e r r o r may occur- Under a f a t a l e r r o r , the c u r r e n t computation i s aborted. 3.) *FULL - This type of e r r o r i s caused when a frame has already f i l l e d the s l o t corresponding to a message j u s t received. *FULL e r r o r s are not f a t a l and are handled i n the same way as the *MESSAGE e r r o r , except no superset processing i s done. Other types of e r r o r s may be defined as the need a r i s e s -There are always two frames necessary i n any e r r o r type i n t e r a c t i o n . One frame must be able to detect an e r r o r and send a message to the second. The second frame must then be able to process the e r r o r when i t occurs. This other frame must be the CD sent with any message that may cause t h i s type of e r r o r . To f a c i l i t a t e sending e r r o r messages to a frame, a f u n c t i o n i s provided. 10.) (COMPLAIN FEAME TYPE MESSAGE) where FEAME should evaluate to the name of the frame to which the e r r o r message i s to be sent, TYPE i s the e r r o r type, which i s not evaluated. TYPE may be one of the e r r o r s mentioned above or i t may be one the user wants to use. MESSAGE i s o p t i o n a l , and i s meant to provide more inf o r m a t i o n about the e r r o r t o the CD. 3.4. Infsrencinc[ and Demon Processing Inferencing plays an important r o l e i n any system which attempts to understand n a t u r a l language. In t h i s system the messages passed from one frame to another perform t h i s f u n c t i o n . A Frame System Model f o r Understanding Natural Language 30 To perform any i n f e r e n c i n g i n the system there i s u s u a l l y some i n t e r a c t i o n between the frames of the system. In some cases i n f e r e n c e s w i l l be performed w i t h i n one frame, but t h i s w i l l not be the usual case. Inferences are needed when some a c t i o n i s t o be performed by the system, or when some question has been asked of the system. A l s o , i n f e r e n c i n g w i l l be necessary i n the process of generating some expectation f o r what the next input to the system might be. Any time a message i s sent to a frame i n f e r e n c i n g i s being performed. The message must be accepted by the r e c e i v i n g frame and should cause i t t o perform some a c t i o n s and p o s s i b l y respond with some answer. In the process of performing these a c t i o n s the frame r e c e i v i n g the message must make sure t h a t the message does not c o n t r a d i c t any knowledge of the system (or at l e a s t not c o n t r a d i c t any c e r t a i n f a c t s , even though some uncertain f a c t s may be c o n t r a d i c t e d ) . The frame a f t e r performing any a c t i o n must e i t h e r r e t u r n c o n t r o l to the CP associated with the message or continue the computation on i t s own. Sending messages to a frame may be thought of as the in v o c a t i o n of a consequent theorem, such as i n Micro-Planner[ 24 ]. However, there i s no i n d i s c r i m i n a n t i n v o c a t i o n of frames when a message i s sent, as there may be when Micro-Planner theorems are invoked. Only the frame which i s meant to rec e i v e the message can rec e i v e i t , so i t i s the only one which w i l l get c o n t r o l of the computation. This provides f a r greater c o n t r o l over the computation than i s po s s i b l e with Micro-Planner i n general. Every theorem which A Frame System Model f o r Understanding Natural Language 31 matches the pattern of the goal may be invoked i n Micro-Planner, whereas i n t h i s frame system only the one frame may be invoked. This means that c o n t r o l i s maintained w i t h i n the system and there should be no chance of a runaway computation to occur as can happen i n a Micro-Planner system. Demon processing f o r the frame system corresponds to the antecedent theorem of Micro-Planner or the If-added method of Conniver. This type of process i s the basis of the expectations generated by the system. In the same way that antecedent theorems i n Micro-Planner are used to expect some f a c t to become evident, demons are used to expect something to happen w i t h i n the system. When some frame i s waiting f o r something to happen, i t may send a demon message to the frame corresponding to t h i s a c t i o n . I f a message which corresponds to the demon i s encountered by the frame, then a f t e r f i n i s h i n g processing the message, i t w i l l send a message to the frame s p e c i f i e d i n the demon message. A f u n c t i o n has been provided to perform t h i s task. 11.) {DEMON-PROCESSOR DEMON-PATTERN MESSAGE CONTEXT) where DEMON-PATTERN i s the pattern which w i l l be used to r e t r i e v e the demon information from the context CONTEXT. MESSAGE w i l l be used to construct the message that w i l l be sent to the frame which i s to r e c e i v e the demon message. The a c t u a l message sent w i l l be of the form: (*OCCDR MESSAGE) . where MESSAGE i s the same one that was passed to the f u n c t i o n DEMON-PROCESSOR. The frame a c t i v a t e d by the *CCC0R message w i l l A Frame System Model f o r Understanding Natural Language 32 then continue with i t s processing, but i t must retu r n c o n t r o l to the frame which seat the *OCCUR message. The computation w i l l then be c a r r i e d on from that point normally. This i s very much l i k e the c o n t r o l s t r u c t u r e of the Micro-Planner antecedent theorem or the Conniver If-added method-To f a c i l i t a t e sending demon messages a s p e c i a l f u n c t i o n , DEMON i s provided. 12. ) (DEMON FRAME RFRAME MESSAGE) where FRAME s p e c i f i e s the frame to be sent the demon message, RFRAME i s the frame to ret u r n c o n t r o l to (usua l l y the c u r r e n t l y a c t i v e frame) when the event expected happens. Message s p e c i f i e s the inf o r m a t i o n about what event i s wanted. 13. ) (CANCEL FRAME RFRAME MESSAGE) Where FRAME, RFRAME and MESSAGE have the same meaning as fo r DEMON. CANCEL w i l l cancel a demon which was created by the f u n c t i o n DEMON. The messages and demons of the frame system provide a l l the i n f e r e n c i n g power that i s necessary to understand the subset of n a t u r a l language i n the domain described i n the I n t r o d u c t i o n . Micro-Planner uses backup to perform i n f e r e n c e s , i . e . when one branch of the s o l u t i o n path f a i l s , Micro-Planner backs up to the l a s t d e c i s i o n point and t r i e s another branch. I t i s not easy i n Micro-Planner to use information about what went wrong to decide what branch should be taken next. Conniver, on the other hand, does allow the programmer the opportunity to make such d e c i s i o n s by a l l o w i n g access to the p o s s i b i l i t i e s l i s t . This frame system allows at l e a s t as much c o n t r o l as Conniver, using the frame A Frame System Model f o r Understanding Natural Language 33 system's e r r o r processing c a p a b i l i t i e s . When a frame makes a d e c i s i o n to send a message to another frame, i t w i l l normally send the name of. i t s CD along with the message. In t h i s way, when the frame being sent the message detects an. e r r o r i t may send an e r r o r message to the CD s p e c i f y i n g what type of e r r o r has occured and an e r r o r message. When the computation i s blocked because of a wrong d e c i s i o n , an e r r o r message w i l l be sent to the CD. Using the information gathered from going down the wrong path and the e r r o r message, the CD can then make a wiser d e c i s i o n about which choice to t r y next. Thus the simple backup technique of Micro-Planner could e a s i l y be implemented by j u s t b l i n d l y choosing the next branch of the path using the technique of t h i s type of e r r o r processing. In most cases the system should pick the r i g h t path the f i r s t time, rather than t r y i n g many d i f f e r e n t paths before f i n d i n g the c o r r e c t one. 3 . 5 . Context and Focus Context plays an important r o l e i n the understanding of n a t u r a l language. Context must often be used to comprehend E n g l i s h sentences that are ambiguous. The context f o r the system w i l l be s p e c i f i e d by the c u r r e n t l y a c t i v e frames and the c u r r e n t l y a c t i v e Conniver contexts. The frames w i l l have s l o t s f i l l e d and w i l l c o n t a i n other information which w i l l s p e c i f y the s t a t e of the system and w i l l help i n disambiguating many sentences. This system depends h e a v i l y upon Conniver contexts to help A Frame System Model f o r Understanding Natural Language 34 i n the processing f o r the frame system. There i s one g l o b a l context which contains g l o b a l i n f o r m a t i o n known to the system. I t w i l l a l s o contain contexts f o r conversations and s i t u a t i o n s which are c u r r e n t l y not a p p l i c a b l e . This g l o b a l context w i l l c o ntain information which i s always true and i s a v a i l a b l e to a l l the frames through the Conniver v a r i a b l e GLOBAL. This g l o b a l context w i l l contain information which w i l l not u s u a l l y be used during a computation once a subject has been chosen and i t s context has been i n s t a n t i a t e d . When the system i s f i r s t i n i t i a l i z e d a blank context w i l l be i n s t a n t i a t e d . This context w i l l be used by the frames to s t o r e information about the computation t h a t takes place, as w e l l as f o r s t o r i n g a s s e r t i o n s the frames need to use and the demon s t r u c t u r e s that the frames may send to one another. These Conniver contexts must be used together with the Conniver data base f u n c t i o n s . The use of general data base f u n c t i o n s such as those provided by Conniver tend to slow down r e t r i e v a l of i n f o r m a t i o n when l a r g e amounts of data are i n a context. Each time information i s r e t r i e v e d from a c o n t e x t , a l l the items i n the context must be pattern matched with the goal pat t e r n . Thus i f each frame were to add information to t h i s c urrent context, so much informat i o n would q u i c k l y accumulate, that the r e t r i e v a l w i l l become very i n e f f i c i e n t . Also, with a l l the frames s t o r i n g i n f o r m a t i o n i n one context, there may be some info r m a t i o n which the wrong frame t h i n k s i s i n f o r m a t i o n f o r i t , but i s a c t u a l l y not, The problem i s solved by more f u l l y u t i l i z i n g the power of a Frame System Model f o r Understanding Natural Language 35 the Conniver c o n t e x t s . This i s done by g i v i n g each frame the p o s s i b i l i t y of having one or more of i t s own contexts. Conniver provides the a b i l i t y to crea t e new contexts at w i l l , so that frames may create contexts whenever they want. When these contexts are created by the frame, they w i l l be added to the current t o p i c context so that the frame may access i t s context whenever i t needs i t . The frame w i l l do t h i s so that when a new t o p i c i s encountered, the frame w i l l not contain a v a r i a b l e which points to the context f o r the o l d t o p i c . Every time a frame needs i t s context i t must do a data base search to r e t r i e v e the current value f o r i t s context. The current t o p i c context w i l l c o n t ain a l l the contexts of frames which need them f o r the current conversation. When a change i n t o p i c i s encountered, the current t o p i c context can be saved and a new t o p i c context can be i n s t a n t i a t e d . This new context w i l l then be used by the frames f o r s t o r i n g any informat i o n i n the data base that they need. The o l d context together with a l l the information stored i n i t by the frames may be saved and l a t e r r e s t o r e d . This stored information w i l l c o n t ain a l l the subcontexts created by the frames invoked f o r t h a t t o p i c . These subcontexts w i l l be hidden from the frames that created them. Thus when a new t o p i c i s introduced, the old t o p i c can be completely removed from the computation so that i t w i l l not i n t e r f e r e with the new t o p i c . Frames which represent instances of objects w i l l s t i l l be i n ex i s t e n c e , but they w i l l be hidden frame the current t o p i c context. Frames which do not represent i n s t a n c e s of objects A Frame System Model f o r Understanding Natural Language 36 w i l l cause no problem, since a l l the inf o r m a t i o n that they ever contain w i l l only be i n t h e i r contexts, which w i l l be saved along with the o l d t o p i c context. They w i l l have to create a new context the next time they need one. Hhen the o l d t o p i c context becomes the current t o p i c context again, a l l t h i s i nformation w i l l be returned and w i l l now be a v a i l a b l e f o r use by the frames. I f necessary a l l inf o r m a t i o n i s a v a i l a b l e through the g l o b a l context but the current t o p i c context w i l l have no d i r e c t access to i t . by the system. This change of t o p i c c a p a b i l i t y i s important, since i t must be po s s i b l e to change t o p i c s with ease. A l l that i s necessary i s to r e i n s t a t e a context to re t u r n to a t o p i c p r e v i o u s l y discussed. In t h i s way the previous computation w i l l be protected from d e s t r u c t i o n by the new computation and the new computation w i l l be protected from i n t e r f e r e n c e from inform a t i o n stored by the ol d computation. Or at l e a s t there w i l l be no d i r e c t i n t e r a c t i o n between the two t o p i c s . The use of contexts focuses on the current t o p i c of the conversation rather than having no current t o p i c . Using the information from the current t o p i c context and informat i o n about the c u r r e n t frames, the s y n t a c t i c and semantic a n a l y s i s frames should be able to bet t e r understand the sentences or sentence fragments input i n t o the system. In many cases t h i s i nformation w i l l be a b s o l u t e l y necessary f o r the system to understand the input utterance. This w i l l be e s p e c i a l l y true with sentence fragments, which often occur i n human conversation- A l s o , t h i s i nformation w i l l be us e f u l i n determining r e f e r e n t s when A Frame System Model f o r Understanding Natural Language 37 pronouns and other ambiguous forms of reference are used i n sentences and i n sentence fragments, 3.6. Representation of Nouns Enough informa t i o n has now been presented to allow a d i s c u s s i o n of how various s y n t a c t i c elements of E n g l i s h are s p e c i f i e d using frames. Nouns w i l l u s u a l l y have two frames associated with them, one (the BF) w i l l c ontain the more general i n f o r m a t i o n about the concept represented by the noun and one (the EF) which contains i n f o r m a t i o n about a s p e c i f i c instance of the concept. Sometimes t h i s l a t t e r frame w i l l not be needed. This u s u a l l y occurs with nouns which are general i n scope, and could denote any one of a number of concepts. For example, the noun " o b j e c t " i s a noun which embodies many d i f f e r e n t concepts (e.g. squares, t r i a n g l e s , c i r c l e s , doors, etc.) and w i l l not have an EF. The s t r u c t u r e of nouns was s p l i t i n t o two frames so that i t would be p o s s i b l e to have one frame i n c o n t r o l over a l l the s p e c i f i c frames. This means that the more general frame has to decide when to create a new instance of the s p e c i f i c frame, r a t h e r than the programmer having to check to see i f a s i n g l e frame f o r an object would have to be i n s t a n t i a t e d or not. This a l s o means that the general frame can keep track of a l l the instances of the s p e c i f i c frame and return these names to any frame which wants to have a current l i s t of a l l the frames of one concept. I t would be wasteful to have an object frame f o r each A Frame System Model f o r Understanding Natural Language 38 s p e c i f i c object that the system knows about, e s p e c i a l l y since there are already frames which contain s p e c i f i c knowledge about a l l the objects the system knows about. In t h i s case, the object frame w i l l know more general i n f o r m a t i o n about objects as a c l a s s . For example, the object frame w i l l know how to move an object around on a graphics screen. This information i s common to a l l o b j e c t s known by the system and should not be contained i n a more s p e c i f i c frame. What a c t u a l l y goes i n s i d e these frames depends very much on what the noun represents. A s p e c i f i c example of what informat i o n i s contained i n a frame f o r a noun or a p h y s i c a l object w i l l now be .given. The example used w i l l be taken from the problem domain described i n the I n t r o d u c t i o n . The f o l l o w i n g d e f i n i t i o n i s the o u t l i n e f o r what the house frame would look l i k e . Words i n lower case which are preceded by a semi-colon(;) are comments. (FRDEFUN HOUSE (BFRAME (ADJECTIVE-LIST HOUSE OBJECT-TIPE OBJECT HOUSE-CONTEXT) : HOUSE-LOOP (CASES ((!>OBJECT-TYPE !>OBJECT) ; an object which could be part of a house has ; been drawn. Create a house EF and send the message ; to i t . (CSETQ HOUSE (CREATE ' HOUSE) ) (DEMON •FRONT HOUSE) ; send demons so the new house (DEMON 'ROOF HOUSE) ; EF i s t o l d whena f r o n t 6 roof occur. (SEND HOUSE FfiMESSAGE FRCONTINUE * HOUSE—ERROR)) ((DRAW . (!>ADJECTIVE-LIST) ) ; the system has been asked to draw a house. ; ADJECTIVE-LIST contains the p r o p e r t i e s that ; the house should have. (CSETQ HOUSE (CREATE •HOUSE)) ; create house EF to ; t o represent new house. (DEMON 'FRONT HOUSE) (DEMON 'EOOF HOUSE) A Frame System Model f o r Understanding Natural Language 39 ; draw the f r o n t of the house. (SEND • FRONT ' (DRAW) CURRENT-FRAME * HOUSE-ERROR) (EXPECT ((FRONT !>FRONT)) ( E L S E : error)) ; draw the roof of the house. (SEND 'ROOF » (DRAW) CURRENT-FRAME 'HOUSE-ERROR) (EXPECT ((ROOF !>ROOF)) ( E L S E : ERROR) ) ; make the f r o n t support the roof. (SEND •SUPPORTS ( L I S T ' M A K E FR'ONT ROOF) CURRENT-FRAME ' HOUSE-ERROR) (EXPECT (T) ( E L S E : ERROR) ) ; make the f r o n t "married" to the roof . (SEND 'MARRY ( L I S T ' I S FRONT ROOF) CURRENT-FRAME 'HOUSE-ERROR) (EXPECT (T) ( E L S E ; ERROR) ) ; process p r o p e r t i e s s p e c i f i e d by A D J E C T I V E - L I S T . ; a house has been recognized, perform demon ; processing to t e l l those frames wa i t i n g f o r ; a house-(DEMON-PROCESSOR * (*DEMON !>RFRAME) ( L I S T •HOUSE HOUSE) 'HOUSE-CONTEXT) (SEND FRCONTINUE ( L I S T * HOUSE HOUSE))) ; must accept messages which c r e a t e and ; destroy demons. ( (*DEMON !>RFRAME)) ( ( • C A N C E L ! >RFRAM E) ) ) ; END OF CASES ; send message to receive next i n p u t . ; and go t o top of loop to r e c e i v e ; message and perform reguired a c t i o n . (SEND 'INPUT-FRAME «*NEXT CURRENT-FRAME) (GO 'HOUSE-LOOP) :HOUSE-ERROR ; e r r o r processing f o r the house BF. ) ; end of BF f o r house. ; d e f i n i t i o n of EF f o r the concept house. (EFRAME ( ) (CASES ))) A Frame System Model f o r Understanding Natural Language 40 As can be seen the s t r u c t u r e f o r a g r a p h i c a l house w i l l c o n s i s t of two a c t u a l frames, s i n c e a house represents a s p e c i f i c object. One frame w i l l c o n s i s t of i n f o r m a t i o n about a s p e c i f i c instance of a g r a p h i c a l house. The more general or BF f o r a g r a p h i c a l house w i l l c o n s i s t of i n f o r m a t i o n about g r a p h i c a l houses i n general. In p a r t i c u l a r , i t w i l l c o n t ain information about how to draw a house, i t w i l l be able to return a l i s t of a l l the houses the system knows about, i n case the semantic a n a l y s i s r o u t i n e s of the system have need of such inf o r m a t i o n . The information f o r drawing a house w i l l c o n s i s t of code f o r sending messages to the subframes of the house-This frame must a l s o be able to accept demon messages from frames wanting to know when a house comes i n t o e x i s t e n c e . This means that i t may have to send a demon to the more s p e c i f i c house frame, which i t has c r e a t e d , so that i t w i l l know when a house has a c t u a l l y been completed. The house BF must be able to create a house EF house frame, when i t r e c e i v e s a message s p e c i f y i n g some object which could be part of a house has been created. This w i l l happen when the f i r s t o b j ect f o r representing the house comes i n t o e x i s t e n c e . When an EF i s created and a message i s sent to i t , the CD s p e c i f i e d i n t h i s f i r s t message w i l l be saved. This CD should s p e c i f y the EF that has as part the current EF. This i s done so that when a message i s sent to the current EF and the message i s not understood, the system may back up through the c o n t r o l l i n k s r a t h e r than sending an e r r o r message to the CD a s s o c i a t e d with the message causing the problem. This type of e r r o r processing A Frame System Model f o r Understanding Natural language 41 w i l l only be used with e r r o r s of type *MESSAGE and *FULL. This c r e a t e s a network of p o i n t e r s between the c u r r e n t l y a c t i v e EFs which w i l l be used f o r performing back up e r r o r processing. The inform a t i o n i n the EF c o n s i s t s of the a c t u a l s l o t s f o r a f r o n t and a roof frame. I t must also contain i n f o r m a t i o n about the r e l a t i o n s h i p s between the two subframes. For example, i n the s p e c i f i c house frame the f o l l o w i n g two r e l a t i o n s h i p s must hold: 1. ) Support - The f r o n t of the house must support the roof of the house. 2. ) Marry - This r e l a t i o n s h i p i s taken from Winston's work [ 2 7 ] , This means that the top of the f r o n t must be i n d i r e c t contact with the bottom of the roof of the house. The two surfaces must be e x a c t l y a l i g n e d , without any overhang by e i t h e r the roof or the f r o n t of the house. Al s o , the frame must be able to r e t u r n information about t h i s instance of a house to any frame which may reguest i t . For example, the house EF must be able to r e t u r n the l o c a t i o n of i t s e l f on the graphics screen, i t s top, i t s bottom and other p h y s i c a l c h a r a c t e r i s t i c s which a g r a p h i c a l house may possess. This information w i l l be needed by the frames f o r Marry and Support, s i n c e they must know the coordinates of the g r a p h i c a l house to e i t h e r check to see i f the r e l a t i o n s h i p i s s a t i s f i e d or t o make the r e l a t i o n s h i p hold. A Frame System Model f o r Understanding Natural Language 42 3.7. Representation of P r o p e r t i e s P r o p e r t i e s modify nouns or obj e c t s and f u r t h e r s p e c i f y the obje c t s described. P r o p e r t i e s correspond most c l o s e l y with a d j e c t i v e s and i n f a c t most of the property frames correspond e x a c t l y with a d j e c t i v e s . P r o p e r t i e s a l s o correspond to p a r t i c i p l e s such as moving, i . e . a p h y s i c a l object may have the property that i t i s moving. These verbs are handled i n e x a c t l y the same way as a d j e c t i v e s . The frame f o r a property i s very much l i k e t h a t f o r a noun, however, there i s always only one frame associated with a property. There are no EE's f o r instances of p r o p e r t i e s , s i n c e the only thing that these would be u s e f u l f o r would be to t e l l which object had that property. The property BF i t s e l f w i l l c o n t a i n a l i s t of a l l such objects already. Thus t h i s s i n g l e frame i s i n complete c o n t r o l of the one property. Any requests to give or remove a property from an object or to check i f an object does or does not have a property must pass through the frame f o r that property. An example of a property frame i s given below. (FRDEFUN BIG (BFRAME (OBJECT BIG-CONTEXT) (CASES ((MAKE !> (OBJECT (ATOM !,OBJECT))) ; pr e t e s t code to make sure object ; can be made b i g . ; code to assign v a r i a b l e BIG-CONTEXT ; to the current value of BIG's context-(ADD (LIST 'SIZE OBJECT * BIG) BIG-CONTEXT) ; code to a c t u a l l y make object BIG. (DEMON-PROCESSOR (LIST * *DEMON !> RFRAME A Frame System Model f o r Understanding Natural Language 43 OBJECT) (LIST 'BIG OBJECT) BIG-CONTEXT) ; perform demon processing i n case ; any frames are waiting f o r t h i s ; o bject to be made b i g . (PSEUD FRCONTINUE (LIST 'BIG OBJECT)) ; r e t u r n to c a l l e r with the message that ; the object i s now b i g . ) ; end of f i r s t case. ((IS !> (OBJECT (ATOM !, OBJECT))) (COND ( ; i s information i n data base. ; i f so then return T. (FSEND FRCONTINUE T)) ( ; check to see i f object i s ; b i g using coordinates e t c . ; i f so then return T. (FSEND FRCONTINUE T)) (T ; otherwise r e t u r n NIL. (FSEND FRCONTINUE NIL))) ) ; end of second case. ) j end of cases. ) ) ; end of d e f i n i t i o n . The a c t u a l frame should be able to handle a message such as: (MAKE OBJ). Which means to make OBJ have the property corresponding to the frame being sent the message. This frame must be able to detect whether OBJ may or may not have the property. This i s a p r e t e s t t h a t must be made by the frame before i t goes ahead and makes OBJ have the property. Another message the frame should be able to handle i s : (IS OBJ) . This message i s asking i f OBJ has the property associated with the frame being sent the message. I f the object OBJ does have a Frame System Model f o r Understanding Natural Language 44 the property, then the message T w i l l be sent to the CP, otherwise NIL w i l l be sent. The a c t u a l t e s t w i l l u s u a l l y i n v o l v e a data base search to see i f OBJ has the property a s s o c i a t e d with the frame. I f the search f a i l s , then more work has to be done to a c t u a l l y check to see i f OBJ has the property. This w i l l u s u a l l y be done by checking the a c t u a l coordinates of the o b j e c t . In a more general domain, t h i s might i n v o l v e invoking v i s i o n procedures on the object to see i f i t a c t u a l l y has the property. This seems very much the way humans work. I f we know something already has a given property from i n f o r m a t i o n stored i n memory, we assume t h i s i nformation i s c o r r e c t . Otherwise we w i l l have to a c t u a l l y check whether the object has the property, u s u a l l y by l o o k i n g at i t . another message the frame should accept i s one of the form: (aSSERT OBJ) . Which i s s t a t i n g that OBJ has the property associated with frame. This message corresponds to an utterance such as: The square i s b i g i . e . i t corresponds to a statement by the student that OBJ has the property associated with the frame being sent the message. This a s s e r t i o n i s f i r s t checked to see i f the property i s true f o r the object or could p o s s i b l y be true f o r an object- The check s t a r t s i n the Conniver data base and then must continue to see i f the property i s true f o r an object i f the data base search f a i l s . The c o n d i t i o n s f o r t h i s search should be more relaxed since t h i s may be a personal preference of the student and o r d i n a r i l y may not be accepted i f the system i t s e l f were to A Frame System Model f o r Understanding Natural Language 45 assign the property to the o b j e c t . For example, i f an object i s coloured red and the student makes a statement of the form: The object i s blue. Then the system should balk and not execute i t . Rather i t should complain to the student about the statement and i n e f f e c t ignore i t . What the student must do i s u t t e r a sentence such as: Make the object blue. Such a statement would have the desired e f f e c t and could be c a r r i e d out by p a i n t i n g the object or whatever- In t h i s case there would be no c o n f l i c t , the o l d colour of the object can be deleted from the c u r r e n t context and the new one added. Other messages which a property frame must be able to handle are the negations of the messages above- These messages w i l l take the form: (HAKE (NOT OBJ) ) (IS (NOT OBJ)) (ASSERT (NOT OBJ)) r e s p e c t i v e l y . So t h i s means that i t i s p o s s i b l e to make an object not have some property, to check to see i f an object does not have some property and to a s s e r t t h a t an object does not have a property. U n f o r t u n a t e l y , i t i s not p o s s i b l e t o use the negation of a property to represent the opposite of that property. For example, big i s the opposite of s m a l l , so i t would be nice to be able to use the negation feature f o r say b i g to represent small A Frame System Model f o r Understanding Natural Language 46 wi t h i n the same frame. However, t h i s i s impossible since small i s not n e c e s s a r i l y the same as not b i g . That i s something may be of medium s i z e , i n which case i t i s n e i t h e r big nor small 3.8. Representation of Rela t i o n s R e l a t i o n s are predicates of two or more arguments. R e l a t i o n s correspond to p r e p o s i t i o n s and composite phrases such as son o f , f r o n t o f , greater than, l e s s than, e t c . Those r e l a t i o n s h i p s which are derived from p r e p o s i t i o n s and composite phrases not using "of" are frames, much l i k e the frames corresponding to p r o p e r t i e s . Associated with each r e l a t i o n s h i p there i s only one frame, i . e . there w i l l be no EF's f o r a r e l a t i o n . There i s no need f o r frames corresponding to instances of r e l a t i o n s h i p s , since the only t h i n g needed to be contained i n such frames would be the two objects which were f u l f i l l i n g t hat p a r t i c u l a r i n s t a n c e of the r e l a t i o n s h i p . This can be more e a s i l y done using the Conniver data base f a c i l i t i e s f o r s t o r i n g the in f o r m a t i o n . Thus a l l reguests to make a r e l a t i o n hold between two obj e c t s or to destroy the r e l a t i o n s h i p between two objects must pass through the s i n g l e frame f o r the r e l a t i o n s h i p . An example of a r e l a t i o n frame f o l l o w s . (FRDEFUN BIGGER (BFRAME (0BJECT1 0BJECT2 BIGGER-CONTEXT) (CASES ((MAKE !>(0BJECT1 (ATOM ! r0BJECT1)) !>(0BJECT2 (ATOM !,0BJECT2))) A Frame System Model f o r Understanding Natural Language 47 p r e t e s t code to make sure OBJECT1 can be made bigger than 0BJECT2. code to assign variable- BIGGER-CONTEXT to the current value of BIGGER * s context. (ADD (LIST 'BIGGER OBJECT 1 0BJECT2) BIGGER-CONTEXT) ; code to a c t u a l l y make OBJECT 1 ; bigger than 0BJECT2. (DEMON-PROCESSOR (LIST 1*DEMON !>RFR AME (LIST OBJECT 1 OBJECT2)) (LIST 'BIGGER OBJECT 1 0BJECT2) BIG-CONTEXT) perform demon processing i n case any frames are waiting f o r 0BJECT1 to be made bigger than 0BJECT2. (FS END FRCONTINUE (LIST * BIGGER 0BJECT1 OBJ ECT 2) ) ; retu r n to c a l l e r with the message that ; OBJECT 1 i s bigger than 0BJECT2 ) ; end of f i r s t case. ( (IS !>(0BJECT1 (ATOM !,OBJECT1)) !>(OBJECT2 (ATOM !,0BJECT2))) (COND ( ; i s informa t i o n i n data base. ; i f so then r e t u r n T to CP. (FSEND FRCONTINUE T)) ( ; check to see i f 0BJECT1 i s ; bigger than 0BJECT2-; i f so then ret u r n T to CP. (FSEND FRCONTINUE T) ) (T ; otherwise ret u r n NIL to CP. (FSEND FRCONTINUE NIL))) ) : end of second case. ) ; end of cases. )) ; end of d e f i n i t i o n . The frame i t s e l f , must be able to handle a message of the form: (MAKE 0BJ1 0BJ2) which means to make 0BJ1 and 0BJ2 have the r e l a t i o n s h i p between A Frame System Model f o r Understanding Natural language 48 them that corresponds to the frame which was sent the message. A pr e t e s t must be made by the frame to make sure that 0BJ1 and 0BJ2 may have that r e l a t i o n s h i p between themselves. I f not then an e r r o r message w i l l be sent to the CD f o r the message sent to the r e l a t i o n frame. Another message the frame must be able to respond to i s of the form: (IS 0BJ1 0BJ2). That i s , do the two o b j e c t s , 0BJ1 and 0BJ2, s a t i s f y the r e l a t i o n s h i p corresponding to the frame being sent the message? I f they do then the message T w i l l be sent to the CP, otherwise NIL w i l l be sent. The a c t u a l processing of such a reguest w i l l i n v o l v e a simple data base search to see i f 0BJ1 and 0BJ2 are i n the c o r r e c t r e l a t i o n s h i p with each another. This search would riot j u s t check to see that 0BJ1 i s i n the c o r r e c t r e l a t i o n s h i p with 0BJ2, but depending on the r e l a t i o n s h i p , the frame may perform more complex processing. For example, with the r e l a t i o n s h i p i n s i d e , the two objects may not be stored with the i n s i d e r e l a t i o n s h i p between them but there may be a s e r i e s of obje c t s such that OBJi+1 i s i n s i d e OBJi f o r a l l i over the s e r i e s . I f the f i r s t element of the s e r i e s i s i n s i d e 0BJ1 and 0BJ2 i s i n s i d e the l a s t element of the s e r i e s , then 0BJ2 i s i n s i d e 0BJ1. This s o r t of i n f e r e n c e i s often made by people and w i l l be easy to perform w i t h i n the one frame. Note that only the context f o r the one frame corresponding to the r e l a t i o n s h i p need be used i n the i n f e r e n c i n g . This should reduce the necessary amount of search to an acceptable l e v e l . I f the data A Frame System Model f o r Understanding Natural Language 49 base search f a i l s , then more processing must be done to a c t u a l l y check to see i f the r e l a t i o n s h i p holds between the two o b j e c t s . In t h i s case the system would have to use the coordinates of the two objects to check that the r e l a t i o n s h i p does indeed hold. In a more general system t h i s might inv o l v e a v i s u a l system which looks at the two obj e c t s i n v o l v e d and uses t h i s i n f o r m a t i o n to check i f the r e l a t i o n s h i p holds. A f u r t h e r message that the frame must be able t o accept i s of the form: (ASSERT 0BJ1 0BJ2) This simply s t a t e s t h a t 0BJ1 and 0BJ2 are i n the c o r r e c t r e l a t i o n s h i p with one another. However, such a r e l a t i o n s h i p must be checked to see i f i t i s v a l i d or at l e a s t p o s s i b l e i n which case the r e l a t i o n s h i p w i l l be i n s t a n t i a t e d i n the data base. I f there i s no p o s s i b i l i t y of such a r e l a t i o n s h i p h o l d i n g , then an e r r o r w i l l occur and an e r r o r message sent to the CD of the a s s e r t i o n message. For example, someone might say: John i s beside the b u i l d i n g . I f no e x p l i c i t check can be made, i . e . you can't see the b u i l d i n g where John i s , then the r e l a t i o n s h i p between John and the b u i l d i n g w i l l be assumed t r u e , at l e a s t u n t i l c o n t r a d i c t o r y i n f o r m a t i o n comes to l i g h t . Other messages which a r e l a t i o n s h i p frame must be able to handle are the negations of the messages above. These messages w i l l have the form: (MAKE (NOT 0BJ1 0BJ2) ) A Frame System Model f o r Understanding Natural Language 50 (IS (NOT OBJ1 OBJ2) ) (ASSERT (NOT 0BJ1 OBJ2)) r e s p e c t i v e l y . This means tha t i t i s p o s s i b l e to make two obj e c t s not have some r e l a t i o n s h i p between them, to see i f two objects do not have some r e l a t i o n s h i p between them and to a s s e r t that two objects do not have some r e l a t i o n s h i p between them. The other type of r e l a t i o n s h i p i s of the form: son o f , f r o n t o f , e t c . Such r e l a t i o n s can be considered as s e l e c t o r s f o r the s l o t s of a frame. For example, consider the f r o n t of the.house. This i s s e l e c t i n g the f r o n t s l o t of the frame representing "the house". Every house must have a s l o t to contain the frame representing i t s f r o n t . A c t u a l l y t h i s w i l l be a pointer to an instance of a frame representing the f r o n t . With a r e l a t i o n s h i p such as the one above, a message i s sent to the frame corresponding to the object on the r i g h t s i d e of the "of". Since there may be a c o n s t r u c t such as: the window of the f r o n t of the house such phrases must be processed r e c u r s i v e l y . The f i r s t t h i n g to be done i s to determine the r e f e r e n t f o r "the house". Once t h i s has been determined a message may be sent to t h i s frame to s e l e c t the s l o t corresponding to the f r o n t of "the house". This "house" frame must be able to respond with the name of the frame f i l l i n g a s l o t when an appropriate message i s sent to i t . Once the frame f o r representing "the f r o n t of the house" has been determined, a message may be sent to t h i s frame to obtain the name of the frame corresponding to the s l o t f o r "window". This A Frame System Model f o r Understanding Natural Language 51 frame would then be the r e f e r e n t f o r the phrase "the window of the f r o n t of the house". The "of" r e l a t i o n s h i p i s t o t a l l y dependent on the objects i n the system and a l l frames as s o c i a t e d with them must be able to handle messages such as those described above. When a message i s sent to a frame wanting a value of a s l o t to be returned, a l i s t of a l l the candidates t h a t f i l l s l o t s of that type i n the frame w i l l be returned to the CP. The frame requesting the l i s t of values f o r a s l o t of a frame must then decide which i f any of the frames i s the one desired- I f no frame i s f i l l i n g the s l o t when the message i s sent, NIL w i l l be returned to the CP-3 . 9 . Representation of Actions or Verbs actions correspond to verbs. Verbs do not have d i s t i n c t frames associated with them. They form part of messages to frames and u s u a l l y correspond to the f i r s t atom i n the message. Thus a c t i o n s may only be performed by a frame -representing the subject of the a c t i o n . A l l frames which may perform an a c t i o n s p e c i f i e d by some verb must be able to handle a message with that verb as the f i r s t word i n the message. For example i n the c u r r e n t problem domain described, a l l the s p e c i f i c object frames must be able to accept a message to draw themselves. Thus to draw a square on the graphics screen a c a l l t o SEND i s made of the f o l l o w i n g form: (SEND * SQUARE ' (DRAW) CONTINUATION COMPLAINT). A Frame System Model f o r Understanding Natural Language 52 Where SQUARE s p e c i f i e s that the message i s to be sent to the square BF. (DRAW) i s a message which s p e c i f i e s that a square i s to be drawn. CONTINUATION i s where the computation should continue when a square has been drawn on the graphics screen, COMPLAINT i s where to go i f an e r r o r i s encountered while drawing the square of i f the message i s not decoded properly. Verbs which s p e c i f y a c t i o n s f o r a s p e c i f i c frame only must be handled by that s p e c i f i c frame. For example, the verb draw s p e c i f i e s a s p e c i f i c a c t i o n to the object being drawn- The object i t s e l f i s the only frame which knows how to draw i t s e l f . In general t h i s i s not always the case, f o r example, f o r moving any object about the graphics screen, i t i s not necessary f o r each object type t o know how to move i t s e l f around the screen. What can be done i s to create a superset frame of a l l these objects which can be moved around on the graphics screen. This superset frame would know a l l about moving o b j e c t s . Some a c t i o n s must be associated with a s p e c i f i c frame and others may be a s s o c i a t e d with a more general frame. Thus superset processing i s used h e a v i l y i n representing a c t i o n s which may be performed on a frame or by a frame. A g r a p h i c a l object frame w i l l c o n t a i n information on how to move g r a p h i c a l o b j e c t s (squares, r e c t a n g l e s , t r i a n g l e s , c i r c l e s , etc.) around a graphics screen. This frame must a l s o accept messages corresponding to sentences l i k e : Draw an o b j e c t . where object r e f e r s to a g r a p h i c a l o b j e c t , In t h i s case the A Frame System Model f o r Understanding Natural Language 53 g r a p h i c a l object frame would have to pick one of i t s subsets at random (or p o s s i b l y i t s f a v o u r i t e type of g r a p h i c a l object) and i send a message to t h i s object to draw i t s e l f . Thus i t might pick a square to be drawn and send a message to the square frame s p e c i f y i n g that a square i s to be drawn. This i s not l i k e superset processing, where a message i s sent to a l l the supersets of a frame i f a message cannot not be understood. The gr a p h i c a l object frame must be able to decode any of the act i o n s that any of i t s subframes can perform. This means that i t must be able to decode a message caused by a sentence such as the above example and then decide what t o do. There can be no automatic subset processing i n the same way that there i s automatic superset processing. With the many d i f f e r e n t a c t i o n s which may be encountered i n a sentence, there are many d i f f e r e n t a c t i o n s that a frame must be able to handle. This number of a c t i o n s may be reduced through the use of p r i m i t i v e a c t i o n s s i m i l a r to those that Schank proposes [20]. In t h i s way the amount of information contained by a. frame may be reduced and the amount of i n f e r e n c i n g needed to handle sentences should a l s o be reduced. In the graphics domain there are very few p r i m i t i v e a c t i o n s necessary. The three a c t i o n s ASSERT, IS and MAKE as described above must be present i n the system. Besides these a c t i o n s the only other ones needed are: DRAW and MOVE. DRAW w i l l be needed f o r drawing new objects on the graphics screen. This a c t i o n would a l s o correspond t o d i f f e r e n t verbs. For example, the sentence: A Frame System Model f o r Understanding Natural Language 54 Place a square i n s i d e the f r o n t would c a l l f o r a new object to be drawn on the screen and the p r i m i t i v e a c t i o n DRAW would be used to handle t h i s sentence-S i m i l a r l y the p r i m i t i v e a c t i o n MOVE w i l l be used to handle other verbs besides the verb "move". For example, the sentence: Place the.small square i n s i d e the f r o n t w i l l cause the p r i m i t i v e a c t i o n MOVE t o be used to move the sguare (which would have to be on the graphics screen already) to a l o c a t i o n i n s i d e the f r o n t of the house. A Frame System Model f o r Understanding Natural Language 55 Chapter 4. The Model i n Use In t h i s chapter an example of how frames i n t e r a c t and perform i n f e r e n c e s f o r understanding n a t u r a l language w i l l be described. This example w i l l c o n s i s t of the necessary i n f e r e n c e s needed when a person goes through the process of drawing a g r a p h i c a l house using E n g l i s h commands. This problem may at f i r s t seem very simple, but i t a c t u a l l y i n v o l v e s many d i f f i c u l t problems of n a t u r a l language understanding. 4 . 1 . S p e c i f i c a t i o n of Top Lev e l frames In a system f o r n a t u r a l language processing, there must be some frames which c o n t r o l the understanding process. 'What i s proposed i s that there be a frame which can be thought of as a "consciousness" frame, which w i l l be i n c o n t r o l of the complete computation. This frame should be ready t o respond to any inp u t s received from any of i t s sensory modes. In t h i s case the only sensory mode i s the input from the t e r m i n a l keyboard typed i n by the user. The "consciousness" frame must be able to accept a l l i n p u t s , some of which may be ignored; others may be suppressed. This "consciousness" frame w i l l send a message to a conversation frame when i t detects an utterance from some input source (e«g- a person), or when i t wants to begin a conversation with a person. A Frame System Model f o r Understanding Natural Language 56 The "consciousness" frame w i l l contain enough i n f o r m a t i o n to decide which subframes are to be a c t i v a t e d on r e c e i v i n g some in p u t . That i s when some form of stimulus i s a p p l i e d to the "consciousness" frame, i t w i l l decide which subfrarae t o invoke. In the case that a stimulus which i s the beginning of a conversation i s a p p l i e d , a conversation subframe w i l l be invoked. In a system which i s dealing only with n a t u r a l language processing and does not have any other form of s t i m u l u s , there i s no need f o r a "consciousness" frame, since i t w i l l immediately see that a conversation i s to take place and w i l l j u s t invoke the conversation frame. The conversation frame i t s e l f w i l l c o n s i s t of two major subframes and must a l s o have the a b i l i t y to send messages to other frames. This frame w i l l u s u a l l y be the frame that begins the process of making an assumption about what i s being t a l k e d about. The f i r s t t h i n g the conversation frame w i l l do i s send a message to an input frame which w i l l i n p u t utterances and convert them i n t o an i n t e r n a l format. This i n t e r n a l format w i l l c o n s i s t of messages to be sent to other frames involved i n the understanding of the utterance. The input frame w i l l c o n s i s t of a s y n t a c t i c analyzer which w i l l be passed the input utterance. This frame w i l l then begin t o parse the utterance as f a r as p o s s i b l e . The s y n t a c t i c a n a l y s i s frame w i l l have f u l l access to a l l the frames known by the system. The parsing frame, having f u l l access to a l l the information stored i n the system w i l l a l s o be able to perform A Frame System Model f o r Understanding Natural Language 57 semantic a n a l y s i s of the utterance at the same time, to help i n disambiguating sentences. In t h i s way the parse of an utterance can be guided by the semantic information a v a i l a b l e i n the system's knowledge base- What t h i s parsing frame w i l l produce i s one or more messages and the frames to which these messages should be sent- These messages w i l l cause the c o r r e c t a c t i o n to be performed, or w i l l update the data base with new i n f o r m a t i o n , or r e t u r n information i n response to a question, The subject of the sentence w i l l be the noun t h a t determines which frame the message or messages are to be sent to. By subject of a sentence, I mean the main noun of a sentence. In an imperative sentence t h i s w i l l u s u a l l y be the a c t u a l object of the sentence. In a d e c l a r a t i v e sentence t h i s w i l l normally be the a c t u a l subject of the the sentence. The d e c i s i o n of which noun i s the main one i s a d i f f i c u l t problem to solve i n general. In some cases, there w i l l only be one noun i n a sentence, i n which case, the d e c i s i o n w i l l be s i m p l i f i e d . In other cases s y n t a c t i c and even semantic knowledge w i l l have to be used. Often noun phrases w i l l have to be disambiguated by the input frame. This should be done by the parsing f u n c t i o n i n most cases. The method w i l l be to send messages to the main noun of the phrase and to a l l the frames t h a t represent the p r o p e r t i e s that t h i s noun must have. These messages w i l l s p e c i f y that a l i s t of a l l the s p e c i f i c i n s t a n c e s of the noun i s t o be returned and that a l i s t of a l l the objects that have the p r o p e r t i e s associated with the property frames sent the message A Frame System Model f o r Understanding Natural Language 58 be returned. In t h i s way, the input frame w i l l have l i s t s of a l l the s p e c i f i c i n stances of the main noun and a l i s t of a l l the objects which have the p r o p e r t i e s s p e c i f i e d i n the noun phrase. These l i s t s may then be i n t e r s e c t e d with one another to produce a l i s t of a l l the p o s s i b l e r e f e r e n t s f o r the noun phrase. This information can then be used to determine an a c t u a l r e f e r e n t f o r the noun phrase. Through the use of Conniver contexts, the whole data base need not be searched but only the c u r r e n t l y a c t i v e data base. Messages w i l l then be sent t o the frames corresponding to the main noun of the sentence. What the input frame does depends on the type of the sentence. When a command i s encountered, the input frame w i l l send a message to the c o r r e c t frame s p e c i f y i n g as CP, the one s p e c i f i e d i n the message to the input frame. When a d e c l a r a t i v e sentence i s encountered, a message w i l l be sent to the c o r r e c t frame s p e c i f y i n g the input frame as the CP. The input frame w i l l , when i t regains c o n t r o l , read i n the next inp u t sentence. When a question sentence i s found a message w i l l be sent t o the c o r r e c t frame s p e c i f y i n g the input frame as the CP. The response to the question w i l l be returned to the input frame. The input frame would then send t h i s information to the output frame so tha t an E n g l i s h sentence may be constructed to be output t o the student. Once the semantics of an utterance have been determined and the associated semantic a c t i o n s have been performed the system w i l l have to output some message to the user. This would i n v o l v e the second important subframe of the conversation frame. A Frame System Model f o r Understanding Natural Language 59 This frame would have to generate surface l e v e l E n g l i s h responses to the i n p u t utterances- This would be passed the o r i g i n a l utterance together with the messages derived from t h i s utterance and the responses that were returned by the frames. The output frame would have to be r e s p o n s i b l e f o r generating surface l e v e l E n g lish sentences from inform a t i o n passed to i t v i a messages. Any frame i n the system would have to be able to send a message to t h i s frame so t h a t i t may output a message to the user. The a c t u a l processes used to generate surface l e v e l E n g l i s h sentences would be completely contained i n t h i s one frame together with i t s subframes. The r e s t of t h i s chapter w i l l assume th a t the input and output frames can be developed to a l e v e l necessary to a c t u a l l y make the system useable. This t h e s i s i s more motivated by the i n t e r n a l workings of the system and not so much with the input and output problems associated with n a t u r a l language. Examples of how inferences are made and how expectations are used to d r i v e the computation w i l l now be given. 4.2. A D e t a i l e d Example In t h i s s e c t i o n I s h a l l give a complete example of the system i n use- The a c t u a l messages sent between the frames w i l l be given. These w i l l be presented i n a t a b u l a r form, the f i r s t entry w i l l be the message, the second w i l l be the frame sent the message, the t h i r d w i l l s p e c i f y the CP and the f o u r t h w i l l give the CD. The frame sending the message w i l l be the one j u s t A Frame System Model f o r Understanding Natural Language 60 above the entry i n the t a b l e . A sentence w i l l be presented, and then the t a b l e with the messages sent to process the sentence and f i n a l l y a comment on why the system sent the messages i n t h i s manner. Frames which have numbers a f t e r t h e i r names are EF's; the others are BF's. When the system i s run the top l e v e l frame (TLF) w i l l be invoked. I t would begin by g i v i n g the student a b r i e f i n t r o d u c t i o n to what the system could do. I t would e x p l a i n to him how to input sentences to the system using the term i n a l keyboard. I t would a l s o d i s p l a y the b u i l t - i n f i g u r e s of the system, so that he w i l l have some idea of what f i g u r e s he may use. The system would then begin the process of teaching the student to use the graphics t e r m i n a l by asking him to rec o n s t r u c t a g r a p h i c a l house, f o r example. At t h i s point the system would prompt the student f o r input and begin the s e s s i o n . 1 T j*NEXT |INPUT FRAME | TLF 1TLF j i j The TLF sends the message *NEXT to the input frame which causes i t to input and process a sentence from the student. 1.) Draw a big square. | (DRAW BIG) 1 | SQUARE i 1 i TLF - • i |INPUT FRAME | i I 1 | (MAKE SQUARE 1) 1 i |BIG i ! 1 1 SQUARE 4 1 \SQUARE | t I i | (BIG SQUARE1) j 1 | SQUARE ' ! 1 1 , 1 1 1 1 i » | (SQUARE SQUARE 1) i , -j | TL F I I J i 1 1 i At t h i s point i n the computation, a b i g square w i l l have A Frame System Model f o r Understanding Natural Language 61 been drawn (see F i g . 1). This square w i l l e v e n t u a l l y be used to represent the f r o n t body of the house. When the BIG frame i s asked to make the square b i g , i t w i l l have no inf o r m a t i o n a v a i l a b l e to decide on how b i g to make the square. What must be done i s to attach context i n f o r m a t i o n to the square BF so that the BIG frame may use t h i s knowledge to make the d e c i s i o n . One p o s s i b l e method i s t o put a l i s t of three numbers on the property l i s t of the square BF. These numbers would be m u l t i p l i c a t i o n f a c t o r s f o r making the d e f a u l t square s m a l l , medium and larg e (e.g. 0.5 1.0 2.0). Another p o s s i b l e way would be to attach a Conniver context t o the square BF which would contain examples of d i f f e r e n t s i z e d squares. The BIG frame could then use t h i s information t o make the d e c i s i o n . The TLF w i l l now have to decide which subframe to make a c t i v e . Since the student was asked to draw a house, t h i s d e c i s i o n can be made e a s i l y and the house frame w i l l be invoked. i J (SQUARE I SQUARE1) | HOUSE 1 TLF | TLF i 1 1 1 | (*DEM0N I HOUSE) | H0USE2 1 HOUSE 1 | TLF i 1 1 l IT 1 | HOUSE 1 1 1 t "" 1 1 ( 1 | (SQUARE 1 SQUARE 1) IHOUSE2 i . i TLF 1 | TLF i ' ~ 11 1 1 | (*DEM0N i H0USE2) 1 |FRONT 1 H0USE2 f |H0USE2 i 1 1 1 i |T I | H0USE2 1 \ 1 i I 1 1 1 | (*DEM0N | HOUSE 2) | ROOF \ H0USE2 ! 1H0USE2 i 11 1 |T i | H0USE2 , , , ... i 1 i ' 1 1 | J | (SQUARE i SQUARE 1) |FRONT T H0USE2 r |H0USE2 i I 1 j i | (*DEM0N l FRONT) |FR0NT3 1 FRONT 1 1 FRONT 1 1 J A Fraae System Model f o r Understanding Natural Language 62 Figure 1. A Frame System Model f o r Understanding Natural Language 6 3 1 " ' I T J F R O N T I I 1 i . .. \ ( S Q U A R E S Q U A R E 1) | F R O N T 3 i F R O N T t | F R O N T i . .. | ( * D E MON F R O N T 3 ) | F R O N T - B O D Y T F R O N T 3 i 1 -j F R O N T 3 i 1 T | F R O N T 3 1 1 1 . _ _ ! „ , | ( * D E MON F R O N T 3 ) | DOOR 1 F R O N T 3 I ~ | F R O N T 3 i i T j j F R O N T 3 1 J -1 i „. | (* DEMON F R O N T 3 ) l WINDOW 1 F R O N T 3 r J FRO NT 3 „ „ i „, 1 T l F R O N T 3 1 1 ™ • •• -1 i | ( S Q U A R E S Q U A R E 1) | F R O N T - B O D Y 1 F R 0 N T 3 1 I F R O N T 3 , i J ( * D E M O N | F R O N T - B O D Y ) J F R O N T - B O D Y 4 ! F R O N T - B O D Y 1 | F R O N T 3 1 i I T | F R O N T - B O D Y i J I | ( S Q U A R E i S Q U A R E 1 ) | F R O N T - B O D Y 4 i FRO NT3 t | F R O N T 3 The message f o r the square has now been f i l t e r e d down the f r o n t body EF which w i l l a s s e r t that i t i s represented by the square. The above sequence of the messages i s r e l a t i v e l y s t r a i g h t forward. The only time any major d e c i s i o n must be made i s when the f r o n t EF must decide whether the square i s t o represent the f r o n t body or the window. In t h i s case the d e c i s i o n that the square should represent the f r o n t body i s made ea s i e r by the e x t r a knowledge that the square i s b i g . In other cases the same assumption w i l l normally be made but f o r a d i f f e r e n t reason. When a person i s drawing a f i g u r e , he tends to draw the major components f i r s t before the minor ones. This assumption may be used to make the d e c i s i o n t h a t the square w i l l represent the f r o n t body. I f , the square had been drawn s m a l l , the d e c i s i o n may be made that the square should represent the A Frame System Model f o r Understanding Natural Language 64 window. The many demon messages are so that when a component of the house i s recognized by the system, the frame of which the component i s part w i l l be n o t i f i e d . Since the f r o n t body has been recognized, t h i s i n f o r m a t i o n w i l l begin to f i l t e r back up the chain through the demons s p e c i f i e d by the higher frames. 1 | (*OCCUR il (FRONT-BODY |FR0NT-B0DY4)) 1 (FRONT-BODY 1 1 j 1 1 1 FRONT-BODY4 |FRONT—BODY4 1 | (*OCCUR | (FRONT-BODY JFR0NT-B0DY4)) | .1 | FR0NT.3 1 1 t r_ I 1 I _ j FRONT-BODY J FRONT-BODY | (*0CCUR (FRONT JFR0NT3) ) t 1 |FRONT 1 I i 1 J i FR0NT3 |FR0NT3 I | (*OCCUR (FRONT J FR0NT3) ) 1 I JHO0SE2 1 i 1— 1 1 _ j FRONT |FRONT J |T i 1 |FRONT I . . . , i i -l JT 1 1 ! |FR0NT3 i —f~ 1 _ j 1 IT 1 1 }FRONT-BODY „ i T 1 i__ j l IT a V J FR0NT-B0DY4 f~ 1 The demon processing w i l l back up a l l the way up to the house EF, s i n c e a f r o n t which j u s t c o n s i s t s of a f r o n t body i s j u s t as good as one which contains a f r o n t body, a door and a window. Control w i l l be returned t o the f r o n t body EF a f t e r the demon processing has f i n i s h e d . At t h i s p o i n t , the f r o n t body EF w i l l pass c o n t r o l to the sguare so that when the word " i t " i s encountered i n a sentence by the input frame, the input frame w i l l be able to determine the re f e r e n t f o r " i t " e a s i l y . A Frame System Model f o r Understanding Natural Language 65 t \ (SQUARE SQUARE1) j |SQUARE1 i | FR0NT-B0DY4 i i J FRONT-BODY** J i i J *NEXT i . , 1 |INPUT FRAME 1 | SQUARE 1 I ... j 1 ] i Note that t h i s i s the f i r s t time that the sguare EF frame has been entered. 2.) Make i t bigger. 1 • | (MAKE BIGGER) 1 | SQUARE i | SQUARE1 j JINPUT FRAME i 1 | (SQUARE 1 (MAKE ] BIGGER) ) 1 J SQUARE 1 I SQUARE1 1 ISQUARE1 J 1 \ (SQUARE 1 (MAKE | BIGGER) ) I JOBJECT ! i | SQUARE i j SQUARE i i 1 1 (MAKE SQUARE 1 JSQUARE1) 1 , . \ \ BIGGER i ( OBJECT 1 j OBJECT \ i ,, , | (BIGGER SQUARE 1 | SQUARE1) « „ 1 |OBJECT 1 j ! • 1 1 J i | (BIGGER SQUARE 1 | SQUA.RE1) l ,, , 1 | SQUARE t i ! j 1 1 j 1 \ (BIGGER SQUARE 1 | SQUARE1) t 1 1 SQUARE 1 I 1 i I 1 1 1 |*NE XT i (INPUT FRAME | SQUARE1 1 i I The above sequence of messages i s an example of superset processing. When the sguare EF i s sent the o r i g i n a l message, i t i s not able t o recognize i t . Rather than immediately causing an e r r o r message to be sent, the square EF i n i t i a t e s superset processing to see i f any of the superset frames know what the message means. In t h i s case the g r a p h i c a l object frame does know what the message means. I t r e a l i z e s that an object i s to have some a c t i o n performed on i t and uses the f a c t that BIGGER A Frame System Model f o r Understanding Natural Language 66 i s a r e l a t i o n to con s t r u c t the message sent to the a c t u a l BIGGER frame (see F i g . 2) . 3.) A t r i a n g l e , please. ] | (DRAW) j |TRIANGLE | SQUARE1 i |INPUT FRAME i | (TRIANGLE |TRIANGLES) 1 j |SQUARE 1 1 S 1 i i j 1 (*EBROB *MESSAGE | (TRIANGLE J TBIANGLE5) ) 1 |FRONT-BODY4 t 1 1 1 i i ] (*ERBOR *MESSAGE 1 (TRIANGLE I TRIANGLES)) t |FRONT3 i 1 1 1 I • l ] (*ERROR *MESSAGE J (TRIANGLE J TBIANGLES)) < IH0USE2 1 I ! i 1 1 When the square r e c e i v e s the message from the t r i a n g l e , i t has no idea what the message means. I t then t r i e s superset processing (which wasn't shown) which f a i l s because none of i t s supersets w i l l know what the message means e i t h e r . I t then generates a ^MESSAGE type e r r o r which t r a v e l s up to the house EF which does know what the message means. The house EF w i l l assume that the message i s meant f o r the roof frame and thus w i l l send i t to the roof BF (see F i g . 3). Frame System Model f o r Understanding Natural Language Figure 2. rame System Model f o r Understanding Natural Language Figure 3. A Frame System- Model f o r Understanding Natural language 69 r • | (TBIANGLE | T H I A N G L E S ) | |ROOF ! HOUSE2 |HOUSE2 1 i | (*DEMGN ROOF) i J ROOF6 i ROOF 1 |HOUSE2 i 1 IT | (ROOF i \ 1 i | (TRIANGLE iTRIANGLE5) j | ROOF6 ! HOUSE2 1 |HOUSE2 1 i i J (*OCCDB (ROOF |R00F6)) i | ROOF ! ROOF6 t |ROOF6 1 1 , l | (* OCCUR (ROOF | ROOF6) ) | IHOUSE2 ! ROOF 1 | ROOF 1 i  (IS FRONT3 J ROOF6) | 1 SUPPORTS ] HOUSE2 1" |HO USE2 1 | NIL 1 JHOUSE2 t 1 , i i | (*DE MON HOUSE2 | (FRONT3 R00F6) ) i | SUPPORTS — J HOUSE2 t |HOUSE2 1 1 I T i i | HOUSE2 1 i 1 j (IS FRONT3 |ROOF6) j „__ | MARRY I HOUSE2 1 1 HOUSE2 1 ,,, i „., ,.„ | NIL i | HOUSE2 — j 1 i. , i i | (*DEMON HOUSE2 J (FR0NT3 R0OF6) ) | 1 MARRY — j — HOUSE2 1 j HOUSE2 1 1 _ I T IHOUSE2 1 1 i I T 1 IROOF 1 j 1 i 1 |T 1 JROOF6 . i 1 J 1 i i | (TRIANGLE iTRIANGLES) n |TSIANGLE5 ! ROOF 6 J |ROOF6 1 i 1*NEXT |INPUT FRAME i TRIANGLE5 1 |TRAINGLE5 The house EF decided that the t r i a n g l e was meant to be part of the roof. When the t r i a n g l e has been assigned the s l o t f o r representing a roof, demon processing w i l l be performed t e l l i n g the house EF of the existence of the roof. At t h i s p o i n t , both A Frame System Model f o r Understanding Natural Language 70 the major components of the house w i l l be i n e x i s t e n c e . This means that the s l o t s f o r the r e l a t i o n s h i p s between the roof and the f r o n t w i l l be checked. In t h i s case n e i t h e r r e l a t i o n w i l l hold and demon messages are sent so that the house EF w i l l be t o l d when they do hold. 4.) Make i t b i g . i 1 J (MAKE BIG) |TRIANGLE5 I TRIANGLES JINPUT FRAME | | j, i j 1(TRIANGLE5 |TRIANGLE | TRIANGLE5 fTRIANGLE5 | | (MAKE BIG) ) | | | | j + ^ + \ UTRIANGLE5 JOBJECT I TRIANGLE I TRIANGLE \ | (MAKE BIG) ) | | | \ j 1 j j 1 | (MAKE TRI ANGLE 5) J BIG | OBJECT jOBJECT ,j I H r + I | (BIG TRIANGLE5) |OBJECT 1 j | j j. .! _| 1 \ (BIG TRI ANGLE 5) | TRIANGLE 1 1 J j j. + -\ 1 \ (BIG TRIANGLES) ]TRIANGLE5 ] ] J j (-- 1 + 1 ;?*NEXT j INPUT FRAME \ TSIANGLE5 J \ i . j This i s another example of superset processing i n a c t i o n . This time, however, the message sent to the g r a p h i c a l object frame s p e c i f i e s that the t r i a n g l e i s to be assigned the property b i g . Now there i s information a v a i l a b l e through demon processing and the e x i s t e n c e of the square f o r the BIG frame to make a d e c i s i o n as to how b i g the t r i a n g l e should be made. That i s the system now has s u f f i c i e n t f a c t s to begin to make in f e r e n c e s about a c t i o n s asked f o r by the student. In t h i s case the t r i a n g l e w i l l be made big enough so t h a t i t s base i s the same width as the top of the sguare (see F i g . 4) . Frame System Model f o r Understanding Natural Language A Frame System Model f o r Understanding Natural Language 72 5.) Move i t up a b i t . r j (MOVE UP BIT) j |TRIANGLES i i TRIANGLE5 |INPUT FRAME J i i | (TRIANGLE5 (MOVE j UP BIT) ) 1 1 |TRIANGLE 1 t , 1 1 1 j TRIANGLE5 f 1 |TRIANGLE \ J 1 • i i J (TRI ANGLE5 (MOVE |DP BIT)) | |OBJECT 3 j i 1 \ i _ TRIANGLE 1 1 J TRIANGLE | i 1 • < JT i 1 TRIANGLE i T 1 1 i i 1 I i . • 1 IT 1 t 1 TRIANGLES i T 1 - 4— i J 1 1 i i • |*NEXT t , , l 1 INPUT FRAME 1 TRIANGLE5 i "• i 1 I i Again superset processing i s necessary s i n c e the t r i a n g l e frame does not know how to move i t s e l f up. The g r a p h i c a l object frame, however, d i d know and thus performed the a c t i o n . Using the demon informat i o n s p e c i f i e d by the house EF f o r the f r o n t and the roof , the g r a p h i c a l object frame knows e x a c t l y how f a r up the t r i a n g l e should a c t u a l l y be moved. In t h i s case i t w i l l be too much to j u s t move the t r i a n g l e up a b i t , so that the t r i a n g l e w i l l onlybe moved up some d e f a u l t amount (say about an inch) (see F i g . 5). Thus no demons w i l l be s a t i s f i e d yet. 6.) Higher. 1 I (MAKE HIGHER) 1 |TRIA NGLE5 | TRIANGLE5 i i ]IN PUT FRAME | i i 1 I (TRIANGLES 1 (MAKE HIGHER) ) i |TRIANGLE J | TRIANGLE5 1 i • 1 — 1 |TRIANGLES | 1 1 i i 1 j (TRIANGLE5 | (MAKE HIGHER) ) • |OBJECT | TRIANGLE 1 1 1 |TRIANGLE j 1 1 . _ i Frame System Model f o r Understanding Natural Languaq Figure 5-A Frame System Model f o r Understanding Natural Language 74 J (MAKE TBI ANGLES 1 HIGHER j TRIANGLE5) J OBJECT J OBJECT j \ (HIGHEB |TBIANGLE5 |TBIANGLE5) 1 4-—•• |OBJECT 1 ] I —4 1 1 i i —-j 1 J 1 i i 1 (HIGHER 1 TBIANGLES |TRIANGLE5) ] l |TRIANGLE 1 ? j j 1 J 1 i 1 • ~ — 1 1 1 • „ , ,. | (HIGHEB j TRIANGLE5 j TBIANGLE5) j l J TRIANGLE5 i 1 i i i J i 1 1 J 1 i j *NEXT i l (INPUT FRAME i — I TBIANGLE5 1 This i s a sentence fragment which must be processed by the input frame. From context and the f a c t t h a t "higher" i s a r e l a t i o n s h i p i t should be easy to r e a l i z e that the sentence means to make the t r i a n g l e higher up the graphics screen. Thus the o r i g i n a l message w i l l be constructed and sent to the t r i a n g l e EF. The r e s t of the processing i s s t r a i g h t forward using superset processing. Again the g r a p h i c a l object frame w i l l not move the t r i a n g l e a l l the way up to the top of the sguare, but w i l l leave i t about an inch short (see F i g . 6). This w i l l normally be done to f r u s t r a t e the student somewhat, which w i l l l a t e r show him how u s e f u l the graphics hardware i s . 7.) Move i t up an i n c h . 1 ( (MOYE UP j (INCH 1.0) ) I j TRIANGLES 1 1 | TRIANGLE5 ,t i |INPUT FRAME | 1 1 i i ( (TRIANGLE5 (UP (INCH 1. i (MOVE 0))) j TRIANGLE I • I | TBIANGLE5 1 l 1 1 — 1 1TBIANGLE5 j i i i Frame System Model f o r Understanding Natural Language Figure 6. A Frame System Model f o r Understanding Natural Language 76 | (TBIANGLE5 |UP (INCH 1. i (MOVE 0) ) ) |OBJECT J OBJECT | TRIANGLE J TRIANGLE |TRIANGLE |TRIANGLE j 1 1 I I IT j i I TRIANGLE i 1 1 1 i 1 1 1 |T j 1 JTRIANGLES i I . t t 1 i S 1 i \*NEXT i IINPUT FRAME 3 | TRIANGLE5 T 1 1 1 J This sentence w i l l be e a s i l y handled by the input frame-The g r a p h i c a l object frame w i l l move the t r i a n g l e up about an inch (see F i g . 7). This time I w i l l assume that the bottom of the t r i a n g l e i s an i n c h below the top of the sguare (with the p o s s i b i l i t y of a small margin of e r r o r ) . Thus the t r i a n g l e w i l l be moved up s u f f i c i e n t l y so that the bottom of the t r i a n g l e i s egual to the top of the sguare even though i t may not be e x a c t l y one inch. At t h i s point the two r e l a t i o n s between the f r o n t and the roof w i l l hold. Thus demon processing w i l l be performed. 1 1 •• • 1 (*0CCUE |(SUPPORTS FR0NT3 | H00F6) ) 1 H0USE2 1 1 i | SUPPORTS j SUPPORTS 1 1 i 1 T 1 |SUPPORTS i 1 1 1 | (*0CCDE (MARRY |FR0NT3 RO0F6)) 1 3 H0USE2 I i | MARRY T " ~ ' • ' — |MARRY 1 i | (*0CCUR (HOUSE | H0USE2) ) I JHOUSE 1 | H00SE2 1 - — |H0USE2 1 i _ I(*OCCUR (HOUSE | H0USE2) ) j ., , | TLF 1 l I TLF i ,„ i TLF 1 i | T J | HOUSE i 1 I 1 i 1 T t 1H0USE2 1 1 * 1 1 i IT l j MABSY i 1 I I i 1 T i 1 J OBJECT 1 1 Figure 7. A Frame System Model f o r Understanding Natural Language 78 r |T j | T R I A N G L E i J t 1 i |T 1 r |TRIANGLE5 i , 1 1 i l 1 i i | * N E X T i -i I I N P U T F R A M E \ | TRIANGLE5 1 1 When the object frame moves the t r i a n g l e up i t w i l l n o t i f y the supports and marry frames that the t r i a n g l e has been moved. The r e l a t i o n frames i n turn w i l l check i f the c o r r e c t r e l a t i o n s hold. In t h i s case they w i l l be s a t i s f i e d and demon processing w i l l n o t i f y the house EF that the r e l a t i o n s between the f r o n t and the roof have been s a t i s f i e d . The house EF w i l l i n tu r n n o t i f y the house BF and the TLF. What t h i s means i s tha t the student may reference these two obj e c t s as one by the word "house". When the door and the window are added to the p i c t u r e , they w i l l not be a c t u a l l y part of the house u n t i l they are i n the c o r r e c t r e l a t i o n with the f r o n t i o d y . This means that i f the student r e f e r s t o "the house", then only the sguare and the t r i a n g l e w i l l be considered as the house u n t i l the door and the window are i n the c o r r e c t r e l a t i o n s h i p f o r them to be inc l u d e d i n the house. 8.) Draw an upright r e c t a n g l e . 1 | (DRAW UPRIGHT) i \RECTANGLE j 1 TBIAGNGL E5 i |INPUT FRAME i T 1 i \ (MAKE |RECTANGLE7) j i |UPRIGHT i i i | RECTANGLE 1 j 1 . ... |RECTANGLE } i 1 1 J 1 5 (UPRIGHT }EECTANGLE7) 1 t • }RECTANGLE \ , i 1 1 i 1 1 1 1 1 1 1 1 | (RECTNAGLE J RECTANGLE7) i l |TRIANGLES 1 1 ] 1 1 1 1 i I A Frame System Model f o r Understanding Natural Language 79 J (*ERR OR * MESS AGE J (RECTANGLE 1 RECTANGLE7) ) \(*ERROR *MESSAGE J (RECTANGLE I RECTA NGLE7) ) ! (RECTANGLE | RECTANGLE7) J (RECTANGLE IRECTANGLE7) I } (*DE MON DOOR) | I T j | (RECTANGLE ! RECTANGLE7) \ I (* DEMON DOOR8) j DOOR 8 DOOR | (RECTANGLE |RECTANGLE7) f EOOF6 HOUSE2 I I FRONT3 HOUSE2 |HOUSE2 DOOR FRONT3 FRONT3 L,. I DOOR |DOOR •4- +-DOOR8 DOOR DOOR-BODY DOOH8 |FRONT3 I DO OR 8 DOORS DOOR-BODY - f - DOOR8 DOOR8 | DOOR-BODY 1 I (*DEMON DOOR-BODY) DOOR-BODY9 DOOR-BODY | T I — DOOR-BODY 4-! (RECTANGLE I RECTANGLE7) | DOOR-BODY9 | DOOR-BODY I | (*DEMON |DOOR-BODY9 |((WIDTH 1 RECTASGLE7) J (TIMES 0.5 | (HEIGHT IRECTANGLE7) ) ) i EQUAL + | DOOR-BODY9 1DOOR8 I IDOOR-BODY9 1 1 IT i 4--DOOR-BODY9 1 j- - I i A Frame System Model f o r Understanding Natural language 80 1 - — | (RECTANGLE |RECTANGLE7) 1 j RECTANGLE? |RECTANGLE7 i I DOOR8 | D00R8 i \DOOR8 J D00R8 t , 1 1 i I |*NEXT i i | INPUT FRAME I 1 RECTANGLE7 1 1 1 i i Again an e r r o r s i t u a t i o n i s encountered. The system hacks up to the house EF and then f o l l o w s the path down to the door frame. The system assumes that the r e c t a n g l e w i l l e v e n t u a l l y form the body of the door (see F i g . 8). A demon i s sent to the equal frame, so that when the width of the door i s approximately h a l f the height, the door body frame w i l l be n o t i f i e d . 9.) Make i t smaller-| (MAKE SMALLER) j |RECTANGLE7 l 1 i RECTANGLE? jINPUT FRAME | (RECTA NGLE7 J (MAKE SMALLER) ) 1 i ]RECTANGLE 1 i 1 J 1 i__ RECTANGLE7 IRECTANGLE7 J i i 1 (RECTANGLE7 | (MAKE SMALLER) ) i t |OBJECT 1 i r 1 1 I RECTANGLE ! |RECTANGLE 1 i 1 |(MAKE |RECTANGLE7) i • t I SMALLER 1 i , , • ir 1 1 i OBJECT i |OBJECT J i 1 J (SMALLER i RECTANGLE7 |RECTANGLE7) I 1 1 OBJECT 1 1 i 1 1 i . 1 1 1 \ t n: • | (SMALLER j RECTANGLE7 | RECTANGLE7) 1 1 |RECTANGLE 1 1 i 1 1 1 1 i I ) l 1 i |(SMALLER |RECTANGLE7 | RECTANGLE7) i 1 ; |RECTANGLE7 1 1 t 1 \ 1 1 The SMALLER frame w i l l be able t o use in f o r m a t i o n , that the door body must be i n s i d e the f r o n t of the house to decide how smal l to make the rectangle (see F i g . 9) . rarae System i-lodel f o r Under s t a riding N a t u r a l Language Figure 8. A Frame System Model f o r Understanding Natural Language 82 Figure 9. A Frame System Model f o r Understanding Natural Language 83 10.) Thinner. j (MAKE THINNER) 1 |RECTA NGLE7 l | RECTANGLE7 i |RECTANGLE7 i i | (RECTANGLE? 1 (MAKE THINNER) ) 1 1 |RECTANGLE i l t | RECTANGLE7 1 i j |RECTANGLE? ] j i J (RECTANG LE7 | (MAKE THINNER) ) 1 I |OBJECT I l l | RECTANGLE 1 I J |RECTANGLE 1 i i 1(MAKE |RECTANGLE7) i JTHINNER 1 1 | OBJECT ! 1 \OBJECT 1 At t h i s p o i n t , the door body w i l l be of the c o r r e c t dimension and thus the door body frame w i l l be n o t i f i e d of the f a c t (see F i g . 10). This i n turn w i l l cause demon processing to occur-1 1 • | (*0CCUR (EQUAL J (WIDTH |RECTANGLE?) \ (TIMES 0.5 |(HEIGHT | RECTANGLE?) ) ) ) j |D00R-B0DY9 1 1 1 1 I 1 i EQUAL I EQUAL I I \ I 1 i i 1 J I 1 1 1 i | (*0CCUR { (DOOR-BODY J DO OR-BODY 9) ) I jDOOR-BODY 1 1 1 1 DOOR-BODY9 " J '• • |DOOR-BODY9 I 1 i - 1 i 3 1 i j | (*0CCUR |(DOOR-BODY j DOOR-BODY9) ) |DOOR8 1— 1 1 I i DOOR-BODY 1 |DOOR-BODY 1 1 i i J i 1 i i | (*OCCUR 3 (DOOR D00R8)) | \ DOOR f— 1 § DOOR 8 - T1DOOR8 I i 1 1 J i 1 (*OCCUR | (DOOR D00R8) ) j j FR0NT3 1 1 j DOOR - 1 • • ~ •J DOOR 1 i - 1 i 1 • | (IS (FRONT-BODY4 ] DOOR8) ) | IINSIDE 1 I I _L_ FRONT3 \ |FR0NT3 1 i 1 1 J t I NIL JINSIBE T i J I 1 I i Frame System Model f o r Understanding Natural Language Figure 1 0 . A Frame System Model f o r Understanding Natural Language 85 1 1(*DEMON FRONTS | (FRONT-B0DY4 j D00R8) ) i |INSIDE i | FRONT3 |FRONT3 i IT i 1 FRONT3 1 1 i | (IS (BOTTOM J FR0NT-B0DY4) | (BOTTOM D00R8)) J 1 EQUAL | FRONT3 T 1 FRONTS \ NIL i | FRONT3 I i i |(*DEMON FRONT3 J ((BOTTOM 1FRONT-BODY4) J (BOTTOM DOOR8) ) ) | |EQUAL I FRONT3 ( |FRONT3 IT | \FRONT3 1 1 IT 1 JDOOR J 1 i | T | J DOOR8 1 1 IT 1 j DOOR-BODY 1 1 i IT | J DOOR-BODY9 1 I IT 1 1 THINNER 1 1 | (THINNER J RECTANGLE7 1 RECTANGLE7) | J OBJECT j j I (THINNER |EECTANGLE7 I J RECTANGLE |RECTANGLE7) i J I (THINNER J RECTANGLE7 IRECTANGLE7) |RECTANGLE7 i i •j I*flEXT )INPUT FRAME i I RECTANGLE7 The demon processing backs a l l the way back up to the f r o n t because a door i s a door when i t i s j u s t represented by the rect a n g l e without the c i r c l e f o r the door knob- The f r o n t frame then checks to see i f the r e l a t i o n s h i p s between the door and the f r o n t body are c o r r e c t ( i . e . the door i s i n s i d e the f r o n t body A Frame System Model f o r Understanding Na t u r a l Language 86 and the bottom of the door i s egual to the bottom of the f r o n t body). In t h i s case the r e l a t i o n s h i p s w i l l not hold and so demon messages w i l l be sent to the r e l a t i o n frames so that when they do hold, the f r o n t frame w i l l be n o t i f i e d . 11.) Move i t down. 1 •• • -f (MOVE DOWN) |RECT ANGLE7 i 1 i RECTANGLE7 |INPUT FRAME I (RECTANGLE? j (MOVE DOWN) ) 1 1 |RECTANGLE 1 - l — j — X— BECTANGLE7 J RECTANGLE7 i | (RECTANG LE7 j (MOVE DOWN) ) | I| OBJECT J RECTANGLE |RECTANGLE i i (*OCCUR (EQUAL | (BOTTOM J FRO NT-B0DY4) J (BOTTOM D00R8) ) ) | -,. _ | FR0NT3 1 ! 1 •• ,i EQUAL 1 I EQUAL t I T j | EQUAL i 1 T 1 1 — — • |(*OCCUR (INSIDE J FRO NT-BODY4 | DO0R8) ) ] 1 |FR0NT3 \ 1 j | INSIDE 1 INSIDE IT j IINSIDE 1 1 1 IT i |RECTANGLE l 1 1 |T 1 1 |RECTANGLE7 I 1 1 i |*NE XT < l |INPUT FRAME f. 1 RECTANGLE7 1 In the above sequence, the rectan g l e i s moved down so that the two r e l a t i o n s h i p s now hold (see F i g . 11) . The f r o n t EF i s then n o t i f i e d v i a demon processing and assigns the s l o t s f o r the two r e l a t i o n s h i p s . The system w i l l know that the rectangle i s to be moved down u n t i l i t s bottom i s egual to the bottom of the door because of demon messages sent to the r e l a t i o n s . 12.) Draw a very small c i r c l e . 87 F i g u r e 11-A Frame System Model f o r Understanding Natural Language 88 1 -I (DRAW | (SMALL VERY) ) | CIRCLE 1 1 - .1— RECTANGLE7 i 3 INPUT FRAME J i i 1 (MAKE CIRCLE10 3 VERY) | SMALL i 1 1 t CIRCLE \ 1 J CIRCLE | 3 (SMALL CIRCLE 10) jCIRCLE 1 1 1 i i | (CIRCLE | CIRCLE1 0) |RECTANGLE7 1 1 1 j 1 i j (*EEROR * MESSAGE | (CIRCLE | CIRCLE 10) ) JDOQR-BODY9 i — 1 \ 1 i \ j | (*ERROR *MESSAG£ | (CIRCLE | CIRCLE 1 0) ) |DOOR8 f— 1 1 1 _ j ! ! l (CIRCLE \ CIRCLE1 0) j DOOR-KNOB T 1 1 . 1 DOOR8 1 DOOR8 J | (*DEMON il DOOR-KNOB) 1DOOS-KNOB11 J 1 1 - J DOOR-KNOB |DOOR-KNOB 3 \ T J DOOR-KNOB 1 i 1 J | (CIRCLE J CIRCLE 1 0) |DOOS-KNOB11 1 1 j DOOR-KNOB JDOOR8 } \ NEXT |INPUT FRAME T3 CIRCLE10 _.... , .„ , i The system assumes that the very s m a l l c i r c l e w i l l represent the door knob (see F i g . 12). The door EF sent demon messages so tha t when the c i r c l e i s i n the c o r r e c t p o s i t i o n , i t w i l l be n o t i f i e d . I am going to assume that the student w i l l move the c i r c l e around u n t i l i t i s i n the c o r r e c t p o s i t i o n . The sentences encountered w i l l be s i m i l a r to those already described. Frame System Model f o r Understanding Natural Language Figure 12. A Frame System Model f o r Understanding Natural Language 90 r — j (DOOR-KNOB | D00R-KN0B11) |DOOR-KNOB I i | D00R-KN0B11-i JDOOR-l j KNOB11 j | (DOOR-KNOB J D0QR-KN0311) j s |DOOR8 \ | 1 | DOOR-KNOB 1 - • |DOOfi-1 . i . .. KNOB | IT I |DOOR-KNOB I 1 1 I i J I IT j 1 1D0OR-KN0B11 1 •j 1 i I | (CIRCLE (CIRCLE 10) 1 1 |CIRCLE10 I i | DOOB-BODY11 1 1 1 • J DOOR-1 i BODY11 \ i |*NEXT i 1 |INPUT FRAME J CIRCLE10 t 1 i i The "door knob" w i l l now be i n the c o r r e c t p o s i t i o n i n r e l a t i o n to the other components (see F i g . 13). The system w i l l now have the expectation that a window f o r the house i s to be drawn. 13.) Draw a sm a l l sguare i n s i d e the f r o n t . 1 I(DRAW SMALL | (INSIDE FRONT3 1?)) ] | SQUARE | CIRCLE10 | INPUT FRAME J I I I I i i | (MAKE SQUARE 1 2) | | SMALL | SQUARE j j iSQUARE | i < | (SMALL SQUARE 1 2) I jSQUARE I r — -1 1 1 i i i |(MAKE FSONT3 J SQUARE12) 1 JINSIDE | SQUARE l — \ |SQUARE J 1 1 i i i J (INSIDE FSONT3 j SQUARE12) I | SQUARE ! t — 1 1 1 1 I i „ , i i | (SQUARE | SQUARE 1 2) |CIRCLE 10 I } - - - • — i 1 ] 1 1 ..— _ _ _. i The pa r t : " (INSIDE FRONT3 ? ) " i n the message of the f i r s t entry of the t a b l e s p e c i f i e s that the sguare to be created i s to be placed i n s i d e the f r o n t of the house. The "?" i s necessary. A Frame System Hodel f o r Understanding Natural Language 92 s i n c e when the sentence i s processed by the input frame, i t w i l l not know the name of the new sguare. This allows the sguare frame to construct the c o r r e c t message to be sent to the INSIDE frame (see F i g , 14). At t h i s point e r r o r processing w i l l occur s i n c e the c i r c l e EF knows nothing about squares. 1 •" | (*ERROH ^MESSAGE } (SQUARE | SQUARE1 2) ) j |DOOR-KNOB 11 i ! i 1 1 1 • | (*ERROR *MESSAGE j (SQUARE | SQUARE1 2) ) | . , , ,. ID00R8 T l 1 ... j I J 1 i \ (*ERROR *MESSAGE | (SQUARE |SQUARE 12)) i | FR0NT3 !— j i 1 I 1 i i I (SQUARE J SQUARE12) 1 | WINDOW ! FR0NT3 |FR0NT3 1 1 I i 1 J (*DEMON WINDOW) j | WINDOW 13 . i WINDOW |FR0NT3 1 I i IT | |WINDOW i 1 1 I i \ (SQUARE | SQUARE 1 2) |WINDOW 13 ! FR0NT3 ]FRONT3 ' 'I 1 1 1 The system assumes that the square w i l l represent the window. I am again going to assume that the student w i l l move the sguare around u n t i l i t i s i n the c o r r e c t p o s i t i o n . When t h i s happens, demon processes w i l l n o t i f y the f r o n t EF (see F i g . 15) . r - -| (*OCCUR (WINDOW |WIND0W13)) 1 | WINDOW I I | WINDOW3 1 i „ ,. JSIND0W3 i i i \ (*OCCUR (WINDOW | WINDOW 1 3) ) j 1 |FR0NI3 1 i t — | WINDOW 1 1 WINDOW 1 i I T * t |WINDOW 1 1 T 1 A Frame System Model t o r Understanding Natural Language 94 Figure 15. A Frame System Model f o r Understanding Natural Language 95 i 1 |T | WINDOW 13 | J \ , +__ , , | (SQUARE |SQUARE12 | WINDOW 13 (WINDOW 13 I | SQUARE12) I I 1 I J ; + ; j |*NEXT IINPUT FRAME | SQUARE12 | | •t 1 At t h i s point the house w i l l have been completed and the student would normally be asked to redraw the same figure. This time, however, he would be told how to use the hardware of the graphics terminal to perform the tasks that he had previously done using English. This w i l l begin to show the student that i t i s r e l a t i v e l y easy to manipulate the objects on the graphics screen using the hardware available rather than having to specify every action i n English or an even less natural form. 4.3. Comments on the Example Most of the example described above has been implemented-However, some of the frames must have additions made, so that they w i l l be able to handle some of the d e t a i l s of the system. The system i s incremental, i n that more d e t a i l may be added by writing new frames or adding information to current frames. No implementation of the input or output frame has been attempted. The example above has gone into many of the features of the system; however, a greater emphasis i s needed on how error processing i s performed when an assumption has been made i n error. This i s an important aspect since any system i s bound to make some assumptions which l a t e r turn out to be incorrect. People sometimes assume something in a conversation which la t e r A Frame System Model f o r Understanding Natural Language 96 turns out t o be untrue and are able to c o r r e c t themselves without any great d i f f i c u l t y . Sometimes the informat i o n t h a t c o n t r a d i c t s the assumption can be used to r e d i r e c t the computation t o the c o r r e c t c o n c l u s i o n s . Thus there must be some f a c i l i t y i n the system to destroy frames t h a t have been created due to i n c o r r e c t assumptions and to rea s s i g n s l o t s of frames which have already been i n s t a n t i a t e d . There i s a problem with t h i s i n that when an object i s o r i g i n a l l y drawn, i t may v i o l a t e a c o n d i t i o n but w i l l be moved about the screen before i t i s i n i t s f i n a l p o s i t i o n . Determining when an object i s i n i t s f i n a l p o s i t i o n i s a problem i n i t s e l f and cannot be e a s i l y a s c e r t a i n e d . In f a c t i t i s impossible s i n c e the student may at any time change i t by moving i t around the graphics screen or by i n c r e a s i n g or decreasing i t s s i z e or by performing some other a c t i o n . There must be some method of determining when an assumption has been c o n t r a d i c t e d . For example, when c o n s t r u c t i n g the house as i n the above example, the f i r s t sguare drawn w i l l normally assumed to be the f r o n t body of the house. In some cases a person may s t a r t to draw the minor d e t a i l s of the house before drawing the major d e t a i l s . That i s the f i r s t sguare drawn may not represent the f r o n t body but may be meant t o represent the window of the house. This i n c o r r e c t i n f e r e n c e at the beginning w i l l not cause any major d i f f i c u l t i e s , s i n c e a l l the a c t i o n s w i l l be d i r e c t e d to the EF f o r the sguare j u s t drawn. The only problem o r i g i n a l l y w i l l be th a t the f r o n t body EF w i l l have the wrong sguare r e p r e s e n t i n g i t . a Frame System Model f o r Understanding Natural Language 97 The system must c o n t i n u a l l y check to see i f new informat i o n introduced i n t o the system by the sentences input by the student c o n t r a d i c t any of the current i n f o r m a t i o n . The system must not be too quick to decide that new information c o n t r a d i c t s c u r r e n t i n f o r m a t i o n . This must be done so t h a t i f the c o n t r a d i c t i o n i s only a temporary one, then there won't be too much work changing in f o r m a t i o n back and f o r t h between frames. In the case of drawing a house, the f i r s t square to be drawn w i l l be assumed to be the f r o n t body f o r the house. However, i f a new sguare i s drawn which completely surrounds i t then the system must decide whether to change the assignments of the s l o t s i n the f r o n t body frame and the window frames or not- This d e c i s i o n should be made at one of two times: when the system i s about to change the focus or when the system must a c t u a l l y use the information about which square represents what to disambiguate a sentence. A change of focus occurs when a sentence causes a message to be sent to a frame other than the r e f e r e n t f o r " i t " . When the system i s about to change the focus of the conversation from one object to another, then i t must decide how the s l o t assignments of the a f f e c t e d frames are to be assigned. This r u l e i s used s i n c e the current t o p i c focus w i l l u s u a l l y be one of the frames th a t i s causing the problem. When the student i s s a t i s f i e d with i t s p o s i t i o n , the system may make assumptions from the current p o s i t i o n s of the objects on the graphics screen and reassign s l o t s of the frames a f f e c t e d . This processing w i l l only happen when there i s some doubt about what the various o b j e c t s represent i n the f i g u r e . In the example given above, none of A Frame System Model f o r Understanding Natural Language 98 t h i s processing would be necessary s i n c e the conversation f o l l o w s the "expected" path. When the assumptions have been made, the computation w i l l continue as i t normally would have under the new s t a t e of the world. When the d e c i s i o n has to be made to disambiguate a sentence the same form of processing as i n the above case w i l l be performed. The system w i l l use the info r m a t i o n about the current s t a t e of the obj e c t s on the graphics t e r m i n a l screen. An important question at t h i s point i s how does the system recognize that the new information c o n t r a d i c t s i n f o r m a t i o n that has been assumed from previous in f o r m a t i o n . The system must have some form of expectation f o r such e r r o r s to occur. This immediately leads to the idea that demons be sent to the frames which w i l l be the ones to recognize the c o n t r a d i c t i o n i n order to t e l l the frame that must make the d e c i s i o n when such c o n d i t i o n s a r i s e . For example, i n the case of drawing a house and the p o s s i b l e confusion between the f r o n t body and the window, the f r o n t EF i s the one which must e v e n t u a l l y make the d e c i s i o n about which square represents the f r o n t body and the window. When the f r o n t EF has assigned the f r o n t body and the window s l o t s , i t w i l l check to see i f the r e l a t i o n s h i p between the f r o n t body and the window are such that the two should reverse t h e i r assignments. I f t h i s i s the case the f r o n t frame must send a demon message to the input frame to t e l l i t to n o t i f y the f r o n t EF when e i t h e r the f r o n t body or the window are referenced or when i t changes the focus from the current object. When t h i s happens the f r o n t EF w i l l be n o t i f i e d about the need A Frame System Model f o r Understanding Natural Language 99 to make the d e c i s i o n . I t may then use the current information a v a i l a b l e to make a d e c i s i o n as to whether the s l o t assignments of the two frames should be changed or not. The s l o t s i n f a c t may change places many times i n a computation (even though t h i s h o p e f u l l y w i l l not be the case) depending on what the student or conversant says to the system. In the example, a l l the e r r o r processing associated with i n v a l i d messages i s done by backing up to the frame i n which the current frame i s part. This does not have to be the way the processing needs to be done. What could happen i s tha t when an i n v a l i d message i s encountered, c o n t r o l may be immediately sent to the top l e v e l frame so that i t may decide what to do with the message. I n most cases the message w i l l be sent down the same path the o r i g i n a l message was sent. In t h i s way the highest l e v e l frame which can accept the message w i l l gain c o n t r o l of the computation. The d i f f e r e n c e i s a matter of emphasis. In the back up method the f i r s t component on the way back up which recognizes the message w i l l c a rry on the computation. In the top down method, the top most component which r e c e i v e s the message w i l l gain c o n t r o l of the computation. The d i s t i n c t i o n i s between f i l l i n g i n minor or major d e t a i l f i r s t . Once some of the major d e t a i l s have been f i l l e d i t i s l i k e l y that the student w i l l f i l l i n the minor d e t a i l s t a r t i n g with the l a s t major component drawn. Which way t h i s type of e r r o r i s processed may be made to depend on what type of f i g u r e i s being drawn, or at what point i n the computation the system i s . Something which was not f u l l y s p e c i f i e d i n the example was A Frame System Model f o r Understanding Natural Language 100 how the g r a p h i c a l object frame would be able t o use the demon informati o n to decide on how much to move an o b j e c t . when a demon message i s sent to a r e l a t i o n frame, the frame w i l l send a message to the g r a p h i c a l object frame s p e c i f y i n g that the r e l a t i o n frame i s i n t e r e s t e d i n the obj e c t s passed i n the demon message. When the g r a p h i c a l object frame i s about to move an object i t w i l l check to see i f there are any demons which contain that object. I f there are, then the g r a p h i c a l object frame w i l l send a message to the r e l a t i o n s h i p frame asking how f a r that object must be moved to s a t i s f y the r e l a t i o n . The r e l a t i o n frame w i l l return a l i s t of two elements. The two elements w i l l be a range that the object may be moved i n the X d i r e c t i o n and the Y d i r e c t i o n r e s p e c t i v e l y . For a r e l a t i o n such as i n s i d e , the ranges may be l a r g e , but f o r other frames there may only be one p o s i t i o n which w i l l s a t i s f y the r e l a t i o n s h i p . The same idea can be used f o r other types of r e l a t i o n s h i p s . Using the combination of a l l such i n f o r m a t i o n , the g r a p h i c a l object frame can a c t u a l l y decide how much t o move the object. A Frame System Model f o r Understanding Natural Language 1 0 1 Chapter 5, Conclusions A model which w i l l handle the semantic knowledge necessary to understand a subset of n a t u r a l language has been described. The model i s incomplete; however, i t shows that i t i s p o s s i b l e to develop a model which handles a small subset of the E n g l i s h language. I t was not designed as a general r e p r e s e n t a t i o n of knowledge. However, i t could be gen e r a l i z e d to represent information f o r more general domains of knowledge to be used f o r understanding n a t u r a l language. The s t r u c t u r e of frames i s such that when a new scene or f i g u r e i s t o be used i n teaching the student the use of a graphics t e r m i n a l , the whole system w i l l not have t o be r e w r i t t e n . Some new frames w i l l be w r i t t e n which correspond to the components of the new f i g u r e . Thus the new f i g u r e w i l l cause only a few new frames t o be w r i t t e n rather than major changes having to be made to the system. The top l e v e l frame w i l l a l s o have to be r e w r i t t e n , so that i t w i l l be able to begin the process of re c o g n i z i n g t h i s new f i g u r e . A l l the r e l a t i o n frames, property frames, b u i l t i n object frames, the input and output frames and the superset frames w i l l remain the same. Some new r e l a t i o n and/or property frames may have to be w r i t t e n to handle the new f i g u r e , but once they have been w r i t t e n they can be used by a l l succeeding f i g u r e s . This makes i t r e l a t i v e l y easy to make a d d i t i o n s to the system. A Frame System Model f o r Understanding Natural Language 102 Most frames w i l l know everything about the concept they represent. This i s not qu i t e true about frames representing nouns, since there w i l l be superset hierarchy among most of the noun frames i n the system. Thus frames which represent s p e c i f i c ^ o b j e c t s w i l l c ontain only information which i s s p e c i f i c to that \ object alone. This frame w i l l have as s o c i a t e d with i t superset ! poi n t e r s to other frames which w i l l c o n t a i n more general i n f o r m a t i o n about the concept. This means that inf o r m a t i o n that i s general i n nature w i l l not be d u p l i c a t e d i n many d i f f e r e n t i frames but may be co n s o l i d a t e d i n t o a general one. Ass e r t i o n s i n the system f o r teaching a student how to use a graphics t e r m i n a l are a l l assumed to be a b s o l u t e l y t r u e . This means t h a t the various frames w i l l have to keep checking to make | sure that the a s s e r t i o n s remain true. In a more general domain i ; f a c t s should have some i n d i c a t i o n of the v a l i d i t y of the ! a s s e r t i o n . How t o implement a s s e r t i o n s which have a v a r i a b l e t r u t h f a c t o r i s a very d i f f i c u l t problem. One simple method using a range of numbers (say 0 to 10) according to how c e r t a i n j the a s s e r t i o n i s (e.g. 10 could mean a b s o l u t e l y t r u e , 0 could i mean a b s o l u t e l y f a l s e , 1 could mean that the a s s e r t i o n may be true but almost c e r t a i n l y not, e t c . ) . This s o r t of method does I not appear very appealing, since people do not seem to use some a r b i t r a r y s c a l e t o decide on the v a l i d i t y of an a s s e r t i o n . A major d i f f e r e n c e between t h i s system and other systems which have been w r i t t e n to understand n a t u r a l language i s t h a t verbs are not separate procedures which are invoked when the a c t i o n corresponding to the verb i s to be performed. In t h i s a Frame System Model f o r Understanding Natural Language 103 system, the verb i s part of a message to the frame th a t represents the object that i s the subject of the a c t i o n ( i . e . the object on which the a c t i o n i s to be performed). Thus to move a square higher up on the graphics screen a message w i l l be sent to the square frame s p e c i f y i n g the a c t i o n move. In some cases the square frame w i l l c o n t a i n the r e q u i r e d information to perform the a c t i o n , i n other cases a superset of the square frame w i l l c ontain the desired i n f o r m a t i o n . In most other systems the verb i s a procedure (or theorem) which i s passed the name of the object f o r which the a c t i o n i s to be performed. This i s r e a l l y only a matter of emphasis, s i n c e both methods should cause the same act i o n s to be performed c o r r e c t l y . The reason that I d i d i t t h i s way i s that the i n f o r m a t i o n about how to perform a c t i o n s on an object i s information which should be a s s o c i a t e d with the object and not be a separate frame. The frame f o r the object knows more about how i t should react to an a c t i o n to be performed on i t than some general procedure which would have to perform some processing to see how to perform the a c t i o n . In a s p e c i f i c domain such as described i n the I n t r o d u c t i o n , there i s no d i f f e r e n c e because each verb w i l l u s u a l l y only have one method of performing an a c t i o n f o r a l l o b j e c t s i n the domain. However, i n a more general domain i t i s p o s s i b l e t h a t the same verb w i l l have a d i f f e r e n t a c t i o n a s s o c i a t e d with i t depending on the subject of the a c t i o n . I f a general procedure f o r an a c t i o n i s used then i t w i l l have t o perform extra processing to decide how e x a c t l y the a c t i o n on the parameter i s A Frame System Model f o r Understanding Natural Language 104 t o be c a r r i e d out. Using the method described above t h i s e x t r a processing would not be necessary (even though superset processing may be necessary) s i n c e the frame (or one of i t s supersets) o r i g i n a l l y sent the message w i l l know e x a c t l y how to perform the a c t i o n . I f an e r r o r i s encountered i n the d e f a u l t processing of the a c t i o n , then the frame with which that a c t i o n i s performed w i l l a l s o be the best frame to decide what i s to be done next, whether to t r y some other method or give up. The superset l i n k s used i n the system w i l l give the a b i l i t y to a s s o c i a t e a c t i o n s with as general a concept as p o s s i b l e and thus a l l subsets t o t h i s concept w i l l have access to t h i s method of performing the a c t i o n and a l l superset frames w i l l not normally have d i r e c t access to the i n f o r m a t i o n . A problem which i s associated more with frames and the rep r e s e n t a t i o n of knowledge r a t h e r than with n a t u r a l language i s how i s l e a r n i n g performed. For example, when drawing a g r a p h i c a l house i f a second s m a l l sguare i s drawn to represent a second window f o r the f r o n t of the house, what i s the system to do. In the present system, the system would complain to the student that there should not be a t h i r d sguare. What i s a c t u a l l y needed i s t o create a new frame using the old f r o n t frame as the prototype and to make the necessary changes to add a second window to the new one. This i s another whole problem which w i l l need much work before i t i s solved. People seem to be able to perform such l e a r n i n g tasks q u i c k l y and e a s i l y i n most cases and so should any sytem f o r representing knowledge. Context i s a very important aspect of a system since i t A Frame System Model f o r Understanding Natural Language 105 must know what the cu r r e n t t o p i c i s . This i s necessary i n a system since t h i s information w i l l often be the only way t h a t some sentences w i l l be disambiguated. Context i s a l s o u s e f u l i n reducing the amount of information that needs to be looked at f o r understanding a sentence. This should g r e a t l y reduce the amount of time needed to understand a sentence. Demon processing i s handled much d i f f e r e n t l y than i n most other systems where there are general demon processes i n existence which must be checked every time i n f o r m a t i o n i s added or deleted from the data base. The patterns associated with the demon processes may match items on which the demon i s not meant to work. In t h i s system the a c t u a l parameters of the demon process are known when the demon i s made a c t i v e . Thus the demon w i l l only be invoked when the parameters sent i n the o r i g i n a l demon message are used. Most demons w i l l be a s s o c i a t e d with s p e c i f i c r e l a t i o n s h i p s between two objects or with the c r e a t i o n of new instances of o b j e c t s . When a demon i s s u c c e s s f u l l y invoked a message w i l l be sent to frame frame waiting f o r the demon, saying t h a t the a c t i o n or object t h a t was wanted has occurred. A problem which i s a s s o c i a t e d with frames i s how to s e l e c t a frame to represent the c u r r e n t s i t u a t i o n . In t h i s system the major d e c i s i o n has already been made sin c e the student i s t o l d which f i g u r e to draw. This i s a major problem which must be solved before frame systems can become f u l l y u s e f u l as a general representation of knowledge. Several conclusions have been made about the design of the A Frame System Model f o r Understanding Natural Language 106 model and how i t represents knowledge for understanding n a t u r a l language. The frame approach to the r e p r e s e n t a t i o n of knowledge seems to work quite w e l l . This i s mainly due to the f a c t that the i n t e r n a l s t r u c t u r e of a frame i s not important, as long as the frames which may send message to a frame know what messages the frame w i l l accept and what responses i t may make. This means that the contents of a frame may be changed without a f f e c t i n g the performance of the system as a whole as long as the e x t e r n a l part of the frame remains the same. The frame may be made to accept more messages and may be changed as to how i t a c t u a l l y handles the processing of already e x i s t i n g messages without a f f e c t i n g other frames i n the system. 1 Frame System Model f o r Understanding Natural Language 107 Bi b l i o g r a p h y £1] Bobrow, D. and Wegbreit, B., "A Model and Stack Implementation of M u l t i p l e Environments", CACM, Vol, 16, No. 10, pp 591-603, 1973. £2] Brown, J . , Burton, R. , B e l l , A., "SOPHIE A S o p h i s t i c a t e d I n s t r u c t i o n a l Environment f o r Teaching E l e c t r o n i c Troubleshooting (An Example of AI i n CAI)", BBN Report No. 2790, 1974. [ 3 ] C a r b o n e l l , J . R., " M i x e d - I n i t i a t i v e Man-Computer I n s t r u c t i o n a l Dialogues", Ph.D. Thesis, BBN Report No. 1971, 1970. [ 4 ] Charniak, E., "Toward a Model of Ch i l d r e n ' s Story Comprehension", M.I.T. AI Lab TR-266, 1972-[ 5 ] C r i g n e t t i , M. and Warnock, E-, " M i x e d - I n i t i a t i v e Information System f o r Computer Aided T r a i n i n g and Decision Making", BBN Report No- ESD-TR-73-200, 1973. [6] Fahlman, S. E., "A Planning System f o r Robot Cons t r u c t i o n Tasks", i n A r t i f i c i l a l I n t e l l i g e n c e V o l . 5, No. 1, pp 1-49, 1973. [7 ] Fahlman, S. E., "A Hypothesis-Frame System f o r Recognition Problems", M.I.T. AI Lab Working Paper 57, 1974. £8] Fahlman, S, E., "Thesis Progress Report: A System f o r Representing and Using Real World Knowledge", M.I.T. AI Lab Memo No. 331, 1975. £9] Havens, W., "A Model f o r A r t i f i c i a l I n t e l l i g e n c e Programming Languages", Thesis Proposal, U.B.C, 1975. [10] Hewitt, C., " D e s c r i p t i o n and T h e o r e t i c a l A n a l y s i s (Using Schemata) of Planner", Ph. D. Thesis, M.I.T. AI Lab TR-258, 1972. [11] Hewitt, C-, Bishop, P. and S t e i g e r , R., "A U n i v e r s a l Modular Fromalism f o r A r t i f i c i a l I n t e l l i g e n c e " , IJCAI-73, pp 235-245, Stanford, C a l i f o r n i a , 1973, [12] Hewitt, C., and G r i e f , I . , "Actor Semantics f o r Planner-73", Sigplan - Sigairt Conference, 1975. £13] de K l e e r , J . , " Q u a l i t a t i v e and Q u a n t i t a t i v e Knowledge i n C l a s s i c a l Mechanics", M.I.T. AI Lab Working Paper 88, 1975. £14] Kuipers, B- J . , "Frames: Representing Knowledge f o r Recognition", M.I.T. Lab, Xerox Palo A l t o Research A Frame System Model for Understanding Natural Language 108 Centre, 1975. [15] McCalla , G . , "Pr ivate Communications", Summer, 1975. [16] McDermott, D. ?. " and Sussman, G. J . , "The Conniver Reference Manual", M. I .T . AI Lab Memo No. 259, 1972. [17] Minsky, M , , "A Framework for Representing Knowledge", M . I . T . AI Lab Memo No. 306, 1974. [18] Q u i l l i a n , M . , "Semantic Memory", Ph.D. Thes i s , Carnegie-Mellon Univer s i ty , repr inted i n Minsky, M. (ed.) Semantic Information Process ing, MIT Press , Cambridge, Mass., 1968. [19] Reiger, C , , "Understanding by Conceptual Inference", Computer Science Department, Univers i ty of Maryland, 1974. [20] Schank, R., " I d e n t i f i c a t i o n of Conceptual izat ion Underlysing Natural Language", i n Schank and Colby, Computer Models of Thought and Language, pp 187-248, 1. H. Freeman, 1973. [21] Schank, R. and Colby, K . , "Computer Models of Thought and Language", W- H. Freeman, 1973. [22] Simmons, R. , "Semantic Networks: Their Computation and Use for Understanding Engl i sh Sentences", i n Schank and Colby, Comp.uter Models of Thought and Language, pp 63-113, W. fl. Freeman, 1973. [23] Smith, B. and Hewitt, C , "Towards a Programming Apprentice" , AISB Summer Conference, Univers i ty of Sussex, 1974. [24] Sussman, G . , Winograd, T. and Charniak, E . , "Micro-Planner Reference Manual", M . I . T . AI Lab Memo No. 203a, 1973. [25] Winograd T . , "Procedures as a Representation for Data i n a Computer Program for Understanding Natural Language", Ph.D. Thes i s , M . I . T . AI Lab TR-84, 1971. [26] Winograd T . , "Frame Representation and the Declarat ive/Procedureal Controversy" , to appear i n Essays i n Memory of Jaime Carbonel l , 1974. [27] Winston, P . , "Learning S tructura l Descriptions from Examples", Ph.D. Thesis , M. I .T , AI Lab TR-231, 1970. A Frame System Model f o r Understanding Natural Language 109 Appendix A B r i e f D e s c r i p t i o n of Conniver Since some of the terminology used i n the t h e s i s comes from the Conniver programming language, t h i s appendix gives a b r i e f view of some of the f e a t u r e s of Conniver which w i l l be u s e f u l i n understanding some of the c o n s t r u c t s i n the t h e s i s . In p a r t i c u l a r , the Conniver pattern matcher and c o n t r o l s t r u c t u r e , which are used h e a v i l y i n the t h e s i s w i l l be described. 1 - 1. XkS. Conniver Pattern Matcher A l l the pattern matching done by the system i s done using the Conniver pattern matcher, so that a b r i e f d e s c r i p t i o n of the more important aspects of the pattern matcher used i n the body of the t h e s i s i s i n order. Most of t h i s d e s c r i p t i o n i s from the Conniver Reference Manual[16]. The Conniver pattern matcher i s c a l l e d i n the f o l l o w i n g way: (MATCH VARPAT DATAPAT). Where the v a r i a b l e p a t t e r n VARPAT i s a pattern which may contain v a r i a b l e s which are to be assigned values from the data pattern DATAPAT or whose values are to be used i n the p a t t e r n match. The pattern matcher works to any l e v e l , so t h a t v a r i a b l e s may occur at any l e v e l i n the v a r i a b l e p a t t e r n , u n l i k e the Micro-Planner p a t t e r n matcher which only matches v a r i a b l e s at A Frame System Model f o r understanding Natural Language 1 1 0 the top l e v e l . The data pattern DATAPAT i s the pattern against which the v a r i a b l e pattern w i l l be matched. This data pattern may co n t a i n v a r i a b l e s , but t h i s feature i s mainly u s e f u l f o r Conniver*s if-added, if-removed and if-needed methods, and are not needed by the frame system, so they w i l l not be described. MATCH re t u r n s NIL i f no match i s p o s s i b l e and returns a l i s t of two a s s o c i a t i o n l i s t s i f the pattern match i s s u c c e s s f u l . The f i r s t a s s o c i a t i o n l i s t corresponds to the v a r i a b l e p a t t e r n and a s s o c i a t e s with each v a r i a b l e i n the v a r i a b l e pattern the sequence i n the data pattern which was matched aqainst that v a r i a b l e . The second a s s o c i a t i o n l i s t corresponds to the data pattern and a s s o c i a t e s with each v a r i a b l e i n the data pattern the sequence i n the v a r i a b l e p a t t e r n which i t was matched against t h a t v a r i a b l e . In most cases the second a s s o c i a t i o n l i s t w i l l be NIL. Note that the v a r i a b l e s i n the data pattern must match against v a r i a b l e s i n the v a r i a b l e p a t t e r n . Another version of the Conniver pattern matcher, which i s not a c t u a l l y part of the conniver system but has been found u s e f u l , i s c a l l e d i n the f o l l o w i n g way: (FRMATCH VARPAT DATAPAT). Where VARPAT and DATAPAT have the same meaning as f o r the d e s c r i p t i o n of MATCH above. However, FRMATCH re t u r n T i f the pattern match i s s u c c e s s f u l and NIL otherwise. As a s i d e e f f e c t the v a r i a b l e s i n the v a r i a b l e pattern are set to the values corresponding to the s e c t i o n of the data pattern that they matched. The v a r i a b l e s are only set i f the pattern match A Frame System Model f o r Understanding Natural Language 111 succeeds. This i s us e f u l when the data patterns are messages sent to a frame. As with Micro-Planner, Conniver v a r i a b l e s i n patterns must be s p e c i f i e d by the use of p r e f i x e s . There are s e v e r a l p o s s i b l e p r e f i x e s which are a v a i l a b l e f o r use. Each of the p r e f i x e s cause the pattern matcher to perform d i f f e r e n t a c t i o n s . Some of the more important p r e f i x e s are: 1. ) !>VAR - This i s the basic Conniver pattern matching v a r i a b l e and w i l l match any expression which does not con t a i n any v a r i a b l e s . The s p e c i a l form !>(VAR RESTRICTION 1, RESTRICTI0N2, ... , RESTRICTION^ matches any form which does not contain any v a r i a b l e s . Also, a l l the r e s t r i c t i o n s , RESTRICTION 1, RESTRICTI0N2, , RESTRICTIONn, must evaluate t o a non-NIL value f o r the match to succeed. 2. ) !,VAR - This does not bind a v a r i a b l e , but r e f e r s to the current value a s s o c i a t e d with the Conniver v a r i a b l e VAR. This value may have been produced by a previous !> binding or by the Conniver binding of the v a r i a b l e VAR before the pattern matching began. 3. ) !,(VAR VALUE) - This binds VALUE to VAR and matches anything that VALUE would match. There are other Conniver pattern matching p r r e f i x e s which are a v a i l a b l e , but they are not used i n the current system. Following are some examples of how the Conniver pattern matcher works. The f o l l o w i n g c a l l to MATCH: (MATCH ' (F00 !>X) • (F00 BAR) ) w i l l return the l i s t of the two a s s o c i a t i o n l i s t s ( ((X BAR)) A Frame System Model f o r Understanding Natural Language 112 NIL). Where the NIL i s the a s s o c i a t i o n l i s t f o r the data pattern (F00 BAR). The patter n : (GRANDFATHER !>X ! , X) w i l l match a l l items corresponding to people who are t h e i r own grandfathers. This could be used i n an If-added p a t t e r n to make sure no c o n t r a d i c t o r y information of t h i s s o r t i s added to the data base. The p a t t e r n : !>(X (ATOM !,X)) w i l l match only atoms. The pa t t e r n : (FUNCT-OF !>FORM !,(F (CAR !,FORM))) w i l l match (FUNCT-OF (FACTORIAL 3) FACTORIAL), but w i l l not match (FUNCT-OF (PLUS 2 2) MINUS). The patter n : ((FREDS !>X) . !>REST) matches ((FREDS FATHER) WHISTLES) assi g n i n g FATHER to X and (WHISTLES) to REST. I t a l s o matches ( (FREDS FATHER) WHISTLES DIXIE) ass i g n i n g FATHER to X and (WHISTLES DIXIE) t o REST. 1.2- The Conniver C o n t r o l S t r u c t u r e The Conniver c o n t r o l s t r u c t u r e d i f f e r s from that of most other languages. LISP's c o n t r o l s t r u c t u r e i s r e c u r s i v e . In Micro-Planner the basic c o n t r o l s t r u c t u r e i s i t s backup f a c i l i t y which can be e a s i l y simulated using the r e c u r s i v e c o n t r o l of L i s p . Conniver, however, does not have r e c u r s i v e c o n t r o l as such, but a s t r u c t u r e s i m i l a r to that proposed by Bobrow and Weigbreit[1 ]- Conniver's c o n t r o l s t r u c t u r e i s a g e n e r a l i z a t i o n A Frame System Model f o r Understanding Natural Language 113 of L i s p ' s . This g e n e r a l i z e d c o n t r o l a l l o w s a r o u t i n e to be invoked and then suspended l e a v i n g i t s environment i n - t a c t . The Conniver c o n t r o l s t r u c t u r e uses the idea of a stack frame developed by Bobrow and Weigbreit[1 ]. A stack frame c o n s i s t s of an a s s o c i a t i o n l i n k which i s a po i n t e r to another stack frame- This a s s o c i a t i o n l i n k i s used as a v a r i a b l e a s s o c i a t i o n l i s t and i s used f o r a s s o c i a t i n g values with v a r i a b l e names. There i s a l s o a c o n t r o l l i n k which i s a pointer to the stack frame which caused the current stack frame to come i n t o e x i s t e n c e . There i s a l s o a l o c a t i o n i n a stack frame f o r s t o r i n g the program counter of the next i n s t r u c t i o n to be executed when c o n t r o l i s returned to the current stack frame. Whenever a r o u t i n e i s c a l l e d a new stack frame i s created f o r i t to carry out i t s computation. When a r o u t i n e i s suspended a pointer must be created which points to the stack frame f o r the r o u t i n e . This means that the c o n t r o l and a s s o c i a t i o n l i n k s w i l l remain i n existence u n t i l t h i s p o i n t e r i s destroyed, since the stack frame w i l l not be garbage c o l l e c t e d u n t i l the po i n t e r no longer e x i s t s . The Conniver c o n t r o l s t r u c t u r e i s a very general one which allows p a r a l l e l processing or simulated p a r a l l e l processing i n t h i s case. At any one time there may be many d i f f e r e n t frames which may be a c t i v a t e d and i n exist e n c e . Each such frame w i l l have associated with i t a pointer to the stack frame corresponding to an i n v o c a t i o n of the frame. 1.3. The Conniver Data Base a Frame System Model f o r Understanding Natural Language 1 1 4 The Conniver data base i s a f l e x i b l e f a c i l i t y a l l o w i n g f o r adding and d e l e t i n g i n f o r m a t i o n , and performing other a c t i o n s on the data i n the data base. The data base c o n s i s t s of a hierarchy of contexts. Each context may or may not co n t a i n some piece of information. The Conniver data base allows f o r the c r e a t i o n of new cont e x t s , pushing and popping of contexts, a l s o , there are methods a v a i l a b l e f o r performing i n f e r e n c e s s i m i l a r to those a v a i l a b l e i n Micro-Planner. when Conniver i s f i r s t run the two Conniver v a r i a b l e s CONTEXT and GLOBaL are assigned the value of the same empty context. The v a r i a b l e CONTEXT i s used as the d e f a u l t value used i n a l l f u n c t i o n s which r e g u i r e a context- In the f o l l o w i n g , v a r i a b l e s enclosed i n brackets ([ ]) are o p t i o n a l and w i l l d e f a u l t to the value of the Conniver v a r i a b l e CONTEXT. The f o l l o w i n g f u n c t i o n s manipulate contexts only: (PUSH-CONTEXT [CONTEXT]) This f u n c t i o n pushes a new l a y e r onto the context s p e c i f i e d by CONTEXT and returns t h i s new context as value. The in f o r m a t i o n i n the o l d context i s s t i l l a v a i l a b l e i n the new context, but any changes to t h i s information w i l l only be r e f l e c t e d i n the new context and not i n the o l d one. This a l l o w s a f u n c t i o n to cr e a t e a h y p o t h e t i c a l context i n which i t may change information without worrying about destroying the o l d context i n case the fu n c t i o n f a i l s . (POP-CONTEXT [CONTEXT]) This f u n c t i o n pops a l a y e r from the context s p e c i f i e d by CONTEXT and returns t h i s new context as i t s value. Thus any inf o r m a t i o n A Frame System Model f o r Understanding Natural Language 115 i n t h i s l a y e r w i l l be l o s t . This r e s t o r e s the context to the s t a t e j u s t before a PUSH-CONTEXT was performed. (FINALIZE [CONTEXT]} This f u n c t i o n has the same value as POP-CONTEXT, with the s i d e e f f e c t of making i t s argument an equivalent context to i t s s u p e r i o r . That i s a l l data w i l l have the same pro p e r t i e s i n the super context t h a t they had i n the o r i g i n a l c ontext. The f o l l o w i n g f u n c t i o n s a l l manipulate data which are i n a context. (ADD ITEM [CONTEXT]) This f u n c t i o n adds item to the context s p e c i f i e d by the context CONTEXT. For example, (ADD ' (IS-A SQUARE SQUARE1) ) w i l l add the data item " (IS-A SQUARE SQUARE 1)" to the current context. (REMOVE ITEM [CONTEXT]) This f u n c t i o n d e l e t e s item from the context s p e c i f i e d but the context CONTEXT. (FETCH PATTERN [CONTEXT]) This f u n c t i o n w i l l r e t u r n a p o s s i b i l i t i e s l i s t of a l l the data items i n the context s p e c i f i e d i>y the context CONTEXT which match the pattern PATTERN. For more inf o r m a t i o n on the p o s s i b i l i t i e s l i s t , see the Conniver Reference Manual [16]-(IF-ADDED ATOM PATTERN BODY) This f u n c t i o n defines a method with name ATOM whose body BODY w i l l be invoked i f any data item which matches pattern i s added to a context i n which the method i s defined. A Frame System Model f o r Understanding Natural Language 116 (IF-NEEDED ATOM PATTERN BODY) This f u n c t i o n defines a method with name ATOM whose body BODY w i l l be invoked i f any f e t c h i s done which matches pattern i n a context i n which the method i s defined. (IF-REMOVED ATOM PATTERN BODY) This f u n c t i o n defines a method with name ATOM whose body BODY w i l l be invoked i f any data item which matches pa t t e r n i s removed from a context i n which the method i s defined. The above three methods may be added to a context by use of the ADD f u n c t i o n described above, by e i t h e r adding the name of the method or by adding the method i t s e l f . 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0051778/manifest

Comment

Related Items