Control in FUF

Pure functional unification can be too slow for practical tasks. FUF offers several control tools that allow the grammar writer to make a grammar more efficient. This section summarizes how control is specified in FUF.

The approach has been to add annotations to the grammars that can be used by the unifier to improve performance. In a sense, this annotation approach is similar to the ``optional type declarations'' in Common Lisp. An important constraint that has been maintained is that the annotations do not change the semantics of the grammar, but uniquely the order in which the unifier processes it.

All the control annotations are applied to disjunctions. From the measurements made on FUF working on large grammars, it was found that optimization of conjunctions was not necessary, as the average length of conjunctions over the course of a unification is quite small (on the order of 10) and time spent processing them is quite small. In contrast, the overhead associated with dealing with disjunctions is quite high.

The control techniques for disjunctions implemented in FUF are the following:

• indexing

• dependency-directed backtracking

• lazy-evaluation / freeze

• conditional evaluation

In addition to these control mechanisms, a series of ``impure'' mechanisms ease the integration of unification-based processing in a larger practical system:

• type hierarchies and procedural typing

• external functions

• ``given'' checking

When all annotations are considered, the syntax of an alt or ralt constructs is:                              

          


(alt { traceflag | (trace on traceflag) | (:trace flag) }
     { (index on path) | (:index path)}
     { (demo str) | (:demo str)}
     { (bk-class class) | (:bk-class class) }
     { (:order {:random | :sequential}) }
     { (:wait <list>) }
     { (:ignore-unless <list>) }
     { (:ignore-when   <list>) }
     ( fd1 ... fdn ))


The annotations (trace, index, bk-class, order, wait and ignore)
can appear in any order.
          
          

This chapter explains and gives examples on how these control features of FUF operate. To better understand why control annotations can make unification faster it is necessary to understand what makes unification slow. So we start by a discussion of how to measure the complexity of a grammar.