Procedural Attachments

A more complicated rule, drawn from the categorial grammar in the appendix is as follows:

  backward_application rule
  (synsem:Z,
   qstore:Qs)
  ===> 
  cat> 
    (synsem:Y,
     qstore:Qs1),
  cat> 
    (synsem:(backward,
             arg:Y,
             res:Z),
     qstore:Qs2),
  goal>
    append(Qs1,Qs2,Qs).

Note that the goal in this rule is specified after the two category descriptions. Consequently, it will be evaluated after categories matching the descriptions have already been found, thus ensuring in this case that the variables Qs1 and Qs2 are instantiated. The append(Qs1,Qs2,Qs) goal is evaluated by ALE's definite clause resolution mechanism. goal> attachments are always evaluated in the order they are specified relative to the enforcement of cat> and cats> daughters, from left to right. All possible solutions to the goal are found with the resulting instantiations carrying over to the rule. These solutions are found using the depth-first search built into ALE's definite constraint resolver. In general, goals may be interleaved with the category specifications, giving the user control over when the goals are fired. Also note that goals may be arbitrary cut-free ALE definite clause goals, and thus may include disjunctions, conjunctions, and negations. Cuts may occur, however, within the code for any literal clause specified in a procedural attachment. The attachments themselves must be cut-free to avoid the cut taking precedence over the entire rule after compilation, thus preventing the rule to apply to other edges in the chart or for later rules to apply. Instead, if cuts are desired in rules, they must be encapsulated in an auxiliary predicate, which will restrict the scope of the cut. For instance, in the context of a phrase structure rule, rather than a goal of the form:

  goal>
    (a, !, b)

it is necessary to encode this as follows:

  goal>  
    c

where the predicate c is defined by:

  c if 
    (a, !, b).

This prevents backtracking through the cut in the goal, but does not block the further application of the rule. A similar strategy should be employed for cuts in lexical rules.

As a programming strategy, rules should be formulated like Prolog clauses, so that they fail as early as possible. Thus the features that discriminate whether a rule is applicable should occur first in category descriptions. The only work incurred by testing whether a rule is applicable is up to the point where it fails.

Just as with PATR-II, ALE is RE-complete (equivalently, Turing-equivalent), meaning that any computable language can be encoded. Thus it is possible to represent undecidable grammars, even without resorting to the kind of procedural attachment possible with arbitrary definite clause goals. With its mix of depth-first and breadth-first evaluation strategies, ALE is not strictly complete with respect to its intended semantics if an infinite number of edges can be generated with the grammar. This situation is similar to that in Prolog, where a declaratively impeccable program might hang operationally.