/******************************************************************** AN IMPLEMENTATION OF DISCOURSE REPRESENTATION THEORY ******************************************************************** /******************************************************************** Experimental implementation of Discourse Representation Theory modeled on that of Johnson and Klein (CSLI Report 86-63). Programmed by Michael Covington, University of Georgia. Supported by National Science Foundation Grant IST-85-02477. ********************************************************************/ /******************************************************************** DECLARATIONS ********************************************************************/ g_features([in,out,syn,sem,index,scope,res,class,arg1,arg2]). /******************************************************************** COMPUTATIONAL UTILITIES ********************************************************************/ /* * reverse(List,Result) * Fast list reversal with stacks. * NOTE: If the tail of the list is uninstantiated, this procedure * will instantiate it to nil. So don't use this procedure on * open lists that need to remain open. */ reverse(List,Result) :- nonvar(List), reverse_aux(List,[],Result). reverse_aux([],Result,Result). reverse_aux([H|T],Stack,Result) :- reverse_aux(T,[H|Stack],Result). /* * unique_integer(N) * Unifies N with a different integer every time it is called. */ unique_integer(N) :- retract(unique_aux(N)), NN is N+1, assert(unique_aux(NN)), !. /* Cut needed by Quintus, not Arity */ unique_aux(0). /* * add_to_topmost_drs(I,Semantics,DRSList,NewDRSList) * Used to let the discourse markers for proper nouns rise to the * universe part of the topmost DRS. * I is an atom (the index); Semantics is a list of DRS-conditions. */ add_to_topmost_drs(I,Semantics,[drs(U,Con)],[drs([I|U],NewCon)]) :- append(Semantics,Con,NewCon). add_to_topmost_drs(I,Semantics,[H|T],[H|NewT]) :- add_to_topmost_drs(I,Semantics,T,NewT). /******************************************************************** I/O UTILITIES ********************************************************************/ /* * display_drs(X) * Outputs a readable representation of a DRS. */ display_drs(X) :- display_drs_indented(X,0). display_drs_indented(X,N) :- var(X), !, write(X),nl. display_drs_indented(ifthen(X,Y),N) :- !, tab(N), write('IF:'), nl, NN is N+2, display_drs_indented(X,NN), tab(N), write('THEN:'), nl, display_drs_indented(Y,NN). display_drs_indented(neg(X),N) :- !, tab(N), write('NOT:'), nl, NN is N+2, display_drs_indented(X,NN). display_drs_indented(query(X),N) :- !, tab(N), write('QUERY:'), nl, NN is N+2, display_drs_indented(X,NN). display_drs_indented(drs(X,Y),N) :- !, reverse(X,RX), tab(N), write(RX), nl, reverse(Y,RY), display_drs_indented(RY,N). display_drs_indented([H|T],N) :- !, display_drs_indented(H,N), display_drs_indented(T,N). display_drs_indented([],_) :- !. display_drs_indented(Cond,N) :- tab(N), write(Cond), nl. /******************************************************************** DRS-BUILDER ********************************************************************/ /*************************************** * Lexicon and lexical insertion rules * ***************************************/ /* * Proper nouns. */ n(N) --> [Form], { proper_noun_features(Form,N) }. /* add_to_topmost_drs }. */ proper_noun_features(Form,N) :- proper_noun(Form,lambda(I,Semantics)), append(Semantics,Con,NewCon), unique_integer(I), N = syn: (index:I :: class:proper) :: sem: (in: DRSList :: out: NewDRSList), add_to_topmost_drs(I,Semantics,DRSList,NewDRSList). proper_noun(pedro, lambda(X,[gender(X,m),named(X,pedro)])). proper_noun(chiquita, lambda(X,[gender(X,f),named(X,chiquita)])). /* * Common nouns. */ n(N) --> [Form], { common_noun_features(Form,N) }. common_noun_features(Form,N) :- common_noun(Form,lambda(I,Semantics)), append(Semantics,Con,NewCon), unique_integer(I), N = syn: (index:I :: class:common) :: sem: (in: [drs(U,Con)|Super] :: out: [drs([I|U],NewCon)|Super]). common_noun(bandersnatch,lambda(X,[gender(X,n),bandersnatch(X)])). common_noun(boojum, lambda(X,[gender(X,n),boojum(X)])). common_noun(man, lambda(X,[gender(X,m),man(X)])). common_noun(woman, lambda(X,[gender(X,f),woman(X)])). common_noun(donkey, lambda(X,[gender(X,n),donkey(X)])). common_noun(farmer, lambda(X,[gender(X,m),farmer(X)])). /* * Adjectives. */ adj(Adj) --> [Form], { adjective_features(Form,Adj) }. adjective_features(Form,Adj) :- adjective(Form,lambda(I,Semantics)), append(Semantics,Con,NewCon), Adj = syn: (index:I) :: sem: (in: [drs(U,Con)|Super] :: out: [drs(U,NewCon)|Super]). adjective(big, lambda(X,[big(X)])). adjective(green, lambda(X,[green(X)])). adjective(rich, lambda(X,[rich(X)])). adjective(old, lambda(X,[old(X)])). adjective(happy, lambda(X,[happy(X)])). /* * Transitive verbs. */ v(V) --> [Form], { transitive_verb_features(Form,V) }. transitive_verb_features(Form,V) :- transitive_verb(Form,lambda(A1,A2,Semantics)), append(Semantics,Con,NewCon), V = syn: (class:transitive :: arg1:A1 :: arg2:A2) :: sem: (in: [drs(U,Con)|Super] :: out: [drs(U,NewCon)|Super]). transitive_verb(see, lambda(X,Y,[sees(X,Y)])). transitive_verb(sees, lambda(X,Y,[sees(X,Y)])). transitive_verb(love, lambda(X,Y,[loves(X,Y)])). transitive_verb(loves, lambda(X,Y,[loves(X,Y)])). transitive_verb(own, lambda(X,Y,[owns(X,Y)])). transitive_verb(owns, lambda(X,Y,[owns(X,Y)])). transitive_verb(have, lambda(X,Y,[has(X,Y)])). transitive_verb(has, lambda(X,Y,[has(X,Y)])). transitive_verb(beat, lambda(X,Y,[beats(X,Y)])). transitive_verb(beats, lambda(X,Y,[beats(X,Y)])). transitive_verb(feed, lambda(X,Y,[feeds(X,Y)])). transitive_verb(feeds, lambda(X,Y,[feeds(X,Y)])). /* * Intransitive verbs. */ v(V) --> [Form], { intransitive_verb_features(Form,V) }. intransitive_verb_features(Form,V) :- intransitive_verb(Form,lambda(Arg,Semantics)), append(Semantics,Con,NewCon), V = syn : (class:intransitive :: arg1:Arg) :: sem : (in: [drs(U,Con)|Super] :: out: [drs(U,NewCon)|Super]). intransitive_verb(bark, lambda(X,[barks(X)])). intransitive_verb(barks, lambda(X,[barks(X)])). intransitive_verb(eat, lambda(X,[eats(X)])). intransitive_verb(eats, lambda(X,[eats(X)])). intransitive_verb(bray, lambda(X,[brays(X)])). intransitive_verb(brays, lambda(X,[brays(X)])). /* * Determiners, each with their own semantics. */ det(Det) --> ([a] ; [an]; [the]), /* Definite and indefinite determiners are both interpreted as being existentially quantified, i.e., their NP rises to the universe part of the current DRS. Generic interpretations are excluded. */ { Det = sem:in:A, Det = sem:res:in:A, /* Pass 'sem:in' to 'res'. */ Det = sem:res:out:B, Det = sem:scope:in:B, /* Pass 'res:out' to 'scope:in'. */ Det = sem:scope:out:C, Det = sem:out:C }. /* Whatever comes out of 'scope:out' is the final result for the whole sentence. */ det(Det) --> [every], { Det = sem:in:A, Det = sem:res:in:[drs([],[])|A], Det = sem:res:out:B, Det = sem:scope:in:[drs([],[])|B], Det = sem:scope:out:[Scope,Res,drs(U,Con)|Super], Det = sem:out:[drs(U,[ifthen(Res,Scope)|Con])|Super] }. det(Det) --> [no], { Det = sem:in:A, Det = sem:res:in:[drs([],[])|A], Det = sem:res:out:B, Det = sem:scope:in:B, Det = sem:scope:out:[DRS,drs(U,Con)|Super], Det = sem:out:[drs(U,[neg(DRS)|Con])|Super] }. det(Det) --> [not,every], { Det = sem:in:A, Det = sem:res:in:[drs([],[])|A], Det = sem:res:out:B, Det = sem:scope:in:[drs([],[])|B], Det = sem:scope:out:[Scope,Res,drs(U,Con)|Super], Det = sem:out: [drs(U,[neg(drs([],[ifthen(Res,Scope)]))|Con])|Super] }. /************************** * Phrase structure rules * **************************/ /* * n1: a common noun preceded by zero or more adjectives. */ n1(N1,H,H) --> n(N1). n1(N1A,H1,H2) --> { N1A = syn:A, Adj = syn:A, N1B = syn:A, /* Indices are syntactic, not semantic. */ N1A = sem:in:B, N1B = sem:in:B, N1B = sem:out:C, Adj = sem:in:C, Adj = sem:out:D, N1A = sem:out:D }, adj(Adj), n1(N1B,H1,H2). /* * n2: a common noun of type n1 optionally followed by relative clause. */ n2(N2,H1,H2) --> n1(N2,H1,H2). n2(N2,H1,H3) --> { N2 = syn:Syn, N1 = syn:Syn, RC = syn:Syn, /* Pass index to 'RC'. */ N2 = sem:in:S1, N1 = sem: (in:S1 :: out:S2), RC = sem: (in:S2 :: out:S3), N2 = sem:out:S3 }, n1(N1,H1,H2), relcl(RC,H2,H3). /* A noun phrase ending with a relative clause. */ /* * Noun phrases. */ np(NP,H,H) --> { N = syn:class:proper, N = syn:A, NP = syn:A, /* 'NP' gets its syntax from 'N'. */ N = sem:B, NP = sem:res:B, /* 'NP' gets its restrictor from 'N'. */ NP = sem:in:C, NP = sem:res:in:C, /* Pass 'sem:in' through 'res:in'. */ NP = sem:res:out:D, NP = sem:scope:in:D, /* Pass further on through 'scope:in'.*/ NP = sem:scope:out:E, NP = sem:out:E }, n(N). /* Proper names do not take determiners. */ np(NP,H1,H2) --> { N2 = syn:class:common, N2 = syn:C, NP = syn:C, /* 'NP' gets its syntax from 'N'. */ Det = sem:A, NP = sem:A, /* 'NP' gets its semantics from 'Det'. */ N2 = sem:B, Det = sem:res:B }, /* 'Det' gets its restrictor from 'N'. */ det(Det), n2(N2,H1,H2). /* * Trace (gap) from moved relative pronoun. */ np(NP,[rel(Index)|Rest],Rest) --> [], /* Trace from moved relative pronoun. */ { NP = sem:in:B, /* This kind of NP has no semantics and hence no restrictor. */ NP = sem:scope:in:B, NP = sem:scope:out:C, NP = sem:out:C, NP = syn:index:Index }. /* * Anaphoric pronouns, with anaphora resolving routine. */ np(NP,H,H) --> ([he];[him]), { NP=sem:in:DrsList, member(drs(U,Con),DrsList), member(Index,U), member(gender(Index2,m),Con), Index == Index2, NP=syn:index:Index, NP=sem:scope:in:DrsList, NP=sem:scope:out:DrsOut, NP=sem:out:DrsOut }. np(NP,H,H) --> ([she];[her]), { NP=sem:in:DrsList, member(drs(U,Con),DrsList), member(Index,U), member(gender(Index2,f),Con), Index == Index2, NP=syn:index:Index, NP=sem:scope:in:DrsList, NP=sem:scope:out:DrsOut, NP=sem:out:DrsOut }. np(NP,H,H) --> [it], { NP=sem:in:DrsList, member(drs(U,Con),DrsList), member(Index,U), member(gender(Index2,n),Con), Index == Index2, NP=syn:index:Index, NP=sem:scope:in:DrsList, NP=sem:scope:out:DrsOut, NP=sem:out:DrsOut }. /* * Verb phrases. */ vp(VP,H1,H2) --> { V = syn:class:transitive, V = syn:D, VP = syn:D, /* 'VP' gets its syntax from 'V'. */ NP = sem:A, VP = sem:A, /* 'VP' gets its semantics from 'NP'. */ NP = syn:index:C, VP = syn:arg2:C, /* 'VP' gets its object index from 'NP'. */ V = sem:B, NP = sem:scope:B }, /* 'NP' gets its scope from 'V'. */ v(V), np(NP,H1,H2). vp(VP,H,H) --> v(VP), { VP = syn:class:intransitive }. /* * Relative clauses. */ relcl(RC,H1,H2) --> { RC = syn:index:Index, RC = sem:Sem, S = sem:Sem }, ([who];[whom];[which];[that]), s(S,[rel(Index)|H1],H2). /* * Simple sentences. */ s(S,H1,H3) --> { NP = sem:A, S = sem:A, /* Pass 'NP=sem' to 'S=sem'. */ VP = sem:C, NP = sem:scope:C, /* Pass 'VP=sem' to 'NP=sem:scope'. */ NP = syn:index:D, VP = syn:arg1:D }, /* Pass 'NP=syn:index' to 'VP=syn:arg1'. */ np(NP,H1,H2), vp(VP,H2,H3). s(S,H1,H3) --> /* * Note: "does not" is given sentential scope here. * That is, "Every man does not love a woman" is * taken to mean "It is not the case that every * man loves a woman." */ { S = sem:in:A, NP = sem:in:[drs([],[])|A], VP = sem:C, NP = sem:scope:C, NP = syn:index:D, VP = syn:arg1:D, NP = sem:out:[DRS,drs(U,Con)|Super], S = sem:out:[drs(U,[neg(DRS)|Con])|Super] }, np(NP,H1,H2), [does,not], vp(VP,H2,H3). s(S,H1,H2) --> { S = sem:A, NP = sem:A, NP = sem:scope:B, Adj = sem:B, NP = syn:C, /* Pass along the syntax. */ Adj = syn:C }, np(NP,H1,H2), [is], adj(Adj). s(S,H1,H2) --> { S = sem:in:A, NP = sem:in:[drs([],[])|A], NP = sem:out:[DRS,drs(U,Con)|Super], S = sem:out:[drs(U,[neg(DRS)|Con])|Super], NP = sem:scope:B, Adj = sem:B, NP = syn:C, Adj = syn:C }, np(NP,H1,H2), [is,not], adj(Adj). s(S,H1,H3) --> { S = sem:A, NP1 = sem:A, NP2 = sem:B, NP1 = sem:scope:B, NP1 = syn:index:A1, NP2 = syn:index:A2, NP2 = sem:scope: (in: [drs(U,Con)|Super] :: out: [drs(U,[(A1=A2)|Con])|Super]) }, np(NP1,H1,H2), [is], np(NP2,H2,H3). s(S,H1,H3) --> { S = sem:in:A, NP1 = sem:in:[drs([],[])|A], NP1 = sem:out:[DRS,drs(U1,Con1)|Super1], S = sem:out:[drs(U1,[neg(DRS)|Con1])|Super1], NP2 = sem:B, NP1 = sem:scope:B, NP1 = syn:index:A1, NP2 = syn:index:A2, NP2 = sem:scope: (in: [drs(U2,Con2)|Super2] :: out: [drs(U2,[(A1=A2)|Con2])|Super2]) }, np(NP1,H1,H2), [is,not], np(NP2,H2,H3). /* * Complex sentences. */ s(S,H,H) --> { S = sem:in: A, S1 = sem:in: [drs([],[])|A], S1 = sem:out:B, S2 = sem:in: [drs([],[])|B], S2 = sem:out:[S2DRS,S1DRS,drs(U,Con)|Super], S = sem:out:[drs(U,[ifthen(S1DRS,S2DRS)|Con])|Super] }, [if], s(S1,[],[]), [then], s(S2,[],[]). /* Empty hold lists enforce Coordinate Structure Constraint. */ /* * Statements, i.e., top-level, non-embedded sentence. */ statement(S) --> s(S,[],[]). /* * Questions. */ question(Q) --> { Q = sem:in:A, NP = sem:in:[drs([],[])|A], VP = sem:C, NP = sem:scope:C, NP = syn:index:D, VP = syn:arg1:D, NP = sem:out:[DRS,drs(U,Con)|Super], Q = sem:out:[drs(U,[query(DRS)|Con])|Super] }, [does], np(NP,[],H2), vp(VP,H2,[]). question(Q) --> { Q = sem:in:A, NP = sem:in:[drs([],[])|A], NP = sem:out:[DRS,drs(U,Con)|Super], Q = sem:out:[drs(U,[query(DRS)|Con])|Super], NP = sem:scope:B, Adj = sem:B, NP = syn:C, Adj = syn:C }, [is], np(NP,[],[]), adj(Adj). question(Q) --> { Q = sem:in:A, NP1 = sem:in:[drs([],[])|A], NP1 = sem:out:[DRS,drs(U1,Con1)|Super1], Q = sem:out:[drs(U1,[query(DRS)|Con1])|Super1], NP2 = sem:B, NP1 = sem:scope:B, NP1 = syn:index:A1, NP2 = syn:index:A2, NP2 = sem:scope: (in: [drs(U2,Con2)|Super2] :: out: [drs(U2,[(A1=A2)|Con2])|Super2]) }, [is], np(NP1,[],[]), np(NP2,[],[]). /* * Discourse * [a,discourse,is,a,series,of,consecutive,sentences, * separated,by,endpuncts,like,this,'.',note,that,an, * endpunct,is,required,after,the,final,sentence,'!'] */ discourse(D1) --> { D1 = sem:in:A, S = sem:in:A, S = sem:out:B, D2 = sem:in:B, D2 = sem:out:C, D1 = sem:out:C }, ( statement(S) ; question(S) ), endpunct, {!}, discourse(D2). discourse(D) --> [], { D = sem:in:A, D = sem:out:A }. /* * Endpunct (sentence terminator). */ endpunct --> ['.'] ; ['?'] ; ['!']. /******************************************************************** TEST SUITE ********************************************************************/ try(String) :- append(String,['.'],Discourse), tryd(Discourse). tryd(String) :- write(String),nl, Features = sem:in:[drs([],[])], phrase(discourse(Features),String), Features = sem:out:DRS, DRS = [Current|Super], display_drs(Current). test1 :- try([a,man,sees,a,donkey]). test2 :- try([a,donkey,sees,a,man]). test3 :- try([every,man,sees,a,donkey]). test4 :- try([every,man,sees,every,donkey]). test5 :- try([if,a,man,loves,a,woman,then,a,boojum,sees,a,bandersnatch]). test6 :- try([if,every,man,loves,a,woman, then,every,boojum,sees,a,bandersnatch]). test7 :- try([no,man,loves,every,woman]). test8 :- try([every,man,loves,no,bandersnatch]). test9 :- try([no,woman,loves,a,bandersnatch]). test10 :- try([no,woman,loves,no,man]). test11 :- try([a,woman,does,not,love,a,man]). test12 :- try([a,man,does,not,love,every,woman]). test13 :- try([every,boojum,does,not,see,every,bandersnatch]). test14 :- try([pedro,owns,a,donkey]). test15 :- try([pedro,loves,chiquita]). test16 :- try([a,man,sees,pedro]). test17 :- try([pedro,has,a,big,green,donkey]). test18 :- try([no,man,has,a,green,donkey]). test19 :- try([if,pedro,has,a,big,green,donkey,then,pedro,has,chiquita]). test20 :- tryd([a,man,loves,a,woman,'.',pedro,owns,a,donkey,'.']). test21 :- tryd([if,pedro,owns,a,donkey,then,pedro,owns,a,big,donkey,'.', chiquita,loves,a,man,'.', chiquita,does,not,love,pedro,'.']). test22 :- tryd([a,donkey,brays,'.']). test23 :- tryd([if,pedro,owns,a,donkey,then,every,donkey,brays,'.']). test24 :- tryd([pedro,is,big,'.']). test25 :- tryd([no,donkey,is,green,'.']). test26 :- tryd([every,big,green,donkey,is,old,'.']). test27 :- tryd([pedro,is,a,man,'.']). test28 :- tryd([every,big,green,donkey,is,an,old,donkey,'.']). test29 :- tryd([pedro,is,not,big,'.']). test30 :- tryd([every,donkey,is,not,big,'.']). test31 :- tryd([pedro,is,not,a,donkey,'.']). test32 :- tryd([every,donkey,is,not,a,man,'.']). test33 :- tryd([not,every,man,is,big,'.']). test34 :- tryd([if,not,every,man,is,big,then,pedro,is,not,big,'.']). test35 :- tryd([not,every,man,is,a,bandersnatch,'.']). test36 :- tryd([every,man,who,owns,a,bandersnatch,is,rich,'.']). test37 :- tryd([every,man,who,does,not,own,a,bandersnatch,that,brays,is,old,'.']). test38 :- tryd([a,man,who,owns,a,bandersnatch,that,does,not,bray,is,happy,'.']). test39 :- tryd([a,man,whom,a,bandersnatch,that,does,not,bray,loves,is,happy,'.']). test40 :- tryd([pedro,owns,a,donkey,'.',he,is,happy,'.']). test41 :- tryd([if,pedro,owns,a,donkey,then,he,is,happy,'.']). test42 :- tryd([every,woman,whom,pedro,loves,is,happy,'.']). test43 :- tryd([pedro,is,a,man,'.',chiquita,loves,him,'.']). test44 :- tryd([chiquita,is,a,farmer,'.',she,feeds,a,donkey,'.']). test45 :- tryd([every,farmer,who,owns,a,donkey,beats,it,'.']). test46 :- tryd([if,a,farmer,owns,a,donkey,then,he,beats,it,'.']). test47 :- tryd([is,pedro,a,man,'?']). test48 :- tryd([does,pedro,own,a,donkey,'?']). test49 :- tryd([does,every,farmer,own,a,donkey,'?']). test50 :- tryd([does,every,farmer,who,owns,a,donkey,beat,it,'?']). test51 :- tryd([chiquita,is,a,woman,'.',is,she,happy,'?']). test52 :- tryd([pedro,loves,chiquita,'.',does,she,love,him,'?']). test53 :- tryd([the,farmer,loves,chiquita,'.']). test54 :- tryd([does,pedro,see,the,donkey,'?']).