Indexing

The main problem for FUF is to handle non-deterministic constructs in the grammar. The non-deterministic constructs are currently: alt, ralt, opt and pattern. Unification of these constructs with an input can produce several results. Whenever the unifier encounters such a construct, it does not know which of the possible results to choose. For example, when unifying an alt there is no way to choose a branch out of the many available in the alt. The way the program works is to try each of the possibilities one after the other. When the unification later on fails, the program backtracks and tries the next possibility.

This method is actually a blind search through the space of all the descriptions compatible with the grammar. Indexing is a technique used to guide the search in a more efficient way when more knowledge is available. Other heuristics to control search are discussed in Section and include goal freezing (with the wait control) and dependency-directed backtracking (with the bk-class construct).      

FUF allows indexing of alt and ralt constructs. ¹² Indexing tells the unifier how to choose one branch out of the alternation based on the value of the index only, and without considering the other branches ever. The following example illustrates the technique.

          
Example taken from gr4


((alt (:trace process) (:index process-type)
   (((process-type actions)
     ...)
    ((process-type mental)
     ...)
    ((process-type attributive)
     ...)
    ((process-type equative)
     ...)))
 ...)
          
          

In the example, the (:index process-type) declaration indicates that all the branches of the alternation can be distinguished by the value of the process-type feature alone. If the input contains a bound feature process-type, it is possible to directly choose the corresponding branch of the alternation. If however the input does not correspond such a feature, it has to go through the alt in the regular way, with no jumping around.  

This is what happens in the tracing messages for each case:

          
If input is:
    ((cat clause) (process-type attributive) ...)
Trace message is:
    ->Entering alt PROCESS - Jump indexed to branch 3 ATTRIBUTIVE


If input does not contain a feature process-type:
    ((cat clause) (prot John) ...)
Trace message is:
    ->No value given in input for index PROCESS-TYPE - No jump
    ->Entering alt PROCESS - Branch #1
          
          

A grammar is always indexed at the top-level by the cat feature (or the currently set cat attribute  ). It makes more sense to index on the features that will be bound in the input or at the moment the alt or ralt will get tried, but it never hurts to index an alt, so it is recommended to index whatever is indexable.  

The indexed feature can be at the top level of all the branches, as in the first example for process-type, but it can also be at lower levels, like in the following example:

          


Example taken from gr4:


((alt verb-trans (:index (verb transitivity-class))
   (((verb ((transitivity-class intransitive)))
     ...)
    ((verb ((transitivity-class transitive)))
     ...)
    ((verb ((transitivity-class bitransitive)))
     ...)
    ((verb ((transitivity-class neuter)))
     ...))
 ...))


          
          

If the index identifies more than one branches in the disjunction, then the index will serve to prune the disjunction from all the banches that do not match the index, and the search will continue with the remaining branches as usual. For example:

          


((alt (:index cat)
   (((cat clause)
     (mood declarative)
     ...)
    ((cat clause)
     (mood non-finite)
     ...)
    ((cat np)
     ...)))
  ...)
          
          

When this disjunction is unified with the input (cat clause), two branches are retained by the index matcher (branches 1 and 2). Branch 3 does not match the index and is therefore eliminated. The unifier will then proceed with the alt as if it only contained branches 1 and 2.

Note that if a branch does not contain a bound value for the index, it is as if it contains the value NIL, and it will therefore always retained in the alt after the index matching.

WARNING: index does not work if several branches are grouped together with an alt embedded under the key attribute. For example, the following input will fail with the following grammar:

          
((cat clause) (mood finite))


((alt (:index cat)
  (((cat ((alt (clause np vp))))
    (cset ((== head))))
   ((cat ((alt (n v adj))))
    (cset (=))))))
          
          

The unification fails because clause does not match the expression ((alt (clause np vp))) in the index search. The reason for this limitation is that index is a speed optimization feature, and making it support alt in some rare cases would make all uses of index slower. It has therefore been decided to make index more restricted and more efficient.