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 <U,C>, 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:<U:{R1, R2},
C:{Bob(R1),
woman(R2)
saw(R1, R2) }>
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:<U,
C := C + {kissed(R1, R2) }>
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:<U := U + {R3},
C := C + {ring(R3),
not wear(R2, R3) }>
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:<U, C := C + {not(K1,
K1:<U1: {R3},
C1: {ring(R3),
wear(R2, R3) }> ) }>
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:<U:{},
C:{K1 ==> K2,
K1: <U1:{R1},
C1:{man(R1),
sad(R1) }>
K2: <U2:{R2},
C2:{woman(R2),
pretty(R2),
loves(R1, R2) }> }>
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:<U: {R1, P1
C: {Carol(R1), want(R1, P1),
P1: <U: {R2},
C: {rich(R2),
man(R2),
kiss(R1, R2) }> }>
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, <Entity, Marker>, 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: <R1,Bob>,
<R2, Venus>,
<R3, Venus>
Internal Anchors:
L: <U: {R2, R3},
C: {evening_star(R2),
morning_star(R3)}>
K: <U: {R1, P1},
C: {Bob(R1),
believes(R1, P1),
P1: <U: {R2, R3},
C: {pretty(R2),
枝1,
K1: <C1: {pretty(R3)}> }> }>
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.