BK-class implements a version of dependency-directed backtracking [#!doyle!#] specialized to the case of FUF. The bk-class construct relies on the fact that in FUF, a failure always occurs because there is a conflict between two values for a certain attribute at a certain location in the total FD. In the example illustrating this section, backtracking is necessary because an equation requires that the value of the feature {manner manner-conveyed} be instantiated, but the actual feature is not. The path {manner manner-conveyed} defines the address of the failure.13
The idea is that the location of a failure can be used to identify the only decision points in the backtracking stack that could have caused it. This identification requires additional knowledge that must be declared in the FUG. More precisely, the FUG writer is first allowed to declare certain paths to be of a certain bk-class. Then, in the FUG, every choice points that correspond to this bk-class must be explicitly declared.
For example, the following statements are used in grammar gr7:
|
|
This fragment extracted from grammar GR7 illustrates a possible use of the bk-class construct. The example is detailed in a paper accompanying the manual (available in file .../doc/bk-class). The fragment above implements the following decisions: if there is no manner role specified in the input, then nothing needs to be done. If there is a manner role, then the grammar must decide how to realize it. One option is to realize it as either an adverbial adjunct or as a PP adjunct. Another option, shown in the next figure, is to realize the manner role by selecting a verb which would carry the manner meaning. The three possibilities are illustrated by the three sentences, where the constituent realizing the manner role is in italics:
The fragment of the grammar implementing the choice of the verb is shown in the next figure:
|
Examples of input that exercise these parts of the grammar are provided in file ir7. A simple example is shown in the next figure:
|
The overall flow of control through this grammar concerning the realization of the manner role is as follows: The unifier first processes the input at the clause level. When it reaches the region dealing with adjuncts, it checks the manner role. There is a manner role in input t1, so the grammar has a choice between the three modes of realization listed above - verb, adverb or PP. The grammar first tries to ``leave a chance to the verb'' - more precisely, it leaves a chance to some other unspecified constituent in the grammar to account for the manner role. If the verb happens to convey the manner, then nothing else needs to be done. This case is illustrated by the following trace of unification of example t1 in file ir7.
But if for any reason (like the interaction between manner and argumentation detailed in the bk-class paper and illustrated in examples found in file ir7 or because the input already specifies the verb) the grammar fails to account for the manner role in other constituents, the ANY constraint put under the manner-conveyed feature will fail at determination time. At this time, we know we failed because of the manner-conveyed feature, so if we backtrack, we want to backtrack to the latest choice that involved the manner role realization. With the bk-class annotations, the unifier will backtrack directly to the last choice point of class manner, ignoring all intermediate decisions. This case is illustrated by the trace of the unification of example t2 from file ir7. In t2 the verb is specified and set to be ``beat'' which does not convey the manner role. In this case, the unifier needs to backtrack as illustrated:
> (uni (t2))
t2 -> The Denver Nuggets narrowly beat the Celtics.
>STARTING CAT CLAUSE AT LEVEL {}
|
Note that in this second example, if the bk-class feature is disabled (by typing (clear-bk-class)), the unifier does not find an acceptable solution after 100,000 backtracking points. This indicates that bk-class is not merely an optimization but is often required to make unification practical.
Figure ![[*]](cross_ref_motif.gif)
illustrates the effect of using
bk-class. The unifier therefore uses the knowledge that only the
verb or the adverb can satisfy the manner constraint in a clause to
drastically reduce the search space. But, this knowledge is locally
expressed at each relevant choice point, retaining the possibility of
independently expressing each constraint in the FUG.
In general, the determination of the address of failure is more complex and
it is necessary to distinguish between initial failures and derived
failures. An initial failure always occurs at a leaf of the total FD,
when trying to unify two incompatible atoms. Failures, however, can also
propagate up the structure of the total FD. For example, when unifying
((a ((b 1)))) with ((a ((b 2)))) the original address of failure is
the path {a b}. When the unifier backtracks, it also triggers a failure
at address {a}, which is not a leaf. This type of failure is called a
derived failure. In the implementation of bk-class, FUF ignores
derived failures and directly backtracks to the first choice point whose
bk-class matches the last initial failure. Determining whether a
failure is derived or initial can be difficult. In FUF, the following
technique is used: I distinguish between forward and backward
processing. Forward processing is the normal advance of the search
procedure through the disjunctions in the grammar. Upon failure, backward
processing starts, which means that the stack of the last decisions is
unwound. Each time a new disjunction is retried and restarted, forward
processing could restart, but unification may fail again immediately,
without making any changes to the total FD being processed. In general,
backward mode continues until one of two events occurs: either a restarted
alt succeeds and at least one change is made to the total FD (a feature is
added to the input), or a failure occurs when unifying a grammar feature
with a feature that was present in the original input, before unification
started. The distinction between forward and backward processing and the
way the address of failure is maintained is illustrated in
Fig..
The figure shows the search space when traversing two successive alts in the grammar. Each arrow corresponds to either the choice of a branch in the alt or to a forced backtracking. Arrows 1 and 2 correspond to the first forward processing step and end up in a failure. This is an initial failure and the address of failure (which is by definition the location which caused the latest significant failure) is set to the current position in the total FD. The backward processing step starts and a second branch of the ALT is tried (arcs 3 and 4). This second branch fails immediately, before any change is made to the total FD. In such a case, the backward processing step continues, and the address of failure is not updated. The motivation is that the unifier is still backtracking for the same original reason: nothing changed in the grammar that makes the original failure less relevant. So the unifier keeps backtracking, and tries the third and last branch of the ALT (arcs 5 and 6). The same failure occurs again, and backward processing proceeds. The second ALT is exhausted and, therefore, fails, and the second branch of the first ALT is tried in turn (arcs 7, 8 and 9). At this time, two reasons can trigger a switch of failure address:
There is one more complication with the use of the address of failure as a
source of information on what decision caused the failure: as already
mentioned in Sect., a given location in the total FD
can be accessed through several paths from the top of the total FD (since
an FD is not a tree but can be an arbitrary graph). So several distinct
paths, with different labels can identify the location where the failure
occurred. The intelligent backtracking component must decide which path
should be matched against the bk-class specifications. The convention used
here is the same one used to disambiguate the up-arrow notation presented
in Sect.: the path used to identify the address of
failure is the path written in the grammar on the feature that caused the
failure. The motivation is that the grammar writer uses the path that is
the most meaningful to access features, and that incidental conflations
along this path would not be as informative for backtracking purposes.
Another approach could have been to use all the path addresses that
identify a location and match them against all bk-class specifications.
But this approach would have imposed too much overhead on the regular
backtracking mechanism.
The bk-class mechanism works well in practice. For the basketball example discussed above, I have measured the number of backtracking points required to generate different clauses conveying the same core content. The following table summarizes these measurements.14
| Input / Output | w/o bk-class | w/ bk-class | |
| No floating constraints: | The DN beat the BC | 110 | 110 |
| Manner in the verb: | The DN edged the BC | 110 | 110 |
| Manner as adverbial: | The DN narrowly beat the BC | >10,000 | 214 |
| AO in the verb: | The DN stunned the BC | 112 | 112 |
| AO as adjective: | The hapless DN beat the BC | 1,623 | 239 |
| AO as adverbial: | The DN surprisingly beat the BC | >100,000 | 268 |
| AO & manner together: | The hapless DN edged the BC | 1,178 | 246 |
The number of backtracking points required to generate each example clause is listed with and without bk-class. The numbers for the first clause, which does not include any floating constraints, give an indication of the size of the grammar. It roughly corresponds to the number of unretracted decisions made by the grammar. It is the optimal number of backtracking points that a search control regime can obtain for the given input with this grammar. Without bk-class, the wide variation in number of backtracking points among the examples indicates the exponential nature of the blind search which floating constraints impose on the standard control regime. In contrast, with bk-class, the variation in number of backtracking points remains within a factor of three among all the examples.