Extensionality

ALE also respects the distinction between intensional and extensional types (see Carpenter (1992:Chapter 8). The concept of extensional typing has its origins in the assumption in standard treatments of feature structures, that there can only be one copy of any atom (a feature structure with no appropriate features) in a feature structure. Thus, if path $\pi_{1}$ leads to atom a, and path $\pi_{2}$ leads to atom a, then the values for those two paths are token-identical. Token-identity refers to an identity between two feature structures as objects, as opposed to structure-identity, which refers to an identity between two feature structures that contain the same information.

Smolka (1988a) partitioned his atoms according to whether more than one copy could exist or not. In ALE, following Carpenter (1992), this notion of copyability has been extended to arbitrary types - loosely speaking, those types which are copyable we call intensional, and those which are not we call extensional. Thus, it is possible to have two feature structures of the same intensional type which, although they may be structure-identical, are not token-identical. Formally:

Given the set of types, Type, defined by an ALE signature, we designate a subset, ${\sf ExtType} \subseteq {\sf Type}$, as the set of extensional types. With the exception of a_/1 atoms, discussed below, this set consists only of maximally specific types, i.e., for each $\sigma \in {\sf ExtType}$, there is no type $\tau$ such that $\sigma$ subsumes $\tau$.

The restriction of ExtType to maximally specific types is peculiar to ALE, and is levied in order to reduce the computational complexity of enforcing extensionality.^4.6

We need one more definition to formally state the effect which an extensional type has on feature structures in ALE.

Given a set of extensional types, ExtType, we define an equivalence relation, $\asymp$, the collasping relation, on well-typed feature structures, such that $F_{1} \asymp F_{2}$ for $F_{1} \neq F_{2}$ only if:

• $F_{1}$ has the same type, $\sigma$, as $F_{2}$, and $\sigma \in {\sf ExtType}$, and
• for every feature, $f$, appropriate to $\sigma$, $F_{1}^{f}$, the value of $f$ in $F_{1}$, and $F_{2}^{f}$, the value of $f$ in $F_{2}$, are defined, and $F_{1}^{f} \asymp F_{2}^{f}$.

In ALE, all feature structures behave as if they are what Carpenter (1992) referred to as collapsed. That is, the only collapsing relation that exists between any two feature structures is the trivial collapsing relation, namely:

$F_{1} \asymp F_{2}$ if and only if $F_{1}$ is token-identical to $F_{2}$.

In the case of acyclic feature structures, this definition is equivalent to saying that two feature structures of the same extensional type are token-identical if and only if, for every feature appropriate to that type, their respective values on that feature are token-identical. For example, supposing that we have a signature representing dates, then the two substructures representing dates in the following structure must be token identical.

  married_person
  BIRTHDAY [1] date
           DAY  12
           MONTH nov
           YEAR 1971
  SPOUSE BIRTHDAY [1] date
                  DAY 12
                  MONTH nov
                  YEAR 1971

In other words, this represents a person born on 12 November 1971, who is married to a person with the same birthdate.

Now consider a slightly more complex example, which employs the following signature.

  bot sub [a,b,c,g].
    a sub []
      intro [f:b,g:c].
    b sub [].
    c sub [].
    g sub []
      intro [h:a,j:a].

If a, b, and c are extensional, then the values of H and J in g are always token-identical, i.e., every feature structure of type g satisfies:

  g
  H [0] a
    F b
    G c
  J [0]

But if only a, and b are extensional, and c is intensional, then the values of H and J are not necessarily token-identical, although they are always structure-identical:

  g
  H a
    F [1] b
    G c
  J a
    F [1]
    G c

To cite an earlier example, suppose we were to specify that the type false, used in the liar sentence and its negation, were extensional. Now the liar sentence's representation is:

  [0] false
      ARG1 [0]

as before, but the negation of the liar sentence would also be represented by:

  [0] false
      ARG1 [0]

since if were still represented by:

  [1] false
  ARG1 [0] false
       ARG1 [0]

then we could cite a non-trivial collasping relation, $\asymp$, in which $[1] \asymp [0]$.

As a related example, consider:

  s
  A [0] t
    C [0]
  B [1] t
    C [1]

Assuming that t is extensional and only appropriate for the feature C, then the structures [0] and [1] in the above structure would be identified.

Extensionality allows the proper representation of feature structures and terms in both PATR-II, the Rounds-Kasper system, and in Prolog and Prolog II. For PATR-II and the Rounds-Kasper system, all atoms (those types with no appropriate features) are assumed to be extensional. Furthermore, in the Rounds-Kasper and PATR-II systems, which are monotyped, there is only one type that is appropriate for any features, and it must be appropriate for all features in the grammar. In Prolog and Prolog II, the type hierarchy is assumed to be flat, and every type is extensional.

Just as with implementations of Prolog, collapsing is only performed as it is needed. As shown by Carpenter (1992), collapsing can be restricted to cases where inequations are tested between two structures, with exactly the same failure behavior. It turns out to be less efficient to collapse structures before asserting them into ALE's parsing chart, primarily because the time to test arbitrary structures for collapsibility is at least quadratic in the size of the structures being collapsed. See the section below on inequations for further discussion. Currently, extensionality is only enforced before the answer to a user query is given.

Extensional types in ALE are specified all at once in a list:

${\tt ext([}ext_{1}, \ldots, ext_{n}{\tt ]).}$

in the same file in which the subsumption relation is defined. All types that are not mentioned in the ext specification are assumed to be intensional, except ALE's a_/1 atoms, discussed below, which have the same extensionality as Prolog terms, i.e., if they are ground or have the same variables in the same positions.^4.7These do not need to be declared as such. If more than one ext specification is given, the first one is used. If no ext specification is given, then the specification:

  ext([]).

is assumed. If a type occurs in ext/1, but does not appear on the left or right-hand side of a sub declaration, it assumed to be maximal, and immediately subsumed by bot.

Of course, collapsing is only enforced between feature structures whose life-spans in ALE^4.8 overlap. So, for example, if one request is made for the representation of the liar sentence:

  [0] false
      ARG1 [0]

and then another is made for that of its negation, the output is not:

  [0]

(referring to the same token above) but rather:

  [0] false
      ARG1 [0]

Every time a new context arises, numbering of structures begins again from [0].