Efficient Parameterizable Type Expansion for Typed Feature Formalisms

1 Introduction

Over the last few years, constraint-based grammar for­ malisms [Shieber, 1986] have become the predominant paradigm in natural language processing and computa­ tional linguistics. While the first approaches relied on annotated phrase structure rules (e.g., PATR-II [Shieber et al., 1983]) , modern formalisms try to specify gram­ matical knowledge as well as lexicon entries entirely through feature structures. In order to achieve this goal, one must enrich the expressive power of the first unification-based formalisms with different forms of dis­ junctive descriptions. Later , other operations come into play, e.g., (classical) negation.

However the most important extension to formalisms consists of the incorporation of types, for instance in modern systems like TFS [Zajac, 1992], CUF [Dorre and Dorna, 1993], or TD.C [Krieger and Schafer, 1994].

*This work was funded by the German Federal Ministry of Education, Science, Research, and Technology as part of the Verbmobil project. We are grateful to three anonymous IJCAI reviewers for helpful comments.

Types are ordered hierarchically as is known from object­ oriented programming languages, a feature heavily em­ ployed in lexicalized grammar theories like Head-Driven Phrase Structure Grammar (HPSG) [Pollard and Sag, 1987]. This leads to multiple inheritance in the descrip­ tion of linguistic entities. In general, not only is a type related to other types through the inheritance hierar­ chy, but is also provided with feature constraints that are idiosyncratic to this type. Hence, a type symbol can serve as an abbreviation for a complex expression and an untyped feature structure becomes a typed one. If a formalism is intended to be used as a stand-alone sys­ tem, it must also implement recursive types if it does not provide phrase-structure recursion directly (within the formalism) or indirectly (via a parserjgenerator). 1 In addition, certain forms of relations (like append) or additional extensions of the formalism (like functional uncertainty) can be nicely modelled through recursive types .

Now, because types allow us to refer to complex con­ straints through the use of symbol names, we need an operation that is responsible for deducing the constraints that are inherent to a type. This means, reconstructing the idiosyncratic constraints of a type, plus those that are inherited from the supertypes. We will call such a mechanism type expansion (TE) or type unfolding. 2 Thus TE is faced with two main tasks:

1. making some or all feature constraints explicit (type expansion is a structure-building operation)
2. determining the global consistency of a type or more generally, of a typed feature structure

Types not only serve as a shorthand, like templates, but also provide other advantages which can only be ac­ complished if a mechanism for TE is available:

1 For instance, ALE employs a bottom-up chart parser, whereas TFS relies entirely on type deduction. Note that recursive types can be substituted by definite clauses (equiv­ alences), as is the case for CUF, such that parsing/generation roughly corresponds to PROLOG's SLD resolution.

2 It is worth noting that our notion of TE shares simi­ larities with Alt-Kaci 's sort unfolding [Ait-Kaci et al., 1993] and Carpenter's total well-typedness [Carpenter, 1992, Ch. 6] . However, the latter notion is not well-defined for true recur­ sive typed feature structures in that such structures cannot be totally well-typed within finite time and space.

· STRUCTURING KNOWLEDGE

Hierarchically ordered types allow for a modular way of representing linguistic knowledge. Gener­ alizations can be put at the appropriate levels of representation. Type expansion, then, is responsi­ ble for gathering the distributed information that is attached to the type symbols.

· SAVING MEMORY

In practice, it is not possible to hold huge lexica in full detail in memory. However, only the idiosyn­ cratic information of a lexicon entry needs to be represented. Type expansion is employed in making the constraints imposed by lexical types explicit.

· EFFICIENT PROCESSING

Working with type names only or with partially ex­ panded types minimizes the costs of copying struc­ tures during processing and speeds up unification. This can only be accomplished if the system makes a mechanism for type expansion available.

• TYPE CHECKING

Type definitions allow a grammarian to declare which attributes are appropriate for a given type and which types are appropriate for a given at­ tribute, therefore disallowing one from writing in­ consistent feature structures. Again, type expansion is necessary to determine the global consistency of a given description.

