Sorting

In this phase, the compiler goes through the instructions and using its knowledge about the type signature on which the grammar is based, it gathers all the necessary information about the description. Before we go any further, we need to define the concept of mode.

When compiling a description, ALE needs to keep track of the information that it has about that description at any given time. This information may not refer to just one feature structure sometimes. For instance, if a description is used in the context of a phrase-structure rule, it may contain variables that have scope over the whole rule. All of the information that ALE has about a description within the current variable scope context (i.e., a phrase-structure rule, complex-antecedent constraints, or simply a line of ALE code) is referred to as mode. We can think of mode as a partial function from the union of all paths and variables to totally well-typed feature structures.

Definition 16   (mode) Given a set of paths $\Pi$, a set of variables $V$, and a set of totally well-typed feature structures $TTF$, we have $mode: \Pi\cup V\rightharpoonup TTF$.

In ALE, mode is represented as paths for terms. We call this Mode. A slightly different kind of Mode is used to keep track of the information ALE has about variables.

Definition 17   (VMode) A Variable Mode (VMode) is a triple $\langle FS, Flag, CBSafe\rangle$ where:

• $FS$ is a feature structure;
• $Flag = \{seen,tricky\}$;
• $CBSafe = \{true,false\}$.

VMode holds for each variable a feature structure $FS$ that is the most general satisfier of that variable depending on its context, a $Flag$ that says whether the variable is $seen$ or $tricky$ (to be discussed shortly), and a $CBSafe$ flag that says whether it is safe to bind that variable at compile-time or not.

When sorting, ALE starts with a minimal Mode (typically $\bot$), and begins going through the instructions adding information as necessary. Let us continue working through our running example from the previous section. The first instruction to process, then, is type [],phrase. What we do at this point is add the most general satisfier of phrase to Mode (in this case $\bot$). This results in the promotion of $\bot$ to phrase which also entails adding all the features introduced by phrase (in this case, only DTRS; see Figure 4.1). ALE goes through the other instructions similarly. When a path is encountered, as in the second instruction type [dtrs], hc_struct, ALE starts at the end of the path (i.e., the terminal path []), and unifies the most general satisfier of the introducer of each feature in the path with the Mode. Note that each nonterminal element in the path refers to a feature. In order to access the value of that feature, ALE needs to make sure that it has access to it, meaning that the Mode contains the most general satisfier of the introducer of that feature. That is why we add the most general satisfier of each element to the Mode. Each instruction, therefore, potentially changes the Mode. If an instruction fails to modify the Mode, it is considered redundant and thus eliminated. An example of this is instruction 2. In this case, ALE ends up not adding anything to the Mode because (assuming that our type signature includes what is depicted in Figure 4.1) all phrases have a DTRS feature with the value restriction hc-struct.

Figure 4.1: A portion of a type signature

After this overview, let us see how each kind of instruction is utilized to potentially modify the Mode. A summary of the actions that ALE takes on the face of each kind of instruction is provided in Table 4.2.

Table 4.2: Summary of actions taken by ALE, for each kind of instruction

Instruction	Action
type Path,Type	Unify the most general satisfier of Type with the Mode of Path.
var Path,Var	Unify the mode of Var with the Mode of Path.
fs Path,FS	Unify FS with the Mode of Path.
ineq Path1,Path2	Do nothing.
fun Rel,Arity,ArgPaths,ResPath	First check ArgPaths to see if the most general satisfier of the input type of each argument subsumes the Mode of the path of that argument. Then unify the input path with the most general satisfier of the output of that argument.
or Path,(Code1;Code2)	Do the above with each disjunct. Then using finite-state automaton intersection and type generalization, combine the output Mode of each disjunct to get the output mode of the whole disjunction.

The arguments of each function are associated with two type specifications: an input type and an output type. Because ALE is a logic-programming language, each argument in a function can potentially be an input or an output argument. The type declarations for the arguments of functions are written as InputType-OutputType pairs. When the user specifies only a single type for the argument of a function, as in Type, ALE interprets that as Type-Type. Therefore,

foo(t,u,v).

is equivalent to

foo(t-t,u-u,v-v).

When executing fun instructions, ALE does not add the type of the input Mode of the function to the Mode. Instead, it just checks to see if the path corresponding to each argument in the function has the input Mode. For instance in the case of append 2,[0,1], it only makes sure that the mode corresponding to the variables 0 and 1 has the type list in its Mode.

Earlier, we mentioned that the initial Mode typically starts with $\bot$. This is true for most descriptions except type-antecedent constraints and relational calls. In the case of a type-antecedent constraint, Type cons Cons, the initial Mode is the most general satisfier of Type. In the case of a relational call, on the other hand, the initial Mode is the most general satisfier of the input Mode.

If during sorting adding a type to the Mode fails at some point, an error message is displayed to the user. If the failure happens within a disjunction however, we wait to see if the other disjunction fails as well. If it does, we complain to user; and if it does not, we will simply eliminate the disjunct that fails together with the disjunction operator.