Lazy Evaluation and Freeze with wait

The bk-class mechanism is useful in general to correct directly a decision made a long time ago, as soon as it appears that the decision was wrong. But this implies that all the work done between the wrong decision and the realization that it is wrong must be re-done once the original wrong has been corrected. For example, in the following case:

          


Frame TOP  -----> failure because of feature P
 Frame T100 )
 Frame T099 )
...        )--> Lots of decisions that do not
...        )      affect the value of P.
...        )
 Frame T016 )
 Frame T015 -----> feature P is set to wrong value
 Frame T014
...
 Frame T001
          
          

The decisions corresponding to frames T016 to T100 are going to be done twice because T015 made the wrong choice originally. While making a decision twice is not too bad compared to the cost of exhaustively searching all the choices corresponding to frames T016 to T100 backwards, it is still sub-optimal.

One could reach a more efficient solution if the decision corresponding to frame T015 is delayed and the unifier commits to a value for P only after frame T100. The wait control specification is used to achieve this effect under certain conditions.

Wait specifies that the decision corresponding to a disjunction depends on the value of certain features. The syntax is as follows:

          
(alt TP (:wait P) ...)
          
          

This declaration indicates to the unifier that the alt TP depends on the value of the feature P. If when it is first met feature P is instantiated, then the alt is evaluated normally. If however P is not yet instantiated, the whole disjunction is delayed: it is put on hold, on an agenda. The rest of the grammar is evaluated, and periodically, the unifier checks the agenda to determine if one of the frozen alts can be awakened.

The following example illustrates a possible use of wait:

          


;; In conjunction: do verb ellipsis?
 ;; If the same verb is used in both conjuncts
 ;; you can ellide it in the second conjunct:
 ;; -> John ate the burger and Mary the fish.
 ;; The ellipsis is done by adding a GAP feature to the second verb.
 ;; Wait until verbs for both conjuncts have been selected.
 ;; This alt does NOT determine what the verbs should be.
 (alt verb-ellipsis (:wait {constituent1 process lex}
                               {constituent2 process lex})
   (((cat clause)
     ({^ constituent1 process lex} {^ ^ ^ ^ constituent2 process lex})
     ({^ constituent2 process gap} yes)
     (verbal-ellipsis yes))
    ((verbal-ellipsis no)))))
          
          

This fragment is extracted from grammar gr10. It is part of the branch of the grammar dealing with conjunction. This alt implements the decision whether to use a verb ellipsis in a conjunction of two clauses. The verb in the second conjunct can be elided if it the same lexical entry as the verb in the first conjunct. This match is checked by testing that the {constituent1 process lex} path can be unified with the {constituent2 process lex} path. When it can be unified, the {constituent2 process} is enriched with the feature (gap yes), which the linearizer will interpret by skipping the verb in the final sentence.

  Now remember that the standard control flow in FUF is top-down breadth-first in the tree of constituents. A conjunction of clauses is made up of the following constituents:

          


COMPLEX-CLAUSE
  |
  |-- ELEMENTS
  |       |
  |       |-- CONSTITUENT1
  |       |       |
  |       |       |-- PROCESS
  |       |       |-- PARTICIPANTS
  |       |       |-- SYNT-ROLES
  |       |
  |       |-- CONSTITUENT2
  |       |       |
  |       |       |-- PROCESS
  |       |       |-- PARTICIPANTS
  |       |       |-- SYNT-ROLES
  |       |       |
          
          

When the branch of the grammar specifying the conjunction is traversed, the choice of the lexical item that will realize the process is still three levels down. The decision whether to use an ellipsis concerns only the conjunction grammar, so it must be located in the conjunction branch, not in the branch of the grammar deciding on lexical choice for the process. But it depends on this later decision - we do not want to influence the choice of the verbs in the conjunct by the fact that they are conjoined. So the decision is instead delayed until the verbs in both conjuncts have been determined.

Note that if the input already specifies the verbs, then the decision can be evaluated right away. It is only delayed when needed.

There can be complications when using wait when two decisions wait for each other, in a deadlock configuration. I have not yet encountered such situations in practice but in such cases, a combination of wait and bk-class could ensure that the deadlock can be broken in an efficient way.