· RECURSIVE TYPES

Recursive types give a grammar writer the oppor­ tunity to formulate certain functions or relations as recursive type specifications. Working in the type deduction paradigm forces a grammar writer to re­ place the context-free backbone through recursive types. Here, parameterized delayed type expansion is the key to controlled linguistic deduction [Uszko­ reit, 1991].

· ANYTIME BEHAVIOUR

Complex architectures for NL processing require modules that can be interrupted at any time, re­ turning an incomplete, nevertheless useful result [Wahlster, 1993). Such modules are able to continue processing with only a negligible overhead, instead of having been restarted from scratch. Type expan­ sion can serve as an anytime module for linguistic processing.

In the next section, we introduce the basic invento­ ry to describe our own novel approach to TE. We then describe the basic structure of the algorithm, present several improvements, and show how it can be parame­ terized w.r.t. different dimension. Finally, we have a few words on theoretical results and compare our treatment with others.

2 Preliminaries

In order to describe our algorithm, we need only a small inventory to abstract from the concrete implementation in TD.C [Krieger and Schafer, 1994) and to make the ap­ proach comparable to others. First of all, we assume pairwise disjoint sets of features (attributes) F, atoms (constants) A, logical variables V, and types T.

In the following, we refer to a type hierarchy I by a pair (/, :::5), such that :::5 ~ J X J is a decidable partial order, i.e., :::5 is reflexive, antisymmetric, and transitive.

