Wait and Constituent Traversal

The delaying of disjunctions interacts in a complex manner with the way the constituent structure is traversed. Recall that the traversal proceeds as follows: the toplevel constituent is unified with the grammar, then at the end of the unification (before determination time), the cset of the constituent is identified, and every descendant specified in the cset is traversed, in order. The structure is then traversed breadth first.

As explained in Sect., there are two ways to specify a cset in a constituent in FUF: implicitly and explicitly. The cset is explicitly specified if there is a complete cset feature found in the constituent. Otherwise it is implicit. The implicit cset is found by using two heuristics: first it is assumed that any path mentioned in a pattern is also a constituent; second, any feature which contains a sub-feature of the form (cat xx) is also assumed to be a constituent.

To override these heuristics, the grammar writer can use incremental cset specifications. There are indeed two types of cset specifications: complete and incremental. A complete specification is of the form (cset (c1 ... cn)) and exhaustively identifies all the subconstituents of the current constituent. An incremental specification is of the form: (cset (+ a ₁ ... a_m) (- d₁ ... d_p )) An incremental cset specifies that all the a_is should be added to the implicit cset and all the d_js should be removed from it. The possibility of specifying the constituent structure incrementally is a great convenience practically since it allows the grammar writer to give partial information on constituency in different regions of the grammar.

Incremental cset specifications may affect delayed disjunctions. The following example illustrates this situation:

          
((alt (:wait {^ manner conveyed})
  (((manner ((conveyed any)))
   ((manner ((conveyed adverb)
             (cat adverb) ...))
    (cset ((+ manner))))))))
          
          

In this case, the decision to express the manner constraint by using an adverb is delayed, leaving a chance for the verb to express it as a connotation. Thus, in the first pass through the grammar, this alt is not evaluated. At the end of the processing of the clause constituent, the cset is determined. The implicit cset is computed and all the incremental cset specifications are added on it. At this point, the manner feature is not identified as a constituent, since there is no cat specified for it and no incremental cset has added it explicitly. The constituent structure is then traversed. At the end of this traversal, the delayed alts on the agenda are processed. The manner alt is thus unblocked, and the second branch is eventually selected. An adverb constituent is then added at the clause level. When the alt is completely processed, this adverb constituent should be unified with the adverb grammar as any subconstituent would be, if it had been processed without being delayed. Unfortunately, the constituent structure was already computed before the delayed alt was unblocked. And the adverb was not part of the cset at this time. So the adverb is not added to the final constituent structure of the clause.

  I have extended the determination process to re-check the constituent structure whenever an alt has been unblocked during determination, thus allowing new constituents to be added by delayed alts without restriction. The determination process performs the following task: first, a delayed alt is selected (the first one that was put on the agenda is chosen) and its evaluation is forced. Next, unification starts again to evaluate all the delayed alts which have been unblocked by the evaluation of the forced alt. At the end of this unification step, determination starts again. This loop continues until the agenda is empty. At this point, the constituent structure is recomputed and retraversed from the top of the total FD down, in breadth-first order. All constituents which have already been unified are skipped, all new constituents identified by the recomputation of the csets at the end of the agenda evaluation are unified again. After this unification step, determination starts again from scratch (since the evaluation of the new constituents may have added delayed alts on the agenda), until the agenda is empty and all constituents have been unified.

This top-down traversal in several passes integrates nicely the regular top-down control regime with the benefits of the dynamic re-ordering of constraints provided by wait. Note that this traversal in several passes does not translate in reduced efficiency: it is only triggered when needed (that is, when decisions had to be delayed), and the traversal/recomputation of the constituent structure is a very efficient operation. As measured, efficiency is overall drastically improved with wait.