Specification of Further Implementation Work in Subtask 3.6

David Beaver, Robin Cooper, Ewan Klein, Marc Moens

DYANA-2

Dynamic Interpretation of Natural Language

esprit Basic Research Project 6852 Deliverable R3.6 October 1994

Specification of Further Implementation Work in Subtask 3.6

David Beaver, Robin Cooper, Ewan Klein, Marc Moens University of Edinburgh

DYANA-2

Dynamic Interpretation of Natural Language esprit Basic Research Project 6852 Deliverable R3.6 October 1994

esprit Basic Research Project 6852 dyana-2

Dynamic Interpretation of Natural Language

Universiteit van Amsterdam Institute for Logic, Language and Computation (ILLC)

University of Edinburgh Centre for Cognitive Science (ECCS)

Universität München Centrum für Informations- und Sprachforschung (CIS)

Universitetet i Oslo Department of Linguistics and Philosophy (ILF)

Universität Stuttgart Institut für Maschinelle Sprachverarbeitung (IMS)

Universität Tübingen Seminar für Sprachwissenschaft (SfS)

Universiteit Utrecht Research Institute for Language and Speech (OTS)

For copies of reports, updates on project activities and other dyana-related information, contact:

The dyana-2 Project Administrator ILLC/Department of Philosophy University of Amsterdam Nieuwe Doelenstraat 15 NL-1012 CP Amsterdam

\begin{matrix}c \\ ◯ \end{matrix} 1994, The Individual Authors

No part of this document may be reproduced or transmitted in any form, or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission from the copyright owner.

Deliverable R3.6

Specification of Further Implementation Work in Subtask 3.6^{∗}

David Beaver  Robin Cooper  Ewan Klein

Marc Moens

1 Introduction

1.1 Goals The dyana-2 Technical Annex stipulates that in the second phase of Subtask 3.6, “we will attempt to integrate a dyamic semantics module into a large coverage grammar of English”. An important goal of this work, as we see it, is to help demonstrate to a general audience that the dynamic perspective can have practical applications in computational linguistics.

Our original hope had been that we would be able to integrate a dynamic semantis into an existing English grammar. However, it has since become apparent that we do not have access to anything suitable. Although the Alvey Natural Language Tools Grammar [?] meets the criterion of ‘large coverage’, the grammar formalism employed does not lend itself naturally to the kind of syntax-semantic interaction which characterises the dyana-2 framework. As a result, we have concluded that we will have to develop an appropriate syntactic component within this task. Of course, we cannot expect to build a truly large coverage grammar in the time allotted. Nevertheless, we will aim at a grammar which deals with a reasonable fragement of English and which is scalable, in the sense that it should be possible to increase coverage without seriously degrading performance.

Even within the framework of dyana-2, there is quite a space of design solutions we could adopt for the implementation. In the rest of this report, we will indicate the major choices which will guide the work on the implementation.

2 Implementation Framework

In principle, we could opt for either direct implementation in a general purpose programming language, or make use of a more restricted programming environment dedicated to linguistic description.

Using a general purpose language such as Prolog might have certain advantages. First, there is considerable past experience in developing Prolog grammars at the dyana-2 sites and elsewhere. Second, whatever language the

∗. We are grateful to Chris Brew, Claire Grover, Peter Krause, and David Milward for input and helpful comments.

grammar is implemented in, it seems likely that there will need to be links to a general purpose programming language for such tasks as evaluation of truth in a database, theorem proving, and I/O. Thus, an argument from uniformity could be made for choosing Prolog as the main implementation language. But Prolog crucially lacks grammar development environment and debugging tools, and is thus not a realistic choice for the task ahead of us.

Instead, we will use the latest release of cuf (2.30) as the implementation framework. The improved debugging facilities and speed of execution makes it a good choice for building natural language prototypes. Another advantage of the new release is that it supports a foreign language interface to Prolog. This may well be crucial if we need to carry out semantic manipulations (e.g. inferencing, or evaluation with respect to a database) which are not easily encoded in cuf itself.

The choice of cuf will have the considerable added benefit of enabling interaction between subtasks 3.6, 3.1 (“Implementation of the Constraint-based Unification Formalism”) and 3.4 (“Specification and Implementation of Semantics in cuf”). Again, given the available resource, it makes sense for these tasks to be as closely related as possible if significant progress is to be made.

