UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

An expert system shell for processing logic grammars Salim, Juliani Susanti 1985

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

Item Metadata

Download

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

Full Text

A N E X P E R T S Y S T E M S H E L L F O R P R O C E S S I N G L O G I C G R A M M A R S B y J U L I A N I S U S A N T I S A L I M B . Sc., M c G i l l U n i v e r s i t y , 1983 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F S C I E N C E i n T H E F A C U L T Y O F G R A D U A T E S T U D I E S (Depar tment of C o m p u t e r Science) W e accept this thesis as c o n f o r m i n g to the required s tandard T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A M a y 1985 © J u l i a n i Susant i S a l i m , 1985 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of C-Q^jpiU^ Sa'evu?? The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 E-6 C3/81) i i Abstract M a n y expert systems have been developed over the past decades. P r o G r a m m a r is a modest expert system shell tha t has been developed recent ly . It is bui l t on top of the C P r o l o g / U N L X * system r u n n i n g on a V A X t 11/750. P r o G r a m m a r is designed for processing a n d developing grammars . It can also be used as a knowledge base constructor for other fields besides grammars , a learning t o o l , a P r o l o g interpreter , a n d as a consul t ing system. P r o G r a m m a r is an interact ive system meaning not only can the user query P r o G r a m m a r b u t P r o G r a m m a r also can question the user. T h e user is a l lowed to request an explanat ion f r o m the P r o G r a m m a r on how the so lut ion to the query was der ived . *UNIX is a trademark of A T & T Bell Laboratories. ^VAX is a trademark of Digital Equipment Corp. iii Table of Contents C h a p t e r 1 - In t roduct ion 1 C h a p t e r 2 - E x p e r t systems 6 2.1. A n a t o m y of expert systems 7 2.1.1. T h e knowledge base 8 2.1.2. H o w to construct a knowledge base 8 2.1.3. T h e inference system 11 2.1.4. T h e explanat ion fac i l i ty 12 2.1.5. H o w to implement the explanat ion fac i l i ty 12 2.2. A p p l i c a t i o n s of expert systems 13 2.3. P r o l o g for i m p l e m e n t i n g expert systems 15 C h a p t e r 3 • T h e interpreters 16 3.1. A brief i n t r o d u c t i o n to P r o l o g 10 3.1.1. P r o l o g database 16 3.1.2. Fac ts 17 3.1.3. Rules 17 3.1.4. Queries 17 3.2. H o w to satisfy a goal 18 3.3. T h e interact ive P r o l o g interpreter 22 3.4. T h e P r o l o g interpreter versus the interactive interpreter 24 C h a p t e r 4 - G r a m m a r s 25 4.1. Context - free grammars 25 4.2. Definite Clause G r a m m a r s 28 4.3. Definite Clause T r a n s l a t i o n G r a m m a r s 32 4.3.1. N o t a t i o n used by D C T G s 32 C h a p t e r 5 - T h e P r o G r a m m a r system 37 5.1. T h e Q u e r y _ t h e _ u s e r fac i l i ty 38 5.1.1. T h e skeleton of Q u e r y _ t f a e _ u s e r interpreter 41 5.2. T h e explanat ion fac i l i ty 43 C h a p t e r 6 - Conc lus ions 47 References 50 A p p e n d i x A - A l i s t ing of the P r o G r a m m a r system 52 iv A p p e n d i x B - Databases 74 A p p e n d i x C - Q u e r y session w i t h P r o G r a m m a r 78 V List of Figures Figure 1 - Sample classification of a small set of car problems 9 Figure 2 - The parse tree for a sentence "John likes a dog" 31 vi Acknowledgement I w i s h to acknowledge several people who were very helpful in the w r i t i n g of this thesis. F i r s t of a l l , I am very grateful to m y supervisor, D r . H . A b r a m s o n , who was very pat ient and he lpful throughout the preparat ion of m y thesis. I extend t h a n k s to M e i Jean G o h for g iv ing the n a m e ( P r o G r a m m a r ) to the system and for m a n y hours of f r u i t f u l discussion. M y apprec ia t ion also goes to D r . K . A b r a h a m s o n , w h o careful ly read the thesis. M a n y t h a n k s go to m y friends i n Gage r e 3 i d e n c c ( E 9 D ) for the fun t imes we h a d a n d their c o n t i n u a l m o r a l support w h i c h I needed throughout this t e r m . 1 Chapter 1 Introduction Considerable a t tent ion has been given to P r o l o g within the past few years. It has been wide ly used i n appl icat ions of symbol ic c o m p u t a t i o n , such as m a n y areas of ar t i f ic ia l intell igence, re lat ional databases, a n d m a t h e m a t i c a l logic. A P r o l o g p r o g r a m consists of a set of clauses. A clause can be either a fact or ru le . F o r example, we can define a rule for a brother as follows b r o t h e r _ o f ( X , Y ) : - male(X) , parent_of (Z ,X) , p a r e n t _ o f ( Z , Y ) . T h e rule sa id for every X and Y , X is a brother of Y if X i3 a male , Z is a parent of X , and Z is also a parent of Y . N o w , we m a y w i s h to ask P r o l o g a question l ike : Is it t rue that S a m is a brother of J i l l ? In order to answer the quest ion, P r o l o g searches the database f rom the top to b o t t o m for i n f o r m a t i o n about S a m and J i l l . T h e answer to the query is " y e s " if P r o l o g can o b t a i n a l l the i n f o r m a t i o n it needs to solve the query f r o m the database i n a finite t i m e . Otherwise the answer w o u l d have been " n o " . P r o l o g adopts a top-d o w n depth-f i rs t strategy a n d N e g a t i o n As F a i l u r e [Clark 78] w h i c h states : Suppose we have a query Q , a n d a database D B N O T Q is assumed to be true if Q is not provable in a finite t ime. 2 N O T Q is assumed to be true if Q is not provable f r o m any clauses i n the database D B . F o r example, suppose we have a database consist ing of adjacent provinces i n C a n a d a . N o w we w a n t P r o l o g to find out whether Quebec is adjacent to O n t a r i o . If P r o l o g cannot find adjacent(Quebec ,Ontar io) f r o m the database, then it w i l l give " n o . " as the answer meaning " N o , Quebec is not adjacent to O n t a r i o . " . T h e answer given by P r o l o g is not quite accurate i n this case since N O T adjacent (Quebec ,Ontar io) is not expl i c i t ly present i n the database. However , to conclude " D o not know if Quebec is adjacent to O n t a r i o . " w o u l d have been more accurate whenever s tr ic t logic is considered an i m p o r t a n t issue. T h e assumpt ion of N e g a t i o n A s F a i l u r e is also made b y what is referred to as the C l o s e d W o r l d A s s u m p t i o n w h i c h says that a n y t h i n g that is not provable to be true is assumed to be false [Reiter 77]. T h e advantage of a p p l y i n g N e g a t i o n A s F a i l u r e is t h a t it is not necessary to include al l negative facts about a given d o m a i n in a database. In general, negative facts o u t n u m b e r posit ive ones. O f t e n , it is not possible to generate a l l negative facts. However , not i n c l u d i n g negative facts expl ic i t ly in a database does not affect the consistency of a database. A p p l y i n g N e g a t i o n A s F a i l u r e has d r a w b a c k s . Sometimes a user might forget to inc lude a l l posit ive facts into a database before he asks P r o l o g to solve hi3 p r o b l e m . F o r example, consider a database w i t h the fo l lowing rules and facts : parent_of(sam,bi l l ) . 3 female( j i l l ) . s i s t e r ( X , Y ) : -female(X) , p a r e n t _ o f ( Z , Y ) , p a r e n t _ o f ( Z , X ) . T h e rule says X is a sister of Y if X is a female, and X a n d Y have same parents. T h e user has forgotten to include parent_of(sam, j i l l ) i n the database. W h e n he ask3 P r o l o g to find out i f J i l l is a sister of B i l l , P r o l o g w i l l give " n o . " as the answer meaning " N o , J i l l is not a sister of B i l l . " because parent_cf (sam, j i l l ) cannot be f o u n d in the database. B y a p p l y i n g N e g a t i o n A s F a i l u r e N O T parent_of(sam, j i l l ) is t rue . Hence J i l l a n d B i l l have different parents . T h i s implies that J i l l cannot be B i l l ' s sister. In this case, a p p l y i n g N e g a t i o n A s F a i l u r e is not desirable because the non-existence of parent_of(sam, j i l l ) i n the database is not caused by the fact tha t sam is not parent_of J i l l b u t is caused b y the user'3 forgetfulness. If P r o l o g asked the user to supply parent_of (X , j i l l ) , about w h i c h the user might happen to k n o w , the answer to the query w o u l d have been "yes . " meaning " Y e s , J i l l is a sister of B i l l . " It w o u l d be desirable to have a P r o l o g interpreter that asks for i n f o r m a t i o n w h i c h is needed for so lv ing a query w h i c h cannot be f o u n d i n the database. 4 Q u e r y _ t h e _ u s e r , in t roduced b y M . Sergot [Sergot 83], is a P r o l o g interpreter t h a t handles interact ive P r o l o g , w h i c h means that not o n l y is the user able to ask the system questions but the system m a y also ask the user questions. M y thesis involves i m p l e m e n t i n g a n expert system shell for processing grammars ( P r o G r a m m a r ) i n P r o l o g . T h e m a i n idea of P r o G r a m m a r came f r o m A P E S [ H a m m o n d 82a], Q u e r y _ t h e _ u s e r [Sergot 83], and [ C l a r k , M c C a b e 82]. P r o G r a m m a r consists of a knowledge base and an inference mechanism w h i c h matches the user's query w i t h rules or facts i n the knowledge base in order to deduce the query. W h e n P r o G r a m m a r cannot find any rules or facts that can be used to solve the user's query, i t w i l l ask the user for i n f o r m a t i o n required to solve the query. T h e user can either provide the i n f o r m a t i o n , if any,, or ask P r o G r a m m a r w h y it needs i n f o r m a t i o n . If the user asks for an explanat ion , P r o G r a m m a r w i l l trace and disp lay the rules used f r o m the point of the user's query u n t i l the point at w h i c h P r o G r a m m a r needs more i n f o r m a t i o n . W h e n P r o G r a m m a r finds the so lut ion to the user's query, it can also provide an explanat ion o n how the so lut ion was der ived . In a d d i t i o n , P r o G r a m m a r has features for pars ing sentences according to grammars and const ruc t ing knowledge bases. It is useful for b u i l d i n g a new language f r o m no p r o d u c t i o n rules to a complete g r a m m a r . D e f i n i t e C l a u s e T r a n s l a t i o n G r a m m a r s ( D C T G ) are used to describe the g r a m m a r o f a language. E x p e r t systems and their appl icat ions w i l l be described in chapter 2. A brief descr ipt ion of P r o l o g and Q u e r y _ t h e _ u s e r w i l l be given in chapter 3. A n overview of C o n t e x t - F r e e G r a m m a r , Definite Clause G r a m m a r , and D e f i n i t e C l a u s e 5 T r a n s l a t i o n G r a m m a r w i l l be discussed i n chapter 4. T h e i m p l e m e n t a t i o n of P r o G r a m m a r w i l l be covered i n chapter 5, a n d conclusions w i l l be discussed i n the last chapter . 6 Chapter 2 Expert systems P roGrammar is a modest expert system shell t h a t was designed for processing grammars . M a n y expert systems have been developed over the past decades. w h a t is an expert system ? A n expert system is a computer program that provides expertise i n a specific subject of knowledge. U s u a l l y an expert system engages the user i n a d ia log to get i n f o r m a t i o n . W h e n the system gets sufficient i n f o r m a t i o n , it w i l l eventual ly provide expert advice or solutions to the user's problem or supply i n f o r m a t i o n the user requests. K n o w l e d g e plays an i m p o r t a n t role in the performance of expert systems. K n o w l e d g e is i n f o r m a t i o n that has been pared, shaped, selected, interpreted, a n d t ransformed. There are t w o different types of knowledge. T h e first type , i n v o l v i n g facta of the d o m a i n , is knowledge t h a t m a y be f o u n d in textbooks and journals of the field of interest. A n d there is heuristic knowledge w h i c h is harder to re tr ieve—it is the knowledge of m a k i n g good educated guesses in that field. A n expert system consists of a knowledge base and an inference mechanism. Some expert systems also provide an explanat ion f a c i l i t y — w h i c h gives explanations on how they derive their conclusions. E x p e r t systems may also provide facilit ies that can expla in w h y some conclusion cannot be reached or w h y the user is being p r o m p t e d for fur ther i n f o r m a t i o n . T h e explanat ion fac i l i ty is a n essential part of an 7 expert system. Besides g i v i n g an explanat ion , i t is also can be used for debugging the knowledge base i n the early stages of its construct ions. A wide v a r i e t y of expert systems have been b u i l t for m a n y appl icat ions especially for medica l diagnosis . T h e Japanese foresee a p r o m i s i n g future for expert systems. In 1981, they announced to the w o r l d their plans for b u i l d i n g a F i f t h Genera t ion of computers . T h e i r goal is to develop very intel l igent expert systems to be used i n the 1990's a n d beyond. T h e a im for these new systems is to be able to communica te w i t h an o r d i n a r y people us ing na tura l language such as E n g l i s h , Japanese and F r e n c h , so that one w o u l d not require any b a c k g r o u n d i n p r o g r a m m i n g languages to use such systems. F i n a l l y , the Japanese expect these new systems to be inexpensive a n d reliable to be used everywhere—in offices, factories, shops a n d homes. These new systems called K n o w l e d g e I n f o r m a t i o n Processing Systems ( K I P S ) . 2.1. A n a t o m y of expert systems T y p i c a l l y , an expert system m a y consist of a knowledge base, an inference system and an explanat ion fac i l i ty . T h e knowledge base w o u l d comprise facts and rules. W h i l e the inference system is responsible for m a t c h i n g the user's query w i t h facts or rules i n the knowledge base i n order to deduce the query. T h e explanat ion fac i l i ty w o u l d be capable of f u r n i s h i n g an explanat ion on how the conclusion to some query is a r r i v e d at. In a d d i t i o n , the explanat ion fac i l i ty can expla in to the user w h y he or she has been p r o m p t e d for some par t i cu lar i n f o r m a t i o n . 8 2.1.1. The knowledge base T h e knowledge base is a pr ime c o n t r i b u t o r to good performance of expert systems. It determines the contents of expert system and also the level of expertise offered by the sys tem. A knowledge base is a symbol ic representat ion of facts and expert knowledge i n the subject d o m a i n of the expert sys tem. E x p e r t knowledge w h i c h cannot be f o u n d in textbooks or j o u r n a l s — i t is experience that a h u m a n expert accumulates over years and years of s t u d y and w o r k . 2.1.2. How to construct a knowledge base K n o w l e d g e base const ruc t ion has been a bott leneck i n the advancement of expert systems. It involves experts i n some d o m a i n a n d computer scientists w o r k i n g together to design and construct the d o m a i n knowledge base. T h e role of computer scientist is to t r a n s f o r m whatever i n f o r m a t i o n the experts give into some f o r m suitable for computer i n p u t . T o i l lustrate , suppose we want to construct a knowledge base for mechanical problem in cars for f a u l t i n g - f i n d i n g consul t ing system (see fig.l).This example is t aken f r o m H a m m o n d 82a. 9 Car Engine Cooling System Carburetor Valves Incorrect Timing Reboring Needed Radiator Fanbelt Complete Overhaul Leak Slackness F i g . l Sample classif icat ion of a smal l set of car problems. T h e items in external nodes are the car problems. T h e classif ication can be represented i n a knowledge base by two relations R l : is_part_of(X,Y). R 2 : is_possibly_identified_in(X,Y). U s i n g our car problems example, fig.l the car problems w i l l be represented in the knowledge base as follows : 10 is_part_of(engine,car) . is_part_of(cooIing_system,car) . is_jpart_of(carburetor,engine). is_part_of(valves,engine) . is _ j>art_of(radiator,cooliag_system). i s_part_of( fa i ibel t , cool ing_system). U s i n g re la t ion R2 the car problems represented look l ike this i s_poss ib ly_ ident i f ied_in( incorrec t_ t iming ,carburetor ) . i s_possibly_ident i f ied_in(reboring_needed 7 valves) . i s_poss ib ly_ ident i f ied_in( leak , radiator ) . i s_possibly_ident i f ied_in(s lackness , fanbel t ) . i s_poss ib ly_ident i f ied_in(complete_overhaul ,cool ing_system) . T o t rans form h u m a n experties into a knowledge base the fo l lowing re lat ion is used R3 : i s _ i d e n t i f i e d _ b y ( i n ( X , Y ) , C o n d i t i o n s ) . W h e r e C o n d i t i o n s is a list of s y m p t o m s of car problems. So the expert knowledge for car problems w o u l d be as fol lows : i s_ ident ined_by( in(engine_problems,car_problems) , engine_wont_star t ) . i s_ ident i f ied_by( in(engine_problems,car_problems) , engine_s tar ts_but_runs_unevenly) . 11 i s_ ident i f ied_by( in(complete_overhaul ,cool ing_system), (badly_rusted_radiator , leaking_hoses) ) . W h e n the car problems is f o u n d , an expert system m i g h t w a n t to give some suggestions. These suggestions can be represented i n the fo l lowing f o r m R4 : is_action_for(X,Y). W h e r e X is a suggestion and Y is the problem that was f o u n d . F o r example , i s_ac t ion_for (sea l_wi th_recommended_compound, leak) . i s_act ion_for( t ighten_and_replace ,s lackness) . T h e above example i l lustrates how a knowledge base may be constructed . A f t e r cons t ruc t ing the knowledge base, we m i g h t w a n t to design an inference system that w i l l look t h r o u g h the knowledge base for finding the so lut ion of some query posed by a user. 2.1.3. The inference system T h e inference system is responsible for searching t h r o u g h the knowledge base i n order to solve a user's query. T h e inference system looks l ike : R5 : is_identified_in(X,Y) : -is_possibly_identified_in(X,Y). 12 R6 : is_identified_in(in(X,Y),Z) : -is_part_of(Y,Z), is_id en tify_in (X, Y). A c o m b i n a t i o n of R 5 and R 6 w i l l al low the expert system to look t h r o u g h al l rules a n d facts i n the knowledge base that can be used for so lv ing the query. It is necessary to be able to give an explanat ion o n how the so lut ion was der ived , should the user request for i t . 2.1.4. T h e explanation facility T h e explanat ion fac i l i ty i n the signif icant part of an expert systems. It gives the user assurance that the so lut ion der ived by the expert system is reasonable and the so lut ion is based o n i n f o r m a t i o n t h a t was suppl ied by the user. T w o forms of explanat ion can be g iven—the " h o w " and the " w h y " . T h e " h o w " explains to the user step by step how the conclusion is der ived. T h e " w h y " al lows the user to request an explanat ion on w h y he is being asked for some par t i cu lar i n f o r m a t i o n . In next section, I w i l l discuss how the " h o w " and the " w h y " explanat ion m a y be i m p l e m e n t e d . 2.1.5. H o w to implement the explanation facility T o implement the " h o w " and the " w h y " explanat ion , we should redefine the inference rules that were given in the previous section as fol lows : 13 R 5 : is_identify_in(X,Y,trace(T)) : -is_possibly_identified_in(X,Y,trace((poss_id(X,Y)|T))). R 6 : is_identify_in(in(X,Y),Z,trace(T)) : -is_part_of(Y,Z) , is_id en tif y_in(X, Y, tr ace( (t_part( Y, Z) \ T))). where T is the level of trace tree. t _ p o s s _ i d ( X , Y ) : - g ive_reason( t_poss_id(X,Y)) . t _ p a r t ( X , Y ) : - g ive_reason( t_par t (X ,Y) ) . T h i s i m p l e m e n t a t i o n was suggested b y C l a r k and M c C a b e [ C l a r k , M c C a b e 82]. A n d the i m p l e m e n t a t i o n has been done i n P r o G r a m m a r . M o r e explanat ion o n this w i l l be given i n chapter 5 ( Implementat ion of P r o G r a m m a r ) . 2 . 2 . A p p l i c a t i o n s o f e x p e r t s y s t e m s O v e r the past decade, extensive research has been done on expert systems by art i f ic ia l intelligence researchers. Research o n expert systems has been m o t i v a t e d by m a n y factors; one of w h i c h is that expert systems seem to have a promis ing future because they can assist i n so lv ing complex, r e a l - w o r l d problems in specific scientif ic , medical specialities a n d engineering requir ing h u m a n expertise. These new machines are not s i m p l y for p l a y i n g games l ike chess, checkers and space invader . M o s t of the t i m e , expert systems can help solve problems more r a p i d l y a n d more accurately t h a n any expert can . M a n y expert systems are available in the m a r k e t . T h e y have been widely u t i l i zed i n var ious fields such as medicine, educat ion , 14 engineering a n d science. D E N D R A L was the first expert system to be designed. T h i s project began i n 1965 at S t a n f o r d univers i ty . D E N D R A L has been i n use for m a n y years i n universit ies and i n d u s t r i a l chemical labs a r o u n d the w o r l d . Its a b i l i t y to expla in the deta i l of molecule s tructure f r o m chemical d a t a now exceeds h u m a n c a p a b i l i t y [Buchanon,Fe igenbaum 78]. M a n y expert systems have also been designed for purposes other t h a n chemis t ry . E x p e r t system for medica l diagnosis designed aid3 i n medica l decis ion m a k i n g . M Y C I N developed i n 1976 at S t a n f o r d univers i ty is one such example. It was designed to diagnose b lood and infections, give suggestions to the phys ic ian on ant ib iot ic therapies for t reat ing the infections [Shortliffe 76] T h e reason for developing a medica l consul ta t ion expert system is tha t i t can very t h o r o u g h l y diagnose the disease that a pat ient is suffering f r o m , never over looking a l l possibil it ies prov ided adequate pat ient d a t a are avai lable in the knowledge base. A phys ic ian tends to make mistakes when he examines a pat ient . O f t e n , most of these mistakes are caused by his carelessness when he leaves out some possibil it ies and these mistakes lead to incorrect diagnosis. However there are certain things that medical consul ta t ion systems cannot yet perform such as physica l examinat ion , p i c k i n g up n o n - v e r b a l i n f o r m a t i o n f rom the pat ient expressed w h e n he is confronted w i t h a question and the system cannot effectively converse w i t h the pat ient to get i n f o r m a t i o n or explain therapy. Perhaps , i n the near fu ture , these problems w i l l be overcome. 15 2.3. Prolog for implementing expert systems T h e use of P r o l o g i n i m p l e m e n t i n g expert systems is now being established both i n industr ies and academic researches. It is because of several reasons such as P r o l o g is a language w i t h a very simple syntax . A n d the semantics of P r o l o g can be understood easily even b y the nonprogrammer user. T h e s i m p l i c i t y of P r o l o g makes i t possible to achieve fast i m p l e m e n t a t i o n a n d easy p o r t a b i l i t y . A n d for this reason, I selected to use P r o l o g to implement P r o G r a m m a r . A brief i n t r o d u c t i o n to P r o l o g w i l l be g iven in chapter 3 . 16 Chapter 3 The interpreters P r o l o g ( P R O g r a m m i n g i n L O G i c ) is based on logic p r o g r a m m i n g as described by K o w a l s k i [ K o w a l s k i 79]. T h e first P r o l o g interpreter was implemented i n the language A L G O L - W b y Roussel at Marsei l le in 1972. T h e r e are m a n y implementat ions of the language now; however, one of the best is the E d i n b u r g h D E C - 1 0 interpreter [Pereira et a l . 79]. P r o l o g has been ga in ing i n p o p u l a r i t y since the early 70's. Its major use has been for research i n art i f ic ia l intell igence, such as for n a t u r a l languages and expert systems. , T h r o u g h o u t this thesis, al l of the examples w i l l conform to the E d i n b u r g h D E C - 1 0 interpreter s t a n d a r d vers ion. 3.1. A brief introduction to Prolog Before discussing Q u e r y _ t h e _ u s e r , I w o u l d l ike to give a brief i n t r o d u c t i o n to P r o l o g for those not fami l iar w i t h P r o l o g . 3.1.1. Prolog database A P r o l o g database consists of a set of clauses and b u i l t - i n predicates, where each clause is either a fact about the given i n f o r m a t i o n or a rule about how the so lut ion to a query m a y relate to given facts. 17 3.1.2. Facts Facts are clauses w i t h o u t an antecedent. F o r instance, if we w a n t to specify i n P r o l o g that B i l l is a parent of J o h n , we enter the fact according to P r o l o g syntax [C locks in ,Mel l i sh 81], l ike so : parent_of (b i l l , john) . 3.1.3. Rules Rules are impl ica t ions of the form h ( A l , , A n ) : - t l , , t k , where k > 0 & n > = 0 each t i is of the form p ( X l , , X m ) , p is the name of a re lat ion fo l lowed by arguments X I , , X m . F o r example, we can give a def in i t ion for s ib l ing as fol lows s i b l i n g ( X , Y ) : -parent_of (Z ,X) , p a r e n t _ o f ( Z , Y ) . w h i c h i m p l y that X and Y are siblings if X and Y share a c o m m o n parent. 3.1.4. Queries Once we have some facts, we can make queries about t h e m . A query has the same f o r m as a fact , w i t h a special symbol(T-) added in f ront of i t . So a query looks l ike : ?- parent_of (b i l l , john) . A query can be more compl i ca ted t h a n this . 18 Suppose, we want to find out who B i l l ' s sister is a n d w h o one of his parents is , the query w o u l d take this f o r m : ?- s is ter(X,bi l l ) , parent_of (Y ,b i l l ) . T h e in terrogat ion is successfully completed when subst i tut ions for X and Y are f o u n d . 3.2. How to satisfy a goal P r o l o g a t tempts to evaluate a con junct ion of goals i n order f r o m left to r i g h t . T h i s means P r o l o g w i l l not t r y to evaluate a goal u n t i l its left neighbor is satisfied. W h e n it is satisfied then its r ight neighbor w i l l be evaluated. Hence, to evaluate a goal q l ( ),q2, , q n , the goal is b r o k e n into subgoals q l ( ) a n d q2, , q n . P r o l o g w i l l t r y to sat isfy subgoal q l ( ) , fo l lowed by an eva luat ion of q2, , q n . In so lv ing the subgoal q l ( ), i t tries to find qi( •) or q l ( ) r l i i r J -A fact q l ( ) causes the subgoal q l ( ) to be satisfied immedia te ly but a rule q l ( ) : - r l , , r j o n l y reduces q l ( ) to the eva luat ion of new subgoal r l , , r j . W h e n the subgoal q l ( ) is satisfied, then its r ight neighbor q2, , qn w i l l be evaluated . T h e goal is completely satisfied if the r ight neighbor of a satisfied subgoal is e m p t y . 19 A fa i lure occurs w h e n none of the clauses i n the database w i l l m a t c h w i t h the a tom of the current goal . W h e n this happens, P r o l o g backtracks to the most recent previously satisfied subgoal a n d uses u n t r i e d clauses i n the database to resatisfy the subgoal . T h e goal has fa i led if there is not any previous subgoal w h i c h can resatisfied d u r i n g b a c k t r a c k i n g . F o r instance, we have a goal g l ( X l , , X n ) , g2(Xi,...., X k ) to be satisf ied. A n eva luat ion of the goal g l ( X l , , X n ) , g2(Xi, , X k ) is broken d o w n into two parts . T h e subgoal g l ( X l , , X n ) w i l l be evaluated first. P r o l o g tries to pa t te rn m a t c h the subgoal w i t h a clause of the f o r m g l ( A l , , A n ) . or g l ( A l , , A n ) : -t l ( A i , , A l ) , , t i ( A k , , A m ) . using a t o p - d o w n d e p t h - f i r s t strategy. W h e n P r o l o g finds a m a t c h i n g clause g l ( A l , , A n ) , ( A l , , A n ) and ( X I , , X n ) are made ident ical by a p p l y i n g a unifier, where a unifier is a sequence of subs t i tu t ion components such that Ai t r = X i t r where A i and X i are l i terals, and tr is a unifier. T h i s process is cal led uni f i ca t ion . F o r example, suppose we want to make ( X , Y ) and (a,Z) to be ident i ca l . W e a p p l y a unif ier ( a / X , Y / Z ) to ( X , Y ) and (a,Z), where a / X means subst i tute X by a. U n i f i c a t i o n of ( X , Y ) ( a / X , Y / Z ) results in (a ,Y) . (a,Z) ( a / X , Y / Z ) results in ( a , Y ) . Hence, ( X , Y ) and (a,Z) are ident ica l under the uni f i ca t ion . A f t e r uni f i ca t ion has been 20 done on ( A l , , A n ) a n d ( X I , , X n ) , g l ( A l , , A n ) a n d g l ( X l , , X n ) are syntac t i ca l ly ident i ca l . P r o l o g fol lows the uni f i ca t ion m e t h o d in t roduced by R o b i n s o n [Robinson 79]. If there are no new goals to be satisfied, then the goal g l ( X l , , X n ) has succeeded. Otherwise P r o l o g has to deduce new goals. W h e n new goals are satisf ied, P r o l o g w i l l a t tempt to satisfy g2 ( X i , , X k ) . T h e goal is satisfied if a l l subgoals have been satisf ied. T o i l lustrate , suppose we have a database parent_of(bi l l , john) . parent_of( john,sam). parent_of(bi l l ,ann) . parent_of(sam, j i l l ) . ances tor_of (X ,Y) : -p a r e n t _ o f ( X , Y ) . ances tor_of (X ,Y) : -parent_of (Z ,Y) , ances tcr_of (X ,Z) . and in response to the query ?- ancestor_of(bi l l ,sam). P r o l o g w i l l t r y to use ances tor_of (X ,Y) : -p a r e n t _ o f ( X , Y ) . and under uni f i ca t ion 21 U = { b i l l / X , s a m / Y } b i l l / X means subst i tute X by b i l l . ancestor_of(bi l l ,sam) a n d ances tor_of (X ,Y) become syntac t i ca l ly ident i ca l . T h e eva luat ion of the goal reduces to eva luat ion of the der ived goal parent_of(bi l l , sam). B u t parent_of(bi l l , sam) cannot be f o u n d i n the database. So parent_of(bi l l , sam) cannot be satisf ied, a n d b a c k t r a c k i n g is i n i t i a t e d . P r o l o g w i l l t r y to find an a l ternat ive w a y to solve the goal . T h i s t ime it uses the second rule of ances tor_of (X ,Y) . W i t h the uni f i ca t ion , U = { b i l l / Y , s a m / Y } the eva luat ion reduces to parent_of(Z,sam) , ancestor_of(bi l l ,Z) . T h e subgoal parent_of(Z,sam) can be satisfied b y s u b s t i t u t i n g Z by John . ancestor_of(bi l l , john) can be satisfied us ing the rule ances tor_of (X ,Y) : -p a r e n t _ o f ( X , Y ) . U = { b i l l / X , j o h n / Y } A new goal to be satisfied is parent_of (b i l l , john) . A n d , indeed, parent_of (b i l l , john) is i n the database, hence the goal has succeeded. T h u s , the answer to the query is "yes" meaning " Y e s , b i l l is the ancestor_of s a m . " . 22 3.3. The interactive Prolog interpreter Q u e r y _ t b . e _ u . s e r has been implemented i n P r o G r a m m a r . Q u e r y _ t h e _ u s e r is an extension of the P r o l o g interpreter . It allows interac t ion between a user and the sys tem. Fac ts and rules can be added to the database whi le the system is processing a query. Q u e r y _ t h e _ u s e r regards the user as an extension of a database. W h e n e v e r i t needs i n f o r m a t i o n to deduce a query a n d that i n f o r m a t i o n is not i n the database, i t prompts the user to see if he can s u p p l y the i n f o r m a t i o n . It checks if the i n f o r m a t i o n is askable meaning " Does the user know a n y t h i n g about this i n f o r m a t i o n ? " before Q u e r y _ t h e _ u s e r requests i n f o r m a t i o n f r o m the user. A t the beginning of the session, the user tells the system a l l relations he knows about . These relations are m a r k under the predicate askable. T o i l lustrate , let's consider an interact ive vers ion of J i l l is a sister of B i l l presented earlier. T h e database consists of parent_of(sam,bi l l ) . female( j i l l ) . s i s te r (X ,Y) : -female(X) , p a r e n t _ o f ( Z , Y ) , p a r e n t _ o f ( Z , X ) . same as before w i t h the a d d i t i o n of askable(parent_of) . 23 T h e assertion askable tells the system t h a t the user knows about the re la t ion parent_of a n d he is w i l l i n g to give i n f o r m a t i o n about the re la t ion . If the i n f o r m a t i o n is askable then the procedure a$k_user asks the user what i n f o r m a t i o n it needs. E v e n t h o u g h Q u e r y _ t h e _ u s e r can get i n f o r m a t i o n f rom the user whenever i t needs i t , N e g a t i o n A s F a i l u r e s t i l l applies. W h e n the user has fa i led to give any helpful response to the quest ion, then Q u e r y _ t h e _ i ! s e r applies N e g a t i o n A s F a i l u r e . T h u s , the answer to the query can s t i l l be " n o " . F o r example, let's go back to our example i n chapter 1. W e query whether J i l l is a sister of B i l l . T h e answer is " n o " according to the P r o l o g interpreter since parent_cf (sam, j i l l ) cannot be f o u n d in the database. N o w we use Q u e r y _ t h e _ u s e r to process the query. W h e n i t cannot find parent_of(sam, j i l l ) in the database i t asks is it t rue , tha t sam parent_of j III ? answer is yes.(user's response) T h e user has responded " y e s " to the quest ion, thus the answer to the user's query is " y e s " because according to the user S a m is parent of J i l l . T h i s implies B i l l a n d J i l l share a c o m m o n parent . B u t if the user h a d responded " n o " to the system's quest ion, then the answer to the query w o u l d have been " n o " , since it is not provable that J i l l and B i l l have the same parent . T h e skeleton of the interact ive P r o l o g interpreter w i l l be presented in chapter 5. 24 3 . 4 . T h e P r o l o g i n t e r p r e t e r v e r s u s t h e i n t e r a c t i v e i n t e r p r e t e r T h e major difference between Q u e r y _ t h e _ u s e r a n d the P r o l o g interpreter is that Q u e r y _ t h e _ u s e r always requests i n f o r m a t i o n t h a t it needs to solve the query f rom the user w h e n the i n f o r m a t i o n cannot be f o u n d i n the database. T h e n it tries to solve the query one more t i m e . If the query s t i l l cannot be solved, then Q u e r y _ t h e _ u s e r applies N e g a t i o n A s F a i l u r e T h e interrogat ion is sort of l ike a w a r n i n g for the u s e r — "If I do not get i n f o r m a t i o n about the query f rom y o u , then I w i l l a p p l y N e g a t i o n A s F a i l u r e . " P r o l o g , on the other h a n d , never asks the user for i n f o r m a t i o n . It applies N e g a t i o n A s F a i l u r e w h e n the i n f o r m a t i o n t h a t it needs cannot be f o u n d i n the database, so the user never gets any w a r n i n g . T h i s implies tha t the user is never given a chance to correct mistakes he inadver tent ly made earlier. A ma jor d r a w b a c k of P r o l o g is that P r o l o g forces the user to s u p p l y i n f o r m a t i o n needed for so lv ing the query i n advance—before the query is even made, a l though the user sometimes does not have any idea w h a t k i n d of i n f o r m a t i o n must be suppl ied for so lv ing his query. 25 Chapter 4 Grammars A g r a m m a r is a set of rules tha t defines the f o r m u l a t i o n of a n a t u r a l language or p r o g r a m m i n g language "sentence" . T h r o u g h o u t this chapter a " sentence" means a sentence i n n a t u r a l language or a statement i n p r o g r a m m i n g language. G i v e n a g r a m m a r of a language, we can examine any sequence of words or symbols to see whether i t meets the cr i ter ia of being an acceptable sentence. In the next sections, I w i l l briefly introduce three types of g r a m m a r s : context- free g r a m m a r s , definite clause grammars , and definite clause t rans la t ion grammars w h i c h are used to describe languages that w i l l be parsed or developed by P r o G r a m m a r . 4.1. Context-free grammars Instead of g i v i n g a formal def ini t ion of w h a t a context- free g r a m m a r is, I w i l l i l lustrate it by p r o v i d i n g an example. T h e f o l l o w i n g n o t a t i o n w i l l be used to represent a g r a m m a r rule, nt — > b o d y . W h e r e nt is a n o n - t e r m i n a l s y m b o l , and body is a sequence of n o n - t e r m i n a l s or terminals separated by commas, where a n o n - t e r m i n a l is a s y m b o l that appears on the left h a n d side of a rule "and a t e r m i n a l is a s y m b o l that does not appear on the left h a n d side of a ru le . T o i l lustrate , here is an example t a k e n f rom 26 [Pere ira ,Warren 80]. T h e fo l lowing is a g r a m m a r that accepts s imple E n g l i s h sentences l ike " M a r y likes a dog " and 1 1 E v e r y m a n t h a t lives loves a w o m a n " . sentence — > noun_phrase , verb_phrase . noun_phrase — > determiner , n o u n , rel_phrase . noun_phrase — > name . verb_phrase — > t rans_verb , noun_phrase . verb_phrase — > in t rans_verb . rel_clause — > [that] , verb_phrase . rel_clause — > Q • determiner — > [a] . determiner — > [every] . determiner — > [all] . n o u n — > [man] . n o u n — > [woman] . n o u n — > [dog] . name — > [John] . name — > [mary] . t rans_verb — > [loves] . t rans_verb — > [likes] . in t rans_verb — > [lives] . A g r a m m a r consists of a set of rules. T h e first rule states t h a t a sentence is fo rmed by a noun_phrase fo l lowed b y a verb_phrase. These two phrases are c o m m o n l y k n o w n as the subject a n d the predicate of a sentence. N o w , we translate the 27 g r a m m a r into P r o l o g clauses. sentence(SO,S) : — noun_phrase(SO,Sl ) , verb_phrase(S l ,S ) . noun_phrase(SO,S) : — d e t e r m i n e ^ S0,S1) , noun(Sl,S2) , rel_clause(S2,S) . noun_phrase(SO,S) : — name(S0,S) . verb_phrase(SO,S) : — trans_verb(SO,S l ) , noun_phrase (S l ,S ) . verb_phrase(SO,S) : — intrans_verb(SO,S) . rel_verb([that|SO],S) : — verb_phrase(SO,S) . rel_clause(S,S) . determiner([every|S],S) . determiner([a|S],S) . determiner([all|S],S) . noun([man|S],S) . noun([woman|S],S) . noun([dog|S],S) . name([john|S],S) . name([mary|S],S) . trans_verb([loves|S],S) . trans_verb([likes|S],S) . intrans_verb([lives|S],S) . 28 •where SO represents the source s t r ing to be parsed, S represents a s t r ing that is left behind after SO is being parsed. T h e first rule states that there is a sentence between SO and S if there is a noun_phrase between SO and S I , and a verb_phrase between SI and S. W e can t r y to prove ?— sentence([mary,likes,john],[]). to determine whether the sentence is acceptable. A context- free g r a m m a r describes a language in a clear and m o d u l a r w a y . However , context- free grammars are not f u l l y adequate for descr ibing n a t u r a l languages or p r o g r a m m i n g languages. It can only check the syntax of a sentence b u t not evaluate the semantics or context dependent i n f o r m a t i o n of a sentence such as the numer ica l agreement between verbs and nouns. Therefore, it does not detect the g r a m m a t i c a l mistakes in a sentence such as " M a r y l ike a dog " . T h i s sentence is accepted as correct according to context-free g r a m m a r . T h i s problem is overcome by the usage of definite clause grammars w h i c h are extensions of context- free g r a m m a r . 4.2. Definite Clause G r a m m a r s ( D C G ) Definite clause grammars were in t roduced in [Pereira ,Warren 80]. Definite clause grammars can be used to define the syntax and the semantics of a language. T h e y have been wide ly used to defined several languages such as P r o l o g and H A S L [Abramson 83]. 29 Definite clause g r a m m a r rules have a nota t ion that is s l ight ly different f r o m context- free grammars i n the fo l lowing w a y : (1) N o n - t e r m i n a l s are al lowed to have arguments . F o r example, sentence(S) , noun_phrase(N) . (2) T h e body of a rule might consist of n o n - t e r m i n a l s , t e rminals , and procedure calls enclosed by { }. Procedure calls are used to express extra condi t ions . F o r example, d e t e r m i n e ^ N , d e t ( W ) ) — > [W] , { i s _ d e t e r m i n e r ( W , N ) } . T h e extra arguments in n o n - t e r m i n a l s can be used for b u i l d i n g the parse tree of a sentence and for descr ibing context dependent in format ion such as the numer ica l agreement (singular or p lura l ) w h i c h is required between nouns and verbs. N o w , let us express the E n g l i s h g r a m m a r using D C G . sentence(s(Np,VP)) — > n o u n _ p h r a s e ( N , N P ) , v e r b _ p k r a s e ( N , V P ) . n o u n _ p h r a s e ( N , n p ( D E T , N o u n , R E L ) ) — > d e t e r m i n e r ( N , D E T ) , n o u n ( N , N o u n ) , r e l _ c l a u s e ( N , R E L ) . noun_phrase(s ingular ,np(Name)) — > name(Name) . v e r b _ p h r a s e ( N , v p ( T V , N P ) ) — > t r a n s _ v e r b ( N , T V ) , n o u n _ p h r a s e ( N l , N P ) . verb_phrase (N,vp( IV) ) — > i n t r a n s _ v e r b ( N , I V ) . re l_c lause(N,re l ( that ,VP) ) — > [that] , v e r b _ p h r a s e ( N , V P ) . 30 rel_clause(N,rel([])) — > 0 • determiner (N,det (W)) — > { i s _ d e t e r m i n e r ( W , N ) } . determiner(plural,det([])) — > [] . n o u n ( N , n ( W ) ) — > [W] , { i s _ n o u n ( W , N ) } . name(name(W)) — > [W] , { i s_name(W) } . t r a n s _ v e r b ( N , t v ( W ) ) — > [W] , { i s _ t r a n s ( W , N ) } . i n t r a n s _ v e r b ( N , i v ( W ) ) — > [W] , { i s _ i n t r a n s ( W , N ) } . i s_determiner(every,s ingular) . is_determiner(a ,s ingular) . i s_determiner(a l l ,p lural ) . i s_noun(man,s ingular ) . i s_noun(woman,s ingular ) . i s_noun(dog,s ingular) . is_name( john) . i s_name(mary) . is_trans(loves,s ingular) . is_trans( l ikes ,s ingular) . i s_intrans( l ives ,s ingular) . A sentence " M a r y likes a dog " is accepted as a g r a m m a t i c a l l y correct sentence but not " J o h n love M a r y " . 31 T h e result of sa t i s fy ing the fo l lowing goal ?— sentence(Tree,[john,likes,a,dog],[]) . produces the parse tree : 5 NP VP name TV NP j o h n l i k e s Det N Rel a dog [ ] Figure 2. T h e parse tree for a sentence " J o h n likes a dog " . T h e parse tree is bu i l t d u r i n g the d e r i v a t i o n of the sentence. T h e parse tree is kept i n one of the arguments of a n o n - t e r m i n a l . A n d the numerica l agreement is also kept in a n argument . O f t e n , it is dif f icult to remember the func t ion of each argument when the argument list becomes rather long. 32 4.3. Definite Clause Translation Grammars (DCTG) T h e definite clause t rans la t ion g r a m m a r , in t roduced by H . A b r a m s o n [Abramson 84], is an improvement to D C G s . T h e syntact ic a n d the semantic actions of the g r a m m a r are separated. T h e semantic actions are appended to a node of a parse tree. These semantic actions are interpreted d u r i n g a t raversal of the parse tree. Def ini te clause t rans la t ion rules are t rans la ted into P r o l o g clauses w i t h three extra arguments . O n e of the arguments represents the parse tree w h i c h is automat i ca l ly generated whi le the rest represent a s t r ing to be parsed as a difference list . T h e notat ions and the examples of definite clause t rans la t ion grammars w i l l be i l lus t ra ted i n the next sect ion. F o r more detai led descr ipt ion o n definite clause t rans la t ion grammars , refer to [Abramson 84]. 4 . 3 . 1 . Notation used by DCTGs T h e n o t a t i o n of a definite clause t rans la t ion g r a m m a r is i n the f o r m : lef tpart ::== r ightpar t < : > semant ic_ac t ion . or lef tpart : : = r ightpar t < : > (semantic_act ion) , (semantic_act ions) . where semantic_action is of the form : a t t r ibute ::- semantic . or semantic . semantic is a P r o l o g t e rm or a con junc t ion cf P r o l o g terms. T h e te rm may be of 33 the f o r m T * * t e r m . T h e leftpart is a n o n - t e r m i n a l whi le the rightpart m a y consist of n o n - t e r m i n a l s , terminals a n d P r o l o g terms that are enclosed by { }. T h e n o n - t e r m i n a l i n the rightpart can be of the f o r m n o n - t e r m i n a l * " N T . NT w i l l be ins tant ia ted to the subtree of the parse tree that corresponds to the sub-der iva t ion of non-terminal. T h e s y m b o l < : > separates the syntact ic and the semantic part of the t rans la t ion rule . Separat ing the syntact ic and the semantic p o r t i o n of the rule improves the readab i l i ty and the ease of modi f i ca t ion of the g r a m m a r rules. E x a m p l e of a D C T G rule . noun_phrase : : = determiner* " D , n o u n " N , rel_clause* * R < : > agree(Num) : : — N * *agree(Num) , D " * a g r e e ( N u m ) , R " * a g r e e ( N u m ) . T h e meaning of the rule is tha t a noun_phrase is defined by a determiner fo l lowed by a noun and a rcl_clause w i t h parse trees D, N, and R respectively, agree is a predicate that checks the numer ica l agreement between the determiner , the noun, and the rel_clause. How is a D C T G rule t rans la ted to a P r o l o g clause ? Suppose we have the fo l lowing rule lef tpart : : = r i g h t l * * R l , r i g h t 2 * * R 2 , { extra_condit ions } < : > ( semant i c_ac t ion l ) , (semantic_act ion2) . the rule is t rans la ted to a P r o l o g clause i n the fo l lowing s tructure 34 lef tpart(node( !p, [Rl ,R2] , [ (semantic_act ionl) , (semantic_act ion2)] ) , SO,S) :— r i g h t l ( R l , S O , S l ) , r i g h t 2 ( R 2 , S l , S ) , extra condit ions . P r o l o g terms such as ex t ra condit ions are not t rans la ted . A functor node represents a node of a parse tree. N o w , let us use the D C T G to describe our E n g l i s h g r a m m a r f r o m previous section. sentence : : = noun_phrase A * N , v e r b _ p h r a s e ' " V , { agree(N,V) }. noun_phrase : : = determiner* " D , n o u n * * N , re l_clause" A R < : > agree(Num) : : — N * A agree(Num) , D " "agree(Num) , R " ' a g r e e ( N u m ) . noun_phrase : : = n a m e A A N < : > agree(singular) . verb_phrase : : — v e r b " " V , n o u n _ p h r a s e " " N < : > agree(Num) : : — V " ' a g r e e ( N u m ) , N " a g r e e ( N u m l ) . verb_phrase : : = verb" A V < : > agree(Num) : : — V A agree(Num) . rel_clause : : = [that] , v e r b _ p h r a s e " " V < : > agree(Num) : : — V " A agree(Num) . rel_clause : : = [] < : > agree(Num) . 35 determiner : : = [every] < : > agree(singular) . determiner : : = [a] < : > agree(singular) . determiner : : = [all] < : > agree(plural) . n o u n : : = [man] < : > agree(singular) . n o u n : : = [woman] agree(singular) . n o u n : : = [dog] < : > agree(singular) . verb : : = [loves] < : > agree(singular) . verb : : = [likes] < : > agree(singular) . verb : : = [lives] < : > agree(singular) . name : : = [John] < : > agree(singular) . name : : = [mary] < : > agree(singular) . agree(N,V) : — N " ' agree (Num) , V " *agree(Num) . 36 F r o m the example above, we can te l l t h a t the w a y the D C T G describes the g r a m m a r for a language is clearer t h a n the D C G does. T h e syntact ic and the semantic parts of a g r a m m a r are separated by < : > . Therefore, i t is easy to separately m o d i f y the syntax or sematics of a g r a m m a r . T h e D C T G has been chosen to describe the g r a m m a r of a language in P r o G r a m m a r . 37 Chapter 5 The ProGrammar system T h e expert system shell for processing g r a m m a r ( P r o G r a m m a r ) is w r i t t e n i n P r o l o g . P r o G r a m m a r is b u i l t o n top of the C P r o l o g / U N E X * system r u n n i n g o n a V A X * 11/750. It provides facil i t ies for pars ing sentences according to grammars and developing grammars of p r o g r a m m i n g languages. It is assumed that readers are fami l ia r w i t h P r o l o g and definite clause t rans la t ion grammars in t roduced by H . A b r a m s o n [Abramson 80], w h i c h is used to describe the g r a m m a r of a language. B r o a d l y speaking, P r o G r a m m a r consists of t w o m a i n parts . • T h e Query_ the_user fac i l i ty is an extension of the P r o l o g interpreter and is able to interact w i t h the user. It elicits i n f o r m a t i o n f rom the user and stores it into the user's database. • T h e explanat ion fac i l i ty provides some i n f o r m a t i o n that is requested by the user d u r i n g or after the in terac t ion . I w i l l describe these t w o m a i n parts of P r o G r a m m a r in the next sections. A l i s t ing of P r o G r a m m a r can be f o u n d i n the appendix A . T h e terms " k n o w l e d g e base" a n d " d a t a b a s e " w i l l be used interchangeably throughout this chapter . *UNIX is a trademark of A T & T Bell Laboratories. 38 5.1. The Query_the_user facility A P r o l o g program is a col lect ion of clauses. There are two types of clauses. T h e s impler clauses are assertions. F o r example, Parent_of ( john ,b i l l ) . and the more general type of clauses are impl ica t ions of w h i c h an example is : u n c l e _ o f ( X , Y ) : -male(X) , parent_of (Z ,Y) , s i b l i n g _ o f ( Z , X ) . T h e example above expresses the rule that for every X and Y , X is the uncle of Y if X is a male , Z is the parent of Y , and Z is the s ib l ing of X . Q u e r y _ t h e _ u s e r is able to extract i n f o r m a t i o n f rom the user as it needs i t . It regards the user as an extension to the database. A l l i n f o r m a t i o n given by the user is stored i n the user's database. T h e ab i l i ty to extract in format ion f r o m the user is very h a n d y for b u i l d i n g the knowledge base of an expert system. Q u e r y _ t h e _ u s e r provides three basic forms in w h i c h questions can be phrased. T h e simplest form is a request for conf i rmat ion of some fact l ike : Is it true that john parent_of jill ? T h e answer to the quest ion is either " y e s " or " n o " . If the user's answer is " y e s " then an assertion parent_of( john, j i l l ) is added to the user's database; otherwise if the 39 answer were " n o " then denied(parent_of( john, j i l l ) ) is added to the database. A quest ion of the more general form could be : give all X where John parent_of X answer is : J i l l . answer is : s a m . answer is : n o _ m o r e . (no more answers) W h e n Q u e r y _ t h e _ u s e r has obta ined the answers, the assertions parent_of( john, j i l l ) and parent_of( john,sam) are added to the user's database. A n o t h e r type of a question w o u l d be : define rules for sibling_of answer is s i b l i n g _ o f ( X , Y ) : - p a r e n t _ o f ( Z , X ) , p a r e n t _ o f ( Z , Y ) . answer is : n o _ m o r e . T h e syntax of rules is : rulehead :- list of conditions. (1) o r rulehead ::= list of conditions (2) semantic actions. 40 A rule of type (2) is t rans la ted into a form l ike : rulehead(node(rulehead,[subtreesJj [semantic actions]), source_string , Rest_string) :• list of conditions . before i t is added to the database. O n the other h a n d , a rule of type (1) can be added to the database w i t h o u t any t r a n s f o r m a t i o n . Q u e r y _ t h e _ u s e r asks conf i rmat ion f rom the user before it adds a new rule given by the user d u r i n g the interac t ion into his database. T h u s , the user s t i l l has a chance to change the rule that he entered earlier if he wishes. F o r the user's convenience, each question that is posed by P r o G r a m m a r is accompanied by a l i t t le guide that gives an ins t ruc t ion how the question can be answered. F o r instance, Is it true that John parent_of jill Please enter yes no list —> list to user db. modify —> to modify user db. why —> for some explanation, or help —> to get some help. answer is : T h e explanat ion of Q u e r y _ t h e _ u s e r and its skeleton w i l l be presented in the next section. 41 5.1.1. The skeleton of Query_the_user interpreter T h e top level of the Q u e r y _ t h e _ u s e r interpreter looks l ike : so lvable(Query,Resul t ) : -bu i l t - in (Query ,Resu l t ) . solvable(Query, true) : -assertion(Query) . so lvable(Query,Resul t ) : -c lause (Query ,NewQuery) , so lvab!e (NewQuery ,Resul t ) , so lvable(Query,Resul t ) : -ask_user(Query) , so lvable(Query,Resul t ) . solvable(Query,false) . ask_user(Query) : -N O T a lready_asked(Query) , askable(Query) , pose_the_quest ion(Query) , read( A n s w e r ) , process_the_answer( A n s w e r ) , assert(already_asked(Query)) . T h e procedure solvable is for processing the user's query. T h e query can be solved by 42 using i n f o r m a t i o n i n the system database or using P r o l o g ' s b u i l t _ i n predicates. In a d d i t i o n , the system m a y also make use of the extra i n f o r m a t i o n obta ined f r o m the user d u r i n g the process of so lv ing the query. E x t r a i n f o r m a t i o n is based on relations that the user suppl ied at the beginning of the session. These relations are kept under the predicate askable. T h e procedure ask_user is the m a i n part of the Q u e r y _ t h e _ u s e r interpreter . Its task is to ask the user for some par t i cu lar i n f o r m a t i o n it needs and to convert the user's answer (if necessary) into an appropriate f o r m that can be used by the system. Before ask_user asks the user any question it has to check if the question is askable and has not been asked previous ly . T h i s el iminates the poss ibi l i ty of get t ing inconsistent answers such as in the fo l lowing s i tua t ion : Is it true that John parent_of jill answer is : yes. Is it true that John parent_of jill answer is : no. T o prevent the occurrences of such cases, ask_user remembers al l questions that have been asked and does not ask them again. N o t o n l y is it dangerous to ask the same question again for fear of inconsistent answers but it is also inconvenient a n d f rus t ra t ing for the user to answer the same question over and over again. A l l questions that have been asked are m a r k e d as 43 already_asked assertions. W h e n ask_user has completed asking the user for extra i n f o r m a t i o n , the system w i l l cont inue processing the user's query. T h e query is not solvable if the user is unable to give any ext ra i n f o r m a t i o n that the system needs. D u r i n g the in terac t ion between the user and the system, the user can ask for an explanat ion of w h y extra i n f o r m a t i o n is needed. T h e user can type " w h y " instead of answering the question that has been posed by the system. It w i l l then give an explanat ion to the user. 5.2. The explanation facility It is i m p o r t a n t to be able to provide an explanat ion to the user. T h e user needs to be convinced that the result produced b y P r o G r a m m a r is reasonable. So, P r o G r a m m a r should be able to give an explanat ion of how it solved the query. O f t e n , P r o G r a m m a r produces its answer by extract ing some i n f o r m a t i o n f rom the user. So, it is reasonable for the user to be able to ask w h y ext ra i n f o r m a t i o n is being requested. Sometimes, the user wants to know w h y the goal has fai led. T h e explanat ion fac i l i ty is also useful for debugging the knowledge base in the early stages of its cons t ruc t ion . B y fo l lowing the explanat ion step by step, a user or knowledge base designer w i l l be able to spot where the inference went w r o n g when checking results w h i c h differed f rom what he expected. Therefore, gaps or mistakes i n the knowledge base can be easily spot ted. In order to be able to give an explanat ion , the system has to record the p a t h that is used to solve the query. T h e p a t h is represented in this form : path(H_clause ,B_c !ause ,Level ,Parent ,S ib l ing) . 44 T o i l lus tra te , let us t r y the fo l lowing example. Suppose our database consists of : parent_of( f rank, john) . parent_of ( f rank,b i l l ) . parent_of( john,sam). male( john). male(sam). male(bi l l ) . u n c ! e _ o f ( X , Y ) : -male(X) , parent_of (Z ,Y) , s i b l i n g _ o f ( Z , X ) . s i b l i n g _ o f ( X , Y ) : -parent_of (Z ,X) , p a r e n t _ o f ( Z , Y ) . D u r i n g the d e r i v a t i o n of the goal , ?- uncle_of(bi l l ,sam). the f o l l o w i n g p a t h is recorded. path(uncle_of(bi l l , sam), (male(bi l l ) ,parent_of(Z,sam),s ibl ing_of(Z,bi l l ) ) , 0 , n i l , l ) . 45 path(male (b i l l ) , t rue , l ,unc le_of (b i l l , sam) , l ) . path(parent_of( john,sam), true , l ,uncle_of(bi l l , sam),2) . path(s ib l ing_of ( john,bi l l ) , (parent_of (X, john) ,parent_of (X,b i l l ) ) , 1 ,uncle_of(bill,sam),3). path(parcnt_of ( f rank, john) , t rue ,2 , s ib l ing_of ( john,b i l l ) , l ) . path(parent_of( frank,bi l l ) , t rue ,2 ,s ib l ing_of( john,bi l l ) ,2 ) . T h e procedure record_path has the task of recording the most recent p a t h that was used by the system. r e c o r d _ p a t h ( H e a d , B o d y , L e v e l , P a r e n t , S i b ) : -r e m o v e _ i r r _ p a t h ( H e a d , B o d y , L e v e l , P a r e n t , S i b ) , record(path(Head,Body,Leve l ,Parent ,S ib ) ) . T h e procedure remove_irr_path is for r e m o v i n g a p a t h that becomes irrelevant w h e n b a c k t r a c k i n g occurs. T h e p a t h is sa id to be irrelevant if a p a t h does not lead to the result of the query. T h e explain procedure is for t rac ing the p a t h and g iv ing the explanat ion to the user. explain(explanat ion_type) : -t race (pa th(H,B ,L ,P ,S ) ) , pose_the_explanat ion(H,B) , w r i t e f Do y o u w a n t fur ther explanat ion ?') , read(Answer) , more_explanat ion(Answer ,explanat ion_type) . 46 There are three types of explanations that can be asked • how gives an explanat ion of how the so lut ion was der ived . T h e user has choices about how t h o r o u g h l y the explanat ion should be given. • w h y gives an explanat ion of w h y the user is being asked for extra i n f o r m a t i o n . • w h y _ f a i l gives an explanat ion of w h y the goal has fa i led . T h i s explanat ion is s i m p l y a trace of the most recent p a t h that was used w h e n P r o G r a m m a r processed the query . 47 Chapter 6 Conclusions P r o l o g is a language w i t h s imple syntax and semantics. Its s i m p l i c i t y a n d m o d u l a r i t y make i t possible to achieve fast i m p l e m e n t a t i o n . F o r these reasons, P r o l o g was chosen for i m p l e m e n t i n g P r o G r a m m a r . It is a suitable language for i m p l e m e n t i n g ques t ion-answer ing systems t h a t require the deduct ion mechanism of P r o l o g and is also suitable for w r i t i n g interpreters . P r o G r a m m a r has been successfully implemented . D u r i n g its development , P r o G r a m m a r was tested for pars ing E n g l i s h sentences and cons t ruc t ing a s imple E n g l i s h g r a m m a r f r o m no p r o d u c t i o n rules u n t i l a complete g r a m m a r i3 accomplished. T h e test results have been very sat is fying. P r o G r a m m a r offers the various features i n c l u d i n g : • It is able to request ex t ra i n f o r m a t i o n that it needs whi le processing the user's query. Therefore , the user is not obliged to provide al l i n f o r m a t i o n that w i l l be required to solve his query in advance. • E a c h question posed b y P r o G r a m m a r is accompanied by a guide that gives ins truct ions on how the quest ion can be answered. T h i s makes the system more u s e r - f r i e n d l y . 48 • T h e explanat ion fac i l i ty gives reasons to the user of how the so lut ion to the query was der ived , w h y the user is being requested p a r t i c u l a r i n f o r m a t i o n , or w h y the query has fa i led . T h i s explanat ion can be given d u r i n g or after P r o G r a m m a r has processed the query. • T h e user is a l lowed to m o d i f y his o w n database at the beginning of each session or d u r i n g the quest ion-answering per iod . T h e contents of the user's database can be d isp layed u p o n request. A l t h o u g h P r o G r a m m a r has been designed for processing a n d developing grammars , i t can also be used for other applicat ions such as as an interact ive P r o l o g interpreter , a learning t o o l , and a knowledge bases constructor . T h e present i m p l e m e n t a t i o n of P r o G r a m m a r has some l imi ta t ions as f o l l o w i n g • T h e three basic forms in w h i c h questions can be phrased by P r o G r a m m a r are rather general . It w o u l d be desirable to have al ternat ive forms of questions w h i c h are customized according to the appl ica t ion of the system. • T h e why_fail explanat ion is not at its best yet . T h e Why_fail explanat ion is a trace of the most recent p a t h that was used by the system d u r i n g the eva luat ion of the query. Sometimes, the trace may not tell the user what the real cause of the fai lure is because the real cause of the fai lure m a y not appear i n the most recent p a t h . A n d it m a y be recorded in a p a t h that becomes irrelevant when b a c k t r a c k i n g occura and this p a t h is removed by the procedure 49 remove_irrjpath. Hence, the system cannot give an explanat ion to the user on w h a t the real cause of the fai lure is . In order to overcome this p r o b l e m , the irrelevant p a t h is removed only if b a c k t r a c k i n g is able to satisfy the subgoal that caused the fa i lure . 50 R e f e r e n c e s [Abramson 83] H. Abramson, " A Prological definition of HASL a purely functional language with unification based conditional binding expressions", Proceeding logic programming workshop '88, Praia da Falesia, Algarve, Portugal, 26 June-1 July 1983. [Abramson 84] H. Abramson, "Definite Clause Translation Grammars", Dept. of Comp. Sc. Technical Report 84-8, University of British Columbia, April 1984. [Buchanon.Feigenbaum 78] B.G. Buchanon, E.A. Feigenbaum, "DENDRAL and Meta-DENDRAL", Journal of Artificial Intelligence, vol. 11, pp. 5-24, 1978. [Clark 78] K.L. Clark, "Negation as failure", Logic and Data bases, H. Gallaire and J. Minker (eds.), Plenum Press, New York , !978. [Clark,McCabe 82] K.L. Clark, F .G. McCabe, "Prolog : A language for implementing expert systems", Machine Intelligence, vol. 10, pp. 445-470, Ellis Horwood, 1982. [Clocksin,Mellish 81] W.F. Clocksin, C.S. Mellish, "Programming in Prolog", Springer-Verlag, New York, 1981. [Hammond 82a] P. Hammond, "APES : A detail description", Dept. of Computing Research Report 82/10, Imperial College, London, 1982. [Hammond 82b] P. Hammond, "APES : A user manual", Dept. of Computing Rerearch Report 82/9, Imperial College, London, 1982. [Kowalski 79] R. Kowalski, "Logic for problem solving", North-Holland, Amsterdam, 1979. [Pereira 79] L. Pereira, "user's guide to DEC-system 10 Prolog", Edinburg, Dept. Of Artificial Intelligence, Edinburg University, 1979. [Pereira,Warren 80] F.C.N. Pereira, D.H.D. Warren, "Definite Clause Grammars for language analysis", Artificial Intelligence, vol. 13, pp. 231-278, 1980. [Reiter 77] R. Reiter, "On Closed World Assumption databases", Logic and Data bases, H. Gallaire and J. Minker (eds.), Plenum Press, New York, 1978 51 [Robinson 65] J.A. Robinson, " A machine-oriented logic based on the resolution principle", JACM vol. 12, PP. 23-41, 1965. [Sergot 83] M. Sergot, " A Query_the_user facility for logic programming", Integrated Interactive Computer Systems, P. Degano and E. Sandwell (eds.), North-Holland , 1983. [Shepherdson 84] J.C. Shepherdson, "Negation As Failure : A comparison of Clark's completed database and Reiter's Closed World Assumption", The Journal of Logic Programming, Vol. 1, PP. 51-79, June 1984. [Shortliffe 76] E.H. Shortliffe, "Computer based medical consultations : MYCIN", New York America Elsevier, 1976. [Warren 77] D.H.D. Warren, "Logic programming and compiler writing", Dept. of Artificial Intelligence Research Report 44> Edinburgh University, Sept 1977. appendix A A listing of the ProGrammar system T H E Q U E R Y _ T H E _ U S E R I N T E R P R E T E R M O D U L E / * QUERY TRANSLATOR * / parse(X) :-clause(X,_) , ! , p_query(X) . parse(X,Source,Tree) :-append([Source],[[]],L) , X=..X1 , append(['EOA',Tree],L,Ll) , retractall(about(Z)) , append(Xl,Ll,L2) , Pred=..L2 , ! , p_query(Pred) , pretty(Tree) . / * T H E INTERPRETER * / p_query(X) :-flush , modified_user_db , remove_args(X,Xl) , find_var(Y,0,Xl,_,_) , calll(X,nil,0,l) , record_path(X,resuIt,x,nil,_) , solution(Xl,Y) . p_query(_) :-path(X,_,0,_,_) , nl , nl , write(' No , cannot confirm ') , write_term(X) , nl , write('Please enter stop , why or help ') , nl , read(A) , assert(par(nil,0)) , reply(A,0,1) , ! , fail . / * PROCESS T H E QUERY * / calll((Gl;G2),Parent,L,S) :- ! , calll(Gl,Parent,L,S) , check_the_cut(Parent,L) ; SI is S + 1 , calll(G2,Parent,L,Sl) . calll((Gl,G2),Parent,L,3) :- ! , calll(Gl,Parent,L,S) , check_the_cut(Parent,L) , SI is S + 1 , calll(G2,Parent,L,Sl) . calll(GOAL,Parent,L,S) :-systems(GOAL) , check_the_cut(Parent,L) , GOAL , modified(GOAL,Parent,L,S) , ! . calll((T"SEM),Parent,L,S) :- ! , call_sem(T,SEM,Parent,L,S) . / * Handling C U T * / calll(!,Parent,L,S) :-modified(!,Parent,L,S) . calll(!,Parent,L,_) :-functor(Parent,P,_) , assert(cut(P,L)) , ! , fail . calll(GOAL,Parent,L,S) :-LI is L + 1 , check_askable(GOAL,Ask) , ask(GOAL,Ask,Parent,L) , ' clause(GOAL,G) , check_the_cut(Parent,L) , check_the_cut(GOAL,Ll) , retrieve(Parent,Ll) , record_path(GOAL,G,L.Parent,S) , retrieve(GOAL,Ll) , calll(G,GOAL,Ll,l) . / * Processing the semantic part of a grammar call_sem(node(H,Sem_list,Actions),Goal,Parent,L,S) :-functor(H,Head,_) , find_action(Actions,Goal,Parent,L,S,node(Head)) . / * Process the semantic action */ find_action([],Goal,_,_,_,_) :- ! , fail . find_action([(Goal::-Body)|Rest],Goal,Parent,L,S,Node) :-clean_up(Body,Zl) , record_path(Node~*Goal,Zl,L,Parent,S) , LI is L + 1 , calll(Body,Node"Goal,Ll,l) . find_action([Goal|Rest],Goal,Parent,L,S,Node) :-record_path(Node"'Goal,true,L,Parent,S) . find_action([X|Rest],Goal,Parent,L,S,Node) :-find_action(Rest,Goal,Parent,L,S,Node) . / * Remove arguments in the semantic action clean_up(((X"Y),Rest),(Xl"Y,Restl)) :- ! , take_node_out(X,Xl) , clean_up(Rest,Restl) . clean_up((Y,Rest),(Y,Restl)) :- ! , clean_up(Rest,Restl) . 54 cIean_up((X-AY),(Xr*Y)) :- ! , take_node_out(X,Xl) . clean_up(Y,Y) . /* check if information is askable */ check_askable(_,trus) :-askable(all) , ! . check_askable(Pred,true) :-functor(Pred,F,J , askable(F) , ! . check_askable(_,false). A S K _ U S E R M O D U L E /* ask information from the user and enter to the user's database */ ask(_,true,_,_) . ask(Pred,true,Parent,L) :-remove_args(Pred,P) , ! , repeatagain(P,Parent,L) , query_the_user(Pred,Parent,L) . ask(_,false,_,_) . /* What type of question should be posed ? */ query_the_uscr(QUERY,Parent,L) :-remove_args(QUERY,Q) , find_var(X,0,Q,Var,P) , question_type(X,qt(Q,Var,P)) , assert(asked(qt(Q,Var,P))) , ! , ask_user(Parent,L) . question_type(X,qt(Q,_,_)) :-var(X) , ! , is_it_rule(Q) . question_type(true,qt(Q,V,l)) > ! , assert(question('Give all X where \qt(Q,V,l))) . question_type(true,qt(Q,V,P)) :-PI is P - 1 , assert(question('Give all X where \qt(Q,V,Pl))) . is_it_r-.:le(Q) :-55 functor(Q,Q,0) , ! , assert(question('Define \qt(Q,_,0))j . is_it_rule(Q) :-assert(question('Is it true that ',qt(Q,_,l))) • /* pose the question to the user */ ask_user(Parent,L) :-question(QT,QUERY) , print_q(QUERY,QT) , ! , get_the_answer(QT,Parent,L) , retractall(question(_,_)) . print_q(qt(QUERY,'X',P),QT) :-nl , write(QT) , print_a(0,QUERY,P) , functor(QUERY,Pred,N) , write(Pred) , write(' ') , print_a(P,QUERY,N) , nl , ! , write_menu(QT,QUERY) . print_a(N,QUERY,N) . print_a(N,QUERY,P) :-Nl is N + 1 , arg(Nl,QUERY,Arg) , write(Arg) , write(' ') , print_a(Nl,QUERY,P) . write_menu('Define ',QUERY) :- ! , write('Please enter <rule> —> rule for ') , functor(QUERY,Q,_) , write(Q) , nl , write(' why —> for explanation.') , nl , write(' list —> list user db..') , nl , write(' modify —> modify the user"s database.') , nl , write(' help —> get some help. ') , nl , write(' or no_more —> no more information to be given.') , nl . write_menu('Is it true that ',QUERY) :- ! , write('Please enter yes ' ) , nl , write(' no ') , nl , write(' list --> list user db.') , nl , write(' modify —> modify the user"s database.') , nl , write(' help —> get some help. ') , nl , write(' or why —> for explanation.') , nl . write_menu('Give all X where ',QUERY) :-writef <X> --> replace X by anything. ') , nl , write(' <rule> —> rule for ') , functor(QUERY,Q,_) , write(Q) , nl , write(' why —> for explanation. ') , nl , write(' list --> list user db.') , nl , write(' modify —> modify the user"s database.') , nl , write(' help —> get some help. ') , nl , write(' or no_more —> no more information to be given.') get_the_answer('Define ',Parent,L) :-write(' The rule is : ') , read(Answer) , answer_is(Answer,_,Parent,L,'Define ') . get_the_answer('Is it true that ',Parent,L) :-write(' Answer is : ') , question(_,qt(QUERY,_,J) , read(Ans) , answer_is(Ans,QUERY,Parent,L,'Is it true that ') . get_the_answer(_,Parent,L) :-question(_,qt(QUERY,Ans,J) , write('Answer is : ') , read(Ans) , answer_is(Ans,QUERY,Parent,L,'Give all X where ') . /* Process the user's answer */ answer_is((X ::== Y <:> Z),^Parent,L,QT) :- ! , confirm_with_user(X,Y,'<:>',Z,Parent,L) , get_the_answer(QT,Parent,L) . answer_is((X ::= Yj.^Parent^QT) :- ! , confirm_with_user(X,Y,' ',' '.Parent,L) , get_the_answer(QT,Parent,L) . answer_is((X>Y),Q,Parent,L,QT) :- ! , . confirm_with_user(X,Y,reg,_,Parent,L) , get_the_answer(QT,Parent,L) . answer_is(no_more,_,_,_,_) :- ! . answer_is(no,QUERY,P,L,QT) > ! , nl , assert(denied(QUERY,P,L)) . answer_is(yes,QUERY,P,L,J :- ! , assert(QUERY) , nl , assert(confirm(QUERY)) , assert(user_define(QUERY,true,_,_)) . answer_is(why,_,H,L,_) :-LI is L - 1 , nl , print_the_reason(H,Ll) , ! , ask_user(H,L) . answer_is(list,_,P,L,_) :-list user db , nl , ! , 57 ask_user(P,L) . answer_is(modify,_,P,L,_) :-reset_user_db , nl , ! , ask_user(P,L) . answer_is(help,_,P,L,_) :-system("more q_user") , nl, ! , ask_user(P,L) . answer_is(X,QUERY,P,L,QT) :-not(QUERY) , assert(QUERY) , assert(confirm(QUERY)) , assert(u8er_define(QUERY,true,_,_)) , ! , get_the_answer(QT,P,L) . /* Print the solutions */ solution(X,Y) :-var(Y) , ! , already_answered(X) , nl , write('*** The answer to the query is YES ***') , nl , retractall(par(_,0)) , assert(par(nil,0)) , prompt_user(0,l) . solution(X,true) :-already_answered(X) , nl , nl , write( '*** top proved ') , write(X) , write(' *** ? ') , nl , nl , retractall(par(_,0)) , assert(par(nil,0)) , write('Please enter stop —> no more explanation. ') , nl , write(' abort —> abort the execution. ') , nl , write(' more —> for more answer. ') , nl , write(' help —> get some helps . ') , nl , write(' or how —> for explanation.') , nl , read(Ans) , reply(Ans,0,l) . already_answered(X) :-not(printed(X)) , assert(printed(X)) . /* Confirm with the user */ confirm_with_user(X,Y,Sem,Z,Parent,L) :-nl , write(' Do you want to assert the rule into user db ? (y/n)') , nl , read(A), assert_rule(A,X,Y,Sem,Z,Parent,L) . assert_rule(y,X,Y,reg,_,Parent,L) :- ! , assert((X:-Y)) , assert(user_define(X,Y,reg,_)) . assert_rule(y,X,Y,Sem,Z,Parent,L) :-tell(rules) , write(X) , write('::='), write(Y) , write(Sem) , write(Z) , writef .') , nl , told , [rules] , is_it_terminal(Y,Yl) , assert(user_define(X,Yl,dcg,(Sem,Z))) , ! . assert_rule(n,_,_,_,_,_,_) :- nl , write(' The rule is not asserted. ') , nl . E X P L A N A T I O N M O D U L E prompt_user(L,S) :-nl , write('please enter stop —> no more explanation.') , nl , write(' ok —> go one level up. ') , nl , write(' how — > explanation for succeeded goal only, nl , write(' why —> explanation for failed goal only.'), nl , writef ldb —> list user db. ') , nl , writef lpred —> list user supplied predicate(s).') , nl , writef help —> get some help. ') , nl , writef abort --> abort the execution. ') , nl , read(Ans) , ! , reply(Ans,L,S) . reply (stop,_,_) :- ! . reply(more,_,_) :- ! , retract(confirm(_)) , retract(denied(_,_)) , fail . reply(ldb,L,S) :- ! , list_user_db , prompt_user(L,S) . reply(lpred,L,S) :- ! , list_user_sup_pred , prompt_user(L,S) . reply(abort,_,_) :- ! , abort . reply (ok, 0,_) :- ! . reply(ok,L,_) :- ! , LI is L - l , nl , writef I can show ') , nl , continue(Ll,l) . reply(how,L,l) :- ! , explain(L,l) . reply(how,L,_) :- ! , nl , write('Which condition : ') , read(S) , explain(L,S) . reply(help,L,S) :- ! , system("more u_explanation ") , system("more why_fail ") , nl , prompt_user(L,S) . reply(why,L,S) :- ! , par(P,L) , path(X,Y,L,P,S) , nl , write_term(X) , nl , writef cannot be deduced from any known facts and rules ') , nl , nl , write_term(X) , nl , writef could be deduced from the rule ') , nl , print_out(X,Y) , nl , LI is L + 1 , assert(par(X,Ll)) , so_on(A,Y,Ll) , delete_parent(L) , retract(not_find(Pred)) , more_explanation(A,Pred) . more_explanation(A,Pred) :-var(A) , ! , nl , nl , writef Cannot deduce ') , write_term(Pred) , nl , writef from any known facts and rules in the database '). more_explanation(n,_) . reply(X,L,_) :-integer(X) , ! , explain(L,X) . reply(_,L,S) :- nl , writef*** Unrecognised command ***') , nl , writef*** Try again ***') , nl , prompt_user(L,S) , ! . /* Traverse the tree */ continue(0,_) :- ! , path(X,result,_,_,_) , nl , write_term(X) , nl , prompt_user(0,l) . continue(L,S) :-par(P,L) , path(X,Y,L,P,S) , writef ') , write(S) , writef. ') , write_term(X) , nl , SI is S + 1 , continue(L,Sl) . continue(L,S) :-SI is S - 1 , prompt_user(L,Sl) . explain(L,S) :-60 par(P,L) , path(X,system_caIl,L,P,S) , ! , nl , write(X) , write(' is a SYSTEM CALL. ') , nl , writej'NO further EXPLANATION will be given .') , nl , ni , write(' I can show ') , nl , continue(L.l) . explain(L,S) :-par(P,L) , path(X,true,L,P,S) , ! , explainl(X,L) . explain(L,S) > par(P,L) , path(X,Y,L,P,S) , remove_args(X,Xl) , remove_args(Y,Yl) , user_define(Xl,Yl,_,_) , ! , nl , write('I deduced ') , write_term(X) , write(' from the rule that was DEFINED by USER ') , nl , print_out(X,Y) , LI is L + 1 , retractall(par(_,Ll)) , assert(par(X,Ll)) , nl , write(' I can show ') , nl , continue(Ll,l). explain(L,S) •:-par(P,L) , path(X,Y,L,P,S) , ! , nl , write('I deduced ') , write_term(X) , write(' from the rule ') , nl , print_out(X,Y) , LI is L + 1 , retractall(par(_,Ll)) , assert(par(X,Ll)) , nl , write(' I can show ') , nl , continue(Ll,l). explainl(X,L) :-confirm(X) , ! , nl , write('YOU CONFIRMED ') , write_term(X) , nl , move_up(L) . explainl(X,L) :-nl , write('I deduced ') , write_term(X) , write(' from the DATABASE ') , nl , move_up(L) . D A T A B A S E E D I T O R M O D U L E / * Editor module * / reset_user_db :- nl , write('Do you wish to modify any rule from your db ? ') , nl , write(' Please enter ') , nl , write(' r, <rule> —> remove a rule from db ') , n ! , write(' i, <rule> —> insert a rule to db. ') , nl , write(' no —> if no rules to be removed ') , nl , write(' list —> list out user"s database ') , nl , writef help —> get some help. ') , nl , write(' or all —> if you want the user db to be cleared ') , nl, which_rule , ! . which_rule :-nl , writef The rule : ') , read(Rule) , modified_u_db(Rule) . / * database modifier * / modified_u_db(help) :- ! , system("more user_db ") , nl ,. which_rule . modified_u_db(list) :- ! , list_user_db , which_rule . modified_u_db(no) :- ! . / * Clear up the user's database modified_u_db(all) :-confirm(all,Confirmation) , delete_rule(Confirmation,all,H,T) . modified_u_db(all) :-write(' The user db is empty now . ') , nl . / * Remove a clause from the user's database modified_u_db((r, (X :- Y))) :- ! , confirm((X :- Y),Confirmation) , delete_rule(Confirmation,X,Y) , which_rule . modified_u_db((r,(X Y <:> Z))) :-confirm((X ::= Y <:> Z),Confirmation) , is_it_terminal(Y,Yl) , delete_ruIe(Confirmation,XYl,'<:>',Z) , which_rule modified_u_db((r,(X ::= Y))) :-confirm((X ::= Y),Confirmation) , is_it_terminal(YYl) , delete_rule(Confirmation,XYl) , which_rule . modified_u_db((r,X)) :-confirm(X,Confirmation) , delete_rule(Confirmation,X,true) , which_rule . / * Add a clause to the user's database modified_u_db((i, (X :- Y))) :- ! , confirm_with_user(X,Y,reg,_,_,_) , which rule . modified_u_db((i,(X ::= Y <:> Z))) :- ! , confirm_with_user(X,Y,'<:> ',Z,_,_) , which_rule . modified_u_db((i,(X ::= Y))) :- ! , confirm_with_user(X,Y,' ',' ',_,_) , which_rule . modified_u_db((i,X)) :-assert(X) , assert(user_define(X,true,_,_)) , which_rule . / * Display the user's database * / list_user_db :-nl , write(' User database : ') , nl , user_define(X,Y,Op,Sem) , writef ') , write_the_rule(X,Y,Op,Sem) , fail . list_user_db :- ! , nl . / * Check and mark the clause that to be deleted delete_rule(y,all,H,T) :-retract(user_define(H,T,Op,Sem)) , retract_rule(Op,H,T) , fail . delete_rule(n,_,_,_) :-delete_rule(n,_,_) . delete_rule(y,H,T) :-retract(user_define(H,T,Op,Sem)) , retract_rule(Op,H,T) . delete_rule(y,H,T) :-write(' No such rule in the user db . ') , nl . delete_rule(n,_,_) :-write(' Rule(s) are not removed ') , nl . delete_rule(y,H,T,'<:>',Sem) :-retract(user_define(H,T,Op,('<:>',Sem))) , retract_rule(Op,H,T,Sem) . delete_rule(y,H,T,_,_) :-write(' No such rule in user db . ') , nl . delete_rule(n,_,_,_,_) :-delete_rule(n,_,_) . / * Remove the clause from the system retract_rule(_,H,true) :- ! , retractall(H) . retract_rule(reg,H,T) :-clause(H,T) , ! , retractall(:-(H,T)) . retract_rule(reg,_,_) :- ! , write(' No such rule in the db .') , nl . retract_rule(dcg,H,T) :-HI =.. [H,_node(_,_,[]),_,_] , clause(Hl,Tail) , remove_args(Tail,T) , ! , retractall(:-(Hl,Tail)) . retract_rule(dcg,_,_) :-write(' No such rule in the db . ') , nl . retract_rule(dcg,H,T,(Sem)) :-make_list(Sem,Sem_list) , HI =..[H,_,node(_,_,Sem_list),_,J , clause(Hl,Tail) , remove_args(Tail,T) , ! , retractall(:-(Hl,Tail)) . retract_rule(dcg,_,_,_) :-write(' No such rule in the db . ') , nl . write_the_rule(X,true,_,_) :-! , nl , write_term(X) , nl . write_the_rule(X,Y,reg,_) :-! , nl , write(X) , writef :- ') , write(Y) , nl . write_the_rule(X,Y,dcg,SEM) :-! , nl , write_term(X) , writef ::= ') , write_term(Y) , nl , write_term(SEM) . confirm(X,A) :-nl , writef Do you really want to remove ') , write(X) , writef rule(s) from user db ? (y/n).') , nl , read(A) , nl , make_list((Seml,Sem2),[Seml|List]) :- ! , make_list(Sem2,List) . make_list(Sem,[Sem]) . S Y S T E M P R E D I C A T E S 8 4 systems(true). systems(c(_,_,J) . systems(consult(X)) . systems(reconsult(X)). systems(fail). systems(var(X)). systems(nonvar(X)). systems(integer(X)). systems(atom(X)). systems(atomic(X)). systems(listing(A)). systems(clause(X,Y)). systems(assert(X)). systems(asserta(X)). systems(retract(X)). systems(retractall(X)). systems(functor(T,F,N)). sysfcems(arg(N,T,A))-systems(X =.. L) . systems(name(A,L)) . systems(repeat). systems(call(X)) . systems(not(X)). systems(X=Y). systems(X==Y). systems(X\==Y). systems(geto(X)). systems(get(X)). systems(skip(X)). systems(read(X)). systems(put(X)). systems(nl). systems(tab(X)). systems(write(X)). systems(display(X)). systems(op(XY,Z)). systems(see(X)). systems(seeing(X)). systems(seen). systems(tell(X)). systems(telling(X)). systems(told). systems(X is Y). systems(X -I- Y). systems(X - Y). systems(X * Y). systems(X / Y). systems(X mod Y). systems(X < Y). systems(X > Y). systems(X > = Y). systems(X = < Y). 65 systems(trace). systems(notrace). systems(spy P). systems(debugging). systems(nodebug). systems(nospy). A S K _ U S E R U T I L I T Y retractall(X) :-retract(X) , fail . retractall(_) . repeatagain(Q,Parent,L) :-find_yar(X,0,Q,Var,P) , not already_asked(qt(Q,Var,P)) , assert_asked(qt(Q,Var,P)) , check_the_cut(Parent,L) . repeatagain(Q,Parent,L) :-find_var(X,0,Q,Var,P) , not already_asked(qt(Q,Var,P)) , check_the_cut(Parent,L) , repeatagain(Q,Parent,L) . /* check for the cut */ check_the_cut(_,L) :-cut(_,Ll) , LI < L , ! , fail . check_the_cut(Funct,L) :-functor(Funct,F,_) , not(cut(F,L)) , ! . /* retract all lower level cut(_,_) */ retrieve(GOAL,X) :-cut(_,Xl) , XI > X , retract(cut(_,Xl)) , fail . retrieve(GOAL,X) :-functor(GOAL,G,_) , retractall(cut(G,X)) , ! . already_asked(X) :-asked(X), ! . assert_asked(X) :-assert(asked(X)) , ! . /* Are there any variable in the query find_var(X,N,Q,V,P) :-Nl is N + 1 , var(X) , arg(Nl,Q,Arg) , ! , check_arg(XArg,q(Q,V,P)) , find_var(X,Nl)Q,V,P) . find.var^P.Q.V,?) :-var(X) , ! . find_var(true,P,Q,V,P) :- ! . checkJist(X,[],q(Q,V,P)) > var(X) , ! . checkJist(X,[H|T],q(Q,V,P)) :-var(X) , ! , check_arg(X,H,q(Q,V,P)) , checkJist(X,T,q(Q,V,P)) . check_list(true,_,q(Q,V,P)) . /* Simple argument check_arg(XArg,q(Q,V,P)) :-functor(Arg,Arg,0) , ! , is_it_var(X,Arg,q(Q,V,P)) . /* The argument is a list check_arg(X,Arg,q(Q,V,P)) :-functor(Arg,.,_) , ! , checkJist(X,Arg,q(Q,V,P)) . /* The argument is a function check_arg(X,Arg,q(Q,V,P)) :-get_arg(X,Arg,l,q(Q,V,P)) . /* Is it a variable */ is_it_var(true,V,q(Q,V,P)) :-var(V) , ! . is_it_var(_J_,q(Q,V,P)) . /* get an argument from a function get_arg(X,F)N,q(Q>V,P)) :-var(X) , arg(N,F,Arg) , ! , check_arg(X,Arg)q(Q,V,P)) , N l is N + 1 , get_arg(X,F,Nl,q(Q,V,P)) . / * no more arg in the function * / get_arg(X ,q(Q,V,P)) > var(X) , ! . / * a variable is found * / get_arg(true,_,_,q(Q,V,P)) . E X P L A N A T I O N U T I L I T Y modified(c(_,X,_),Parent,L,S) :-! , LI is L - 1 , retract(path(Parent,_,Ll,Y,Z)) , assert(path(Parent,c(_,X,_),Ll,Y,Z)) , record_path(c(_,X,_),true,L,Parent,S) . modified(G,P,L,S) :-record_path(G,system_caII,L,P,S) . record_path(H,T,Level,P,S) :-remove_path(H,T,Level,P,S) , assert(path(H,T,Level,P,S)) , ! . / * remove arguments in the grammar rules remove_args((Taill,Tail2),(Tl,T2)) > ! , remove_args(Taill,Tl) , rcmove_args(Tail2,T2) . remove_args((Taill;Tail2),(Tl;T2)) :- ! , remove_args(Taill,Tl) , remove_args(Tail2,T2) . remove_args((T"Sem),(Tr*Seml)) :- ! , take_node_out(T,Tl) , remove_irr_args(Sem,Seml) . remove_args(Tail,T) :-remove_irr_args(Tail,T) . remove_irr_args(Fl,F2) :-FI =.. [H|T] , remove(T,NT) , F2 =..[H|NT] . remove([],[]) :- ! . remove([H|T],[]) :-not var(H) , H = 'EOA' , ! . remove([H|T],[]) :-not var(H) , H = node(_,_,_) , ! . remove([H|T],[H|Tl]) :- remove(T,Tl) . /* Remove the irrelevant path remove_path(Head,_,Level,Parent,S) :-path(Hl,_,Level,Pl,S) , uninstantiate_arg(Head,H) , uninstantiate_arg(Hl,H) , uninstantiate_arg(Parent,P) , uninstantiate_arg(Pl,P) , retract(path(Hl,_,Level,Pl,S)) , fail . remove_path(_,Tail,Level,Parent,S) :-path(_,Tl,Level,Pl,S) , uninstantiate_arg(Tail,T) , uninstantiate_arg(Tl,T) , uninstantiate_arg(Parent,P) , uninstantiate_arg(Pl,P) , retract(path(_,Tl,Level,Pl,S)) , fail . remove_path(_,_,_,_,_) . uninstantiate_arg((Argl,Arg2),(Al,A2)) uninstantiate_arg(ArglAl) , uninstantiate_arg(Arg2,A2) . uninstantiate_arg((Argl;Arg2),(Al;A2)) uninstantiate_arg(Argl,Al) , uninstantiate_arg(Arg2,A2) . uninstantiate_arg((N" "Sem),(Nl * "Semi take_node_out(N,Nl) , Sem =..[Pred|Args] , uninstantiate(Args,Argsl) , Semi =..[Pred|Argsl] . uninstantiate_arg(Sem,Seml) :-Sem =..[Pred|Args] , uninstantiate(ArgsArSsl) , Semi =..[Pred|Argsl] . uninstantiate([],[]) . uninstantiate([H|T],[_|Tl]) :-uninstantiate(T,Tl) . /* Print the reasoning of why ask print_the_reason(H,0) :-path(H,T,0,nil,_) , ! , print_out(H,T) , nl , nl , write_term(H) , nl , writefwhich is what you originally asked about .') , nl . print_the_reason(H,L) :-path(H,T,L,P,S) , T == true , nl , ! , print_out(H,T) , LI is L - 1 , write_q(Ans) , more_reason(Ans,P,Ll) . print_the_reason(H,_) :- nl , writef No explanation at top level ') , nl . more_reason(y,H,L) :-print_the_reason(H,L) . more_reason(n,_,_) . /* Travel down the tree */ so_on(A,(Hl,H2),L) :-var(A) , ! , move_down(A,Hl,L) , delete_parent(L) , so_on(A,H2,L) . so_on(A,H,L) :-var(A) , ! , move_down(A,H,L) . so_on(n,_,_) . move_down(A,H,L) :-par(P,L) , path(H,true,L,P,S) , ! , nl , writef FACT : ') , write_term(H) , nl , check_denied(L,P) , retractall(not_find(_)) . move_down(A,H,L) :-par(P,L) , path(H,T,L,P,S) , retractall(not_find(_)) , nl , ! , writef The rule that can be used ') , nl , print_out(H,T) , check_denied(L,P) , nl , nl , LI is L + 1 , assert(par(H,Ll)) , write_q(Ans) , more_explanation(A,Ans,T,Ll) . move_down(A,H,L) :-par(P,L) , check_denied(L,P) , cannot_find(H,L) . move_up(0) :-nl , writef I can show ') , 70 nl , continue(0,_) . move_up(L) :-LI is L - 1 , nl , write(' I can show ') , nl , continue(Ll,l) . write_q(Ans) :- nl , write(' Do you want more explanation ? (y/n) ') , nl , read(Ans) , ! . more_explanation(A,y,H,L) :-so_on(A,H,L) . more_explanation(n,n,_,_) . delete_parent(L) :-par(_,Ll) , LI > L , retract(par(_,Ll)) , fail . delete_parent(_) . / * cannot find the node in the tree cannot_find(X,L) :-path(X,_,L,__) . cannot_find(X,_) :-not(not_find(_)) , ! , assert(not_find(X)) . cannot_find(_,_) . check_denied(L,P) :-denied(X,P,L) , nl , write(' You denied ') , write_term(X) , nl , fail . check_denied(_,_) . / * Print the explanation */ print_out(H,T) :-nl , write(' IF ') , nl , write(' ') , write_term(T) , nl , write(' T H E N ') , nl , write(' ') , write_term(H) , nl , nl . write_term(X) :-remove_args(X,Xl) , write_funcs(Xl) . write_funcs((Xl,X2)) :- ! , write_func(Xl) , nl , 7 1 writef ') , write_funcs(X2) . write_funcs(X) :-write_func(X) . write_func(c(_,X,_)) :-var(X) , ! , writef [ terminal-symbol ] ') . write_func(c(_,X,_)) :- ! , writef [ ') , write(X) , writef ]') . write_furic(X) :-write(X) . A S K A B L E U T I L I T Y /* Mark all relations that the user's knows about. */ /* These relations are kept under the predicate askable. */ what_to_be_asked :- nl , writefDo you have any askable predicate to be declared ? ') , nl, writef Enter <predicate(s)> —> askable predicate(s) to be added.') , nl , writef all —> all predicates are askable.') , nl , writef list —> list all askable predicate(s). ') , nl , writef help —> get some help. ') , nl , writef or no —> no askable predicates to be declared.') , nl , read_ask , ! . what_not_to_ask :- nl , writefDo you want to remove askable predicates ?') , nl , writef Enter <predicate(s)> —> askable predicates to be removed. ') , nl , writef list —> list all askable predicate(s). ') , nl , writef help —> get some help. ') , nl , writef or no —> no askable predicate(s) to be removed.') , nl , read_not_ask , ! . read_ask :-writef The predicate(s) : ') , read(X) , nl , add_askable(X) . read_not_ask :-writef The predicate(s) : ') , read(X) , nl , remove_askable(X) . /* add new askable relations into the database */ 72 add_askable(help) :- ! , system("more askable") , nl , read_ask. add_askable(list) :- ! , list_user_sup_pred , read_ask . add_askable(none) :- ! . add_askable((X,Y)) > ! , retractall(askable(X)) , assert(askable(X)) , add_askable(Y) . add_askable(Y) :-retractall(askable(Y)) , assert(askable(Y)) . / * Remove askable relations from the database * / remove_askable(help) > ! , system("more askable2") , nl , read_not_ask . remove_askable(none) :- ! . remove_askable(list) :- ! , list_user_sup_pred , read_not_ask . remove_askable((X,Y)) :- ! , retractall(askable(X)) , remove_askable(Y) . remove_askable(Y) :-retractall(askable(Y)) . / * Display askable relations * / list_user_sup_pred :-nl , write(' Ask about : ') , nl , askable(X) , write(' ') , write(X) , nl , fail . list_user_sup_pred :- nl , ! . / * Prompt the user if he want to make any changes to his db * / modified_user_db :-nl , write(' Do you want to modify askable predicate or your database ? (y/n) . ') , read(Ans) , which_one(Ans) . which_one(y) :- ! , nl , write(' You can 1. Add new askable predicate(s) . ') , nl , writef 2. Remove askable predicate(s) . ') , nl , write(' 3. Modify your database . ') , nl , write(' or 4. No more changes to be made . ') , nl , write(' Enter a number ') , nl , read(Ans) , menu(Ans) . which_one(n) . menu(l) :- ! , what_to_be_asked , which_one(y) . menu(2) :- ! , what_not_to_ask , which_one(y) . menu(3) :- ! , reset_user_db , which_one(y) . menu(4) :- ! . menu(_) :- nl , write(' Syntax error please reenter again ') , nl , which_one(y) , ! . U T I L I T Y append([],L,L) . append([X|R],L,[X|Rl]) :- append(R,L,Rl) . is_it_terminal((X,Y),(Xl,Yl)) :- ! , is_it_terminal(X,Xl) , is_it_terminal(Y,Yl) . is_it_terminal([X],c(_,X,_)) :- ! . is_it_terminaI(X,X) . take_node_out(X.X) :- var(X) , ! . take_node_out(node(X,_,_),node(Xl)) :- ! , functor(X,Xl,_) . take_node_out(X,X) . /* flush the database */ flush :-retractall(asked(_)) , retractall(cut(_,_)) , retractall(printed(_)) , retractall(path(_,_,_,_,_)) , retractall(par(_,_)) , retractall(confirm(_)) , retractall(denied(_,_,_)) , retractall(question(_,_)) . Appendix B Databases The grammar for simple English. sentence ::= noun_phraseA A N , verb_phraseAAV, !, { agree(N,V) } <:> logic(P) : : -N"logic(X,Pl,P), VA Alogic(X,Pl)-noun_phrase ::= determiner"D, nounA AN, rel_clauseA AR <:> (agree(Num) ::- N A "agree(Num), D A 'agree(Num), RA 'agree(Num)), (logic(X,Pl,P) ::- DA-logic(X,P2,Pl,P), NAAlogic(X,P3), RAAlogic(X,P3,P2)). noun_phrase ::= nameA AN <:> agree(singular), (logic(X,P,P) ::- NAAlogic(X)). verb_phrase ::= verbA AV, { transitive(V) }, noun_phraseA A N <:> (agree(Num) ::- VA'agree(Num), NAAagree(Numl)), (logic(X,P) ::- V" Alogic(transitive,X,Y,Pl), NAAIogic(Y,Pl,P)). verb_phrase ::= verb**V, { intransitive(V) } <:> (agree(Num) ::- V"'agree(Num)), (logic(X,P) ::- V A Alogic(intransitive,X,P)). rel_clause ::= [that], verb_phraseA " V <:> (agree(Num) ::- V A Aagree(Num)), (logic(X,Pl,&(Pl,P2)) ::- V"logic(X,P2)). rel_clause ::= [] <:> agree(Num), logic(X,P,P). determiner ::= [every] agree(singular), logic(X,Pl,P2,al!(X=>(Pl,P2))). determiner ::= [a] < > agree(singular), logic(XIPl,P2,exists(X,&(Pl,P2))). noun ::= [man] < > agree(singular), logic(X,man(X)). noun ::= [woman] <:> agree(singular), logic(X,woman(X)). noun ::= [cat] < > agree(singular), logic(X,cat(X)). name ::= [John] logic(john). name ::= [mary] <:> logic(mary). verb ::= [loves] <:> agree(singular), logic(transitive,X,Y,loves(X,Y)), logic(intransitive,X,loves(X)). verb ::= [lives] <:> agree(singular), logic(intransitive,X,lives(X)). agree(N.V) :-N"'agree(Num), V" "agree(Num). transitive(V) :-V"logic(transitive,_,_,_). intransitive(V) :-V"'logic(intransitive,_,_). 76 sentence(Source) :-sentence('EOA',T,Source,[]) , T"logic(Proposition) , write(Proposition) , nl . 77 Prolog program for searching an ancestor of somebody. parent_of(charles,william). parent_of(elizabeth,charles). parent_of(elizabeth,ann). parent_of(george,elizabeth). ancestor_of(X,Y) :-parent_of(X,Y) . ancestor_of(X,Y) :-parent_of(Z,Y) , ancestor_of(X,Z) . 78 Appendix C Query session with ProGrammar T h e databases t h a t are going to be used i n examples are l is ted i n appendix B . There are two ways to query P r o G r a m m a r : (1) ?- parse( question ). F o r example, ?- parse(father_of( john,mary)) . (2) parse( grammar_to_be_used, [ str_to_be_parsed ], p_tree ). F o r example, ?-parse( sentence,[ john,loves,mary],Tree). E x a m p l e 1. T h e user asks P r o G r a m m a r if John likes M a r y is a sentence. | ? -parse (sentence (\john ,likes ,mary ])). D o y o u want to m o d i f y askable predicates or user" 3 database ? ( y / n ) . y. Y o u can 1. A d d new askable predicate(s) . 2. Remove askable predicate(s) . 3. M o d i f y y o u r database . or 4. N o more changes to be made . E n t e r a n u m b e r |: verb. S y n t a x error please reenter again Y o u can 1. A d d new askable predicate(s) . 2. R e m o v e askable predicate(s) . 3 . M o d i f y y o u r database . or 4. N o more changes to be made . E n t e r a n u m b e r |: 1. D o y o u have any askable predicate to be declared ? E n t e r <pred ica te ( s )> — > askable predicate(s) to be added, al l — > a l l predicates are askable, list - -> list al l askable predicate(s). help - -> get some help, or no — > no askable predicates to be declared. T h e predicate(s) : verb. Y o u can 1. A d d new askable predicate(s) . 2. Remove askable predicate(s) . 3 . M o d i f y y o u r database . or 4. N o more changes to be made . E n t e r a n u m b e r |:4. Define verb Please enter < r u l e > — > rule for verb w h y — > for explanat ion . l ist — > list user d b . m o d i f y - -> m o d i f y the user"s database. help — > get some help, or no_more — > no more i n f o r m a t i o n to be given. T h e rule is : why. IF verb t r a n s i t i v e ( _ 5 3 3 ) noun_phrase T H E N verb_phrase D o y o u w a n t more explanat ion ? ( y / n ) I: y-I F noun_phrase verb_phrase agree T H E N sentence D o y o u w a n t more explanat ion ? ( y / n ) IF sentence _971""logic(_972) write(_972) n l T H E N sentence([john,likes,mary]) sentence([john,likes,mary|) w h i c h is w h a t y o u or ig ina l ly asked about . Define verb Please enter < r u l e > - -> rule for verb w h y — > for explanat ion . l ist — > list user d b . m o d i f y - -> m o d i f y the user" s database. help — > get some help , or no_more ~ > no more i n f o r m a t i o n to be given. T h e rule is : verb -.—[likes] |: < : > |: agree (singular), |: logic (transitive ,X,Y Jikes (X ,Y)). D o y o u w a n t to assert the rule into user db ? ( y / n ) |: ». rules consul ted 172 bytes 0.116671 sec. T h e rule is : list. User database : verb ::== [ likes ] < : > agree(singular) logic(transitive,_1321,_1322,likes(_1321,_1322)) Define verb Please enter < r u l e > — > rule for verb w h y —> for explanat ion . l ist - -> list user d b . m o d i f y -- > m o d i f y the user" s database. help - -> get some help, or no_more - -> no more i n f o r m a t i o n to be g iven. T h e rule is : no_more. l ikes( john,mary) * * * T h e answer to the query is Y E S * * * please enter stop - -> no more explanat ion , ok — > go one level u p . how — > explanat ion for succeeded goal on ly , w h y — > explanat ion for fa i led goal on ly , ldb — > l ist user d b . lpred — > list user suppl ied predicate(s). help - -> get some help, abort — > abort the execution |: how. I deduced sentence([John,likes,mary]) f r o m the rule IF sentence _2560" ' logic(_2561) write(_2561) n l T H E N sentence([john,likes,mary]) I can show 1. sentence 2. node(sentence)" Alogic(_2997) 3. wri te( l ikes( john,mary)) 4. n l please enter stop - -> no more explanat ion , ok — > go one level u p . how — > explanat ion for succeeded goal on ly , w h y — > explanat ion for fai led goal on ly , l d b — > list user d b . lpred - -> list user suppl ied predicate(s). help — > get some help, abort - -> abort the execution. |: 1. I deduced sentence f r o m the rule IF noun_phrase verb_phrase l agree(_3088,_3089) T H E N sentence I can show 1. noun_phrase 2. verb_phrase 3. ! 4. agree please enter stop - -> no more explanat ion , ok — > go one level u p . how — > explanat ion for succeeded goal only , w h y — > explanat ion for fa i led goal only , ldb — > list user d b . lpred - -> list user suppl ied predicate(s). help — > get some help, abort — > abort the execution. I deduced noun_phrase f rom the rule IF name T H E N noun_phrase I can show 1. name please enter stop — > no more explanat ion , ok — > go one level u p . how — > explanat ion for succeeded goal only , w h y --> explanat ion for fa i led goal only , l d b — > list user d b . Ipred ~ > list user suppl ied predicate(s). help — > get some help, abort - -> abort the execution. |: ok. I can show 1. noun_phrase 2. verb_phrase 3. ! 4. agree please enter stop — > no more explanat ion , ok — > go one level u p . how --> explanat ion for succeeded goal o n l y , w h y —> explanat ion for fa i led goal on ly , ldb — > list user d b . Ipred -- > list user suppl ied predicate(s). help - -> get some help, abort — > abort the execution |:2. I deduced verb_phrase f r o m the rule IF verb transit ive(_3805) noun_phrase T H E N verb_phrase I can show 1. verb 2. t rans i t ive 3. noun_phrase please enter stop - -> no more explanat ion , ok - -> go one level u p . how - -> explanat ion for succeeded goal on ly , w h y — > explanat ion for fai led goal on ly , ldb -- > l ist user d b . Ipred — > list user suppl ied predicate(s). help - -> get some help, abort — > abort the execution |: l . I deduced verb f r o m the rule tha t was D E F I N E D by U S E R IF [ likes ] THEN verb I can show 1. [ likes ] please enter stop --> no more explanation, ok — > go one level up. how — > explanation for succeeded goal only, why --> explanation for failed goal only, ldb -- > list user db. lpred — > list user supplied predicate(s). help — > get some help, abort — > abort the execution. |: ok. I can show 1. verb 2. transitive 3. noun_phrase please enter stop --> no more explanation, ok — > go one level up. how — > explanation for succeeded goal only. why — > explanation for failed goal only. ldb — > list user db. lpred --> list user supplied predicate(s). help --> get some help. abort --> abort the execution. •|: 2. I deduced transitive from the rule IF node(verb)"*logic(transitive,_4660,_4661,_4662) THEN transitive I can show 1. node(verb)""logic(transitive,_4806,_4807,likes(_4808,_4807)) please enter stop --> no more explanation, ok — > go one level up. how w h y l d b Ipred help abort |: ok. I can show 1. verb 2. t rans i t ive 3. noun_phrase please enter stop - -> no more explanat ion , ok - -> go one level u p . how — > explanat ion for succeeded goal on ly , w h y — > explanat ion for fa i led goal on ly , ldb - -> l ist user d b . Ipred — > list user suppl ied predicate(s). help --> get some help, abort — > abort the execution. |: ok. I can show 1. noun_phrase 2. verb_phrase 3. ! 4. agree please enter stop - -> no more explanat ion , ok — > go one level u p . how --> explanat ion for succeeded goal only . w h y — > explanat ion for fai led goal only . ldb — > list user d b . ipred — > list user suppl ied predicate(s). help - -> get some help. abort - -> abort the execution |: ok. I can show 1. sentence 2. node(sentence)" *logic(_5415) 3. wri te( l ikes( john,mary)) 4. n l please enter stop - -> no more explanat ion , ok — > go one level u p . — > explanat ion for succeeded goal o n l y . - -> explanat ion for fa i led goal on ly . — > l ist user d b . — > list user suppl ied predicate(s). — > get some help. — > abort the execution. how — > explanat ion for succeeded goal on ly . w h y — > explanat ion for fa i led goal on ly . ldb - -> l ist user d b . Ipred — > list user suppl ied predicate(s). help — > get some help. abort — > abort the execution |:2. I deduced node(sentence)A Alogic(_5506) f r o m the rule IF node(noun_phrase) A Alogic(_5507,_5508,_5506) node(verb_phrase) A Alogic(_5507,_5508) T H E N node(sentence)" Alogic(_5506) I can show 1. node(noun_phrase) A Alogic(_5682,_5679,_5679) 2. node(verb_phrase) A " logic( john,_5739) please enter stop — > no more explanat ion , ok — > go one level u p . how — > explanat ion for succeeded goal only , w h y — > explanat ion for fai led goal only , ldb — > list user d b . Ipred — > list user suppl ied predicate(s). help — > get some help, abort — > abort the execution |:2. I deduced node(verb_phrase) A ' logic( john,_5797) f rom the rule IF node(verb) A A logic(transitive, john,_5801,_5802) node(noun_phrase) A Alogic(_5801,_5802,_5797) T H E N node(verb_phrase) A A logic( john,_5797) I can show 1. node(verb) A A logic(transit ive, john,_6012,l ikes( john,_6012)) 2. node(noun_phrase) A A Iogic(_6081,l ikes( john,_6081), l ikes( john,_6081)) please enter stop — > no more explanat ion , ok — > go one level u p . how — > explanat ion for succeeded goal only . w h y — > explanat ion for fa i led goal on ly . ldb — > l ist user d b . Ipred -- > list user suppl ied predicate(s). help - -> get some help. abort — > abort the execution |: ok. I can show 1. node(noun_phrase)* *Iogic(_6152,_6149,_6149) 2. node(verb_phrase)* "logic( john,_6209) please enter stop — > no more explanat ion , ok - -> go one level u p . how — > explanat ion for succeeded goal only , w h y --> explanat ion for fa i led goal only , l d b — > l ist user d b . Ipred — > list user suppl ied predicate(s). help — > get some help, abort - -> abort the execution |: stop. yes T h e answer to the query sentence([john,likes,mary]) is " y e s " . E x a m p l e 2. T h e user queries P roGrammar if Jane is an ancestor of Char les . | ? -parse (ancestor_of (jane ,charles)). D o y o u w a n t to m o d i f y askable predicates or user"s database ? ( y / n ) . y. Y o u can 1. A d d new askable predicate(s) . 2. R e m o v e askable predicate(s) . 3. M o d i f y y o u r database . or 4. N o more changes to be made . E n t e r a n u m b e r D o y o u have any askable predicate to be declared ? E n t e r <pred ica te ( s )> — > askable predicate(s) to be added, a l l - -> a l l predicates are askable, list - -> list al l askable predicate(s). help — > get some help, or no — > no askable predicates to be declared. T h e predicate(s) : parent_of. Y o u can 1. A d d new askable predicate(s) . 2. Remove askable predicate(s) . 3. M o d i f y y o u r database . or 4. N o more changes to be made . E n t e r a n u m b e r |:3. D o y o u w i s h to m o d i f y any rule f rom y o u r db ? Please enter r , < r u l e > - -> remove a rule f rom db i , < r u l e > — > insert a rule to d b . no — > if no rules to be removed list — > list out user"s database help — > get some help, or al l — > if y o u want the user d b to be cleared T h e rule : i ,(brother_of (X ,Y)\-|: male(X),parmt_of (Z ,X),arent_of (Z,Y)). 89 D o y o u w a n t to assert the rule into user db ? ( y / n ) \:y-T h e rule : list. User database : verb : : = [ l ikes ] < : > agree(singular) l o g i c ( t r a n s i t i v e , _ l 10,_111 , l i k e s ( _ l 10,_111)) brother_of(_ l08 ,_109) :- male (_ l08 ) ,parent_of (_ l 10._108) ,parent_of(_l 10,_109) T h e rule : no. Y o u can 1. A d d new askable predicate(s) . 2. R e m o v e askable predicate(s) . 3 . M o d i f y y o u r database . or 4. N o more changes to be made . E n t e r a n u m b e r |: 4. Is i t true that jane parent_of charles Please enter yes no list - -> l ist user d b . m o d i f y — > m o d i f y the user"s database, help — > get some help, or w h y — > for explanat ion . A n s w e r is : no. Is i t true that jane parent_of e l izabeth Please enter yes no l ist - -> list user d b . m o d i f y — > m o d i f y the user"s database, help — > get some help, or w h y — > for explanat ion . A n s w e r is : why. IF parent_of( jane,el izabeth) 90 T H E N ancestor_of( jane,elizabeth) D o y o u w a n t more explanat ion ? ( y / n ) I: y. IF parent_of(_532,charles) ancestor_of(j ane,_532) T H E N ancestor_of (j ane ,charles) ancestor_of(jane,charles) w h i c h is w h a t y o u or ig inal ly asked about . Is it t rue that jane parent_of e l izabeth Please enter yes no l ist — > l ist user d b . m o d i f y - -> m o d i f y the user"s database, help — > get some help, or w h y — > for explanat ion . A n s w e r is : no. Is i t true that jane parent_of george Please enter yes no l ist — > list user d b . m o d i f y — > m o d i f y the user"s database, help - -> get some help, or w h y - -> for explanat ion . A n s w e r is : no. G i v e a l l X where X parent_of george < X > — > replace X by a n y t h i n g . < r u l e > — > rule for parent_of w h y - -> for exp lanat ion . l ist — > list user d b . m o d i f y — > m o d i f y the user"s database. help - -> get some help, or no_more ~ > no more i n f o r m a t i o n to be g iven . A n s w e r is : no_more. G i v e a l l X where X parent_of e l izabeth < X > — > replace X b y a n y t h i n g . < r u l e > — > rule for parent_of w h y --.> for explanat ion . l ist — > list user d b . m o d i f y — > m o d i f y the user"s database. help - -> get some help , or no_more — > no more i n f o r m a t i o n to be given A n s w e r is : no_more. G i v e a l l X where X parent_of charles < X > — > replace X by a n y t h i n g . < r u ! e > — > rule for parent_of w h y — > for explanat ion . l ist — > list user d b . m o d i f y — > m o d i f y the user"s database. help - -> get some help , or no_more — > no more i n f o r m a t i o n to be given A n s w e r is : no_more. N o , cannot conf i rm ancestor_of(jane,charles) Please enter stop , w h y or help |: why. ancestor_of(jane,charles) cannot be deduced f r o m any k n o w n facts and rules ancestor_of(jane,charles) cou ld be deduced f r o m the rule IF parent_of(_67,charles) ancestor_of(jane,_67) T H E N ancestor_of(jane,charles) F A C T : parent_of(el izabeth,charles) Y o u denied parent_of( jane,charles) T h e rule t h a t can be used IF parent_of(_279,el izabeth) 92 ancestor_of( jane,_279) T H E N ancestor_of( jane,el izabeth) D o y o u w a n t more e x p l a n a t i o n ? ( y / n ) |:y. F A C T : parent_of(george,el izabeth) Y o u denied parent_of( jane,e l izabeth) T h e rule t h a t c a n be used IF parent_of(_433,george) ancestor_of( jane,_433) T H E N ancestor_of( j ane,george) D o y o u w a n t more e x p l a n a t i o n ? ( y / n ) Y o u denied parent_of( jane,george) C a n n o t deduce parent_of(_563,george) f r o m any k n o w n facts a n d rules i n the database no T h e answer to the query ancestor_of( jane,charles) is " n o " . 

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}]}"
                            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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051902/manifest

Comment

Related Items