Research Report XXXXXXXXXX Artificial Intelligence Programs The University of Georgia Athens, Georgia 30602 Available by ftp from aisun1.ai.uga.edu (128.192.12.9) Series editor: Michael Covington mcovingt@aisun1.ai.uga.edu 1 Handling Constrained Clauses in Discourse Representation Theory William H. Smith Piedmont College Demorest, GA 30535 Artificial Intelligence Research Group The University of Georgia Athens, GA 30602 August 8, 1990 Introduction This report describes a Prolog program that transforms a natural language input into a knowledge base of Prolog clauses. The key element of the program is its ability to handle constrained clauses--embedded clauses whose truth evaluation is different from that of independent clauses. Consider sentence (0.1.a): (0.1.a) Bob, who is a farmer, believes that Carol regrets that she kissed Ted. (b) Bob is a farmer. (c) Carol regrets that she kissed Ted. (d) Carol kissed Ted. Clauses (0.1.b,c,d) are embedded in (0.1.a). (0.1.b) is not constrained; it is subject to the same truth evaluation that (0.1.a) is. (0.1.c) and (0.1.d) are constrained. (0.1.a) reports what Bob believes, but Bob may be wrong, so the truth of (0.1.a) should not depend on the truth value of (0.1.c). As we shall see in Section 3 of this report, (0.1.d) should be subjected to truth evaluation; the difference between (0.1.c) and (0.1.d) is determined by the difference between the constrainers believe and regret. The theoretical basis of this program is an extension of Discourse Representation Theory (Kamp 1981). Kamp proposed Discourse Representation Theory (DRT) as a bridge between the output of a syntactic parse and model theoretic semantics, a bridge that would combine "a definition of truth with a systematic account of semantic representations." (277) The DRT algorithm produces a representation that can be used to determine the truth conditions of a discourse. Subsequent research has 2 extended the original theory and has implemented it in computer programs. Section 1 of this report presents a description of the theoretical framework of DRT, a description that will further clarify what is meant by 'constrained clause' and 'truth contribution.' Section 2 examines suggested extensions to DRT that enable it to handle a wider range of sentences. Section 3 presents the linguistic theory underlying the difference between (0.1.c) and (0.1.d). In the remaining sections the report shifts its focus from theory to implementation. Section 4 describes the Prolog program of which this is an extension, and Section 5 describes the extensions to that program. Section 6 evaluates the success of the program and suggests other extensions that are needed. 1. DISCOURSE REPRESENTATION THEORY A model consists of two sets: a set of entities (the universe) and a set of properties of those entities and relations that hold among them. DRT seeks to provide a representation for discourse that will be suitable for truth evaluation in a model. DRT takes as input the output of a syntactic parse (e.g. the Logical Form of Government and Binding Theory) and produces a representation whose structure parallels that of the model. The central notion of DRT is the Discourse Representation Structure (DRS). A DRS K is a pair , where U is a set of reference markers (the universe) and C is a set of conditions (properties, relations, or complex conditions--negation, disjunction, or implication). The initial DRS, K0, contains none of the information in the discourse. As the discourse is processed, the DRS construction algorithm, taking the output of a syntactic parse as its input, produces a sequence of K' as it incorporates new material from the discourse into K. For example: (1.1) Bob saw a woman. K: At any point in the construction, the current DRS may be evaluated for truth in the model. Discourse truth in model theoretic semantics is determined by a mapping from a representation of the discourse (in DRT, a DRS) to the model, a mapping that preserves the properties and relationships expressed in the discourse. A discourse is held to be true in a model if there is a mapping such that the set of referenced items (the discourse referents in DRT) maps to a subset of the universe of 3 the model and each property or relation expressed by the discourse (the set of conditions in DRT) is true of the corresponding entities in the model. (For ease of exposition, I refer to the truth evaluation of a clause or discourse; it is in fact the DRS that is evaluated.) In DRT, each proper noun and each indefinite noun phrase (NP) in the input is taken to have existential quantification. (In a DRS, quantifiers are implicit; with exceptions to be noted shortly, all discourse referents are understood as being existentially quantified.) Thus, when the construction algorithm encounters a proper noun or indefinite NP, a new discourse referent is added to U (R1 and R2 in (1.1)). Each definite NP (including each pronoun) in the discourse must be coreferential with a discourse referent. Antecedent assignment is accomplished by finding an item in U that agrees with the anaphoric expression (for pronouns, an entity that agrees in gender and number). (It should be noted that the fragment of natural language that can be handled by current versions of DRT is quite limited, excluding plural and generic NPs.) Thus, (1.2) shows an extension of (1.1). (1.2) He kissed her. K: As in Pascal, := is an assignment operator and + indicates union of sets. Thus, the third line of (1.2) means that the new C is the union of the old C and the set {kissed(R1, R2)}. The basic theory would add R3, R4 to U, and then set them equal to R1, R2, respectively. A later "clean-up" operation would eliminate these redundant discourse referents by equating coreferential discourse referents. In the implementation to be described here, resolution of anaphoric relations is accomplished during the syntactic parse, so the redundancy does not occur. If U contains two or more possible antecedents, the conflict is resolved by selecting the most recent one. Consequently, U must be ordered, contrary to Kamp (1981) in which U is a set, and must be re-ordered each time an entity is referenced (see, for example, Goodman 1988). Kamp (1985) describes the DRS construction algorithm as "a set of rules that operate, in a roughly top-down manner, on the nodes of the parse tree," (2) converting those nodes into the conditions of C and, when appropriate, introducing new discourse referents into U. The basic version of DRT is directed toward the role of NP nodes in the discourse--their relationship to U. The special value of DRT is its ability to handle in- definite NPs that should not introduce new discourse referents. Consider the following extension of (1.2): 4 (1.3.a) She did not wear a ring. We must extend the algorithm, because as described so far it would produce something like (1.3.b): (1.3.b) K: The truth contribution of (1.3.a) to the truth of the discourse will depend on the existence in the model of a ring that she did not wear. But that is not what (1.3.a) means; (1.3.a) is true in the model only if there is no ring in the model such that she wore it. That is, (1.3.c) must be false: (1.3.c) She wore a ring. Thus, the truth evaluation of a negative clause demands a special representation. Kamp's solution is to add to C a sub-DRS for (1.3.a): (1.3.d) K: ) }> Discourse referents in U are visible to conditions in C1, but those in U1 are not visible to C. Since the sub-DRS is controlled by negation, its truth contribution is the opposite of the truth value of K1; that is, if K1 can be satisfactorily mapped to the model, the discourse is false. I shall speak of clauses such as (1.3.c) in (1.3.a) as 'constrained clauses' because their truth contributions to the DRS in which they are embedded are constrained, in this case by negation. (This definition of 'constrained clause' may seem to be at odds with that offered in the introduction, since (1.3.c) is not, in traditional terms, an embedded clause. Some syntacticians, however, treat negation as a 'higher predicate' whose argument is the embedded clause to be negated. (e.g. McCawley 1988)). Other constrained clauses handled by Kamp's original theory are those in disjunctions, implications, and universally quantified NPs. In each case, the constrained clauses are represented by sub-DRSs. The truth contribution of a disjunction is 'true' if one of the disjuncts evaluates to true; that of an implication is 'true' provided that in any mapping in which the antecedent is true the consequent is true also. An important feature of DRT is that it treats sentences containing universally quantified NPs as implications. The information within the universally quantified NP restricts the 5 set of entities in the universe to which the NP can refer, and the remainder of the sentence is the scope of the quantifier. For example, the scope of the subject NP is the VP, and the scope of the direct object is the verb. Kamp treats the information in the universally quantified NP as the antecedent of an implication whose consequent is the information in the scope of that NP. Thus, (1.4.a) is represented as (1.4.b). (1.4.a) Every sad man loves a pretty woman. (b) K: K2, K1: K2: }> The effects of sentence connectives as constrainers is uncomplicated, as they are taken directly from formal logic. The treatment of other constrainers is more complex, as will be seen when extensions to the basic theory are considered. 2. EXTENSIONS TO THE BASIC THEORY Events and Propositions The basic theory is confined to a very limited subset of natural language. In particular, it is limited to singular, non- generic NPs, to anaphoric reference (i.e. the referent is present in the discourse), and to sentences whose main verbs do not take propositions (i.e. DRSs) as arguments. Reducing the first two limitations requires a full theory of reference that must take into account grammar, pragmatics, and knowledge of the real world, and is beyond the scope of this study. Here we are concerned with reducing the third limitation. Guenthner et al. (1986) extend the basic theory by adding two new types of discourse referent: event markers and time markers. These researchers also include meaning rules in the DRS construction algorithm that assign an event marker to each verb and to each noun that refers to an action (e.g. accident). Each time reference (i.e. time of day or extent of duration) is assigned to a time marker. Events are temporally ordered with respect to each other and to time references: an event may precede or overlap another event or time, it may be given an argument expressing its duration, or it may be a subset of another event. The addition of event markers makes it possible for predicates to take DRSs as arguments. Guenthner et al. (1986) do not include any examples of such a use of event markers, but Guenthner (1987) does. In that article he also 6 makes a notational distinction between events, which advance the time of discourse, and situations, which do not. Spencer-Smith (1987) does not use event markers, but adds a different type of discourse referent, a proposition marker. This extension makes it possible to include embedded predicates, such as infinitival complements and beliefs, in the DRS: (2.1) Carol wants to kiss a rich man. K: }> The embedded DRS of (2.1) is an example of a constrained clause, in this case constrained by want. (2.1) may evaluate to true even if no such R2 exists in the model. (Note that this reading gives narrow scope to rich man; Carol does not know which rich man she wants to kiss.) Beliefs Kamp (1985) also explored the representation of beliefs. His treatment requires two further additions to DRT: internal and external anchors. Anchors are used to connect discourse referents to entities in the world. External anchors are ordered pairs, , that associate the two as they actually are, while internal anchors are DRS-like structures that associate items as a subject believes they are. The use of anchors makes it possible to represent propositions that are in fact contradictory but are not so in the subject's belief system because his internal anchors differ from the external anchors: 7 (2.2) Bob believes that Hesperus is pretty and Phosphorus is not pretty. External Anchors: , , Internal Anchors: L: K: }> }> The extension of DRT with internal and external anchors give the theory considerable power, but is far from giving it the power necessary to represent adequately the full range of meanings of natural language. It does not, for example, specify whose internal anchor is to be invoked. Asher (1986) combined the concepts of proposition markers and of anchors in order to handle the problem, again with considerable modification to DRT and the DRS construction algorithm. Asher dealt with the problem of Pierre, who, as a child in Paris, saw Londres--London--in a picture book, and who, as an adult, lives in a London slum. It is now reported that (2.3) Pierre believes that Londres is pretty and London is not pretty. Sentences like (2.2) and (2.3) have been a serious problem for traditional logic, which holds that the set of true sentences is closed under substitution of coreferential terms (SC), such as Londres and London. The belief cannot be added to the toplevel DRS because under SC it is contradictory in the model and its truth value is false, although it is actually a true report of Pierre's belief. The belief must somehow be constrained in a sub-DRS whose truth is evaluated according to Pierre's cognitive state. But the belief remains contradictory in a simple sub-DRS such as that used for (2.2). Asher made use of a proposition marker that refers to a sub-DRS rather than an entity, one that represents the content of the complement of believes. This sub-DRS, a 'delineated DRS', is more complex than those of the basic theory. It is augmented with DRS-like structure representing the cognitive state of the believer--entities and properties that are not explicit in the discourse but must be true in the possible world in which the belief is true. This internal anchor may contain a condition 8 that distinguishes between two referents that are coreferential in the model, as in Pierre's case, or vice versa. In addition, Asher argues that SC does not hold in natural language; two NPs that are coreferential but different in form convey different information and are not substitutable. In Smith (1989), I applied DRT, the basic theory augmented by the extensions suggested above, to a narrative that had been normed at sixth-grade comprehensibility in order to detect further extensions to DRT that would be necessary in order to represent adequately a natural language discourse. That study suggested the need for additional mechanisms for handling the truth contributions of constrained clauses; mechanisms that deal with the influence of the constrainer on the constrained clause and mechanisms that determine whether, on the basis of subsequent information, a constrained clause should be elevated to the toplevel. These topics are the focus of this study, and will be considered in the next section. 3. THE TRUTH-CONTRIBUTIONS OF CONSTRAINED CLAUSES Clearly, beliefs are constrained clauses; their truth evaluation is constrained by believe to a method such as that described by Asher. However, while Asher's procedure answers a number of problems when truth is considered from the standpoint of philosophical logic, it is rather awkward when truth is considered from the point of view of information retrieval. For an information retrieval system, truth may simply be the ability, given (2.3), to answer such questions as (3): (3.1.a) What does Pierre believe? (b) Does Pierre believe that London is pretty? Although Pierre's belief is contradictory, the report of that belief is not. Perhaps the user does not care that the answer to (3.1.a) is contradictory (the user may even want to know if it is contradictory); or that the answer to (3.1.b) is one of two possible answers. Furthermore, the software necessary to construct a possible world in which Pierre's belief is true (if such a program can be constructed at all) comes at a considerable cost in production time, program size, and run time, and the world it describes might be even less acceptable than Pierre's contradictory belief system. We turn now to a method by which constrained clauses can be handled, from an information retrieval point of view, by a much less elaborate method. Truth Evaluation in an Information Retrieval System From the information retrieval point of view, truth is what the user claims to be true; input is taken to be true unless it is constrained, as in (2.3) (unless, perhaps, it is 9 inconsistent with the knowledge base). However, constrained clauses are not always blocked from toplevel truth evaluation. I turn now to an examination of various constraining terms and their effects on truth evaluation. This examination is limited to constrained clauses whose truth value is available; that is, the event or state reported has already occurred or failed to occur. Consider the 'neutral' constrainer in (3.2): (3.2.a) Ted said that Bob kissed Alice. (b) Ted said, "Yecch!" (c) She does not kiss yuppies. (d) Ted was right. (3.2.a) is true if Ted uttered the constrained clause (or words to that effect), even if the user knows Ted to be a pathological liar. Thus, the constrained clause should not be evaluated for truth at all. The simplest representation of (3.2.a) would assign a discourse referent to the constrained clause in its surface form, without analysis, as is necessarily the case for (3.2.b). However, there are at least four reasons for representing the constrained clause as a sub-DRS, albeit a DRS that is shielded from truth evaluation: (3.3.a) The user might have applied SC to Ted's actual utterance. If the system includes a facility for calculating a confidence factor (i.e. How reliable is Ted?), it will be necessary to analyze the constrained clause in order to allow for SC in checking for corroboration. (b) (3.2.a) might be followed by (3.2.c). If the constrained clause has not been analyzed, the discourse referent for Alice will not be available as an antecedent for she. (c) If (3.2.a) is the first occurrence of either proper NP, a discourse referent for that entity should be added to the toplevel universe; that entity is 'pragmatically presupposed' by the proper NP (McCawley 1981). This addition can only be made if the constrained clause is first analyzed. (d) If (3.2.a) is sometime later followed by (3.2.d), provided by the user, the discourse referents and conditions for the constrained clause should be added to the toplevel DRS, and that addition should be based on the context available at the time of (3.2.a), excluding anything that might have been added by intervening sentences. While the necessary analysis could be carried out at the time of (3.2.d), it would be much simpler if it were done at the time of (3.2.a). 10 Types of Constrainers The procedure described above, which blocks the truth evaluation of the constrained clause, may, depending on the requirements of the information retrieval system, be satisfactory for a number of constrainers that report utterances or cognitive states, including the following: (3.4) SAY CLASS (OBJECT) say suppose allege believe deem assert assume charge fancy conclude maintain intimate deny conjecture (The list of constrainers in (3.4), as well as those lists that follow, is taken largely from Kiparsky and Kiparsky (1970), as is the analysis on which what follows is based.) Note that if a sentence whose main verb is deny is later confirmed, it is the negation of the constrained clause that must be added to the toplevel DRS. The same would be true of (3.2.a) followed by (3.2.d) with right replaced by wrong. Assuming this fact to be self-evident, I shall not make special note of other constrainers of this type. The representation described above will allow an infor- mation retrieval system to answer questions such as those in (3.1). However, there remains an implementation problem to be resolved. Should the system respond only when the constrainer in the inquiry is identical to that in the original input, or should it respond when one constrainer in (3.4) is replaced by another? If the answer is the latter, which constrainers are substitutable? The answer depends on the needs of the particular system, and will not be examined further here. A group of constrainers whose truth evaluation should be treated in the same fashion is illustrated in (3.5): (3.5) It seems that Bob kissed Alice. Constrainers such as seem question or hedge on the truth of their subjects, which are often extraposed, as in (3.5). Similar constrainers are shown in (3.6): (3.6) SAY CLASS (SUBJECT) seems is likely is possible appears is probable Kiparsky and Kiparsky point out the fact that some of these constrainers allow non-finite for-to clauses (e.g. 'for Bob to kiss Carol') as their subjects, but do not allow poss-ing (e.g. 'Bob's kissing Carol') subjects. I shall return to this fact shortly. 11 Many of the Say Class of constrainers have adverbial forms: (3.6.a) It is probable that Ted kissed Carol. (b) Ted probably kissed Carol. Although the two sentences in (3.6) are synonymous, the constrained clause in (3.6.a) is dependent while the same clause in (3.6.b) is independent. Nevertheless, synonymous clauses should be treated in the same manner; that is, the constrained clause should not be evaluated for truth in the toplevel DRS. The group of constrainers shown in (3.7) is syntactically identical to those in (3.6), but the truth contribution is quite different. (3.7) TRUE CLASS (SUBJECT) true happens certain chances sure false turns out These constrainers assert the truth (or falsity) of the constrained clause. Thus, the constrained clause should not be shielded from the truth evaluation of the toplevel DRS. The simplest representation of a sentence containing one of these constrainers would ignore the constrainer and add the representation of the constrained clause to the toplevel DRS. Such a representation would make it impossible to refer to the constrained clause (cf. 3.2.d), but such reference seems unlikely. If such references must be allowed, sentences containing those constrainers can be handled in the manner of (3.2.a) followed by (3.2.d). Note that if one of the True Class of constrainers appears in negated form, it is the negation of the constrained clause that is added to the DRS. (However, the negation of certain is a Say Class constrainer. The converse is true of possible.) A fourth group of constrainers, although syntactically identical to the Say and True Classes, makes a truth contribution that is different from either. (3.8) REGRET CLASS (SUBJECT) surprising exciting amuses matters significant relevant counts suffices tragic odd bothers makes sense These constrainers ('factives' for Kiparsky and Kiparsky) semantically presuppose the truth of their complement clauses. That is, the complement clause is held to be true, whether the constrainer appears in positive or negative, declarative or interrogative form. Therefore, the constrained clause should not be shielded from toplevel truth evaluation. In addition, these 12 constrainers have semantic content of their own, unlike those in the True Class. (e.g. The user may want to know what the signif- icance is.) It is thus necessary to assign a discourse referent to the constrained clause so that it can appear as an argument to the constrainer. These considerations suggest that a clause constrained by one of these terms should be represented twice, once as an independent sentence and once in the manner of a clause constrained by a Say Class constrainer. The fifth group of constrainers functions syntactically like the Say Class (Object), but makes a truth contribution like that of the Regret Class (Subject). (3.9) REGRET CLASS (OBJECT) regret forget (about) be aware (of) resent make clear bear in mind deplore ignore take into mind comprehend account/ care (about) grasp consideration These verbs also have semantic content, so discourse referents for the constrained clauses must be added to the toplevel DRS. These verbs allow the fact that and poss-ing complements, but not for-to complements (at least, not with presuppositional value). Some (regret, forget) have presuppositional value under equi-NP deletion, but others do not. Kiparsky and Kiparsky note that the truth contribution of a clause depends only on the immediate constrainer, no matter how deeply it is embedded: (3.10.a) Carol appears to believe that Bob regrets that he kissed Alice. (b) Bob kissed Alice. Thus, (3.10.a) presupposes (3.10.b), because it is constrained by regret, in spite of the fact that the intervening appear and believe are Say Class constrainers. The next class of constrainers is labeled 'indifferent' by Kiparsky and Kiparsky because the truth of the constrained clause may or may not be presupposed. (3.11) SUSPECT CLASS (OBJECT) suspect acknowledge announce emphasize anticipate admit report remember deduce With poss-ing complements, these verbs are factives, Regret Class constrainers. With finite and for-to complements, however, it is unclear whether they are Say Class or True Class constrainers. 13 It may have been noted that there is no list of True Class (Object) constrainers. This gap is particularly striking when one considers that two of the verbs in (3.7), certain and sure, can constrain object clauses. (3.12.a) It was certain that Bob kissed Alice. (b) Ted was certain that Bob kissed Alice. (c) Ted was certain of Bob's kissing Alice. (d) Bob kissed Alice. (e) I am certain that Bob kissed Alice. Sentence (3.12.a) asserts the user's belief that (3.12.d) is true, but (3.12.b) only asserts Ted's belief; the user may know Ted to be wrong. Sentence (3.12.c) is even worse; Ted may have believed that (3.12.d) had already occurred, or that it was potential. Thus, while these verbs are True Class (Subject) constrainers, they are Say Class (Object) constrainers. Almost paradoxically, this class shift holds even with a first-person subject. Sentence (3.12.e) seems to assert what (3.12.a) asserts, the user's belief that (3.12.d) is true in the model. However, the user's choice of (3.12.e) rather than (3.12.a) is a hedge on that assertion. Another complex group of constrainers is that shown in (3.13): (3.13) KNOW CLASS (OBJECT) know comprehend learn see understand realize When one of these verbs is used in a past tense, it is factive; the truth of its constrained clause is presupposed, regardless of the subject or the polarity (affirmative or negative). With a third-person subject, the constrained clause is presupposed in the present tense. (It is assumed here that the constrainer is provided by the user and is not his ironic quotation of the subject.) It is when the verb has a first-person subject in a present tense that the complexity arrives. In this case, the verbs in (3.13) must be treated on an individual basis. To do so, it will help to use the template in (3.14), where the blank is to be filled in by a (possibly negated) constrainer. (3.14) I __________ a. (that) Bob kissed Alice. b. (of/about) Bob's kissing Alice. c. (for) Bob (to) kiss Alice. The constrainer know allows (3.14.a,b). In either case, it is like certain: in the affirmative it is a True Class constrainer, but in the negative it shifts to the Say Class. As 14 in the case of certain, the poss-ing complement is not presupposed. In (3.14.b), comprehend and understand presuppose their complement clauses. The verb understand allows (3.14.a), but only in the affirmative, in which case it is a Say Class constrainer, with a meaning something like "Someone said that Bob kissed Alice." The constrainer realize is acceptable only in (3.14.a) and presupposes its complement clause; thus, if it is negated, it denies its own presupposition and the sentence makes no sense. The simple present tense of learn does not work in (3.14) except in special contexts (e.g. an actor referring to his role as himself), and the present progressive requires that the learning process be extended, so that what is learned is (usually) not a simple fact. While in some special contexts the constrained clause is presupposed, it is more practical to treat first-person present tense learn as a Say Class constrainer. The verb see is ambiguous between an act of perception and a state of cognition. In the former case it allows (3.14.c) (without prepositions) and is a True Class constrainer. In (3.14.a), see reports a cognitive state; in the affirmative it acts as does understand, but in the negative it is a Say Class constrainer. This section has examined clauses whose truth contribu- tions to a DRS are constrained by a certain group of predicates (verbs and adjectives). It has found five classes of constrainer, some with subclasses according to whether the constrained clause is the subject (perhaps extraposed) or the object of the predicate: (3.15.a) SAY CLASS: The constrainer makes no claim about the truth contribution of the constrained clause, so that clause should be shielded from toplevel truth eval- uation. However, the clause should be identified by a discourse referent because it may later be confirmed or contradicted. (b) TRUE CLASS: The constrained clause is added to the toplevel DRS because the constrainer asserts the truth of its complement. (If the constrainer is negated, it is the negation of the constrained clause that is added.) Such clauses might not require discourse referents, although no harm is done if referents are assigned. (c) REGRET CLASS: The constrainer presupposes the truth of the complement clause, so that clause is added to the toplevel DRS. This addition is independent of the form of the matrix clause (i.e. affirmative- negative, declarative-interrogative). 15 (d) SUSPECT CLASS: Presupposition depends on the syntactic form of the constrained clause. poss-ing complements are presupposed, but other complements are unclear about presupposition and are to be treated as those under Say Class constrainers. (e) KNOW CLASS: The constrained clause is presupposed unless the constrainer is first-person, present tense. In the latter case, each verb requires its own treatment. It was noted that some True Class constrainers have corresponding adverbs. Other adverbs can act as constrainers, and their truth contributions must be examined. Modal auxiliaries and verbs with similar semantic value (e.g. ought to, want to) also require such analysis. Associated with the modal class is the case of constrained clauses whose truth is not yet known; should they be left unevaluated, or should they become 'demons' whose truth must eventually be evaluated? These questions remain to be answered. In the next section we examine a computer implementation of DRT that is able to handle certain of the constrained clauses described here. 4. AN IMPLEMENTATION OF DRT In this section and the next we describe a computer implementation of DRT. It takes as input a 'discourse' of one or more English sentences, parses the input and constructs a DRS for it, and then asserts the set of conditions in that DRS to a Prolog knowledge base. The language it accepts includes both the types of sentence described in Section 2 and a subset of those described in Section 3. Specifically, it handles noun clause complements of a selected group of Say, True, and Regret Class Constrainers. This implementation is an extension of From English to Prolog via Discourse Representation Theory (Covington, Nute, Schmitz, & Goodman, 1988; henceforth CNS&G). That program is "a set of techniques for translating the discourse representation structures of Kamp (1981) into semantically equivalent clauses in a slightly extended form of Prolog. (1)" That program is in turn an extension of An Implementation of Discourse Representation Theory (Covington & Schmitz, 1988; henceforth C&S), "a program that constructs discourse representation structures from ordinary English input. (1)" It, in turn, is an extended version of the program described in Johnson & Klein (1986). (The extension to be described in Section 5 of this report is designated CONSTRAIN. Note that the abbreviations C&S and CNS&G will be used to refer both to the programs and to the documents describing them.) 16 Phrase Structure Rules C&S is a top-down parser, written in definite clause grammar (DCG) notation, for a phrase structure (PS) grammar. The PS rules are augmented with a hold mechanism that allows the parsing of certain empty categories, and with a feature structure that allows syntactic and semantic information to be passed from one node of the parse tree to another. Although Kamp employs a top-down procedural algorithm, CNS&G view the PS-to-DRT mapping as a static relation defined in terms of unification of feature structures. (The CNS&G view follows that of Johnson & Klein (1986) and is in the spirit of Zeevat (1989)). The addition of a hold mechanism and a feature structure, although necessary to give the program its power, can make the description of the parser complicated; the reader who is only concerned with the syntactic rules is likely to be confused by the presence of the feature unification rules. To avoid that confusion, this description will be presented in three passes. The first pass will treat the parser as if it consisted of DCG rules only, the second will add the hold mechanism to that description, and the final pass will treat the feature structure. Because of the interaction between the three, this neat simplification is not entirely possible. For the first two passes the reader must accept without explanation the fact that the semantic features carry the DRS for the portion of the discourse already processed. C&S accepts discourses that conform to the PS rules shown below. (Parentheses indicate optional elements; the parser actually has separate rules for these possibilities. Words in brackets are terminal symbols.) (4.1) discourse --> statement, (discourse). discourse --> question, (discourse). statement --> sentence. question --> [does], np, vp. question --> [is], np, adj. question --> [is], np, np. sentence --> np, vp. sentence --> np, [does, not], vp. sentence --> np, [is], adj. sentence --> np, [is, not], adj. sentence --> np, [is], np. sentence --> np, [is, not], np. sentence --> [if], sentence, [then], sentence. The PS rules for VP and Adj are straightforward, as is shown in (4.2). (Form is a variable representing a terminal symbol.) 17 (4.2.a) vp --> v, np. (b) vp --> v. (c) v --> [Form]. (d) adj --> [Form]. As we shall see below, syntactic features prevent (4.2.c) from selecting a transitive verb for (4.2.b), or an intransitive for (4.2.a). While the rules for VP are essentially those of Chomsky (1965), the NP rules make use of X-bar theory. NP is bar-3, and numeric suffixes indicate the other bar levels. As is the case for VP, syntactic features subcategorize Form for lexical insertion--proper or common noun. (Pronoun is a notational device; each gender of pronoun requires a separate rule. C&S is not sensitive to pronoun case.) (4.3.a) np --> n. (Proper noun) (b) np --> [Pronoun]. (c) np --> []. (Empty category) (d) np --> det, n2. (e) n2 --> n1. (f) n2 --> n1, relcl. (NP with relative clause) (g) n1 --> n. (h) n1 --> adj, n1. (i) n --> [Form]. Rules (4.3.c) and (4.3.f) will be discussed with the hold mechanism. Rule (4.3.b) searches the incoming DRS for the most recent discourse referent that matches Pronoun in gender. (Remember that this version of DRT does not handle plural NPs.) Rule (4.3.h) is recursive, so n1 may contain any number of adjectives. In order to handle empty categories, C&S adds to each phrasal rule two arguments, an input and an output hold list. When rule (4.3.f) is applied, the discourse referent of n1 is placed at the head of the input list and that list is passed to relcl. When (4.3.c) is applied while processing relcl, the first referent on the hold list is removed and assigned to the empty category. This procedure insures that empty categories are instantiated on a last-in-first-out basis. The rules for discourse, statement and question require that the hold lists be empty, since empty categories cannot be bound across sentence boundaries. Unification of Feature Structures The C&S parser incorporates a unification based grammar (Schieber 1986) that passes feature structures from one node of the parse tree to another. Since features are passed by means of unification, it is possible to pass a feature from one node to 18 another before it has been instantiated. For example, rule (4.2.a) unifies the discourse referent of np with the second argument of v before either (4.2.c) or (4.3) is applied. The use of feature structures is facilitated by the use of the GULP extension to Prolog (Covington 1987). GULP makes it possible for the programmer to refer to features by name, rather than by position in the feature structure. In consequence, a parser written in GULP is much easier to read than is one written in standard Prolog notation. The C&S parser uses syntactic features that constrain the parse procedure and semantic features that construct DRSs during the parse procedure. The syntactic features employed by C&S are syn:index, syn:class, syn:arg1 and, syn:arg2. syn:index is a unique integer that is generated for each noun in the discourse; its value is the discourse referent that is used to bind pronouns and empty categories. syn:arg1 and syn:arg2 are also integers; they are unified with the syn:index features of the nouns in a sentence and become the arguments of its predicates. The syn:class feature of a noun (proper or common) or verb (transitive or intransitive) is a subcategorization that serves to constrain the parse procedure, as was noted above. The semantic features are sem:in, sem:out, sem:res:in, sem:res:out, sem:scope:in, sem:scope:out. GULP makes it possible to address an individual feature or a bundle of features; for example, a variable may be bound to sem:res:in, to sem:res (both in and out are bound), or to sem (all features are bound). Features may be cross-unified, so that sem:res of one node may be bound to sem of another node. The value of a semantic feature is a list of one or more structures of the form drs(U, Con), where U is a list of discourse referents and Con is a list of conditions. The first drs/2 on the list is the representation currently being processed. Not all of the features are instantiated for every node; in fact, most nodes use only the sem:in/out features. Each parent node instantiates the sem:in of its daughter(s) to the DRS for the portion of the discourse already processed. The daughter then adds its own discourse referents to U and its conditions to Con, and returns the expanded drs/2 as sem:out to its parent. (The initial sem:in for a discourse is [drs([], [])].) Consider, for example, (4.4), which gives the full form of (4.2.d) along with the rules that it calls. 19 (4.4.a) adj(Adj) --> [Form], {adjective_features(Form, Adj)}. (b) adjective_features(Form,Adj):- append(Semantics, Con, NewCon), Adj = syn: (index:I) :: sem: (in : [drs(U, Con)| Super] :: out: [drs(U, NewCon)| Super]). (c) adjective(big, lambda(I, [big(I)])). The N1-rule that calls (4.4.a) unifies the syn features of Adj with those of the noun that the adjective modifies. It also unifies the sem:in feature of Adj with the appropriate feature of that noun (which feature it is unified with depends on the calling rule). The entire feature structure of Adj is then passed to (4.4.b). Rule (4.4.b) unifies I with the syn:index feature of the modified noun and passes it to (4.4.c), which in turn unifies it with the argument of Form, the adjective being processed. The resulting structure is appended to Con, the condition list on the input DRS, and the result, NewCon, is passed in the output DRS. The sem:res and sem:scope features are needed in order to handle universally quantified NPs. DRT treats a sentence with a universally quantified NP as an implication. The antecedent, the sem:res feature, consists of the information in the NP itself, information that restricts the set to which the NP refers. The consequent, the sem:scope feature, consists of the information in the remainder of the sentence, the scope of the NP. Scope is determined by the left-to-right ordering of NPs; the verb falls within the scope of all NPs, and the object NP is within the scope of the subject NP. C&S follows Johnson & Klein (1986) in treating the determiner as the key element in determining quantification. Thus, the sem of a sentence is the sem of the subject NP, which in turn is the sem of the determiner of that NP. Consider (4.5). 20 (4.5) 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] }. Let us assume that (4.5) is called by an NP-rule that is called directly by an S-rule (i.e. the NP in question is the subject of the sentence), and let us trace the feature unifications through the parse tree. At this point, the only feature that has been instantiated is sem:in (A in rule (4.5)), which contains the DRS for the preceding portion of the discourse. The NP-rule unifies its entire sem feature with that of Det, and the S-rule likewise unifies its sem feature with that of NP. The S-rule also unifies the sem of VP with the sem:scope of NP, from which it is passed to the sem:scope of Det. The NP- rule also unifies the sem of N2 with sem:res of Det. Rule (4.5) unifies A with sem:in, the incoming DRS list, and conses to A a DRS with empty universe and condition lists. The resulting list becomes sem:res:in, and therefore sem:in of N2. The N2-rule fills those empty lists and returns them as B, the sem:res:out of Det. (4.5) then prefixes an empty DRS to B, producing the sem:scope:in of Det and NP, and the sem:in of VP. The VP-rule fills the empty DRS and returns it as sem:scope:out of NP and Det. (4.5) extracts from sem:scope:out the first three DRSs: Scope, the now filled DRS from VP, Res, the now filled DRS from N2, and the first DRS in A (the input DRS list), drs(U, Con). Finally, Res and Scope are made arguments to the functor ifthen, which is prefixed to Con. The result is the sem:out of Det, NP, and S. Rule (4.5) is more complicated than most of the C&S rules, but all phrasal rules work in the same general fashion. The reader is referred to C&S for complete specification of the grammar; here we are concerned with the extensions to that program necessary in order to handle constrained clauses. Prologization of a DRS CNS&G adds to C&S procedures that translate the DRS in the sem:out feature of a discourse into Prolog clauses (Prologization) and then assert/process those clauses. Again, we are concerned primarily with those portions that must be modified or extended for the present implementation. The reader is referred to CNS&G for a complete specification of that program. 21 Before translating the set of conditions of the output DRS into Prolog, two "clean-up" steps must be performed. The lexical insertion rules of the parser provide two conditions for each noun in the discourse: the property denoted by the noun and the gender of the noun. The latter is needed only for anaphora resolution and is discarded before that set is processed. The second clean-up step involves unifying equated discourse referents. The original C&S parser assigns to each noun a unique integer, even in sentences such as (4.6): (4.6) Pedro is a farmer. The parser would then add a condition that equates the discourse referent of Pedro with that of farmer. The parser in CNS&G is modified to defer the assignment of integers to discourse referents to the Prologization module. That delay makes it possible to unify the discourse referents for (4.6) so that only one integer is assigned to them. With that unification accomplished, the universe of the DRS is no longer needed, and Prologization converts the list of properties/relations in the conditions into a list of Prolog clauses. Prologization works its way through the list of conditions and produces a new list that is suitable for asserting or querying. If a condition is a simple property or relation, the output of a lexical rule, it is simply added to the new list. If the condition is query(DRS), DRS itself has to be cleaned up, Prologized, and converted into a conjunction of clauses. If the condition is ifthen(DRSA, DRSC), DRSA (the antecedent) and DRSC (the consequent) must be cleaned up and Skolemized before they can be Prologized and converted into conjunctions of goals. Skolemization involves binding each uninstantiated variable in DRSC that does not appear in DRSA to a list whose head is a unique integer and whose tail is the universe of DRSA. Skolemization insures that such variables have existential import and narrow scope. Processing Prologized Clauses The output of Prologization is a list of clauses, each in one of the following forms: (4.7.a) Clause (b) neg(Clause) (c) (ClauseList1 ::- ClauseList2) (d) query(Clause) Processing (4.7.a) in the assert/query module is a simple matter of asserting Clause. CNS&G does not support negation; (4.7.b) is processed simply by noting that negation is not supported. The symbol ::- in (4.7.c) is a functor corresponding roughly to :- in 22 Prolog; processing involves converting the list of clauses into a conjunction of Prolog terms and asserting them. Similarly, Clause in (4.7.d) is converted to a conjunction of Prolog terms and called, and the result is reported to the user. Actually, CNS&G does not assert or query anything; it simply announces what it would do if it did. One of the first extensions to that implementation made by CONSTRAIN is to make the processing step work. In essence, this extension is a matter of making the program do what the CNS&G program says it would do. In the case of (4.7.b), Clause is not converted to a conjunction of terms; it remains a list, the single argument to neg. This treatment of negation is rather cursory, but the treatment of negation is not the focus of this study. CONSTRAIN extends the C&S grammar to include disjunction, to which the processing step pays similar lip service. This limitation is due to the fact that a disjunction such as (4.8.a) is not a Horn clause and cannot be represented directly in Prolog (although a disjunction may appear in the body of a rule). (4.8.a) could be represented as (4.8.b) and (4.8.c), but it would be unwise to do so before the details of neg/1 are worked out. (4.8.a) p OR q (b) p ::- neg(q) (c) q ::- neg(p) (d) query(p) Further extensions to the grammar require more significant refinement of the assert/query module especially in the case of questions; we shall return to these after examining the extensions to the parser. 5. EXTENDING THE IMPLEMENTATION OF DRT CONSTRAIN is divided, for ease of development, into eleven modules: (5.1) DRT_LOAD.GLP DRT_UTIL.GLP DRT_PS1.GLP DRT_PS2.GLP DRT_PS3.GLP DRT_LEX.GLP DRT_RED_GLP DRT_PRO1.GLP DRT_PRO2.GLP DRT_TRY.GLP DRT.TEST.GLP 23 DRT_LOAD loads the program. Files that include feature structures make use of the GULP load/1 command, which converts GULP feature notation into Prolog form. Those that do not use feature structures are consulted because that procedure is faster. DRT_LOAD also defines the goal loadred/0, which is used to load the lexical redundancy rules in DRT_RED, a process that must be repeated every time the knowledge base is cleared with newkb/0. Placing all of the load commands in one file facilitates relocating the program. If, for example, the program is to be run from the A: drive, only DRT_LOAD need be edited. DRT_UTIL contains general utility routines, such as list manipulation procedures, and procedures for displaying a DRS in a readable form. DRT_PS1, DRT_PS2, and DRT_PS3 contain the phrase structure rules. DRT_PS1 contains lexical insertion rules: rules that make direct calls to the lexicon (DRT_LEX). DRT_PS3 contains rules that deal with whole clauses (discourse, question, statement). DRT_PS2 contains rules that rewrite intermediate structures. DRT_LEX and DRT_RED contain the lexicon. The former contains the lexicon proper, while DRT_RED contains lexical redundancy rules, such as the rule that allows the program to infer that Bob is a man. DRT_PRO1 and DRT_PRO2 contain the rules that apply the DRS output by the parser to a Prolog knowledge base. DRT_PRO1 contains the Prologization module that translates the conditions of the DRS into Prolog clauses, and DRT_PRO2 contains the assert/query module that asserts these clauses to the knowledge base or calls them as queries to that knowledge base. DRT_TRY and DRT_TEST contain the user interface. DRT_TRY contains the rules that accept an input and send it to the program for processing, while DRT_TEST contains a test suite that calls DRT_TRY for processing. Knowledge Representation Most of the changes to C&S involve the addition of PS rules to DRT_PS2 or DRT_PS3. These additions, of course, entail concomitant modifications to the other modules. These modifications, however, are based on a more fundamental modification, a change in the form of knowledge representation in DRT_LEX. In Kamp's version of DRT, conditions are represented as predicate-argument structures: Pred(Arg) or Pred(Arg1, Arg2). Pred is the natural language word (noun, verb, or adjective), and Arg is a discourse referent. C&S follows that representation, with one modification: rather than being treated as predicates, 24 proper nouns are second arguments to the predicate named/2. Thus, (5.2.a) is represented by the conditions in (5.2.b). (5.2.a) Bob kisses Alice. (b) [named(1, bob), named(2, alice), kiss(1, 2)] This representation poses several problems for the design goals of CONSTRAIN: First, with such a representation it is awkward to distinguish between events and states. Although that distinction plays a relatively minor role in this implementation, it could play a major role in an extension that incorporates Guenthner's (1987) proposals. Second, as was noted in Section 3 of this report, some constrainers behave differently depending on the tense of the sentence, so it is necessary to include tense in the representation. It would, of course, be possible to add an argument for tense to the structure shown above, but such a solution would be, at best, unesthetic. Third, in order to query a knowledge base using the format shown above, it is necessary to know the predicate in advance. One can ask who Bob kisses, but one cannot ask what Bob does. Finally, the use of redundancy rules is very awkward with this format. Given (5.3.a), one would like to get an affirmative response to (5.3.b). (5.3.a) Bob knows that Ted kissed Alice. (b) Does Bob believe that Ted kissed Alice? Using the knowledge representation in (5.2.b), it is necessary to have a separate rule for each verb that entails believe. In order to overcome these difficulties, this program reifies natural language predicates so that they become arguments to Prolog predicates. (This, in effect, is the reverse of Kamp (1981), who uses proper nouns as predicates.) Thus, the conditions in a DRS have one of the four forms in (5.4). (5.4.a) named(Index, Name) (b) isa(Noun, Index) (c) event(Tense, Event, [Arg1|Rest]) (d) state(Tense, State, [Arg1|Rest]) Event is an action verb, while State is a stative verb or an adjective. Representing the argument(s) to a natural language predicate as a list makes it unnecessary to have separate rules for addressing one- and two-place predicates. Representations (5.4.a,b) are adequate for the current implementation, which assumes that the name and/or class of an entity does not change during the time covered by a discourse. 25 If the program is to cover greater periods of time, tense arguments must be added to these predicates in order to account for (5.5.a, b), for example. (5.5.a) Bob was a boy. (b) Bob is a man. For affirmative statements, the addition of time reference to the knowledge representation requires, at first glance, only a simple modification of the lexical rules. That is, the C&S rule in (5.6.a) need only be changed to that in (5.6.b) and an additional rule be added for saw. (5.6.a) transitive_verb(sees, lambda(A1, A2, [see(A1,A2)])) (b) transitive_verb(sees, lambda(pres,A1, A2, [event(pres, see, [A1,A2])]) For negatives and questions, however, tense is determined by the form of the auxiliary, not that of the main verb. It is necessary, therefore, to add a syntactic feature, syn:tense, to the GULP feature structure in order to pass tense from the clause-level rule to the lexical rules. Thus, for example, the question rule of (4.1), repeated as (5.7.a), is modified to the form of (5.7.b). (For clarity of exposition, hold arguments are not shown, and only those feature unification rules that are relevant to the present discussion are displayed.) (5.7.a) question(Q) --> [does],np(NP),vp(VP). (b) question(Q) --> {DO = syn:tense:Tense, VP = syn:tense:Tense, NP = syn:tense:Tense}, do(DO), np(NP), vp(VP). (5.7.b) requires the addition of a lexical insertion rule for do and lexical rules for do and does. The variable Tense is bound in the do rule, and its value is passed, by way of VP, to the lexical rule for the verb. Similar modifications are needed for the PS rules that include the copula is, passing tense to the subject complement. (5.7.b) does not pass syn:tense only to VP; it also unifies that feature with the corresponding feature in NP. Although nouns do not have tense (at least, in the present system, but see the discussion of isa/2 above), nouns may be modified by attributive adjectives--states that require tense arguments--which receive their tense from the matrix clause. Thus, every clause-level rule must pass a tense feature to its subject, and a VP rule must pass that feature to the direct object. 26 Even within the limits noted above, the addition of time reference to the knowledge representation introduces a further difficulty: the frame problem. Given that a state obtained in the past, does it continue into the present? For the human processor of natural language, the frame problem is rarely a problem. He knows which states can be assumed to be permanent (in the absence of evidence to the contrary) and which can be assumed to be momentary. For those states that fall in between, he is able to assign a probable length of duration. This assignment is based on real-world knowledge of the state and the participants. Acquiring and programming such knowledge, however, is a daunting problem for artificial intelligence. As is the case for negation, CONSTRAIN adopts a simplistic approach: a state that was true in the past remains true in the present unless its negation in the present has been asserted. This approach is encoded in a meaning postulate in the file DRT_RED: (5.8) state(pres, Verb, Args) :- state(past, Verb, Args), not neg([state(pres, Verb, Args)]) Proper Nouns A further extension that is independent of processing constrained clauses is the treatment of proper nouns. Kamp (1981) assigns a discourse referent to each proper noun, and then equates those referents that are arguments to the same name; thus, there can be only one individual for each name. CNS&G take the opposite approach, allowing for more than one individual with a particular name. Each proper noun is assigned a unique integer, and there is no way to show that two instances of Bob refer to the same individual. CONSTRAIN takes a middle road. Within a discourse (a list of words and punctuation marks), all instances of a proper noun are assumed to refer to the same individual. The first rule for a proper noun treats it as a pronoun, seeking a match in the input universe. If a match is found, the new instance is assigned the same discourse referent; otherwise a new discourse referent is generated. Between discourses that apply to the same knowledge base, however, the program allows for the possibility that a new instance of a name refers to a different individual. Before the input string is sent to the parser, the rule preprocess/2 creates a list of the proper nouns in the input, eliminates duplication, and queries the user about each of the names that appears in the knowledge base. If the user responds that this is the same (i.e. last mentioned) or the previous individual of that name, the ap- propriate named/2 and gender/2 propositions are placed in the initial DRS, K0; otherwise the parser will generate a new discourse referent for the name. To allow correct application of 27 this procedure, when the assert/query module of DRT_PRO2 encounters a named/2 clause it first retracts that clause, if it is present in the knowledge base, and then adds it with asserta/1 to insure that it will be the next such clause to be accessed. (Note that pronominal anaphora can only be resolved within a discourse. In order to address a discourse referent in the knowledge base, it is necessary to refer to that individual by name.) Answering a Query A final modification to CNS&G that is necessary for the handling of constrained clauses but also applies to other clauses is an extension of the mechanism for querying the knowledge base. A query in CNS&G can only ask a yes/no question: given (5.9.a), one may query (5.9.b), but not (5.9.c,d). (5.9.a) Bob kissed Carol. (b) Did Bob kiss Carol? (c) Who kissed Carol? (d) Whom did Bob kiss? The first problem is to find a place to put the answer. The CNS&G program would handle questions by converting the list of queried propositions to a conjunction in the Prologization step and passing that conjunction to assert_or_process/1, That predicate in turn calls test(Goal, Result) and prints Result. test/2 uses the built-in predicate call/1 to test that conjunction. Result is bound to 'yes' if the call succeeds and 'no' if it fails. The first step in this extension to that program is to expand the possibilities for Result. test(Goal, Result), after displaying the goal that is being queried, calls test_list(Goal, Result). If the latter call fails, Result is bound to 'INSUFFICIENT DATA'; otherwise it returns the value assigned by test_list/2. test_list/2 tries three methods for assigning a value to Result. The first method is that of CNS&G, converting the list of propositions to be queried into a conjunction and calling that conjunction; if the call is successful, Result is bound to 'AFFIRMATIVE.' The next method checks the knowledge base for neg(Goal); if that check succeeds, Result is bound to 'NEGATIVE.' Thus, this implementation replaces Prolog's negation-as-failure with true negation. However, this procedure is not complete; a query will return 'NEGATIVE' only if an identical list of propositions exists as an argument to neg. Consequently, the response to (5.10.b) will be 'INSUFFICIENT DATA.' 28 (5.10.a) Bob did not kiss a woman. named(p0, bob), neg([isa(X, woman), event(past, kiss, [p0, X])]) (b) Did he kiss a pretty woman? query([isa(Y, woman), state(past, pretty, [Y]), event(past,kiss,[p0, Y]) ]) If neither of the above methods succeeds, test_list/2 enters a recursive loop that calls query(Goal, Result) on the head of the list of queries and than calls test_list/2 on the remainder of the list. This recursion is necessary in order to handle wh-questions. At first glance, the treatment of wh-questions might seem a trivial matter. One need only leave the discourse referent for the interrogative word unbound, so that query/2 will seek to bind it. However, the CNS&G parser leaves the discourse referents of all common nouns unbound until the clean-up step is reached, at which point it is impossible to distinguish the referents that should be bound from those that should remain free. To overcome this difficulty, the CONSTRAIN parser unifies the pertinent syn:arg with the atom wh. A query containing wh will not unify with any clause in the knowledge base, so the first two methods for test/2 will fail for such a clause. (Note that the treatment of interrogative who/who is quite distinct from that for relative who/whom, which unifies the syn:index of the relative pronoun with that of its antecedent.) When query/2 encounters such a clause, it uses the built-in predicate set_of/3 on a copy of the clause with wh replaced by a variable. It then uses get_id_list/2 to produce a list of names of those discourse referents or, if they are not named, of their classes. Result is then bound to that list. The recursion on test_list terminates when one of three conditions is met: (5.11.a) The input list is empty and Result is bound. (b) The input list is empty and Result is free (it is neither 'NEGATIVE' nor a discourse referent). Result is then bound to 'AFFIRMATIVE.' (c) The input list can be satisfied by one of the non-recursive methods. Result is then bound to that Result. Note that if Result is bound by query/2, test_list(Goal, Result) cannot unify with the non-recursive methods. 29 Constrained Clauses: Say Class The extensions to CNS&G described above provide the tools necessary for the addition of constrained clauses to the language handled by the extended program. The first step in adding such clauses is the development of a representation of the embedded clause, an implementation of the proposition markers used by Spencer-Smith (1987) and Asher (1986). The representation chosen is an additional knowledge base predicate, prop(Index, Clause). This structure is created by the following PS rule: (5.12) nouncl(NC, [], []) --> { NC = syn:index:Index, NC = sem:in:A, S = sem:in:[drs([],[])|A], S = sem:out:[DRS,drs(U, Con)|Super], NC = sem:scope:in:[drs([Index|U], [prop(Index,DRS)|Con])|Super], NC = sem:scope:out:DRSList, NC = sem:out:NewDRSList }, [that], s(S, [], []), { add_to_topmost_drs(Index, [prop(Index, DRS)], DRSList, NewDRSList) }. The hold lists in (5.12) must be empty in order to prevent an empty category's referring to an element outside its governing category. Like the rules for quantified NPs and negated sentences, (5.12) first conses an empty DRS to the input DRS; that DRS is filled in as S is processed, becoming DRS. The remaining NC unification rules convert Index and DRS into a prop/2 structure and create the output. After the DCG rule has instantiated those bindings, the rule add_to_topmost_drs/4 elevates Index and the prop/2 structure to the toplevel DRS. The nouncl rule is called by the rules VP --> V NC and S --> it BE (not) Adj NC, which bind the syn:class feature of V to 'mental.' The 'mental' feature contrasts with the features 'transitive' and 'intransitive,' in the case of verbs, and 'common,' in the case of adjectives. The syn:class feature in a lexical insertion rule determines which lexical rule will be called, and the distinction must be reflected in the lexicon. These modifications allow the program to handle clauses constrained by the Say Class of constrainers. Such clauses are simply added to the DRS and are shielded from further truth evaluation. Thus, the program at this point will properly handle the discourse in (5.13). (Responses to queries are shown below the queries.) 30 (5.13.a) Bob said that Ted kissed Alice. (b) Did Bob say that Ted kissed Alice? AFFIRMATIVE (c) Who said that Ted kissed Alice? bob (d) Did Ted kiss Alice? INSUFFICIENT DATA (e) What did Bob say? event(past, kiss, [ted, alice]) Regret Class Constrainers In order to extend the set of constrainers that the program handles to the Regret Class, the PS rule that calls the nouncl-rule must call check_factive(NC, X) after the DCG rule completes feature bindings. NC is the feature structure of the constrained clause (actually, only the sem:out feature is used), and X is that of the constrainer's category (verb or adjective). check_factive/2 tests the constrainer with factive(Constrainer), a redundancy rule in DRT_LEX. If the test succeeds, add_to_topmost_drs/4 elevates the discourse referent(s) and condition(s) of the constrained clause to the toplevel DRS and the sem:out feature of X is bound to the result. If the test fails, the sem:out feature of X is bound to that of NC. Crucially, check_factive/2 makes no distinction between positive and negative constrainers, although different rules are necessary to handle the two structures. Given this addition to the program, if say in (5.13) is replaced by regret, the response to (5.13.c) is AFFIRMATIVE. Thus, the program is able to handle Regret Class constrainers properly. Since the Know Class differs from the Regret Class only for first-person subjects, and since this parser does not handle first-person NPs, the latter class is subsumed by the former; in fact, three of the five factive constrainers included in the program are effectively in the Know Class. The parser is also limited to constrained clauses in the that S form, and Suspect Class constrainers are factive only in the poss-ing form, so that class is omitted from consideration. Implicational relationships between know on the one hand and think and believe on the other are captured in lexical redundancy rules in DRT_RED. Another redundancy rule takes a rather optimistic view of learning: that if someone has learned something, he knows it. With these additions, the program will handle the following discourse: 31 (5.14.a) Carol learned that Bob kissed Alice. (b) Did Bob kiss Alice? AFFIRMATIVE (c) Does Carol know that Bob kissed Alice? AFFIRMATIVE (d) Does Carol believe that Bob kissed Alice? AFFIRMATIVE True Class Constrainers As Kiparsky and Kiparsky (1970) note, the truth con- tribution of a clause embedded under a factive verb depends only on the immediate constrainer; depth of embedding is irrelevant. It is for this reason that check_factive/2 can work in the parser, even though depth of embedding is not available at the time the rule is called. In fact, if the treatment of such clauses were deferred, the constrainer might be buried in a list (e.g. within prop/2) and not available for examination. That independence does not hold for clauses constrained by True Class constrainers. Such clauses are true only if the constrainer is true (i.e. a toplevel assertion or the complement of a factive), and the constrainer's truth value is not available when the con- strainer is being parsed. Furthermore, the effect of a True Class constrainer is dependent on its polarity, and that informa- tion also may not be available when the constrainer is being parsed. Thus, the treatment of complements of such constrainers must be deferred to the processing step of the program. CNS&G uses the predicate note/1 to assert the output of the Prologization step to the knowledge base. That rule would simply assert its argument. CONSTRAIN expands note/1 considerably so that it tests its argument before asserting it. One modification that has gone unremarked is that note/1 first attempts to retract the clause before asserting it, then uses asserta/1 rather than assertz/1, as in CNS&G. These steps eliminate duplication in the knowledge base and insure that the most recently evoked clauses are at the head of the knowledge base. It is the latter feature that allows proper nouns to be identified across discourses. A further modification that is made necessary by the addition of True Class constrainers is the elimination of double negation; if the argument to neg/1 is itself a neg/1, the argument of the inner negation is processed and asserted. The only clauses that reach note/1 for processing are those that are not shielded from truth evaluation--initially, toplevel assertions and conditions that have been raised to toplevel by check_factive/2. Implications, including those created from universally quantified NPs, have been converted into 32 proper Prolog rules and are subject to the constraints imposed by the interpreter. Clauses that constitute the conditions of negations and of embedded clauses remain in a list, an argument to neg/1 or prop/1, and are not sent to note/1 on their own. The representation of a True Class constrainer has the form state(Tense, State, [X]), where State is the constrainer and X is the discourse referent for the embedded prop/1. When note/1 encounters a clause of that form, it calls the disjunctive query (true(State); certain(State)). These predicates, similar to factive/1, identify those constrainers whose complements are to be asserted to the knowledge base when the constrainer is positive. If the call succeeds, prop(X, PropList) is called and PropList is Skolemized and processed. The original argument to note/1 is also asserted. Processing PropList may bring a new True Class constrainer to note/1. Thus, a clause embedded successively under True Class constrainers will eventually come to note/1 to be asserted. However, if a Say Class constrainer intervenes, the sequence will be blocked. Thus, (5.15.c) will receive AFFIRMATIVE if (5.15.a) has been entered, but INSUFFICIENT DATA if only (5.15.b) has been entered. (5.15.a) It is true that it is certain that Ted kissed Carol. (b) It is true that it is possible that Ted kissed Carol. (c) Did Ted kiss Carol? Since PropList is a list of conditions, there is no universe to provide the set of discourse referents to be Skolemized, so set_of_args(PropList, Args) must be called to collect those referents. Actually, this predicate was already necessary. This program, like C&S, raises the discourse referents of proper nouns to toplevel during parsing. CNS&G does not do so, so these referents are available in the subordinate universe when an implication is Skolemized. Thus, this program must call set_of_args/2 before Skolemizing an implication. note/1 follows a similar procedure in the case of neg([state(Tense, State, [X])]). In this case, however, the disjunctive query is (true(State); possible(State)); which identifies those constrainers for which, when negated, the negation of the complement should be asserted. 33 note/1 is also used to handle the discourse shown in (5.16), the last of the extensions to CNS&G. (5.16.a) Alice thinks that Ted kissed Carol. (b) Alice is right. (c) Did Ted kiss Carol? AFFIRMATIVE Because think is a Say Class constrainer, (5.16.c) will receive INSUFFICIENT DATA if it only has (5.16.a) to work on. In order to handle (5.16.b), it is necessary to find what she is right about and process that proposition appropriately. The following clause for note/1 accomplishes that. (5.17) note(state(Tense, Truth, [X])):- (Truth == right ; Truth == wrong), (event(Tense, _, [X,P]) ; state(Tense, _, [X,P])), prop(P, Prop), note_truth(Prop, Truth). If Truth is bound to 'right' or 'wrong,' note/1 seeks an event or state whose subject is X and whose complement is an embedded clause. It then passes Prop and Truth to note_truth/2, which asserts Prop or its negation, according to the value of Truth. If the clause to be asserted already exists in the knowledge base, note_truth/2 simply advises the user; if the opposite of the clause exists there, it is retracted before the new clause is asserted. This is a rather simple-minded treatment of belief re- vision, but CONSTRAIN assumes that anything entered by the user is true unless it is constrained. 6. CONCLUSION This report has presented an extension of Discourse Representation Theory that allows the representation of embedded noun phrases whose truth evaluation demands special treatment (constrained clauses), treatment that is determined by the constrainer (verb or adjective) of the embedded noun phrase. It has also described an implementation of DRT, CONSTRAIN, that takes an English language input (which may contain such clauses) and transforms it into a Prolog knowledge base that can be queried. Both the theory and the implementation remain at the experimental stage; both must be extended considerably before they can be used as a natural language interface for practical programs. In this section we consider some of the necessary extensions. The most needed extension to the implementation is a proper treatment of negation. CONSTRAIN replaces the negation- 34 as-failure of Prolog with true negation, but in so doing it trades one form of unsoundness for another. CONSTRAIN will return NEGATIVE as the response to a query only if the knowledge base contains a clause neg(Query) such that the elements in the query exactly match those in Query. Thus, CONSTRAIN may return INSUFFICIENT DATA to a query when the knowledge base contains information that entails the response NEGATIVE. With a more complete treatment of negation, proper treatment of disjunction may be added. CONSTRAIN can parse a disjunction and add it to the knowledge base, but it is unable to use those disjunctions in order to infer conclusions. As was noted in Section 4, a more complete treatment of negation will make possible a more adequate treatment of disjunction. Improved treatment of negation and disjunction are matters of the DRT-to-Prolog portion of CONSTRAIN. An extension needed at the other end of CONSTRAIN, the parser, is the ability to handle other syntactic types of constrained clauses: poss-ing and for-to complements. That extension is made difficult by the fact that either construction may involve equi-NP deletion. Given such an extension to the parser, it should be possible to add other constrainers that take VP complements to the language handled by CONSTRAIN. Other needed additions to the parser are the facilities to handle subordinating conjunctions and sentence adverbials (e.g. probably, certainly). The former require a knowledge representation that allows non-constrained clauses to be addressed in a manner like those that are arguments to prop/2. One possibility for such a representation is the event markers of Guenthner (1987). Handling sentence adverbials is a relatively simple but time-consuming matter. The machinery for DRS construction already exists in CONSTRAIN, but it will be necessary to add to each sentence rule a new version for each possible adverbial position. Extensions of the implementation will, of, course, be required by extensions to the theory. The current version of DRT is limited to a very small subset of natural language. Many extensions to the theory are required before it can handle a useful range of natural language. The most obviously needed extensions are the ability to handle definite NPs and plural NPs. Although definite NPs are usually anaphoric and thus could be treated in the same fashion as pronouns, the head noun of a definite NP is often not identical to that of its antecedent (e.g. the two may be synonyms). Furthermore, definite NPs are not infrequently exophoric or generic, and an implementation would need to have some means of distinguishing between the possibilities. Another needed extension to the theory is a formalism for specifying arguments that are not syntactically indicated (e.g. 35 sell requires, conceptually, a price, but that argument is not syntactically obligatory). Handling this argument requires default specifications and a means of determining whether the default value applies. These extensions, both to the implementation and to the theory, probably require user interaction. The implementation may need to query the user about the scope of negation, non- anaphoric definite NPs, and default values. With these extensions, DRT can provide a useful natural language interface to a knowledge base. WORKS CITED Asher, N. 1986. Belief in discourse representation theory. Journal of Philosophical Logic 15:127-89. Chomsky, N. 1965. Aspects of the Theory of Syntax. Cambridge, MA: MIT Press. Covington, M. 1987. GULP 1.1: An extension of Prolog for unification-based grammar. ACMC Research Report 01-0021, The University of Georgia, Athens. Covington, M., D. Nute, N. Schmitz, and D. Goodman. 1988. From English to Prolog via Discourse Representation Theory. ACMC Research Report 01-0024, the University of Georgia, Athens. Covington, M. and N. Schmitz. 1988. An Implementation of Discourse Representation Theory. ACMC Research Report 01-0023, The University of Georgia, Athens. Goodman, D. 1988. An Implementation of and extension to discourse representation theory: Translating natural language to discourse representation structures to Prolog clauses. Unpublished master's thesis, The University of Georgia, Athens. Guenthner, F. 1987. Linguistic meaning in discourse representation theory. Synthese 73:569-98. Guenthner, F., H. Lehman, and W. Schonfeld. 1986. A Theory for the representation of knowledge. IBM Journal of Research and Development 30:1.39-56. Johnson, M., and Klein, E. 1986. Discourse, Anaphora, and Parsing. CSLI Research Report 86-63,Stanford University. Kamp, H. 1981. A Theory of truth and semantic representation. In 36 J. Groendendijk, T. Janssen, and M. Stokhof (eds.) Formal methods in the Study of Language, 277-322. University of Amsterdam. Kamp, H. 1985. Unpublished discourse representation theory project description, University of Texas, Austin. Kiparsky, P., and C. Kiparsky. 1971. Fact. In D. Steinberg and L. Jakobovits (eds.), Semantics, 345-369. New York: Cambridge University Press. McCawley, J. 1981. Everything that Linguists have Always Wanted to know about Logic. Chicago: The University of Chicago Press. McCawley, J. 1988. The Syntactic Phenomena of English. Chicago: The University of Chicago Press. Shieber, S. 1986. An Introduction to Unification-based Approaches to Grammar. CSLI Lecture Notes No. 4, Stanford University. Spencer-Smith, R. 1987. Semantics and discourse representation. Mind and Language 2:1.1-26. Smith, W. 1989. Problems in applying discourse representation theory. Research Report AI-1989-04, The University of Georgia, Athens. Zeevat, H. 1989. A compositional approach to discourse representation theory. Linguistics and Philosophy 12:95-131.