3 Grammar Framework

If we were confining ouselves to grammar frameworks that were available at the start of dyana-1, the two main contenders would be Categorial Grammar (cg) and Head-driven Phrase Structure Grammar (hpsg). Since Montague’s pioneering work, there has been a well established approach to formal semantics within cg, while hpsg has gained some preeminence within the European computational linguistics community and has also been a vehicle for relatively large coverage grammars in English, German and Dutch.

However, the ongoing work by dyana-2 researchers and their affiliates has reduced the necessity to choose between these two frameworks by exposing the common features of both frameworks and developing a more general philosophy of sign-based grammar logic which encapsulates aspects of both traditions. For examples of this philosophy in action, the reader is referred to [?] (see especially Moortgat’s introduction), [?], [?], [?] and [?]. The earlier work of [Uszkoeit 86], [?] and [?] to a great extent prefigures these developments.

The essence of this sign-based approach can be summed up as follows:

• Constituent words and phrases of linguistic expressions each correspond to structured objects referred to as signs, syntactic, semantic and other information being combined in the description of each sign.

• The integration of information from different sources into a single unit allows for information flow between the different components of the grammar.

• Syntactic coverage is determined by a resource sensitive grammar logic, the resources relevant to determining the grammaticality of a given expression usually being determined by the available lexical signs in the expression.

• The process of parsing a string becomes a problem of proving within the grammar logic that the available resources are neither more nor less than is needed to justify the attribution of some particular sign (typically a structured object of sentential category) to the whole string.

• Construction of the proofs does not require arbitrary computation: it may be seen as an example of one particular brand of equational constraint solution. Guided by these ideas, we will develop a sign-based grammar in which

signs are encoded as feature terms, using some of the lingua franca of current hpsg. Another common characteristic of cg and hpsg is their lexicalist nature, and a significant part of our work will therefore be devoted to building an appropriate hierarchical lexicon.

One option which we will explore is the extent to which the grammar rules can be constrained to be binary branching. This will make it easier to build on results from work in cg, given the equivalence between such a binary branching hpsg, and a corresponding cg.^{1}

4 Semantic Framework

4.1 Semantic Representation There are now several varieties of dynamic semantics ‘on the market’, many of which have been developed in response to Kamp’s original Discourse Representation Theory (drt). Within the ambit of dyana-2, we can point to the account of meaning developed by [?] and [?].

From an implementational point of view, it is desirable that at least the predicate-argument part of the semantics be encoded in a compositional form. Moreover, by attributing a clearly defined meaning to every linguistic expression, it becomes possible to calibrate alternative presentations of the grammar, ensuring that at least the semantic component remains constant. This means that it should be possible in future work to ‘migrate’ information from our formulation to other varieties of sign-based grammar.

For most linguists, maintenance of compositionality means using some variant of classical type theory, usually Montague’s Intensional Logic (il), and indeed most of the work that has been done on producing compositional grammars in which dynamic semantics plays a role involves some version of type theory — see for instance the systems in [?], [?] and [?]. An exception to this rule is the adaption of the [Groenendijk & Stokhof 91b] system of Dynamic Montague Grammar in [?], to which we shall return shortly.

Nevertheless, recursively associating types with hpsg categories is not a natural operation; in particular, it is unclear how to embed a type-theoretical semantics into an hpsg sign so as to yield a natural and uniform notion of semantic composition. Even having decided how this is to be done, considerable artificiality remains, since both hpsg and cuf are best suited to notions of semantic composition which are related to the unification of signs.

1. To exemplify the correspondence observe that we may view an hpsg sign of type X with subcat list ⟨A_{1}, A_{2}, …, A_{n}⟩ as equivalent to a cg expression of category (… (X | A_{1}) | A_{2}) | … A_{n}), with the direction of the categorial slashes being determined by the Linear Precedence rules of the hpsg grammar.

