Grammar Engineering Frequently Asked Questions
What's a difference list, and why do we use them?
The tdl formalism does not allow the statement of relational
constraints. That is, particular values can be equal to other
values, but not equal to some function of other values. One
kind of relational constraint that we find very useful nonetheless
Two lists can be appended using just unification if the
the length of the first is known:
[ FEAT1 < #val1, #val2 >,
RESULT < #val1, #val2 . #list > ].
This won't work, however, if the length of the first list is
unknown. Instead, we use difference lists, which are a means
of embedded a list in a structure with a pointer to the end.
The matrix type diff-list
is defined as follows:
diff-list := avm &
[ LIST list,
LAST list ].
The Matrix defines the following type to illustrate how diff-list
append works, though of course any particular case where you want
a diff-list append you won't be able to inherit from this type
(the feature names, geometry etc will be wrong):
dl-append := avm & [APPARG1 [LIST #first,
APPARG2 [LIST #between,
RESULT [LIST #first,
Diff-lists are currently used in the Matrix for the values
of the semantic features
and for the long-distance
. For the most
part, the diff-list appends involved in handling these features
appropriately should all be taken care of in
exception would be if you are defining a new phrase type, in which
case you would need to make sure you either inherit from an appropriate
matrix type which does the appends or code them in.
Because of the (admittedly somewhat subtle) logic of diff-list
appends, constraints involving diff-list valued features
can cause problems that are difficult to debug. In some cases, everything
will unify just fine, but not give you the result that you were
expecting. For more information, see the related topics links below.
Back to FAQs page
Back to main course page
- 18 May 2005