A typed feature structure (TFS) B is essentially either a '¢'-term or an E-term [Ai't-Kaci, 1986), i.e.,

such that X E V, 7 E /,<I>= {/I='= B1, ... ,fn ='= Bn}, and 0 = {81 , ... ,Bn}, where each /i E F and Bi is again aTFS.

We will call the equation f ='= B a feature constraint (or an attribute-value pair). 3 <I> is interpreted conjunctively, whereas 0 represents a disjunction. Variables are used to indicate structure sharing.

Let us give a small example to see the correspondences. The typed feature structure

should denote the same set of objects as the following two-dimensional attribute-value matrix (AVM) notation:

It is worth noting that for the purpose of simplicity and clarity, we restrict TFS to the above two cases. Ac­ tually, our algorithm is more powerful in that it handles other cases, for instance conjunction, disjunction, and negation of types and feature constraints.

A type system n is a pair ( 0, I), where 0 is a finite set of typed feature structures and I an inheritance hi­ erarchy. Given n, we call B E 0 a type definition.

Our algorithm is independent of the underlying de­ duction system-we are not interested in the normaliza­ tion of feature constraints (i.e., how unification of feature structures is actually done) nor are we interested in the logic of types, e.g., whether the existence of a greatest lower bound is obligatory (TFS [Zajac, 1992); ALE [Car­ penter and Penn, 1994)) or optional as in TD.C [Krieger and Schafer, 1994]. We assume here that typed unifica­ tion is simply a black box and can be accessed through an interface function (say unify-tfs). From this perspec­ tive, our expansion mechanism can be either used as a stand-alone system or as an integrated part of the typed unification machinery.

We only have to say a few words on the semantic foun­ dations of our approach at the end of this paper. This is because we could either choose extensions of feature logic [Smolka, 1989) or directly interpret our structures within the paradigm of (constraint) logic programming [Lloyd, 1987; Jaffar and Lassez, 1987).

3 It should be noted that we define TFS to have a nested structure and not to be flat (in contrast to feature clauses in a more logic-oriented approach, e.g., [Ai't-Kaci et al., 1993]) in order to make the connection to the implementation clear and to come close to the structured attribute-value matrix notation.

3 Algorithm

The overall design of our TE algorithm was inspired by the following requirements:

• support a complete expansion strategy
• allow lazy expansion of recursive types
• minimize the number of unifications
• make expansion parameterizable for delay and pref­ erence information

Before we describe the algorithm, we modify the syn­ tax of TFS to get rid of unimportant details . First, we simplify TFS in that we omit variables. This can be done without loss of generality if variables are direct­ ly implemented through structure-sharing (which is the case for our system) . Hence conjunctive TFS have the form (r, {h ='= (h , . . . , fn ='= Bn}), whereas disjunctive are of the form (r, {81 , .. . , Bn}) .

Given a TFS B, type-of(B) returns the type of B, whereas typedef(r) obtains the type definition with­ out inherited constraints as given by the type system n = (0,I) . We call this TFS a skeleton. It is either (a, {Bl, ... ,Bn}) or (a, {h ='= B1 , ... , jn ='= Bn}), where a are the direct supertype(s) ofT.

Because the algorithm should support partially ex­ panded (delayed) types, we enrich each TFS B by two flags:

1. !::.- expanded (B) =true, iff typedef (type- a f (B)) and the definitions of all its supertypes have been unified with B, and false otherwise.
2. expanded(B)=true, iff t:.- expanded(B)=true and ex­ panded(Bi )=true for all elements Bi of TFS B.

Hence !::.-expanded is a local property of a TFS that tells whether the definition of its type is already present, while expanded is a global property which indicates that all substructures of a TFS are !::.-expanded. Clearly, atoms and types that possess no features are always ex­ panded. The exploitation of these flags leads to a drastic reduction of the search space in the expansion algorithm.

3.1 Basic Structure

The following functions briefly sketch the basic algo­ rithm. It is a destructive depth-first algorithm with a special treatment of recursive types that will be ex­ plained in Section 3.3.

expand- tfs is the main function that initializes TE. The while loop is executed until the TFS B is expanded or so-called "resolved" (see keyword :resolved-predicate in Section 3.5) . Several passes may be necessary for re­ cursive TFS.

expand- tjs(O) := while not ( expanded- p(O) or resolved- p(O) or no unification occurred in last pass) depth- first - expand ( 8) . I* or types-first-expand ( 0) , resp. *I

depth-first - expand and types-first-expand recursively traverse a TFS. Which of both functions is employed, can be specified by the user. The visited check is done by comparing variables (actually, structure-sharing in the implementation makes variables obsolete). types­ first - expand is defined analogously by first expanding the root type of a TFS, and then processing the feature constraints.

depth- first - expand ( 8) := if(} has been already visited in this pass then return else if(}= (T, {81 , ... 1 On}) then for every(} E {81, .. . , On} : depth- first - expand ( 8) else do I* 0 = (T, {/1 ='= 01, . .. , fn ='=On}) *I for every 0 E { 01, .. . , On} : depth- first- expand ( 8) ; if not b.-expanded( B) then unify- type-and- node( T, 8) od.

unify- type- and- node destructively unifies B with the ex­ panded TFS of T. The index L specifies which "proto­ type" ofT is chosen (see Section 3.2) .

unify- type- and- node(T, 0) := if T = ·a then unify-tfs ( negate- fs ( expand-type(a, ~)) , 0) else unify- tfs (expand- type( T, ~), 8); b.-expanded((}) t- true.

We adapt Smolka's treatment of negation for our TFS [Smolka, 1989]. Note that we only depict the conjunctive case here.

negate- fs(O = (T, {/1 ='= 01 , . .. , /n ='=On})) := return (T, {(·T, {}) , (T,{/1 t}) , (T, {/1 ='= negate-fs(Ol)}) , . .. , (T, {/n t}) , (T, {/n ='= negate-Js(On)})}) .

3.2 Indexed Prototype Memoization

The basic idea of memoization [Michie, 1968] is to tab­ ulate results of function applications in order to prevent wasted calculations. We adapt this technique to the type expansion function. The argument of our memoized ex­ pansion function is a pair consisting of a type name (or a name of a lexicon entry or a rule) and an arbitrary in­ dex that allows access to different TFS of the same type which may be expanded in different ways (e.g., partially or fully) . Such feature structures are called prototypes .

Once a prototype has been expanded according to the attached control information, its expanded version is recorded and all future calls return a copy of it, in­ stead of repeating the same unifications once again:

expand-type(T, index):= if protomemo(T, index ) undefined then (} t- expand- tfs ( typedef ( T)); protomemo( T, index) t- 8; return copy- tfs ( 8) else return copy- tjs(protomemo(T, index)).

Most of these computations can be done at compile time (partial evaluation), and hence speed up unification at run time. The prototypes can serve as basic blocks for building a partially expanded grammar.

Some empirical results indicate the usefulness of in­ dexed prototype memoization. Figure 1 contains sta­ tistical information about the expansion of an HPSG

grammar with approx. 900 type definitions. About 250 additional lexicon entries and rules have been expanded from scratch, i.e., all types are unexpanded (are skele­ tons) at the beginning. The type and instance skeletons together consist of about 9000 nodes, whereas the result­ ing structures have a total size of approx. 50000 nodes.

The measurements show that memoization speeds up expansion by a factor of 5 here (or 10 if all types ex­ cept the lexicon entries are pre-expanded). These fac­ tors are directly proportional to the number of unifica­ tions. The time difference between the memoized and non-memoized algorithm may be even bigger if disjunc­ tions are involved. The sample grammar contains only a few disjunctions.

3.3 Detecting Recursion

The memoization technique is also employed in detect­ ing recursive types. This is important in order to pre­ vent infinite computations. We use the so-called "ex­ pand stack" of expand-type to check whether a type is recursive or not (see Section 3.4). Each call of expand­ type( T, index) will push T onto the expand stack. This stack then is passed to expand-tfs.

If a type T on top of the expand stack also occurs below in the stack ( T, an , . . . , a1 , T, Pm , ... , pi) , we immediate know that the types T, an, ... , a1 are recursive. Further­ more, these types form a strongly connected component (sec) of the type dependency (or occurrence) graph, i.e., each type in the sec is reachable from every other type in the sec. Examples for such sees are (cons list) and (statel) in the trace of the example below (Section 3.4).

Testing whether a type is recursive or not thus reduces to a simple find operation in a global list that contains all sees. The expansion algorithm uses this information in expand-tfs to delay recursive types if the expand stack contains more than one element. Otherwise, prototype memoization would loop.

If a recursive type occurs in a TFS and this type has already been expanded under a subpath, and no features or other types are specified at this node, then this type will be delayed, since it would expand forever (we call this lazy expansion). An instance of such a recursive type that stops is the recursive version of list, as defined below.

3.4 Example

In the following, we define a finite automaton with two states that accepts the language a*(a +b) . The input is specified through a list under path INPUT ; cf. the definition of type ab below. The distributed (or named) disjunction [Eisele and Dorre, 1990] headed by $1 in type statel is used to map input symbols to state types (and vice versa). Defining FA this way provides a solid basis for the integration of automata-based allomorphy (e.g., 2-level morphology) and morphotactics within the same constraint-based formalism (cf. [Krieger et al., 1993]) .

Fig. 2 shows a trace of the expansion of type ab. The algorithm is depth-first-expand without any delay or preference information. In this trace, we assume that it was not known before that the types cons (abbreviat­ ed as ( . .. ) ), list, and statel are recursive, hence the sees will be computed on the fly.

The result of expand- type( ab) is the following feature structure:

If we ran our automaton on the input abb,

it would be rejected: expand-type(abb) =>fail.

3.5 Declarative Specification of Control Information

Control information for the expansion algorithm can be specified globally, locally for each prototype, as well as for a specific expand-tfs call. The following control key­ words have been implemented so far.

• :expand-function {depth I types }-first-expand specifies the basic expansion algorithm.
• :delay { ( {type I (type [pred])} {path}+ ) } * specifies types at path to be delayed. path may be a feature path or a complex path pattern with wildcard sym­ bols *, +, ? , feature and segment variables. pred is a test predicate to compare types, e.g., = or ~ (checked in unify-type-and-node).
• {:expandl:expand-only} { ( {type I (type [index [pred]])} {path}+ ) } * There are two mutually ex­ clusive modes concerning expansion of types. If the :expand-only list is specified, only types in this list will be expanded with the specified prototype in­ dex, all others will be delayed. If the :expand list

is specified, all types will be expanded (checked in unify- type- and-node).

• :maxdepth integer specifies that all types at paths longer than integer will be delayed anyway (checked in unify- type- and- node).
• :attribute-preference {attribute}* defines a partial order on attributes that will be considered in the functions depth- first -expand and types- first ­ expand. The substructures at the attributes left­ most in the list will be expanded first. This non­ numerical preference may speed up expansion if no numerical heuristics are known.
• :use-{conjldisj}-heuristics {tlnil} [Uszkoreit, 1991) suggested exploiting numerical preferences to speed up unification. Both keywords control the use of this information in functions depth- first -expand and types- first -expand .
• :resolved-predicate {resolved-plalways-falsel ... } This slot specifies a user definable predicate that may be used to stop recursion (see function expand- tfs) . The default predicate is always-false which leads to a complete expansion algorithm if no other delay information is specified.
• :ask-disj-preference {tlnil} If this flag is set tot, the expansion algorithm interactively asks for the order in which disjunction alternatives should be expand­ ed (checked in depth- first -expand and types-first­ expand)
• :ignore-global-control {tlnil} Specifies whether glob­ ally specified :expand-only, :expand, and :delay infor­ mation should be ignored or not .

Let us give an example to show how control infor­ mation can be employed. Note that we formulate this example in the concrete syntax of TD.C.

defcontrol verb ((:delay ((sign Subsumes) SYNSEM.NONLOCAL.?.SLASH)) ;; ? matches INHERITED and TO-BIND (:attribute-preference SYNSEM DTRS SUBCAT HEAD) (:use-disj-heuristics T) (:ignore-global-control T) (:expand ((local initial) *))) ;; *matches all paths in type local :index 1.

3.6 How to Stop Recursion

Type expansion with recursive type definitions is unde­ cidable in general , i.e., there is no complete algorithm that halts on arbitrary input (TFS) and decides whether a description is satisfiable or not (see Section 5). How­ ever, there are several ways to prevent infinite expansion in our framework:

• The first method is part of the expansion algorithm (lazy expansion) as described before.
• The second way is brute force: use the :maxdepth slot to cut expansion at a suitable path depth.

• The third method is to define :delay patterns or to select the :expand-only mode with appropriate type and path patterns.
• The fourth method is to use the :attribute-preference list to define the "right" order for expansion.
• Finally, one can define an appropriate :resolved­ predicate that is suitable for a class of recursive types.

4 Applications

In Section 3.4, we have already mentioned an NL ap­ plication in which type expansion was employed, viz., in the formulation of the interface between allomorphy and morphotactics [Krieger et al., 1993] . Let us quickly present two other areas that profit from type expansion: parsing/ generation as type expansion and distributed parsing with partially expanded information.

Parsing and generation can be seen in the light of type expansion as a uniform process, where only the phonol­ ogy (for parsing) or the semantics (for generation) must be given, for instance:

Type expansion together with a sufficiently specified grammar then is responsible in both cases for construct­ ing a fully specified feature structure which is maximal informative and compatible with the input structure.

Distributed parsing is a strategy which reduces the representational overhead: given one grammar which co­ specifies syntax and semantics, proper constraints (i.e., filters) are separated from purely representational con­ straints. The resulting subgrammars are then processed by two parsers in parallel. This presupposes that we can properly handle partially expanded typed feature struc­ tures.

5 Theoretical Results

It is worth noting that testing for the satisfiability of feature descriptions admitting recursive type equa­ tions/definitions is in general undecidable. [Rounds and Manaster-Ramer, 1987] were the first to have shown that a Kasper-Rounds logic enriched with recursive types al­ lows one to encode a Turing machine. Later, [Smol­ ka, 1989] argued that the undecidability result is due to the use of coreference constraints. He demonstrated his claim by encoding the word problem of Thue systems. Hence, our expansion mechanism is faced with the same result in that expansion might not terminate.

However, we conjecture that non-satisfiability and thus failure of type expansion is, in general, semi­ decidable. The intuitive argument is as follows: given an arbitrary recursive TFS and assuming a fair type un­ folding strategy, the only event under which TE termi­ nates in finite time follows from a local unification failure which then leads to a global one. In every other case, the unfolding process goes on by substituting types through their definitions. Recently, [A'it-Kaci et al., 1993] have formally shown a similar result by using the compact­ ness theorem of first-order logic. However, their proof assumes the existence of an infinite OSF clause (gener­ ated by unfolding a ~-term).

Thus, our algorithm might not terminate if we choose the complete expansion strategy. However, we noted above that we can even parameterize the complete ver­ sion of our algorithm to ensure termination, for instance to restrict the depth of expansion (analogous to the off­ line parsability constraint). The non-complete version always guarantees termination and might suffice in prac­ tice.

Semantically, we can formally account for such recur­ sive feature descriptions (with respect to a type system) in different ways: either directly on the descriptions, or indirectly through a transformational approach into (first-order) logic. Both approaches rely on the construc­ tion of a fixpoint over a certain continuous function. 4 The first approach is in general closer to an implemen­ tation (and thus to our algorithm) in that the func­ tion which is involved in the fixpoint construction cor­ responds more or less to the unification/substitution of TFS (see for instance [A'it-Kaci, 1986] or [Pollard and Moshier, 1990]) . The latter approach is based on the assumption that TFS are only syntactic sugar for first­ order formulae. If we transform these descriptions into an equivalent set of definite clauses, we can employ tech­ niques that are fairly common in logic programming, viz. characterizing the models of a definite program through a fixpoint. Take, for instance, our cyc-list example from the beginning to see the outcome of such a transforma­ tion (assume that cyc-list is a subtype of list) :

6 Comparison to other Approaches

To our knowledge, the problem of type expansion within a typed feature-based environment was first addressed by Hassan A'it-Kaci [A'it-Kaci, 1986]. The language he described was called KBL and shared great similarities with LOGIN; see [Alt-Kaci and Nasr, 1986]. However, the expansion mechanism he outlined was order dependent in that it substituted types by their definition instead of unifying the information. Moreover, it was non-lazy, thus it will fail to terminate for recursive types and per­ forms TE only at definition time as is the case for ALE [Carpenter and Penn, 1994]. However, ALE provides re­ cursion through a built-in bottom-up chart parser and through definite clauses. Allowing TE only at definition time is in general space consuming, thus unification and copying is expensive at run time.

Another possibility one might follow is to integrate TE into the typed unification process so that TE can take place at run time. Systems that explore this strategy are TFS [Zajac, 1992] and LIFE [A'it-Kaci, 1993]. However, both implementations are not lazy, thus hard to control and moreover, might not terminate. In addition, if pro­ totype memoization is not available, TE at run time is inefficient; cf. Fig. 1). A system that employs a lazy strategy on demand at run time is CUF [Di::irre and Dor­ na, 1993]. Laziness can be achieved here by specifying delay patterns as is familiar from PROLOG. This means delaying the evaluation of a relation until the specified parameters are instantiated.

4 In both cases, there is, in general, more than one fixpoint , but it seems desirable to choose the greatest one, as it would not rule out, for instance, cyclic structures.

7 Summary

Type expansion is an operation that makes constraints of a typed feature structure explicit and determines its satisfiability. We have described an expansion algorithm that takes care of recursive types and allows us to ex­ plore different expansion strategies through the use of control knowledge. Efficiency is addressed through spe­ cialized techniques: (i) prototype memoization reduces the number of unifications, and (ii) preference informa­ tion directs the search space. Because our notion of type expansion is conceived as a stand-alone module here, one can freely choose the time of its invocation, e.g., during typed unification, parsing, etc.

The algorithm, as presented in the paper, has been ful­ ly implemented within the TDC/UDiNe system [Krieger and Schafer, 1994; Backofen and Weyers, 1994] and is an integrated part of Drsco [Uszkoreit et al., 1994].

We are convinced that our approach is also of interest to those who are working with (possibly recursive and hi­ erarchically ordered) record-like data structures in other areas of computer science.