We therefore suggest an alternative, in a direction pointed to by the system in [?]. There the insights of dmg are moved from their original type theoretic setting into a constraint based framework utilising recent developments in Situation Theory. The example of this system and the compositional constraint based ASTL system of Alan Black (see eg. [?]) pave the way to developing constraint based compositional grammars which utilise the insights of dynamic semantics. The system envisaged would utilise underspecified meanings encoded in a dynamic formalism, meanings which would become more specified via the unification of signs. The approach, which is developed more formally in the technical appendix to this deliverable, is of comparable generality to the use of type theory in semantics, and in principle could be applied to any of the dynamic systems which have been developed in dyana-1 and dyana-2, such as dpl, Dekker’s edpl [?] or Beaver’s able [?]. The latter incorporates a range of dyana-2-originated dynamic treatments of semantic phenomena, including quantification, anaphora, modality and presupposition, and would make a sensible starting point.

4.2 Semantic Evaluation We are aware that a useful semantic implementation that can be evaluated for its contribution to any kind of practical system has to be one that does more than produce a semantic representation. We will therefore show how discourses can be evaluated in a database and how they can be used to update a database. In doing this we will develop a limited reasoning capability that will enable us to check for some of the obvious cases of inconsistency. In order to do this we will need to develop a database formalism that is rich enough to express the kind of information that can be represented in our semantic representation language, possibly the semantic representation language itself.^{2}

5 Grammar Coverage

The core grammar fragment should have syntactic coverage comparable to that of the system presented in [?], and semantic coverage including dynamic treatments of quantification and pronominal anaphora. We envisage modular extensions to the core grammar including, for example, treatments of:

• VP anaphora,

• temporal anaphora,

• presupposition,

• attitude verbs,

• epistemic modality.

Naturally, we aim for as many as possible of these modular extensions to be mutually compatible, so that the ideal final result would be a single implementation extending the core grammar with treatments of all of the above listed semantic phenomena. In addition, we will experiment with implementing some aspects of the approach to information structure developed in dyana-2 Report R1.3.B.

2. An alternative would be just to encode the database as a list of Prolog clauses. In this case, we will need to be able to translate the output of the analyser into Prolog clauses.

Since we are committed to examining discourse, one way of proceeding would be to develop a grammar which finds general solutions for a small number of exemplary texts; that is, texts which combine a number of the phenomena that we wish to study.

The following example illustrates the kind of text which will be used.

(1) Peter told his neighbour in great detail what had happened. Around 9 o’clock, two little monkeys had run into the office, climbed on a desk, and begun to throw pencils at the secretaries, paper clips at the office boy and rubbers at each other. When she saw them, the personnel manager tried to get the boss to call the zoo. She hadn’t realized that it was him that the apes belonged to. They were a present from his daughter. He claimed that they always behaved themselves. But afterwards, everybody who’d brought a lunch box found it had been raided. The woman found it hard to believe Peter’s story.

(2) Peter vertelde zijn buurvrouw nauwkeurig wat er gebeurd was. Rond 9 uur waren twee aapjes het kantoor binnengelopen, op een bureau geklommen, en potloden naar de secrateressen, paperclips naar de kantoorjongen en gommen naar elkaar beginnen te gooien. Toen ze ze zag, had de personeelschef geprobeerd om de baas de dierentuin te doen bellen. Ze had zich niet gerealiseerd dat hij de eigenaar van de aapjes was. Ze waren een cadeau van zijn dochter. Hij beweerde dat ze zich altijd goed gedroegen. Maar achteraf ontdekte iedereen die een lunchpakket had meegenomen dat dat geplunderd was. De vrouw vond het moeilijk om Peters verhaal te geloven.

(3) Peter erzählte seiner Nachbarin ganz genau, was geschehen war. Etwa 9 Uhr waren zwei kleine Affen in das Büro gelaufen, waren auf einen Schreibtisch geklettert und hatten begonnen, Bleistifte nach den Sekretärinnen, Büroklammern nach dem Laufburschen und Radiergummis aufeinander zu werfen. Als sie sie sah, versuchte die Personalchefin, den Chef zu veranlassen, den Zoo anzurufen. Sie hatte nicht erkannt, daß ihm die Affen gehörten. Sie waren ein Geschenk seiner Tochter. Er behauptete, daß sie sich immer gut benahmen. Aber nachher entdeckte jeder, der ein Essenspaket mitgebracht hatte, daß es geplündert worden war. Die Frau fand es schwer, Peters Geschichte zu glauben.

6 Related Work in DYANA-2

