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 EXPERT SYSTEM SHELL FOR PROCESSING LOGIC G R A M M A R S  By  JULIANI SUSANTI SALIM B . Sc., M c G i l l U n i v e r s i t y ,  1983  A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R OF SCIENCE in T H E F A C U L T Y OF G R A D U A T E STUDIES ( D e p a r t m e n t of C o m p u t e r Science)  W e accept this thesis as  conforming  to the required s t a n d a r d  T H E UNIVERSITY OF BRITISH C O L U M B I A May  ©  1985  Juliani Susanti Salim,  1985  In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t o f the requirements f o r an advanced degree a t the U n i v e r s i t y o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make it  freely  a v a i l a b l e f o r r e f e r e n c e and study.  I further  agree t h a t p e r m i s s i o n f o r e x t e n s i v e copying o f t h i s f o r s c h o l a r l y purposes may  be granted by the head o f my  department o r by h i s o r her r e p r e s e n t a t i v e s . understood t h a t copying o r p u b l i c a t i o n o f t h i s for f i n a n c i a l  gain  C-Q^jpiU^  The U n i v e r s i t y o f B r i t i s h 1956 Main Mall  Vancouver, Canada V6T 1Y3  E-6  C3/81)  It i s thesis  s h a l l not be allowed without my  permission.  Department o f  thesis  Sa'evu?? Columbia  written  ii  Abstract  Many  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 t h a t has been developed r e c e n t l y . It is  built  on  top  of  the  CProlog/UNLX*  system  running  on  a  P r o G r a m m a r is designed f o r processing a n d d e v e l o p i n g g r a m m a r s .  VAX  t  11/750.  It c a n also be  used as a k n o w l e d g e base c o n s t r u c t o r for other fields besides g r a m m a r s , a l e a r n i n g tool,  a Prolog  interactive  interpreter,  system  ProGrammar  also  meaning can  a n d as not  a consulting system. P r o G r a m m a r  only  q u e s t i o n the  can  the  user. T h e  e x p l a n a t i o n f r o m the P r o G r a m m a r on how the  *UNIX is a trademark of A T & T Bell Laboratories. ^ V A X is a trademark of Digital Equipment Corp.  user user  is  query P r o G r a m m a r is a l l o w e d to request  an but an  s o l u t i o n to the q u e r y was d e r i v e d .  iii  Table of Contents Chapter 1 - Introduction  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 k n o w l e d g e base  8  2.1.2. H o w to c o n s t r u c t a k n o w l e d g e base  8  2.1.3. T h e inference s y s t e m  11  2.1.4. T h e e x p l a n a t i o n f a c i l i t y  12  2.1.5. H o w to i m p l e m e n t the e x p l a n a t i o n f a c i l i t y  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 f o r 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 3.1. A brief i n t r o d u c t i o n t o P r o l o g  16 10  3.1.1. P r o l o g d a t a b a s e  16  3.1.2. F a c t s  17  3.1.3. R u l e s  17  3.1.4. Queries  17  3.2. H o w t o satisfy a goal  18  3.3. T h e i n t e r a c t i v e 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  Chapter 4 - Grammars 4.1. C o n t e x t - f r e e g r a m m a r s  25 25  4.2. Definite C l a u s e G r a m m a r s  28  4.3. Definite 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  32  4.3.1. N o t a t i o n used by D C T G s C h a p t e r 5 - T h e P r o G r a m m a r system 5.1. T h e Q u e r y _ t h e _ u s e r f a c i l i t y 5.1.1. T h e skeleton of Q u e r y _ t f a e _ u s e r interpreter 5.2. T h e e x p l a n a t i o n f a c i l i t y  32 37 38 41 43  Chapter 6 - Conclusions  47  References  50  A p p e n d i x A - A l i s t i n g of the P r o G r a m m a r s y s t e m  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 Figure 2 - The parse tree for a sentence "John likes a dog"  9 31  vi  Acknowledgement I w i s h t o a c k n o w l e d g e several people w h o were v e r y h e l p f u l i n the w r i t i n g of this thesis. F i r s t of a l l , I a m v e r y g r a t e f u l to m y supervisor, D r . H . A b r a m s o n , w h o was v e r y p a t i e n t a n d h e l p f u l t h r o u g h o u t the p r e p a r a t i o n of m y thesis. I e x t e n d t h a n k s to M e i J e a n G o h for g i v i n g the n a m e ( P r o G r a m m a r ) to the s y s t e m a n d f o r m a n y hours of f r u i t f u l d i s c u s s i o n . M y a p p r e c i a t i o n also goes t o D r . K . A b r a h a m s o n , w h o c a r e f u l l y r e a d the thesis. M a n y t h a n k s go to m y friends i n G a g e r e 3 i d e n c c ( E 9 D ) f o r the f u n times we h a d a n d t h e i r c o n t i n u a l m o r a l s u p p o r t w h i c h I needed t h r o u g h o u t this t e r m .  1  Chapter 1 Introduction  C o n s i d e r a b l e a t t e n t i o n has been g i v e n t o P r o l o g  within the past few years. It  has been w i d e l y used i n a p p l i c a t i o n s of s y m b o l i c c o m p u t a t i o n , s u c h as m a n y areas of a r t i f i c i a l intelligence, r e l a t i o n a l 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 c a n be either a fact or r u l e . F o r e x a m p l e , we c a n define a r u l e for a b r o t h e r as follows  brother_of(X,Y) : - male(X) , parent_of(Z,X) , parent_of(Z,Y).  T h e r u l e s a i d f o r every X a n d Y , X is a b r o t h e r of Y if X i3 a m a l e , Z is a p a r e n t of X , a n d 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 i k e :  Is it t r u e t h a t S a m is a b r o t h e r of J i l l ?  In o r d e r to answer the q u e s t i o n , P r o l o g  searches the database f r o m the t o p  to  b o t t o m for i n f o r m a t i o n a b o u t S a m a n d J i l l . T h e answer to the query is " y e s "  if  P r o l o g c a n o b t a i n a l l the i n f o r m a t i o n it needs t o solve the query f r o m the database i n a finite t i m e . O t h e r w i s e the answer w o u l d have been " n o " . P r o l o g adopts a t o p d o w n d e p t h - f i r s t strategy a n d N e g a t i o n As F a i l u r e [ C l a r k 78] w h i c h states : S u p p o s e we have a q u e r y Q , a n d a database D B N O T Q is assumed to be true if Q is not p r o v a b l e i n a finite t i m e .  2 N O T Q is assumed to be true if Q is n o t p r o v a b l e f r o m any clauses i n the database D B . For  e x a m p l e , suppose we have  a database  c o n s i s t i n g of a d j a c e n t  provinces i n  C a n a d a . N o w we w a n t P r o l o g t o find o u t w h e t h e r Quebec is adjacent t o O n t a r i o . If P r o l o g c a n n o t find a d j a c e n t ( Q u e b e c , O n t a r i o ) f r o m the database, t h e n it w i l l give " n o . " as t h e answer m e a n i n g " N o , Quebec is not adjacent t o O n t a r i o . " . The  answer  given  by  Prolog  is  not  quite  accurate  in  this  case  since  N O T a d j a c e n t ( Q u e b e c , O n t a r i o ) is not e x p l i c i t l y present i n the database. H o w e v e r , t o c o n c l u d e " D o n o t k n o w if Quebec is adjacent to O n t a r i o . " w o u l d have been m o r e accurate w h e n e v e r s t r i c t logic is considered an i m p o r t a n t issue. T h e a s s u m p t i o n of N e g a t i o n A s F a i l u r e is  also m a d e b y w h a t 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 t h a t a n y t h i n g t h a t is not p r o v a b l e to be t r u e is assumed t o be false [Reiter 77]. T h e a d v a n t a g e 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 n o t necessary to include all negative facts a b o u t a given d o m a i n i n a database. In general, negative facts o u t n u m b e r p o s i t i v e ones. O f t e n , it is n o t possible to generate a l l negative facts. H o w e v e r , not i n c l u d i n g negative facts e x p l i c i t l y i n a database does not affect the consistency of a d a t a b a s e . 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 m i g h t forget to i n c l u d e a l l p o s i t i v e facts i n t o a database before he asks P r o l o g  t o solve h i 3  problem.  F o r e x a m p l e , co n s i d e r a database w i t h t h e f o l l o w i n g rules a n d facts :  parent_of(sam,bill).  3  female(jill). sister(X,Y) :female(X) , parent_of(Z,Y) , parent_of(Z,X).  T h e r u l e says X is a sister of Y if X is a female, and X a n d Y h a v e same parents.  T h e user has f o r g o t t e n to i n c l u d e p a r e n t _ o f ( s a m , j i l l ) i n the d a t a b a s e . W h e n he ask3 P r o l o g t o find o u t 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 m e a n i n g " N o , J i l l is not a sister of B i l l . " because p a r e n t _ c f ( s a m , j i l l ) c a n n o t be f o u n d i n the d a t a b a s e . 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 p a r e n t _ o f ( s a m , j i l l ) is t r u e . Hence J i l l a n d B i l l have different p a r e n t s .  T h i s i m p l i e s t h a t J i l l c a n n o t be B i l l ' s  sister. In t h i s 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 n o n existence of p a r e n t _ o f ( s a m , j i l l ) i n the database is not caused b y the fact t h a t s a m is not p a r e n t _ o f J i l l b u t is caused b y t h e user'3 forgetfulness. If P r o l o g  a s k e d t h e user to s u p p l y p a r e n t _ o f ( X , j i l l ) , a b o u t w h i c h the  user  m i g h t h a p p e n to k n o w , t h e answer t o the query w o u l d h a v e been " y e s . " m e a n i n g "Yes,  J i l l is a sister of B i l l . " It w o u l d be desirable t o h a v e a P r o l o g i n t e r p r e t e r t h a t asks for i n f o r m a t i o n  w h i c h is needed for s o l v i n g a query w h i c h c a n n o t be f o u n d i n the d a t a b a s e .  4  Q u e r y _ t h e _ u s e r , i n t r o d u c e d b y M . Sergot [Sergot 83], is a P r o l o g i n t e r p r e t e r t h a t handles i n t e r a c t i v e P r o l o g , w h i c h means t h a t not o n l y is the user able t o ask the s y s t e m questions b u t the system m a y also ask the user questions. My  thesis  involves  grammars ( P r o G r a m m a r ) A P E S  implementing  an  expert  system  shell  for  processing  i n P r o l o g . T h e m a i n i d e a of P r o G r a m m a r came f r o m  [ H a m m o n d 82a], Q u e r y _ t h e _ u s e r [Sergot 83], a n d [ 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 k n o w l e d g e base a n d a n inference m e c h a n i s m w h i c h matches the user's query w i t h rules or facts i n the knowledge base i n order to deduce the q u e r y .  W h e n P r o G r a m m a r cannot find a n y rules or facts t h a t c a n be used to  solve the user's q u e r y , it w i l l ask the user for i n f o r m a t i o n required t o solve the q u e r y . T h e user c a n either p r o v i d e 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 a n e x p l a n a t i o n , P r o G r a m m a r w i l l t r a c e a n d d i s p l a y t h e rules used f r o m the p o i n t of the user's query u n t i l the p o i n t 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 s o l u t i o n t o the user's query, it can also p r o v i d e an e x p l a n a t i o n o n how the s o l u t i o n was d e r i v e d . In a d d i t i o n , P r o G r a m m a r  has features for p a r s i n g sentences a c c o r d i n g  to  g r a m m a r s a n d c o n s t r u c t i n g 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  Translation  G r a m m a r s ( D C T G ) are used t o describe the g r a m m a r o f a language. E x p e r t systems a n d t h e i r a p p l i c a t i o n s w i l l be described i n c h a p t e r 2. A brief d e s c r i p t i o n of P r o l o g a n d Q u e r y _ t h e _ u s e r w i l l be given i n c h a p t e r 3. A n overview of  Context-Free  Grammar,  Definite  Clause  Grammar,  and  Definite  Clause  5 Translation  Grammar  will  be discussed i n c h a p t e r 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 c h a p t e r 5, a n d conclusions w i l l be discussed i n the last c h a p t e r .  6  Chapter 2 Expert systems  P r o G r a m m a r is a modest expert system shell t h a t was designed f o r processing g r a m m a r s . M a n y expert systems have been developed over the past decades. w h a t is a n expert s y s t e m ? A n expert system is a c o m p u t e r p r o g r a m t h a t p r o v i d e s expertise i n a specific subject of  knowledge. Usually  information. expert  an  expert  system  engages the  user  in a dialog  to  get  W h e n the system gets sufficient i n f o r m a t i o n , it w i l l e v e n t u a l l y p r o v i d e  a d v i c e or s o l u t i o n s t o the  user's p r o b l e m or s u p p l y i n f o r m a t i o n the  user  requests. Knowledge  p l a y s a n i m p o r t a n t role i n 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 t h a t has been p a r e d , s h a p e d , selected, i n t e r p r e t e d , a n d t r a n s f o r m e d . T h e r e are t w o different types of k n o w l e d g e . T h e first t y p e , i n v o l v i n g facta of the d o m a i n , is k n o w l e d g e t h a t m a y be f o u n d i n t e x t b o o k s a n d j o u r n a l s of the field of interest. A n d there is heuristic  knowledge w h i c h is h a r d e r to r e t r i e v e — i t  is the k n o w l e d g e of m a k i n g good educated guesses i n t h a t  field.  A n expert system consists of a k n o w l e d g e base a n d an inference m e c h a n i s m . Some expert systems also p r o v i d e a n e x p l a n a t i o n f a c i l i t y — w h i c h gives e x p l a n a t i o n s o n how t h e y d e r i v e t h e i r c o n c l u s i o n s . E x p e r t systems m a y also p r o v i d e facilities t h a t c a n e x p l a i n w h y some  conclusion cannot  be reached  or w h y the  user is b e i n g  p r o m p t e d for f u r t h e r i n f o r m a t i o n . T h e e x p l a n a t i o n f a c i l i t y is a n essential p a r t of a n  7  expert s y s t e m . Besides g i v i n g an e x p l a n a t i o n , i t is also c a n be used for d e b u g g i n g the k n o w l e d g e base i n the early stages of its c o n s t r u c t i o n s . A  wide variety  of expert  systems  have  been  b u i l t for  many  applications  especially for m e d i c a l diagnosis. T h e Japanese foresee a p r o m i s i n g f u t u r e f o r expert systems.  In 1981,  t h e y a n n o u n c e d t o the w o r l d t h e i r plans for b u i l d i n g a F i f t h  G e n e r a t i o n of c o m p u t e r s . T h e i r goal is t o develop v e r y intelligent expert systems to be used i n the 1990's a n d b e y o n d . T h e a i m for these new systems is to be able to communicate  with  a n o r d i n a r y people  using natural  language  such  as E n g l i s h ,  Japanese a n d F r e n c h , so t h a t one w o u l d not require a n y b a c k g r o u n d i n p r o g r a m m i n g languages t o use such systems. F i n a l l y , the Japanese expect these new systems to be inexpensive  a n d reliable t o  be  used e v e r y w h e r e — i n offices,  factories,  shops  and  homes. T h e s e new systems called K n o w l e d g e I n f o r m a t i o n P r o c e s s i n g Systems ( K I P S ) .  2.1. A n a t o m y o f e x p e r t s y s t e m s T y p i c a l l y , an expert  system  m a y consist  of a k n o w l e d g e base, a n  inference  system a n d an e x p l a n a t i o n f a c i l i t y . T h e k n o w l e d g e base w o u l d comprise facts a n d rules. W h i l e the inference s y s t e m 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 k n o w l e d g e base i n order t o deduce the query. T h e e x p l a n a t i o n f a c i l i t y w o u l d be capable of f u r n i s h i n g a n e x p l a n a t i o n o n how the c o n c l u s i o n to some query is a r r i v e d at. In a d d i t i o n , the e x p l a n a t i o n f a c i l i t y c a n e x p l a i n to the user w h y he o r she has been p r o m p t e d for some p a r t i c u l a r i n f o r m a t i o n .  8  2.1.1. T h e knowledge base T h e k n o w l e d g e base is a p r i m e c o n t r i b u t o r t o good p e r f o r m a n c e of expert systems. It determines the contents of expert system a n d also the level of expertise offered b y t h e s y s t e m . A k n o w l e d g e base is a s y m b o l i c r e p r e s e n t a t i o n of facts a n d expert k n o w l e d g e i n the subject d o m a i n of the expert s y s t e m . E x p e r t knowledge w h i c h c a n n o t be f o u n d i n t e x t b o o k s or j o u r n a l s — i t is experience t h a t a h u m a n expert a c c u m u l a t e s over years a n d years of s t u d y a n d w o r k .  2.1.2. H o w  t o c o n s t r u c t a knowledge base  K n o w l e d g e base c o n s t r u c t i o n has been a b o t t l e n e c k i n t h e a d v a n c e m e n t  of  expert systems. It i n v o l v e s experts i n some d o m a i n a n d c o m p u t e r scientists w o r k i n g together to d e s i g n a n d c o n s t r u c t the d o m a i n k n o w l e d g e base. T h e role of c o m p u t e r scientist is t o t r a n s f o r m w h a t e v e r i n f o r m a t i o n the experts give i n t o some f o r m s u i t a b l e for c o m p u t e r i n p u t . T o i l l u s t r a t e , suppose we w a n t t o c o n s t r u c t a k n o w l e d g e base (see  for  mechanical  fig.l).This  problem  in  cars  for  faulting-finding  e x a m p l e is t a k e n f r o m H a m m o n d 82a.  consulting  system  9  Car  Engine  Cooling System  Carburetor  Valves  Incorrect Timing  Reboring Needed  Fig.l  Radiator Fanbelt  Leak  Complete Overhaul  Slackness  S a m p l e classification of a s m a l l set of car p r o b l e m s . T h e items i n e x t e r n a l  nodes are the c a r p r o b l e m s .  T h e classification c a n be represented i n a k n o w l e d g e base by t w o relations  R l : is_part_of(X,Y). R 2 : is_possibly_identified_in(X,Y).  U s i n g o u r car p r o b l e m s e x a m p l e , k n o w l e d g e base as follows :  fig.l  the car problems w i l l be represented i n the  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). is_part_of(faiibelt,cooling_system).  U s i n g r e l a t i o n R2 the car problems represented l o o k like this  is_possibly_identified_in(incorrect_timing,carburetor). is_possibly_identified_in(reboring_needed valves). 7  is_possibly_identified_in(leak,radiator). is_possibly_identified_in(slackness,fanbelt). is_possibly_identified_in(complete_overhaul,cooling_system).  T o t r a n s f o r m h u m a n experties i n t o a k n o w l e d g e base the f o l l o w i n g r e l a t i o n is used  R3  : is_identified_by(in(X,Y),Conditions). 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 p r o b l e m s .  So the expert knowledge for car p r o b l e m s w o u l d be as follows :  is_identined_by(in(engine_problems,car_problems), engine_wont_start).  is_identified_by(in(engine_problems,car_problems), engine_starts_but_runs_unevenly).  11  is_identified_by(in(complete_overhaul,cooling_system), (badly_rusted_radiator,leaking_hoses)).  W h e n the car p r o b l e m s is f o u n d , a n expert system m i g h t w a n t t o give some suggestions. T h e s e suggestions c a n be represented i n the f o l l o w i n g f o r m  R4 : is_action_for(X,Y).  W h e r e X is a suggestion a n d Y is the p r o b l e m t h a t was f o u n d . F o r example, is_action_for(seal_with_recommended_compound,leak). is_action_for(tighten_and_replace,slackness).  The  above example illustrates how a k n o w l e d g e base m a y be  constructed.  A f t e r c o n s t r u c t i n g the knowledge base, we m i g h t w a n t to design an inference system t h a t w i l l look t h r o u g h the k n o w l e d g e base for finding the s o l u t i o n of some query posed b y a user.  2.1.3. T h e 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 q u e r y . T h e inference system looks like :  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 a n d R 6 w i l l allow the expert system to look t h r o u g h a l l rules a n d facts i n the k n o w l e d g e base t h a t c a n be used f o r s o l v i n g the q u e r y . It is necessary to be able to give an e x p l a n a t i o n o n how the s o l u t i o n was d e r i v e d , s h o u l d the user request f o r i t .  2.1.4. T h e e x p l a n a t i o n facility T h e e x p l a n a t i o n f a c i l i t y i n the significant p a r t of an expert systems. It gives the user assurance t h a t the s o l u t i o n d e r i v e d b y the expert system is reasonable a n d the s o l u t i o n is based o n i n f o r m a t i o n t h a t was s u p p l i e d b y the user. T w o f o r m s of e x p l a n a t i o n c a n be g i v e n — t h e " h o w " a n d the " w h y " . T h e " h o w " explains to the user step b y step how the c o n c l u s i o n is d e r i v e d . T h e " w h y " allows the user t o request  a n e x p l a n a t i o n o n w h y he is being asked for some  particular  information. In next section, I w i l l discuss how the " h o w " a n d the " w h y " e x p l a n a t i o n m a y be i m p l e m e n t e d .  2.1.5. H o w to i m p l e m e n t the e x p l a n a t i o n facility T o i m p l e m e n t the " h o w " a n d the " w h y " e x p l a n a t i o n , we s h o u l d redefine the inference rules t h a t were g i v e n i n the previous section as follows :  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 tify_in(X, Y, tr ace( (t_part( Y, Z) \ T))). where T is t h e level of trace tree. t_poss_id(X,Y) : - give_reason(t_poss_id(X,Y)). t _ p a r t ( X , Y ) :- give_reason(t_part(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 a n d M c C a b e [ C l a r k , M c C a b e 82]. A n d t h e 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 e x p l a n a t i o n o n t h i s w i l l be g i v e n i n c h a p t e r 5 ( I m p l e m e n t a t i o n o f P r o G r a m m a r ) .  2.2. A p p l i c a t i o n s  of expert  systems  O v e r t h e past decade, extensive research has been done o n expert systems b y a r t i f i c i a l intelligence researchers.  Research o n expert systems has been m o t i v a t e d b y  m a n y factors; one of w h i c h is t h a t expert systems seem t o have a p r o m i s i n g f u t u r e because t h e y c a n assist i n s o l v i n g c o m p l e x , r e a l - w o r l d p r o b l e m s i n specific scientific, m e d i c a l specialities a n d engineering r e q u i r i n g h u m a n expertise. T h e s e new machines are n o t s i m p l y f o r p l a y i n g games l i k e chess, checkers a n d space i n v a d e r . M o s t of t h e t i m e , expert systems c a n help solve p r o b l e m s more r a p i d l y a n d more a c c u r a t e l y t h a n a n y expert  c a n . M a n y expert systems  are available i n t h e  m a r k e t . T h e y have been w i d e l y u t i l i z e d i n v a r i o u s fields s u c h as m e d i c i n e , e d u c a t i o n ,  14  engineering a n d science. D E N D R A L was the first expert s y s t e m to be designed. T h i s project began i n 1965  at  Stanford  university. D E N D R A L  has  been  i n use  for  many  years  in  universities a n d i n d u s t r i a l c h e m i c a l labs a r o u n d the w o r l d . Its a b i l i t y t o e x p l a i n the d e t a i l of molecule  structure  [Buchanon,Feigenbaum Many  expert  from chemical data  now exceeds h u m a n  capability  78].  systems  have  also  been  designed  for  purposes  other  than  c h e m i s t r y . E x p e r t s y s t e m for m e d i c a l diagnosis designed aid3 i n m e d i c a l d e c i s i o n m a k i n g . M Y C I N developed i n 1976  at S t a n f o r d u n i v e r s i t y is one s u c h e x a m p l e . It  was designed to diagnose b l o o d a n d infections, give suggestions t o the p h y s i c i a n o n a n t i b i o t i c therapies for t r e a t i n g the infections  [Shortliffe 76]  T h e reason for d e v e l o p i n g a m e d i c a l c o n s u l t a t i o n expert s y s t e m is t h a t it c a n very  thoroughly  diagnose  the  disease  that  o v e r l o o k i n g a l l possibilities p r o v i d e d adequate  a  patient patient  is data  suffering are  from,  available  never in  the  knowledge base. A p h y s i c i a n tends t o m a k e mistakes w h e n he examines a p a t i e n t . O f t e n , most of these m i s t a k e s are caused by his carelessness w h e n he leaves out some possibilities a n d these mistakes lead to incorrect diagnosis. H o w e v e r there are c e r t a i n t h i n g s t h a t m e d i c a l c o n s u l t a t i o n systems cannot  yet  p e r f o r m s u c h as p h y s i c a l e x a m i n a t i o n , p i c k i n g u p n o n - v e r b a l i n f o r m a t i o n f r o m the p a t i e n t expressed w h e n he is c o n f r o n t e d w i t h a question a n d the system  cannot  effectively converse w i t h the p a t i e n t to get i n f o r m a t i o n or e x p l a i n t h e r a p y . P e r h a p s , i n the near f u t u r e , 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  b o t h i n i n d u s t r i e s a n d academic researches. It is because of several reasons s u c h as P r o l o g is a language w i t h a v e r y simple s y n t a x .  A n d the semantics of P r o l o g c a n  be u n d e r s t o o d easily even b y the n o n p r o g r a m m e r user.  T h e s i m p l i c i t y of P r o l o g  makes it 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 t h i s reason, I selected to use P r o l o g to i m p l e m e n t P r o G r a m m a r . to P r o l o g w i l l be g i v e n i n c h a p t e r 3 .  A brief i n t r o d u c t i o n  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 o n 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  language  ALGOL-W  by  Roussel  at  interpreter was implemented i n the  Marseille  in  1972.  There  are  many  i m p l e m e n t a t i o n s of t h e language n o w ; h o w e v e r , one of the best is t h e 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 g a i n i n g i n p o p u l a r i t y since t h e early 70's. Its m a j o r use has been for research i n a r t i f i c i a l intelligence, s u c h as f o r n a t u r a l languages a n d expert systems. , T h r o u g h o u t t h i s thesis, a l l of t h e examples w i l l c o n f o r m t o the E d i n b u r g h D E C - 1 0 interpreter standard version.  3.1. A brief introduction to Prolog Before d i s c u s s i n g Q u e r y _ t h e _ u s e r , I w o u l d like t o give a brief i n t r o d u c t i o n t o P r o l o g for those  not familiar w i t h P r o l o g .  3.1.1. Prolog database A P r o l o g d a t a b a s e consists of a set of clauses a n d b u i l t - i n predicates, where each clause is either a fact a b o u t t h e given i n f o r m a t i o n o r a rule a b o u t how t h e s o l u t i o n t o a query m a y relate t o g i v e n facts.  17  3.1.2. Facts F a c t s are clauses w i t h o u t a n antecedent. F o r i n s t a n c e , if we w a n t t o specify i n P r o l o g t h a t B i l l is a p a r e n t of J o h n , we enter the fact a c c o r d i n g t o P r o l o g s y n t a x [ C l o c k s i n , M e l l i s h 81], like so : parent_of(bill,john).  3.1.3. Rules R u l e s are i m p l i c a t i o n s of the f o r m h(Al,  , A n ) :- t l ,  each t i is of the f o r m p ( X l , arguments X I ,  , t k , where  k > 0 & n > = 0  , X m ) , p is the name of a r e l a t i o n  f o l l o w e d by  , Xm.  F o r e x a m p l e , we c a n give a d e f i n i t i o n for s i b l i n g as follows sibling(X,Y) :parent_of(Z,X) , parent_of(Z,Y). w h i c h i m p l y t h a t X a n d Y are siblings if X a n d Y share a c o m m o n parent.  3.1.4. Queries O n c e we have some facts, we c a n m a k e queries about t h e m . A query has the same f o r m as a f a c t , w i t h a special symbol(T-) a d d e d i n f r o n t of i t . So like : ?- p a r e n t _ o f ( b i l l , j o h n ) . A q u e r y c a n be more c o m p l i c a t e d t h a n t h i s .  a query looks  18  S u p p o s e , we w a n t to find o u t w h o 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 t a k e t h i s f o r m : ?- s i s t e r ( X , b i l l ) , p a r e n t _ o f ( Y , b i l l ) . The  i n t e r r o g a t i o n is successfully c o m p l e t e d w h e n s u b s t i t u t i o n s for X  and Y  are  found.  3.2. H o w  t o satisfy a g o a l  P r o l o g a t t e m p t s t o evaluate a c o n j u n c t i o n of goals i n order f r o m left t o 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 n e i g h b o r is satisfied. W h e n it is satisfied t h e n its r i g h t neighbor w i l l be e v a l u a t e d . Hence, t o evaluate a goal q l (  ) a n d q2,  , qn.  P r o l o g w i l l t r y to satisfy subgoal q l (  ) , f o l l o w e d b y an e v a l u a t i o n of q2,  , qn.  In s o l v i n g the s u b g o a l q l (  find  ),q2,  , q n , the goal is b r o k e n i n t o subgoals q l (  ), it tries t o  qi(  •)  ql(  )  or  A fact q l ( :-  rli  i  r  ) causes the subgoal q l (  ql(  )  rl,  , rj  o n l y reduces  rl,  , r j . W h e n the s u b g o a l q l (  J -  ) ql(  t o be satisfied i m m e d i a t e l y b u t a rule ) to  the  e v a l u a t i o n of new  subgoal  ) is satisfied, t h e n its r i g h t n e i g h b o r q2,  , qn  w i l l be e v a l u a t e d . T h e goal is c o m p l e t e l y satisfied if the r i g h t neighbor of a satisfied subgoal is e m p t y .  19  A f a i l u r e 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 t o m of the c u r r e n t g o a l . W h e n this happens, P r o l o g b a c k t r a c k s t o the most recent p r e v i o u s l y satisfied subgoal a n d uses u n t r i e d clauses i n the database to resatisfy the s u b g o a l . T h e goal has f a i l e d if there is not a n y previous subgoal w h i c h c a n resatisfied during backtracking. F o r instance, we have a goal g l ( X l , e v a l u a t i o n of the goal g l ( X l , T h e subgoal g l ( X l ,  , X n ) , g2(Xi,...., X k ) t o be satisfied. A n  , X n ) , g2(Xi,  , X k ) is b r o k e n d o w n i n t o t w o p a r t s .  , X n ) w i l l be e v a l u a t e d first. P r o l o g tries t o p a t t e r n m a t c h the  subgoal w i t h a clause of the f o r m gl(Al,  , An).  gl(Al,  , A n ) :-  or  tl(Ai, using a  t o p - d o w n depth-first  gl(Al,  , An), ( A l ,  unifier, Aitr =  where  a  , Al) ,  strategy.  , A n ) and ( X I ,  unifier  is  a  sequence  , ti(Ak,  When P r o l o g  , Am). finds  a matching  clause  , X n ) are m a d e i d e n t i c a l b y a p p l y i n g a of  substitution  components  such  that  X i t r where A i a n d X i are literals, a n d tr is a unifier. T h i s process is called  u n i f i c a t i o n . F o r e x a m p l e , suppose we w a n t t o m a k e ( X , Y ) a n d (a,Z) to be i d e n t i c a l . W e a p p l y a unifier ( a / X , Y / Z ) t o ( X , Y ) a n d (a,Z), where a / X means s u b s t i t u t e X b y a. U n i f i c a t i o n of ( X , Y ) ( a / X , Y / Z ) results i n ( a , Y ) . (a,Z) ( a / X , Y / Z ) results i n ( a , Y ) . Hence, ( X , Y ) a n d (a,Z) are i d e n t i c a l under the u n i f i c a t i o n . A f t e r u n i f i c a t i o n has been  20  done o n ( A l , syntactically  , A n ) and ( X I , identical.  Prolog  , Xn), g l ( A l , follows  the  , A n ) and g l ( X l ,  unification  method  , Xn)  are  introduced  by  R o b i n s o n [ R o b i n s o n 79]. If there are no new goals to be satisfied, t h e n the goal gl(Xl,  , X n ) has succeeded. O t h e r w i s e P r o l o g has to deduce new goals. W h e n new  goals are satisfied, P r o l o g w i l l a t t e m p t t o satisfy g 2 ( X i , if a l l subgoals have been satisfied. T o i l l u s t r a t e , suppose we have a d a t a b a s e parent_of(bill,john). parent_of(john,sam). parent_of(bill,ann). parent_of(sam,jill).  ancestor_of(X,Y)  :-  parent_of(X,Y). ancestor_of(X,Y)  :-  parent_of(Z,Y) , ancestcr_of(X,Z).  and i n response t o the query ?-  ancestor_of(bill,sam).  P r o l o g w i l l t r y to use ancestor_of(X,Y)  :-  parent_of(X,Y). and u n d e r u n i f i c a t i o n  , X k ) . T h e goal is satisfied  21  U =  { bill/X , sam/Y }  b i l l / X means s u b s t i t u t e X b y b i l l . ancestor_of(bill,sam)  and  ancestor_of(X,Y)  become  syntactically  identical.  The  e v a l u a t i o n of the goal reduces t o e v a l u a t i o n of the d e r i v e d goal parent_of(bill,sam). But  parent_of(bill,sam)  cannot  cannot  be f o u n d i n the  database. So  be satisfied, 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 .  alternative  way  to  solve  the  goal.  This  time  parent_of(bill,sam)  P r o l o g w i l l t r y to it  uses  the  second  find  an  rule  of  ancestor_of(X,Y). W i t h the u n i f i c a t i o n , U =  { bill/Y , sam/Y }  the e v a l u a t i o n reduces to parent_of(Z,sam) , ancestor_of(bill,Z). The  subgoal  parent_of(Z,sam)  can  be  satisfied  by  substituting  Z  by  John.  a n c e s t o r _ o f ( b i l l , j o h n ) c a n be satisfied u s i n g the rule ancestor_of(X,Y) :parent_of(X,Y). U =  { bill/X , john/Y }  A new goal t o be satisfied is parent_of(bill,john). A n d , i n d e e d , p a r e n t _ o f ( b i l l , j o h n ) is i n the database, hence the goal has succeeded. T h u s , the answer t o the query is " y e s " m e a n i n g " Y e s , b i l l is the ancestor_of sam." .  22  3.3. The interactive Prolog interpreter Q u e r y _ t b . e _ u . s e r has been i m p l e m e n t e d i n P r o G r a m m a r .  Query_the_user  is a n extension of the P r o l o g i n t e r p r e t e r . It allows i n t e r a c t i o n between a user a n d the s y s t e m . F a c t s  a n d rules c a n be a d d e d t o the database w h i l e the system  is  processing a q u e r y . Q u e r y _ t h e _ u s e r regards the user as a n extension of a d a t a b a s e . W h e n e v e r it needs i n f o r m a t i o n t o deduce a query a n d t h a t i n f o r m a t i o n is not i n the database, it p r o m p t s the user t o see if he c a n 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 m e a n i n g " Does the user k n o w a n y t h i n g about t h i s 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 b e g i n n i n g of the session, the user tells the system a l l relations he k n o w s a b o u t . T h e s e relations are m a r k u n d e r the predicate  askable.  T o i l l u s t r a t e , let's consider a n i n t e r a c t i v e v e r s i o n of J i l l is a sister of B i l l presented earlier. T h e d a t a b a s e consists of  parent_of(sam,bill). female(jill). sister(X,Y) :female(X), parent_of(Z,Y), parent_of(Z,X).  same as before w i t h the a d d i t i o n of  askable(parent_of).  23  The  assertion  askable  tells t h e s y s t e m t h a t  t h e user k n o w s a b o u t  the relation  p a r e n t _ o f a n d he is w i l l i n g t o give i n f o r m a t i o n a b o u t t h e r e l a t i o n . If t h e i n f o r m a t i o n is askable t h e n t h e procedure a$k_user asks t h e user w h a t i n f o r m a t i o n i t needs. E v e n t h o u g h Q u e r y _ t h e _ u s e r c a n get i n f o r m a t i o n f r o m t h e user w h e n e v e r 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 t h e user has f a i l e d t o give a n y helpful  response  to the question, then  Query_the_i!ser  applies N e g a t i o n A s  F a i l u r e . T h u s , t h e answer t o t h e query c a n s t i l l be " n o " . F o r e x a m p l e , let's go b a c k t o o u r e x a m p l e i n c h a p t e r 1. W e query w h e t h e r J i l l is a sister o f B i l l . T h e answer is " n o " a c c o r d i n g t o t h e P r o l o g i n t e r p r e t e r since p a r e n t _ c f ( s a m , j i l l ) c a n n o t be f o u n d i n t h e d a t a b a s e . N o w w e use Q u e r y _ t h e _ u s e r t o process t h e q u e r y . W h e n i t c a n n o t find p a r e n t _ o f ( s a m , j i l l ) i n t h e d a t a b a s e i t asks  is i t t r u e , t h a t s a m p a r e n t _ o f j III ? answer is yes.(user's response) T h e user has r e s p o n d e d " y e s " t o t h e q u e s t i o n , t h u s t h e answer t o t h e user's query is " y e s " because a c c o r d i n g t o t h e user S a m is p a r e n t o f J i l l . T h i s i m p l i e s B i l l a n d J i l l share  a c o m m o n parent.  B u t i f t h e user h a d responded " n o " to t h e system's  q u e s t i o n , t h e n t h e answer t o t h e q u e r y w o u l d have been  " n o " , since i t is n o t  p r o v a b l e t h a t J i l l a n d B i l l have t h e same p a r e n t . The c h a p t e r 5.  skeleton  of the interactive  Prolog  interpreter  will  be presented i n  24  3 . 4 . T h e P r o l o g interpreter versus the interactive interpreter T h e m a j o r difference between Q u e r y _ t h e _ u s e r a n d the P r o l o g i n t e r p r e t e r is t h a t Q u e r y _ t h e _ u s e r a l w a y s requests i n f o r m a t i o n t h a t it needs t o solve t h e query f r o m the user w h e n the i n f o r m a t i o n c a n n o t be f o u n d i n the database. T h e n it tries to solve  the  query  one  more  time.  If  the  query  still  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 i n t e r r o g a t i o n is sort of l i k e 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 a b o u t t h e query f r o m y o u , t h e n I will apply N e g a t i o n A s F a i l u r e . " P r o l o g , o n the o t h e r h a n d , never asks t h e 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 t h e i n f o r m a t i o n t h a t it needs c a n n o t be f o u n d i n the d a t a b a s e , so t h e user never gets a n y w a r n i n g . T h i s i m p l i e s t h a t the user is never given a chance to correct mistakes he i n a d v e r t e n t l y made earlier. A  major  d r a w b a c k of P r o l o g  is t h a t  Prolog  forces  the  user t o  supply  i n f o r m a t i o n needed for s o l v i n g the q u e r y i n a d v a n c e — b e f o r e the query is even m a d e , a l t h o u g h the user sometimes  does not have a n y i d e a w h a t k i n d of i n f o r m a t i o n m u s t  be s u p p l i e d for s o l v i n g his q u e r y .  25  Chapter 4 Grammars  A g r a m m a r is a set of  rules t h a 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 " s e n t e n c e " . T h r o u g h o u t this c h a p t e r a " s e n t e n c e " 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 c a n examine a n y sequence of w o r d s or s y m b o l s to see w h e t h e r it meets the c r i t e r i a of b e i n g a n acceptable sentence. In  the  context-free  next  sections,  I  will  briefly  g r a m m a r s , definite clause  introduce  grammars,  three  types  of  grammars:  a n d definite clause  translation  g r a m m a r s w h i c h are used t o describe languages t h a t w i l l be parsed or developed b y ProGrammar.  4.1. C o n t e x t - f r e e g r a m m a r s Instead of g i v i n g a f o r m a l d e f i n i t i o n of w h a t a c o n t e x t - f r e e  g r a m m a r is, I w i l l  i l l u s t r a t e it b y p r o v i d i n g an e x a m p l e .  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 — > Where  body .  nt is a n o n - t e r m i n a l s y m b o l , a n d  body  is a sequence of n o n - t e r m i n a l s or  t e r m i n a l s separated b y c o m m a s , where a n o n - t e r m i n a l is a s y m b o l t h a t 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 t h a t does not appear on the left h a n d side of a r u l e . T o i l l u s t r a t e , here is an example t a k e n f r o m  26 [ P e r e i r a , W a r r e n 80].  The  following  is  sentences like " M a r y likes a d o g " a n d sentence — >  a 11  grammar  that  accepts  simple  English  E v e r y m a n t h a t lives loves a w o m a n " .  noun_phrase , verb_phrase .  noun_phrase — >  d e t e r m i n e r , n o u n , rel_phrase .  noun_phrase — >  name .  verb_phrase — >  trans_verb , noun_phrase .  verb_phrase — >  intrans_verb .  rel_clause — >  [that] , v e r b _ p h r a s e .  rel_clause — >  Q •  determiner — >  [a] .  determiner — >  [every] .  determiner —>  [all] .  noun —>  [man] .  noun —>  [woman] .  noun — >  [dog] .  name — >  [John] .  name — >  [mary] .  trans_verb — >  [loves] .  trans_verb —>  [likes] .  intrans_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 f o r m e d b y a noun_phrase known  as the  f o l l o w e d b y a verb_phrase.  subject  a n d the  predicate  T h e s e t w o phrases are c o m m o n l y  of a sentence.  N o w , we t r a n s l a t e  the  27 g r a m m a r i n t o P r o l o g clauses.  sentence(SO,S) : — noun_phrase(SO,Sl) , verb_phrase(Sl,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,Sl) , noun_phrase(Sl,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 t h e source s t r i n g t o be p a r s e d , S represents a s t r i n g t h a t is left b e h i n d after SO is b e i n g p a r s e d . T h e first rule states t h a t there is a sentence SO a n d S if there is a noun_phrase  between SO a n d S I , a n d a verb_phrase  between  between S I  and S.  W e c a n t r y t o prove  ?—  sentence([mary,likes,john],[]).  to d e t e r m i n e w h e t h e r t h e sentence is acceptable. A  context-free  However,  g r a m m a r describes  context-free  grammars  a language i n a clear a n d m o d u l a r w a y .  are n o t f u l l y  languages o r p r o g r a m m i n g languages.  adequate  for describing natural  It c a n o n l y check t h e s y n t a x of a sentence b u t  not evaluate t h e semantics o r context dependent i n f o r m a t i o n of a sentence s u c h as the n u m e r i c a l agreement between verbs a n d n o u n s . T h e r e f o r e , it does not detect t h e g r a m m a t i c a l m i s t a k e s i n a sentence such as " M a r y like a d o g " . T h i s sentence is accepted as correct a c c o r d i n g to c o n t e x t - f r e e g r a m m a r . T h i s p r o b l e m is overcome b y the usage of definite clause g r a m m a r s w h i c h are extensions of c o n t e x t - f r e e g r a m m a r .  4.2. Definite Clause G r a m m a r s D e f i n i t e clause  grammars  (DCG)  were i n t r o d u c e d i n [ P e r e i r a , W a r r e n 80]. Definite  clause g r a m m a r s c a n be used to define t h e s y n t a x a n d the semantics of a language. T h e y have been w i d e l y used to defined several languages such as P r o l o g a n d H A S L [ A b r a m s o n 83].  29  Definite clause g r a m m a r rules  have a n o t a t i o n t h a t is s l i g h t l y different f r o m  c o n t e x t - f r e e g r a m m a r s i n the f o l l o w i n g w a y :  (1)  N o n - t e r m i n a l s are a l l o w e d to have a r g u m e n t s . F o r e x a m p l e ,  sentence(S) , n o u n _ p h r a s e ( N ) .  (2)  T h e b o d y of a rule m i g h t consist of n o n - t e r m i n a l s , t e r m i n a l s , a n d procedure calls enclosed b y { }. P r o c e d u r e calls are used to express e x t r a c o n d i t i o n s . F o r example,  determine^N,det(W)) —>  [W] , { i s _ d e t e r m i n e r ( W , N ) } .  T h e e x t r a a r g u m e n t s i n n o n - t e r m i n a l s c a n be used for b u i l d i n g the parse tree of a sentence a n d for d e s c r i b i n g context dependent i n f o r m a t i o n s u c h as the n u m e r i c a l agreement (singular or p l u r a l ) w h i c h is required between nouns a n d verbs. N o w , let us express the E n g l i s h g r a m m a r u s i n g D C G .  sentence(s(Np,VP)) — > noun_phrase(N,NP) , verb_pkrase(N,VP) . noun_phrase(N,np(DET,Noun,REL)) —> determiner(N,DET) , noun(N,Noun) , rel_clause(N,REL) . noun_phrase(singular,np(Name)) — > verb_phrase(N,vp(TV,NP)) —>  name(Name) .  trans_verb(N,TV) ,  noun_phrase(Nl,NP) . verb_phrase(N,vp(IV)) —>  intrans_verb(N,IV) .  rel_clause(N,rel(that,VP)) —>  [that] ,  verb_phrase(N,VP) .  30 rel_clause(N,rel([])) — > determiner(N,det(W))  0• —>  { is_determiner(W,N) } . determiner(plural,det([])) noun(N,n(W)) —>  —>  [] .  [W] ,  { is_noun(W,N) } . n a m e ( n a m e ( W ) ) — > [W] , { is_name(W) } . trans_verb(N,tv(W)) —>  [W] ,  { is_trans(W,N) } . intrans_verb(N,iv(W)) —>  [W] ,  { is_intrans(W,N) } . is_determiner(every,singular) . is_determiner(a,singular) . is_determiner(all,plural) . is_noun(man,singular) . is_noun(woman,singular) . is_noun(dog,singular) . is_name(john) . is_name(mary) . is_trans(loves,singular) . is_trans(likes,singular) . is_intrans(lives,singular) . A sentence " M a r y likes a d o g " is accepted as a g r a m m a t i c a l l y correct sentence b u t not " J o h n love M a r y " .  31  T h e result of s a t i s f y i n g the f o l l o w i n g goal  ?— sentence(Tree,[john,likes,a,dog],[]) .  produces the parse tree : 5  NP  VP  name  TV  john  likes  NP  Det  N  Rel  a  dog  []  F i g u r e 2. T h e parse tree for a sentence " J o h n likes a d o g " .  T h e parse tree is b u 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 k e p t i n one of the a r g u m e n t s of a n o n - t e r m i n a l . A n d the n u m e r i c a l agreement is also k e p t i n a n a r g u m e n t . O f t e n , it is difficult to r e m e m b e r the f u n c t i o n of each a r g u m e n t w h e n the a r g u m e n t list becomes r a t h e r l o n g .  32  4.3. Definite Clause Translation Grammars (DCTG) The  definite  clause  translation  grammar,  introduced  by  H . Abramson  [ A b r a m s o n 84], is a n i m p r o v e m e n t t o D C G s . T h e s y n t a c t i c a n d t h e semantic actions of t h e g r a m m a r are s e p a r a t e d . T h e semantic actions are a p p e n d e d t o a node of a parse tree. tree.  T h e s e semantic actions are i n t e r p r e t e d d u r i n g a t r a v e r s a l of t h e  parse  D e f i n i t e clause t r a n s l a t i o n rules are t r a n s l a t e d i n t o P r o l o g clauses w i t h three  extra  arguments.  O n e of t h e a r g u m e n t s  represents  t h e parse  tree  which  is  a u t o m a t i c a l l y generated w h i l e t h e rest represent a s t r i n g t o be parsed as a difference list. T h e n o t a t i o n s a n d t h e examples of definite clause t r a n s l a t i o n g r a m m a r s w i l l be i l l u s t r a t e d i n t h e next s e c t i o n . F o r more d e t a i l e d d e s c r i p t i o n o n definite  clause  t r a n s l a t i o n g r a m m a r s , refer to [ A b r a m s o n 84].  4.3.1.  Notation used by D C T G s  T h e n o t a t i o n of a definite clause t r a n s l a t i o n g r a m m a r is i n t h e f o r m :  l e f t p a r t ::== r i g h t p a r t < : >  semantic_action .  leftpart : : = rightpart < : >  (semantic_action) , ( s e m a n t i c _ a c t i o n s ) .  or  where semantic_action  is o f t h e f o r m : a t t r i b u t e ::- semantic . or  semantic  semantic.  is a P r o l o g t e r m or a c o n j u n c t i o n c f P r o l o g t e r m s . T h e t e r m m a y 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 w h i l e the rightpart  m a y consist of  non-terminals,  by  terminals  and P r o l o g  n o n - t e r m i n a l i n t h e rightpart  terms  that  are enclosed  {  }.  The  c a n be of t h e f o r m n o n - t e r m i n a l * " N T . NT w i l l be  i n s t a n t i a t e d t o the subtree of t h e parse tree t h a t corresponds t o t h e s u b - d e r i v a t i o n of non-terminal.  T h e symbol < : >  separates t h e s y n t a c t i c a n d t h e semantic p a r t of  the t r a n s l a t i o n r u l e . S e p a r a t i n g t h e s y n t a c t i c a n d t h e semantic p o r t i o n of t h e r u l e i m p r o v e s t h e r e a d a b i l i t y a n d t h e ease of m o d i f i c a t i o n of t h e g r a m m a r rules.  E x a m p l e of a D C T G r u l e .  n o u n _ p h r a s e : : = d e t e r m i n e r * " D , n o u n " N , rel_clause* * R <:> agree(Num) : : — N * *agree(Num) , D"*agree(Num) , R"*agree(Num) .  T h e m e a n i n g of t h e rule is t h a t a noun_phrase a noun  a n d a rcl_clause  is defined b y a determiner  w i t h parse trees D, N, a n d R respectively,  predicate t h a t checks the n u m e r i c a l agreement between the determiner a n d the  followed by agree is a , t h e noun,  rel_clause.  H o w is a D C T G rule t r a n s l a t e d t o a P r o l o g clause ? Suppose w e have t h e f o l l o w i n g rule  leftpart : : = r i g h t l * * R l , r i g h t 2 * * R 2 , { extra_conditions } <:> (semantic_actionl) , (semantic_action2) .  the rule is t r a n s l a t e d to a P r o l o g clause i n t h e f o l l o w i n g s t r u c t u r e  34  leftpart(node(!p,[Rl,R2],[(semantic_actionl),(semantic_action2)]), SO,S) : — r i g h t l ( R l , S O , S l ) , right2(R2,Sl,S) , extra conditions .  P r o l o g t e r m s such as e x t r a c o n d i t i o n s are not t r a n s l a t e d . A f u n c t o r node represents a node of a parse tree. N o w , let us use the D C T G  to describe o u r E n g l i s h g r a m m a r f r o m previous  section.  sentence : : =  n o u n _ p h r a s e * N , v e r b _ p h r a s e ' " V , { a g r e e ( N , V ) }. A  n o u n _ p h r a s e : : = d e t e r m i n e r * " D , n o u n * * N , re l _ c l a u s e " R <:> agree(Num) : : — N * agree(Num) , D " "agree(Num) , R " 'agree(Num) . A  A  noun_phrase ::= <:> agree(singular) .  name  A A  N  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"agree(Numl) . verb_phrase ::=  verb" V  <:> agree(Num) : : — V rel_clause : : =  A  A  agree(Num) .  [that] , v e r b _ p h r a s e " " V  <:> agree(Num) : : — V " agree(Num) . A  rel_clause : : = <:> agree(Num) .  []  35 d e t e r m i n e r : : = [every] <:> agree(singular) . determiner ::=  [a]  <:> agree(singular) . determiner ::=  [all]  <:> agree(plural) . noun ::=  [man]  <:> agree(singular) . noun ::=  [woman]  agree(singular) . n o u n : : = [dog] <:> agree(singular) . v e r b : : = [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 e x a m p l e above, we c a n t e l l t h a t the w a y the D C T G describes t h e g r a m m a r for a language  is clearer t h a n the D C G does. T h e s y n t a c t i c a n d t h e s e m a n t i c parts  of a g r a m m a r are s e p a r a t e d b y < : > s y n t a x or sematics  . T h e r e f o r e , it is easy to separately m o d i f y t h e  of a g r a m m a r . T h e D C T G  g r a m m a r of a language i n P r o G r a m m a r .  has been chosen to describe  the  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 Prolog.  P r o G r a m m a r is b u i l t o n t o p of the C P r o l o g / U N E X * s y s t e m r u n n i n g o n a  V A X * 11/750.  It p r o v i d e s facilities f o r p a r s i n g sentences a c c o r d i n g t o g r a m m a r s a n d  developing grammars  of p r o g r a m m i n g languages.  It is assumed  that  readers  are  familiar with P r o l o g  a n d definite clause t r a n s l a t i o n g r a m m a r s i n t r o d u c e d b y H .  A b r a m s o n [ A b r a m s o n 80], w h i c h is used t o describe the g r a m m a r of a language.  B r o a d l y s p e a k i n g , P r o G r a m m a r consists of t w o m a i n p a r t s . • T h e Query_the_user facility is a n extension of the P r o l o g interpreter a n d is able t o i n t e r a c t w i t h the user.  It  elicits i n f o r m a t i o n f r o m the  user a n d stores it i n t o the  user's  database.  • T h e explanation facility provides some i n f o r m a t i o n t h a t is requested b y the user d u r i n g or after the interaction.  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 i n the next sections. A l i s t i n g of P r o G r a m m a r c a n be f o u n d i n the a p p e n d i x A . T h e terms " k n o w l e d g e b a s e " a n d " d a t a b a s e " w i l l be used i n t e r c h a n g e a b l y t h r o u g h o u t this c h a p t e r . *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 p r o g r a m is a c o l l e c t i o n of clauses. T h e r e are t w o t y p e s of clauses. T h e s i m p l e r clauses are assertions. F o r e x a m p l e ,  Parent_of(john,bill).  a n d t h e more general t y p e of clauses are i m p l i c a t i o n s of w h i c h a n e x a m p l e is :  uncle_of(X,Y) :male(X) , parent_of(Z,Y) , sibling_of(Z,X) .  T h e e x a m p l e above expresses t h e rule t h a t f o r every X a n d Y , X is t h e uncle of Y i f X is a m a l e , Z is t h e p a r e n t of Y , a n d Z is t h e s i b l i n g of X . Q u e r y _ t h e _ u s e r is able to e x t r a c t i n f o r m a t i o n f r o m t h e user as i t needs i t . It regards t h e user as an extension t o t h e database. A l l i n f o r m a t i o n given b y t h e user is stored i n t h e user's database. T h e a b i l i t y t o e x t r a c t i n f o r m a t i o n f r o m t h e user is v e r y h a n d y f o r b u i l d i n g t h e k n o w l e d g e base of a n expert s y s t e m . Q u e r y _ t h e _ u s e r provides three basic forms i n w h i c h questions c a n be p h r a s e d . T h e s i m p l e s t f o r m is a request f o r c o n f i r m a t i o n of some fact like :  Is it true that john parent_of  jill ?  T h e answer t o t h e q u e s t i o n is either " y e s " or " n o " . If t h e user's answer is " y e s " t h e n an assertion p a r e n t _ o f ( j o h n , j i l l ) is a d d e d t o t h e user's database;  otherwise if t h e  39  answer were " n o " t h e n d e n i e d ( p a r e n t _ o f ( j o h n , j i l l ) ) is a d d e d t o t h e d a t a b a s e .  A q u e s t i o n of t h e more general f o r m c o u l d 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 o b t a i n e d t h e answers, t h e assertions p a r e n t _ o f ( j o h n , j i l l ) a n d p a r e n t _ o f ( j o h n , s a m ) are a d d e d to t h e user's database.  Another  t y p e of a question w o u l d be :  define rules for sibling_of answer  is  sibling_of(X,Y)  :-  parent_of(Z,X)  parent_of(Z,Y) .  answer is : n o _ m o r e .  T h e s y n t a x of rules is :  rulehead :- list of conditions.  (1)  or rulehead  semantic  ::=  list of conditions  actions.  (2)  ,  40  A rule of t y p e (2) is t r a n s l a t e d i n t o a f o r m l i k e :  rulehead(node(rulehead,[subtreesJj [semantic actions]), source_string , Rest_string) :• list of conditions .  before i t is a d d e d t o t h e database.  O n t h e other h a n d , a rule of t y p e (1) c a n be  added to the database w i t h o u t a n y transformation. Query_the_user  asks c o n f i r m a t i o n f r o m t h e user before i t adds a new r u l e  given b y t h e user d u r i n g t h e i n t e r a c t i o n i n t o his database. chance  t o change  t h e rule t h a t  he entered  T h u s , t h e user s t i l l has a  earlier i f he wishes. F o r t h e user's  convenience, each question t h a t is posed b y P r o G r a m m a r is a c c o m p a n i e d b y a little guide t h a t gives a n i n s t r u c t i o n how t h e question c a n be answered. F o r instance, Is it true that John parent_of jill Please enter yes no list —> modify —> why —> or help —>  list to user db. to modify user db. for some explanation, to get some help.  answer is : T h e e x p l a n a t i o n of Q u e r y _ t h e _ u s e r a n d its skeleton next section.  w i l l be presented i n t h e  41  5.1.1. The skeleton of Query_the_user interpreter T h e t o p level of the Q u e r y _ t h e _ u s e r i n t e r p r e t e r looks l i k e : solvable(Query,Result) : built-in(Query,Result) .  solvable(Query,true) : assertion(Query) .  solvable(Query,Result) :clause(Query,NewQuery) , solvab!e(NewQuery,Result) ,  solvable(Query,Result) : ask_user(Query) , solvable(Query,Result) .  solvable(Query,false) .  ask_user(Query) :NOT  already_asked(Query),  askable(Query), pose_the_question(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 c a n be solved b y  42  using i n f o r m a t i o n i n t h e system database o r u s i n g P r o l o g ' s b u i l t _ i n predicates. I n a d d i t i o n , t h e system m a y also m a k e use of t h e e x t r a i n f o r m a t i o n o b t a i n e d f r o m t h e user d u r i n g t h e process of s o l v i n g t h e q u e r y . E x t r a i n f o r m a t i o n is based o n relations t h a t t h e user s u p p l i e d at t h e b e g i n n i n g of t h e session. T h e s e relations are k e p t u n d e r the predicate  askable.  T h e procedure ask_user  is t h e m a i n p a r t of 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 .  Its t a s k is t o ask t h e user f o r some p a r t i c u l a r i n f o r m a t i o n i t needs a n d to c o n v e r t t h e user's answer (if necessary) i n t o a n a p p r o p r i a t e f o r m t h a t c a n be used b y t h e s y s t e m . Before ask_user asks t h e user a n y question i t has to check if t h e question is askable and  has n o t been  asked  previously. This  eliminates  t h e p o s s i b i l i t y of g e t t i n g  inconsistent answers s u c h as i n t h e f o l l o w i n g s i t u a t i o n : Is it true that John parent_of  jill  answer is : yes.  Is it true that John parent_of  jill  answer is : n o .  T o p r e v e n t t h e occurrences of s u c h cases, ask_user remembers a l l questions t h a t have been a s k e d a n d does n o t ask t h e m a g a i n . N o t o n l y is i t dangerous to ask t h e same question again f o r fear of inconsistent answers b u t i t is also i n c o n v e n i e n t a n d f r u s t r a t i n g for t h e user t o answer t h e same question over a n d over a g a i n . A l l questions t h a t have been asked are m a r k e d as  43  already_asked  assertions. W h e n ask_user  has c o m p l e t e d a s k i n g the user f o r  extra  i n f o r m a t i o n , the s y s t e m w i l l c o n t i n u e processing the user's q u e r y . T h e query is not solvable if the user is u n a b l e to give a n y e x t r a i n f o r m a t i o n t h a t the s y s t e m needs. D u r i n g the i n t e r a c t i o n between the user a n d the s y s t e m , the user c a n ask for an e x p l a n a t i o n of w h y e x t r a i n f o r m a t i o n is needed. T h e user c a n t y p e " w h y " i n s t e a d of a n s w e r i n g the q u e s t i o n t h a t has been posed b y the s y s t e m . It w i l l t h e n give an e x p l a n a t i o n t o the user.  5.2. T h e explanation facility It is i m p o r t a n t to be able t o p r o v i d e an e x p l a n a t i o n to the user. T h e user needs to be c o n v i n c e d t h a t ProGrammar  the  result p r o d u c e d b y P r o G r a m m a r  is reasonable.  So,  s h o u l d be able to give a n e x p l a n a t i o n of how it solved the q u e r y .  O f t e n , P r o G r a m m a r produces its answer b y e x t r a c t i n g some i n f o r m a t i o n f r o m the user. So, it is reasonable for the user to be able to ask w h y e x t r a i n f o r m a t i o n is being requested.  Sometimes,  the  user w a n t s  to  k n o w w h y the  goal has  failed.  The  e x p l a n a t i o n f a c i l i t y is also useful for d e b u g g i n g the knowledge base i n the early stages of its c o n s t r u c t i o n . B y f o l l o w i n g the e x p l a n a t i o n step  by step, a user or  k n o w l e d g e base designer w i l l be able to spot where the inference w e n t w r o n g w h e n c h e c k i n g results w h i c h differed f r o m w h a t he expected. T h e r e f o r e , gaps or mistakes i n the k n o w l e d g e base c a n be easily s p o t t e d . In o r d e r to be able to give an e x p l a n a t i o n , the system has to r e c o r d the p a t h t h a t is used t o solve the q u e r y . T h e p a t h is represented i n t h i s f o r m :  path(H_clause,B_c!ause,Level,Parent,Sibling) .  44 T o i l l u s t r a t e , let us t r y the f o l l o w i n g e x a m p l e .  Suppose o u r database consists of :  parent_of(frank,john). parent_of(frank,bill). parent_of(john,sam). male(john). male(sam). male(bill).  unc!e_of(X,Y) :male(X) , parent_of(Z,Y) , sibling_of(Z,X) .  sibling_of(X,Y) :parent_of(Z,X) , parent_of(Z,Y).  D u r i n g the d e r i v a t i o n of the g o a l ,  ?- u n c l e _ o f ( b i l l , s a m ) .  the f o l l o w i n g p a t h is r e c o r d e d .  path(uncle_of(bill,sam),(male(bill),parent_of(Z,sam),sibling_of(Z,bill)), 0,nil,l).  45  path(male(bill),true,l,uncle_of(bill,sam),l). path(parent_of(john,sam),true,l,uncle_of(bill,sam),2). path(sibling_of(john,bill),(parent_of(X,john),parent_of(X,bill)), 1 ,uncle_of(bill,sam),3). path(parcnt_of(frank,john),true,2,sibling_of(john,bill),l). path(parent_of(frank,bill),true,2,sibling_of(john,bill),2).  T h e procedure record_path has t h e t a s k of r e c o r d i n g the most recent p a t h t h a t was used b y t h e s y s t e m .  record_path(Head,Body,Level,Parent,Sib) : remove_irr_path(Head,Body,Level,Parent,Sib) , record(path(Head,Body,Level,Parent,Sib)) . T h e procedure remove_irr_path is f o r r e m o v i n g a p a t h t h a t becomes i r r e l e v a n t 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 s a i d t o be irrelevant i f a p a t h does n o t lead to the result of the q u e r y . T h e explain procedure is for t r a c i n g the p a t h a n d g i v i n g the e x p l a n a t i o n to the user.  explain(explanation_type) : trace(path(H,B,L,P,S)) , pose_the_explanation(H,B) , w r i t e f D o y o u w a n t f u r t h e r e x p l a n a t i o n ?') , read(Answer), more_explanation(Answer,explanation_type) .  46  T h e r e are three types of explanations t h a t can be asked •  how gives an e x p l a n a t i o n of how the s o l u t i o n was d e r i v e d . T h e  user has  choices  a b o u t how t h o r o u g h l y the e x p l a n a t i o n s h o u l d be g i v e n . •  why gives a n e x p l a n a t i o n of w h y the user is being asked for e x t r a i n f o r m a t i o n .  •  why_fail gives an e x p l a n a t i o n of w h y the goal has f a i l e d . T h i s e x p l a n a t i o n is s i m p l y a trace of the most recent p a t h t h a t was used w h e n P r o G r a m m a r processed the query.  47  Chapter 6 Conclusions  Prolog modularity  is a language w i t h s i m p l e s y n t a x a n d semantics. make  it possible to  achieve  Its s i m p l i c i t y a n d  fast i m p l e m e n t a t i o n . F o r these  P r o l o g was chosen f o r i m p l e m e n t i n g P r o G r a m m a r .  reasons,  It is a s u i t a b l e language for  i m p l e m e n t i n g q u e s t i o n - a n s w e r i n g systems t h a t require the d e d u c t i o n m e c h a n i s m of P r o l o g a n d is also s u i t a b l e for w r i t i n g interpreters. ProGrammar ProGrammar English  has  been successfully i m p l e m e n t e d . D u r i n g its  development,  was tested f o r p a r s i n g E n g l i s h sentences a n d c o n s t r u c t i n g a s i m p l e  grammar  from  no  production  rules  until  a  complete  grammar  i3  a c c o m p l i s h e d . T h e test results have been v e r y s a t i s f y i n g .  P r o G r a m m a r offers the v a r i o u s features i n c l u d i n g : •  It is able t o request e x t r a i n f o r m a t i o n t h a t it needs w h i l e processing the user's q u e r y . T h e r e f o r e , the user is not obliged t o p r o v i d e all i n f o r m a t i o n t h a t w i l l be r e q u i r e d to solve his query i n a d v a n c e .  •  E a c h question posed b y P r o G r a m m a r is a c c o m p a n i e d b y a guide t h a t gives i n s t r u c t i o n s o n how the q u e s t i o n c a n be answered. T h i s makes the system more user-friendly.  48  •  T h e e x p l a n a t i o n f a c i l i t y gives  reasons  t o the user of how the s o l u t i o n to the  query was d e r i v e d , 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 why  the  query  has  failed. T h i s  explanation  can  be  g i v e n d u r i n g or  after  P r o G r a m m a r has processed the q u e r y .  •  T h e user is a l l o w e d t o m o d i f y his o w n d a t a b a s e at the b e g i n n i n g of each session or d u r i n g the q u e s t i o n - a n s w e r i n g p e r i o d . T h e contents of the user's d a t a b a s e can be d i s p l a y e d u p o n request.  Although P r o G r a m m a r  has  been designed  for processing  and  developing  g r a m m a r s , it can also be used f o r other a p p l i c a t i o n s s u c h as as a n interactive P r o l o g interpreter, a l e a r n i n g t o o l , a n d a k n o w l e d g e bases c o n s t r u c t o r .  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 i m i t a t i o n s •  as f o l l o w i n g  T h e three basic forms i n w h i c h questions c a n be p h r a s e d b y P r o G r a m m a r rather  general. It w o u l d be desirable to have a l t e r n a t i v e  forms of  are  questions  w h i c h are c u s t o m i z e d a c c o r d i n g to the a p p l i c a t i o n of the s y s t e m .  •  T h e why_fail trace  of the  e x p l a n a t i o n is not at its best y e t . T h e most  recent  path  that  was  used  by  Why_fail the  e x p l a n a t i o n is a  system  during  the  e v a l u a t i o n of the q u e r y . Sometimes, the trace m a y not tell the user w h a t  the  real cause of the failure is because the real cause of the failure m a y not i n the  most  recent p a t h . A n d it m a y be recorded i n a p a t h t h a t  appear  becomes  irrelevant w h e n b a c k t r a c k i n g occura a n d this p a t h is r e m o v e d b y the procedure  49  remove_irrjpath.  Hence, t h e system c a n n o t give a n e x p l a n a t i o n t o t h e user o n  w h a t t h e real cause of t h e f a i l u r e i s . In  order  to  overcome  this  problem,  the  irrelevant  path  is r e m o v e d  b a c k t r a c k i n g is able t o satisfy t h e subgoal t h a t caused t h e f a i l u r e .  only  if  50  References  [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, Portugal, 26 June-1 July 1983.  [Abramson 84] H. Abramson, "Definite Clause Translation Grammars", Dept. of Comp. Sc. Technical Report University of British Colum 1984.  84-8,  [Buchanon.Feigenbaum 78] B.G. Buchanon, E.A. Feigenbaum, " D E N D R A L and Meta-DENDRAL", Journal of Artificial Intelligence, vol. 11, pp. 1978. [Clark 78] K . L . Clark, "Negation as failure", Logic and Gallaire and J. Minker (eds.), Plenum Press, New York , !978.  Data bases,  H  [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. Rerearch Report 82/9, Imperial College, London, 1982.  of Computing  [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. Grammars for language analysis", Artificial 1980.  Warren,  "Definite  Intelligence,  Clause vol. 13, pp. 231-278,  [Reiter 77] R. Reiter, "On Closed World Assumption databases", Logic and H. Gallaire and J. Minker (eds.), Plenum Press, New York, 1978  Data bases,  51  [Robinson 65] J.A. Robinson, " A machine-oriented resolution principle", JACM vol. 12, PP. 23-41, 1965.  logic based on the  [Sergot 83] M . Sergot, " A Query_the_user facility for logic programming", Integrated Interactive Computer Systems, P. Degano and E. Sand 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 : M Y C I N " , New York America Elsevier, 1976. [Warren 77] D.H.D. Warren, "Logic programming and compiler writing",  Dept. of Artificial Intelligence Research Report 44> Sept 1977.  Edinbu  appendix A A listing of the ProGrammar system  THE QUERY_THE_USER INTERPRETER MODULE /* QUERY T R A N S L A T O R 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) . /*  THE 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) , G O A L , 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- Y),(Xr*Y)) :- ! , take_node_out(X,Xl) . A  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).  ASK_USER MODULE  /* 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(' write(' write(' write(' write('  why —> for explanation. ') , nl , list --> list user db.') , nl , modify —> modify the user"s database.') , nl , help —> get some help. ') , nl , 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 .  EXPLANATION MODULE  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 S Y S T E M C A L L . ') , nl , writej'NO further E X P L A N A T I O N 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 D A T A B A S E ') , nl , move_up(L) .  DATABASE EDITOR MODULE  /*  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]) .  SYSTEM  PREDICATES  84  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).  ASK_USER  UTILITY  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) :N l 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(_ _,q(Q,V,P)) . J  /*  get an argument from a function  get_arg(X,F N,q(Q V,P)) :var(X) , arg(N,F,Arg) , ! , )  >  check_arg(X,Ar q(Q,V,P)) , g)  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  UTILITY  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 ,  */  71  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  /* /*  UTILITY  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 nl nl nl nl  , , , , ,  writef 2. Remove askable predicate(s) . ') , write(' 3. Modify your database . ') , write(' or 4. No more changes to be made . ') , write(' Enter a number ') , 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) , ! .  UTILITY  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) . /*flushthe 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_phrase N , verb_phrase V, !, { agree(N,V) } <:> logic(P) ::-N"logic(X,Pl,P), V logic(X,Pl)AA  AA  AA  noun_phrase ::= determiner"D, noun N, rel_clause R <:> (agree(Num) ::- N "agree(Num), D 'agree(Num), R 'agree(Num)), (logic(X,Pl,P) ::- D -logic(X,P2,Pl,P), N logic(X,P3), R logic(X,P3,P2)). AA  A A  A  A  A  A  AA  AA  noun_phrase ::= name N <:> agree(singular), (logic(X,P,P) ::- N logic(X)). AA  AA  verb_phrase ::= verb V, { transitive(V) }, noun_phrase N <:> (agree(Num) ::- V 'agree(Num), N agree(Numl)), (logic(X,P) ::- V" logic(transitive,X,Y,Pl), N Iogic(Y,Pl,P)). AA  AA  A  AA  A  AA  verb_phrase ::= verb**V, { intransitive(V) } <:> (agree(Num) ::- V"'agree(Num)), (logic(X,P) ::- V logic(intransitive,X,P)). AA  rel_clause ::= [that], verb_phrase " V <:> (agree(Num) ::- V agree(Num)), (logic(X,Pl,&(Pl,P2)) ::- V"logic(X,P2)). A  A A  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(X Pl,P2,exists(X,&(Pl,P2))). I  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 g o i n g t o be used i n examples are l i s t e d i n a p p e n d i x B . T h e r e are t w o w a y s t o query P r o G r a m m a r : (1)  ?- parse( question ). F o r example, ?- p a r s e ( f a t h e r _ o f ( j o h n , m a r y ) ) .  (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 i f J o h n likes M a r y is a sentence.  | ? -parse (sentence (\john ,likes ,mary ])).  D o y o u w a n t t o m o d i f y askable predicates or user" 3 database ? ( y / n ) . y. Y o u c a n 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 m o r e changes t o be m a d e . Enter a number |: verb.  S y n t a x e r r o r please reenter again Y o u c a n 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 m o r e changes t o be m a d e . Enter a number  |: 1. D o y o u have a n y askable predicate t o be declared ? Enter <predicate(s)> — >  askable predicate(s) t o be a d d e d ,  all  —>  a l l predicates are a s k a b l e ,  list  -->  list a l l askable predicate(s).  help or no  -->  get some h e l p ,  —>  n o askable predicates t o be d e c l a r e d .  T h e predicate(s) : verb.  Y o u c a n 1. A d d new askable predicate(s) . 2. R e m o v e a s k a b l e predicate(s) . 3 . M o d i f y y o u r database . or 4. N o m o r e changes t o be m a d e . Enter a number  |:4. Define v e r b Please enter < r u l e > — > rule f o r v e r b why — > for explanation. list — > list user d b . modify --> modify the user"s database. help — > get some h e l p , o r n o _ m o r e — > no more i n f o r m a t i o n to be g i v e n . T h e rule is : why.  IF verb transitive(_533)  noun_phrase THEN verb_phrase  D o y o u w a n t more explanation ? ( y / n )  I:  y-  IF noun_phrase verb_phrase  agree THEN sentence  Do y o u want more explanation ? ( y / n )  IF sentence _971""logic(_972) write(_972) nl THEN sentence([john,likes,mary])  sentence([john,likes,mary|) w h i c h is w h a t y o u o r i g i n a l l y a s k e d about . Define v e r b Please enter < r u l e > - - > r u l e f o r v e r b why — > for explanation. list — > list user d b . m o d i f y - - > m o d i f y t h e user" s database. help — > get some h e l p , or n o _ m o r e ~ > no more i n f o r m a t i o n t o be g i v e n . 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 t o assert t h e r u l e i n t o user d b ? ( y / n ) |: ». rules c o n s u l t e d 172 bytes 0.116671 sec. T h e ru l e is : list. U s e r database : v e r b ::== [ likes ] <:> agree(singular) logic(transitive,_1321,_1322,likes(_1321,_1322))  Define v e r b Please enter < r u l e > — > r u l e for v e r b why —> for e x p l a n a t i o n . list --> list user d b . m o d i f y -- > m o d i f y the user" s database. help - - > get some h e l p , o r n o _ m o r e - - > no more i n f o r m a t i o n to be g i v e n . T h e rule is : no_more.  likes(john,mary) * * * T h e answer to the query is Y E S  ***  please enter stop - - > no more e x p l a n a t i o n , ok — > go one level u p . how — > e x p l a n a t i o n for succeeded goal o n l y , why — > e x p l a n a t i o n for f a i l e d goal o n l y , ldb — > list user d b . l p r e d — > list user s u p p l i e d predicate(s). help - - > get some help, a b o r t — > abort the execution |: how.  I d e d u c e d sentence([John,likes,mary]) f r o m the rule IF sentence _2560"'logic(_2561) write(_2561) nl THEN sentence([john,likes,mary])  I can show 1. sentence 2. node(sentence)" logic(_2997) 3. w r i t e ( l i k e s ( j o h n , m a r y ) ) 4. n l A  please enter stop - - > no more e x p l a n a t i o n , ok — > go one level u p . how — > e x p l a n a t i o n for succeeded goal o n l y , why — > e x p l a n a t i o n for f a i l e d goal o n l y , ldb — > list user d b . l p r e d - - > list user s u p p l i e d predicate(s).  help — > abort -->  get some help, a b o r t the execution.  |: 1. I d e d u c e d sentence f r o m the rule IF noun_phrase verb_phrase l agree(_3088,_3089) THEN sentence  I c a n show 1. n o u n _ p h r a s e 2. v e r b _ p h r a s e 3. ! 4. agree please enter stop - - > no more e x p l a n a t i o n , ok — > go one level u p . how — > e x p l a n a t i o n for succeeded goal o n l y , why — > e x p l a n a t i o n for f a i l e d goal o n l y , ldb — > list user d b . l p r e d - - > list user s u p p l i e d predicate(s). help — > get some h e l p , a b o r t — > a b o r t the execution.  I d e d u c e d n o u n _ p h r a s e f r o m the rule IF name THEN noun_phrase  I can show 1. n a m e please enter stop — > no more e x p l a n a t i o n , ok — > go one level u p . how — > e x p l a n a t i o n for succeeded goal o n l y , why --> e x p l a n a t i o n for f a i l e d goal o n l y , ldb — > list user d b .  Ipred ~ > list user s u p p l i e d predicate(s). help — > get some h e l p , a b o r t - - > a b o r t the execution.  |: ok. I c a n show 1. n o u n _ p h r a s e 2. v e r b _ p h r a s e 3. ! 4. agree please enter stop — > no more e x p l a n a t i o n , ok — > go one level u p . how --> e x p l a n a t i o n for succeeded goal o n l y , why —> e x p l a n a t i o n for f a i l e d goal o n l y , ldb — > list user d b . Ipred -- > list user s u p p l i e d predicate(s). help - - > get some help, a b o r t — > abort the execution |:2. I d e d u c e d v e r b _ p h r a s e f r o m the r u l e IF verb transitive(_3805) noun_phrase THEN verb_phrase  I can show 1. v e r b 2. t r a n s i t i v e 3. n o u n _ p h r a s e please enter stop - - > no more e x p l a n a t i o n , ok - - > go one level u p . how - - > e x p l a n a t i o n for succeeded goal o n l y , why — > e x p l a n a t i o n for f a i l e d goal o n l y , ldb -- > list user d b . Ipred — > list user s u p p l i e d predicate(s). help --> get some help, abort — > abort the execution  |: l . I d e d u c e d v e r b f r o m the rule t h a t was D E F I N E D b y 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 —> why --> ldb —> Ipred — > help — > abort — >  e x p l a n a t i o n for succeeded goal o n l y . e x p l a n a t i o n for f a i l e d goal o n l y . list user d b . list user s u p p l i e d predicate(s). get some h e l p . abort the execution.  |: ok. I c a n show 1. v e r b 2. t r a n s i t i v e 3. n o u n _ p h r a s e please enter stop - - > no more e x p l a n a t i o n , ok - - > go one level u p . how — > e x p l a n a t i o n for succeeded goal o n l y , why — > e x p l a n a t i o n for f a i l e d goal o n l y , ldb - - > list user d b . Ipred — > list user s u p p l i e d predicate(s). help --> get some help, abort — > abort the execution. |: ok. I c a n show 1. n o u n _ p h r a s e 2. v e r b _ p h r a s e 3. ! 4. agree please enter stop - - > no more e x p l a n a t i o n , ok — > go one level u p . how --> e x p l a n a t i o n for succeeded goal o n l y . why — > e x p l a n a t i o n for failed goal o n l y . ldb — > list user d b . i p r e d — > list user s u p p l i e d predicate(s). help --> get some h e l p . abort --> abort the execution |: ok. I can show 1. sentence 2. node(sentence)" *logic(_5415) 3. w r i t e ( l i k e s ( j o h n , m a r y ) ) 4. n l please enter stop - - > no more e x p l a n a t i o n , ok — > go one level u p .  how — > e x p l a n a t i o n for succeeded goal o n l y . why — > e x p l a n a t i o n for f a i l e d goal o n l y . ldb - - > list user d b . Ipred — > list user s u p p l i e d predicate(s). help — > get some h e l p . abort  —>  a b o r t the e x e c u t i o n  |:2. I d e d u c e d node(sentence)  A  A  logic(_5506) f r o m the rule  IF n o d e ( n o u n _ p h r a s e ) logic(_5507,_5508,_5506) n o d e ( v e r b _ p h r a s e ) logic(_5507,_5508) THEN A  A  node(sentence)"  A  A  A  logic(_5506)  I c a n show 1. n o d e ( n o u n _ p h r a s e ) logic(_5682,_5679,_5679) 2. n o d e ( v e r b _ p h r a s e ) "logic(john,_5739) please enter stop — > no more e x p l a n a t i o n , ok — > go one level u p . how — > e x p l a n a t i o n for succeeded goal o n l y , why — > e x p l a n a t i o n for f a i l e d goal o n l y , ldb — > list user d b . Ipred — > list user s u p p l i e d predicate(s). help — > get some h e l p , a b o r t — > a b o r t the e x e c u t i o n A  A  A  |:2. I deduced node(verb_phrase) 'logic(john,_5797) A  f r o m the rule  IF node(verb) logic(transitive,john,_5801,_5802) n o d e ( n o u n _ p h r a s e ) logic(_5801,_5802,_5797) THEN A A  A  node(verb_phrase)  A  A  A  logic(john,_5797)  I c a n show 1. node(verb) logic(transitive,john,_6012,likes(john,_6012)) 2. node(noun_phrase) Iogic(_6081,likes(john,_6081),likes(john,_6081)) please enter stop — > no more e x p l a n a t i o n , ok — > go one level u p . how — > e x p l a n a t i o n for succeeded goal o n l y . A  A  AA  why — > e x p l a n a t i o n for f a i l e d goal o n l y . ldb — > list user d b . Ipred -- > list user s u p p l i e d predicate(s). help - - > get some h e l p . abort — > abort the execution |: ok. I c a n show 1. n o d e ( n o u n _ p h r a s e ) * *Iogic(_6152,_6149,_6149) 2. n o d e ( v e r b _ p h r a s e ) * "logic(john,_6209) please enter stop — > no more e x p l a n a t i o n , ok - - > go one level u p . how — > e x p l a n a t i o n for succeeded goal o n l y , why - - > e x p l a n a t i o n for f a i l e d goal o n l y , ldb — > list user d b . Ipred — > list user s u p p l i e d predicate(s). help — > get some h e l p , a b o r t - - > a b o r t the e x e c u t i o n |: stop. yes T h e answer to the q u e r y sentence([john,likes,mary]) is " y e s " .  E x a m p l e 2. T h e user queries  P r o G r a m m a r i f Jane is a n ancestor of C h a r l e s .  | ? -parse (ancestor_of  (jane  ,charles)).  D o y o u w a n t t o m o d i f y askable predicates o r user"s database ? ( y / n ) . y. Y o u c a n 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 m o r e changes to be m a d e . Enter a number  D o y o u have a n y askable predicate t o be declared ? E n t e r < p r e d i c a t e ( s ) > — > askable predicate(s) t o be a d d e d , all - - > a l l predicates are a s k a b l e , list - - > list a l l askable predicate(s). help — > get some help, or n o — > n o askable predicates t o be d e c l a r e d . T h e predicate(s) : parent_of.  Y o u c a n 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 m o r e changes to be m a d e . Enter a number  |:3. D o y o u wish to modify any rule from your d b ? Please enter r, < r u l e > --> remove a rule from d b i , < r u l e > — > insert a r u l e t o d b . no — > i f no rules t o be r e m o v e d list help or a l l  — > list o u t user"s database — > get some help, — > if y o u w a n t the user d b to be cleared  T h e r u l e : 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 t o assert t h e r u l e i n t o user d b ? ( y / n ) \:y-  T h e ru l e : list. User database : verb ::=  [ likes ]  <:> 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)) b r o t h e r _ o f ( _ l 0 8 , _ 1 0 9 ) :- m a l e ( _ l 0 8 ) , p a r e n t _ o f ( _ l 1 0 . _ 1 0 8 ) , p a r e n t _ o f ( _ l 10,_109) T h e ru l e : no. Y o u c a n 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 m o r e changes to be m a d e . Enter a number |: 4. Is i t t r u e t h a t j a n e p a r e n t _ o f charles Please enter yes no list - - > 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 e x p l a n a t i o n . A n s w e r is : no.  Is i t true t h a t j a n e p a r e n t _ o f e l i z a b e t h Please enter yes no list - - > list user d b . m o d i f y — > m o d i f y the user"s database, help — > get some h e l p , or w h y — > for e x p l a n a t i o n . A n s w e r is : why.  IF pa re n t _ o f(j a n e , e l i z a b e t h )  90 THEN ancestor_of(jane,elizabeth)  Do y o u w a n t more explanation ? (y/n)  I:  y.  IF parent_of(_532,charles) ancestor_of(j ane,_532) THEN ancestor_of (j ane ,charles)  ancestor_of(jane,charles) w h i c h is w h a t y o u o r i g i n a l l y a s k e d a b o u t . Is it t r u e t h a t j a n e p a r e n t _ o f e l i z a b e t h Please enter yes no list — > list user d b . m o d i f y - - > m o d i f y the user"s database, help — > get some h e l p , or w h y — > for e x p l a n a t i o n . A n s w e r is : no.  Is i t t r u e t h a t j a n e p a r e n t _ o f george Please enter yes no list — > list user d b . m o d i f y — > m o d i f y the user"s database, help - - > get some h e l p , or w h y - - > for e x p l a n a t i o n . A n s w e r is : no.  G i v e a l l X where X p a r e n t _ o f george <X> — > replace X b y a n y t h i n g . < r u l e > — > r u l e for p a r e n t _ o f why --> for explanation. list — > list user d b . m o d i f y — > m o d i f y t h e user"s d a t a b a s e . help - - > get some h e l p , or n o _ m o r e ~ > no more i n f o r m a t i o n to be g i v e n . A n s w e r is : no_more.  G i v e a l l X where X p a r e n t _ o f e l i z a b e t h <X> — > replace X b y a n y t h i n g . < r u l e > — > r u l e for p a r e n t _ o f why --.> f o r e x p l a n a t i o n . list — > list user d b . m o d i f y — > m o d i f y the user"s database. help - - > get some h e l p , o r n o _ m o r e — > no more i n f o r m a t i o n t o be given A n s w e r is : no_more. G i v e a l l X where X p a r e n t _ o f charles <X> — > replace X b y a n y t h i n g . < r u ! e > — > r u l e for p a r e n t _ o f why — > for explanation. list — > list user d b . m o d i f y — > m o d i f y the user"s database. help - - > get some h e l p , or n o _ m o r e — > no more i n f o r m a t i o n t o be given A n s w e r is : no_more.  N o , c a n n o t c o n f i r m ancestor_of(jane,charles) Please enter s t o p , w h y o r help |: why.  ancestor_of(jane,charles) c a n n o t be d e d u c e d f r o m any k n o w n facts a n d rules ancestor_of(jane,charles) c o u l d be d e d u c e d f r o m the r u l e IF parent_of(_67,charles) ancestor_of(jane,_67) THEN ancestor_of(jane,charles)  F A C T : parent_of(elizabeth,charles) Y o u d e n i e d parent_of(jane,charles) T h e rule t h a t c a n be used IF parent_of(_279,elizabeth)  92 ancestor_of(jane,_279) THEN  ancestor_of(jane,elizabeth)  Do y o u want more explanation ? (y/n) |:y.  F A C T : parent_of(george,elizabeth) Y o u denied parent_of(jane,elizabeth) T h e r u l e t h a t c a n be u s e d IF parent_of(_433,george) ancestor_of(jane,_433) THEN ancestor_of( j ane,george) Do y o u want more explanation ? (y/n)  Y o u d e n i e d parent_of(jane,george)  C a n n o t deduce parent_of(_563,george) f r o m a n y k n o w n facts a n d rules i n the d a t a b a s e no  T h e a n s w e r to t h e q u e r y 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