TRALE-EXTENSION:Step One: Generating Frames

In this first step of the compiler, we assert lexical rule predicates corresponding to each user-specified lexical rule, in addition to frame predicates for each lexical rule. Generally speaking, frames specify which feature values in the input are equated with the corresponding value in the output, and, when called, the frame predicates achieve the transfer of this information from one lexical entry (the input) to a derived lexical entry (the output).

In terms of input to the actual process of frame generation, we are working with two feature descriptions (lexical rule input and output), which may or may not be of the same type. When a feature appropriate to the type of both lexical rule input and output is not mentioned in the output description, we ensure transfer of the input specification to the output via a path equality in the frame predicate. The process of frame generation is recursive, since the (possible) need for path equalities to transfer information applies not only at the top level, but along all paths and subpaths mentioned in the output description. At any level, that is, even when we are working with feature structures or descriptions embedded in our original input, we refer to the current input to the process as lexical rule input and output.

The frame predicates have three arguments: the first identifies the associated lexical rule, while the second and third (referred to as IN and OUT, respectively) are feature structures of type word (or some maximally specific subtype of word). Path equality in TRALE is realized by means of variables. For feature values that demand a path equality (as described above), we assign the same variable as the value of that feature in both IN and OUT. By unifying the input of the lexical rule with IN and the output of the lexical rule with OUT, ``transfer'' is achieved.

Two aspects of the task of frame generation here make it relatively complicated: disjunction in the descriptions, and types. We discuss issues related to disjunction in section T8.2.1, and the interpretation of types in the input and output of a lexical rule with respect to framing in section T8.2.2.

TRALE-EXTENSION:Disjunction in the input and output specifications

While our treatment of disjunction in the lexical rule specifications is consistent with ordinary interpretation of disjunction in TRALE, there are several aspects of that interpretation worth discussing in this particular context.

First, it should be noted that disjunction in a description is a compact representation of two distinct feature descriptions, and so disjunction in the input or output descriptions of a lexical rule is actually a compact representation of what could be two distinct lexical rules. Second, TRALE's syntax does not include named disjunction. For example, an input description a;b with an output description c;d does not restrict the possible mappings of input to output to a to c and b to d. Instead, such a specification allows fours possible mappings of input to output: a to c, a to d, b to c, and b to d. A disjunction in the input or output of a lexical rule means that we will need to calculate a frame corresponding to each disjunct. Each disjunction in either input or output multiplies the number of frames needed by two.

Further, TRALE's internal feature structure representation does not include disjunction. If asked to translate the the user-specified description (a;b) to a feature structure, Prolog will return a. The feature structure b is obtained by asking for more solutions. The disjunctive possibilities with regard to a feature description can be generated by means of code which utilizes a failure-driven loop calling TRALE's translation predicate and then collects the results, or by means of code which step-wise multiplies out the disjunctions, yielding some number of disjunctionless feature descriptions.

In our implementation of the algorithm, we deal with disjunction in the input and output of a lexical rule differently, based on the kind of representation we want to work with during the compilation process. Because we only make use of the internal representation of the input during processing, and not the original user-specified description, we use a failure-driven loop to generate all possible input feature structures. Because we want to know what the user has specified in the output, which is not possible to know from the internal representation of that description, we work with feature description representations of the output during processing. We have implemented code which takes a feature description possibly containing disjunction as input, and returns a list of disjunctionless descriptions. We then then generate a list of frames for each input-output pair.

TRALE-EXTENSION:Interpreting lexical rule descriptions

A lexical rule can apply to a variety of lexical entities. While each of these lexical entities must be described by the input of the lexical rule in order for the rule to apply, other properties not specified by the lexical rule can and will vary between lexical entries. Feature structures corresponding to lexical entities undergoing the lexical rule therefore may differ in terms of type value and appropriate features. Frames carrying over properties not changed by the lexical rule need to take into account different feature geometries. Since framing utilizes structure sharing between input and output, we only need to be concerned with the different kinds of objects that can undergo a lexical rule with regard to the paths and subpaths mentioned in the output description. Specifically, when the objects undergoing lexical rule application differ with regard to type value along some path mentioned in the output description, we may need to take into account additional appropriate attributes in framing. Each such possibility will demand its own frame.