Although the implementation work will be able to draw on a number of strands in dyana-2, the most important ongoing interaction will involve Subtask 3.4, in which the Stuttgart team will be extending cuf to allow the declarative construction of semantic structures. Part of this work will involve implementing some, if not all, of the plural data analysed in Chapter 4 of [?]. The syntax will probably be specified by an hpsg style grammar, and the grammar will employ ideas developed by Reyle (e.g. [?]) for representing quantifier scope constraints in underspecified drss.

There will be many points of contact between the two Subtasks, and Edinburgh will collaborate closely with Stuttgart. Following Stuttgart’s initiative, we will investigate the possibility of implementing parts of the temporal data in Chapter 5 of [?].

As mentioned above, we also expect interaction with Subtask 3.5, with the possibility existing of using an adaption of the grammar developed in Subtask 3.6 as a test grammar for the extended Lambek theorem prover.

7 Previous Work

7.1 DYANA-2 The first, ‘experimental’, phase of Subtask 3.6 developed a suite of small-scale prototypes, including:

• Theorem provers for update logics;

• Prolog implementations of Dynamic Predicate Logic (dpl);

• Prolog implementations of Dynamic Montague Grammar (dmg);

• cuf implementations of static and dynamic versions of Head Driven Phrase Structure Grammar (hpsg). The dpl implemention takes sentences of dpl and uses them to update

a representation of a dpl state. The dmg implementation parses, updates a representation of a dmg state, and checks validity of sentences against a model.

It seems unlikely that the work on theorem provers for update logics will have any direct bearing on the final stage implementation. However, the dmg and dpl implementations will form a useful basis for the work.

The cuf-hpsg implementations, which are described in the technical appendix, will form a starting point for the proposed implementation.^{3}

The other major strand of implementation in dyana-2 also involves cuf. At Stuttgart, Dörre and Koenig have implemented categorial grammar fragments (or, more properly, sign-based extensions of categorial grammars) in cuf, as have students of Moortgat’s in Utrecht.

7.2 Other Projects We have also taken into account relevant work conducted outside of dyana-2:

FraCaS FraCaS, funded by LRE from January 1994 for two years, aims to bring about a convergence of current efforts in computational semantics, and is currently working on a detailed comparison of several existing semantic theories: drt, Situation Theory, Property Theory, Dynamic Semantics, and Monotonic Semantics. The project has identified a set of ‘core’ examples for semantic processing, and it is likely that we will be able to draw on the results of FraCaS analyses of this data.

QUADS There are two prototype implementations built as part of the quads project at the Centre for Cognitive Science in Edinburgh (Analysis and Computation of Quantification and Anaphora using Dynamic Semantics). Both rely on

3. Note that the originally scheduled work on prototype implementation of presuppositional systems was replaced by the development of the cuf-hpsg implementations, which were felt more likely to have an impact on the final year’s implementation work.

an incremental parsing algorithm, which provides a scoped logical form word by word. In the first implementation, the pronoun resolver may result in some variables being unbound (under a static interpretation of the logical form). There is therefore a second interpretation process, based on work of Lewin which interprets the logical form using a dynamic semantics, resulting in a new logical form where all variables are correctly bound. In the second implementation, pronoun resolution is built into the dynamic interpretation procedure, with pronouns being treated as definite descriptions (she treated as the female etc.). This implementation is based on a more unconventional dynamic semantics where context consists of structured situations, rather than sets of assignments.

Verbmobil Vermobil is a large national project funded by the German BMFT. Within the project, work will be carried out on implementing fragments of German which combine ideas from drt with the hpsg grammar framework. The research being carried out by teams at Saarbrücken, Stuttgart and Tübingen is likely to be particularly relevant.

Work at Tübingen Gerhardt, Krause and Richter [?] have developed a prototype illustrating how formulae of Dynamic Intensional Logic and Dynamic Predicate Logic can be constructed according to the compositional rules of Dynamic Montague Grammar (Groenendijk and Stokhof 1990) in a Prolog implementation using term-rewriting.

References

[Beaver 93] Beaver, D. (1993)Kinematic Montague Grammar, in [?] [Beaver et al 91] Beaver D., A. Black, R. Cooper and I. Lewin (1991) DMG in

