ALE Data Structure

[Code]
Internally, ALE represents a feature structure as a term of the form Tag-Sort(V1,...,Vn) where Tag represents the token identity of the structure using a Prolog variable, Sort is the name of the type of the structure. The terms V1 through Vn are the values for the features F1 through Fn that are appropriate for the type Sort. The features are sorted alphabetically based on their names in V1...Vn. This results in the kind of record structure presented in Figure 1.1 for feature structures.

Figure 1.1: Internal representation of Tag-Sort(V1,...Vn)

When a type is promoted, Tag is replaced with a new pair of Tag-Sort(V1,...,Vm) with m possibly larger than n in order to make room for any new features introduces by the new type. For example, given the type signature in Figure 1.2, the internal ALE representation of the feature structure in (1) will be (2).

Figure 1.2: A sample type signature

But when this type is promoted to noun, the ALE representation of that type is updated to (3).

Note that in this example, the variable Tag of (2) has been bound to Tag2-noun(Z-case,X-plus,Y-minus) in (3), and now we have a new tag (Tag2) at the beginning of the reference chain. The positional encoding of feature values in this manner means that, at compile time, we know which features any two types have.