We provide a truthful procedural realization of the formal interpretation of lexical rules defined in Meurers (2001). Generally speaking, the input description of a lexical rule specifies enough information to capture the class of lexical entries intended by the user to serve as inputs. The output description, on the other hand, specifies what should change in the derivation. All other specifications of the input are supposed to stay the same in the output.

In the spirit of preserving as much information as possible from input to output, we generate frames on the basis of species (=most specific type) pairs; that is, we generate a frame (an IN-OUT pair) on the basis of a maximally specific input type, and a maximally specific output type, subtypes of those specified in, or inferred from, the lexical rule description. In this way we maintain tight control over which derivations we license, and we guarantee that all possible information is transferred, since the appropriate feature list we use is that of a maximally specific type. We create a pair of skeleton feature structures for the species pair, and it is to this pair of feature structures that we add path equalities. We determine the appropriate list of species pairs on the basis of the types of the input and output descriptions.

The first step in this process is determining the types of the input and output of the lexical rule. We then obtain the list of species of the input type, and the list of species of the output type. We refer to these as the input species list, and the output species list, and their members as input and output species. At this point it will be helpful to have an example to work with. Consider the type hierarchy in figure 8.2.

Figure 8.2: An example hierarchy illustrating the interpretation

We can couch the relationship between the input and output types in terms of type unification, or in terms of species set relations. In terms of unification, there are four possibilities: the result of unification may be the input type, the output type, something else, or unification may fail. In the first case the input type is at least as or more specific, and the input species will be a subset of the output species. In the second case the output is more specific and the output species will be a subset of the input species. In the third case the input and output types have a common subtype, and the intersection of input and output species is nonempty. In the fourth case the input and output types are incompatible, and the intersection of their species sets is empty.

Given in figure 8.3 are examples of all four cases, using the example signature, showing input and output types, the result of unification, their species lists, and the species-pairs licensed by the algorithm described below. Calling these separate ``cases'' is misleading, however, since the algorithm is the same in every case.

Figure 8.3: Examples for the four cases of mappings

If a (maximally specific) type value can be maintained in the output, it is. Otherwise, we map that input species to all output species. In terms of set membership, given a set of input species $X$, a set of output species $Y$, the set of species pairs $P$ thus can be defined as:

$$P = \{\langle x,x\rangle \mid x \in X \wedge x \in Y\} \cup \{\langle x,y\rangle \mid x \in X, x \not\in Y \wedge y \in Y\}$$

This definition translates to a simple algorithm in the code itself:

• For an input species x, if x is a member of the output species list, then calculate a frame for x-x.

• Otherwise, calculate a frame for every x-y pair, where y is an output species.

TRALE-EXTENSION:Overview of code for frame generation

Taking the input and output descriptions for a particular lexical rule, we first generate a list of possible feature structures corresponding to the input description. (As discussed in section T8.2.1 there will be multiple feature structures if there is disjunction in the description.) We then derive from the output description a list of disjunctionless descriptions, and obtain the internal representation of each.^8.2For each input-output pairing (where ``output'' is itself a description-feature structure pair), we obtain the list of species pairs for which we want to generate a frame predicate. In a species pair, we refer to the input species as IN and the output species as OUT.

There may in fact be more than one frame necessary per species pair because of embedded feature structures which themselves require multiple ``small'' frames. For each of these, a copy of the larger frame (an IN-OUT pair) is created, and the small IN and OUT are assigned as feature values in the larger frame. Therefore, we obtain a list of frames for each species pair.

Given a particular species pair, we create skeleton feature structures for the IN and OUT types that constitute the pair, and obtain a list of appropriate features for the OUT type. We then walk through the output description, removing mentioned features from the appropriate features list. Concomitantly, when we find a feature with a non-atomic value during the walk-through, we call the process of frame generation for the description which is the value of that feature in the output, generating a list of ``small'' frames, which are incorporated into the larger one (as mentioned in the previous paragraph). This is accomplished by obtaining the embedded feature structures from the frames and unifying the small frames with these. This process of walk-through, removing mentioned features from an appropriate-feature list and incorporating small frames into large ones, applies recursively along every path and subpath in the output description.

Once we have walked through the entire output description at a particular level of embedding, path equalities are added for features which are appropriate for the input type and have not been removed from the appropriate features list of the output.