EKN, in [?] [Black 93] Black, A. (1993) Some Different Approaches to DRT, in [?] [Cooper (ed.) 93] Cooper, R. (ed.) (1993) Integrating semantic Theories,

dyana-2 Deliverable R2.1.A [Dekker 93] Dekker, P. (1993) Trans-sentential Meditations, Phd Dissertation,

University of Amsterdam. [Dörre et al 94] Dörre, J., D. Gabbay and E. König (1994)‘Fibred Semantics

for Feature-Based Grammar Logic’, in [?] [Dörre 94] Dörre, J. (ed.) (1994)Computational Aspects of Constraint-based

Linguistic Description II, dyana-2 Deliverable R1.2.B [Engdahl (ed.) 94] Engdahl E. (ed.) (1994) Integrating Information Structure

into Constraint-based and Categorial Approaches, dyana-2 Deliverable R1.3.B

[Frank & Reyle 94] Frank, A., U. Reyle (1994) Principle Based Semantics for HPSG, Arbeitspapiere des Sonderforschungsbereichs 340, University of Stuttgart.

[Gerhardt et al 93] Gerhardt F., P. Krause, F. Richter (1993) Computational Experiments with Dynamic Semantics, Manuscript, University of Tübingen [Groenendijk & Stokhof 91a] Groenendijk, J. and M. Stokhof (1991) Dynamic

Predicate Logic, Linguistics and Philosophy 14(1), p. 39–100 (Also in dyana-1Deliverable R2.1.A)

[Groenendijk & Stokhof 91b] Groenendijk, J. and M. Stokhof, (1991) Dynamic

Montague Grammar, in [?] [Groenendijk et al. 91] Groenendijk J., M. Stokhof and D. Beaver (eds.) (1991)

Quantification and Anaphora I dyana-1 Deliverable R2.2.A [Grover et al. 93] Grover, C., J. Carroll, T. Briscoe (1993) The Alvey Natural

Language Tools Grammar (4th Release), Technical Report 284, Computer Laboratory, University of Cambridge.

[Kamp (ed.) 93] Presupposition, dyana-2 Deliverable R2.2.A [Kamp & Reyle 93] Kamp, H. and U. Reyle (1993)From Discourse to Logic.

Kluwer, Dordrecht. [König (1994)] König, E. (1994)A Study in Grammar Design, Report no.

54, Arbeitspapiere des Sonderforschungsbereichs 340, Institut für Maschinelle Sprachverarbeitung, Universität Stuttgart

[Morrill 94] Morrill, G. (1994) ‘Structural Facilitation and Structural Inhibition’, in: M. Abrusci, C. Casadio and M. Moortgat (eds.), Linear Logic and Lambek Calculus, Proceedings First Rome Workshop, ots/dyana-2, Utrecht/Amsterdam

[Moortgat (ed.) 94] Moortgat, M. (ed.) (1994) Lambek Calculus, Multimodal

and Polymorphic Extensions, dyana-2Deliverable R1.1.B [Muskens 93] Muskens, R. (1993) ‘A Compositional Discourse Representation

Theory’, in: P. Dekker and M. Stokhof (eds) Proceedings of the 9th Amsterdam Colloquium, ILLC/Department of Philosophy, University of Amsterdam. Pp467–486.

[Pollard & Sag 87] Pollard, C. and I. Sag (1987) Information-Based Syntax and

Semantics, volume 1, CSLI [Seligman (ed.) 91] Seligman J. (ed.) (1991) Partial and Dynamic Semantics

III, dyana-1 Deliverable R2.1.C [Uszkoreit 86] Uszkoreit, H. (1986) Categorial Unification Grammars, in COL-

ING 11, Bonn, p. 187–194 [Veltman 91] Veltman, F. (1991) Defaults in update semantics, in dyana-1 de-

liverable R2.5.C (to appear in the Journal of Philosophical Logic) [Zeevat 91] Zeevat, H. (1991) Aspects of Discourse Semantics and Unification

Grammar, PhD. Thesis, University of Amsterdam [Zeevat et al 87] Zeevat, H., J. Calder and E.Klein (1987) “Unification Catego-

rial Grammar”, in Haddock, N., E. Klein and G.Morrill (eds) Categorial Grammar, Unification Grammar and Parsing, Centre for Cognitive Science, Edinburgh