Edge can be built interactively, but isn't in the chart

Dear all,

[Cross-posted to developers and the delphinqa.]

After 16 years of teaching grammar engineering, I thought I’d found all of the ways in which one can be in the situation of seemingly being able to build an edge through interactive unification which isn’t in the chart. I’ve documented all of the ones I know about here:

http://moin.delph-in.net/GeFaqUnifySurprise

Alas, I’ve found evidence of a new one. Or rather: I’m in that situation (together with a student) but none of the cases noted there apply. More specifically, with the grammar for Meithei [mni] that can be found here:

http://faculty.washington.edu/ebender/mni-debug.tgz

If we try to analyze this sentence:

yoŋ-siŋ túm-í čá-í
monkey-PL sleep-NHYP eat-NHYP
Monkeys sleep and eat.

The LKB and ace both return no parses found. If instead of using the two verbs (one intransitive and one transitive but with a dropped object), we repeat either one of the verbs, we get the expected parses (with both the LKB and ace).

yoŋ-siŋ čá-í čá-í

yoŋ-siŋ túm-í túm-í

Returning to the non-parsing sentence, and looking at the LKB’s parse chart, what’s missing is the VP-T built out of applying the VP1-TOP-COORD rule to the VP-B over čá-í and the VP over túm-í. Puzzlingly, I can build this edge interactively just fine. I’ve run out of guesses as to why it’s not showing up in the char and so I thought I’d put this puzzle out in case other DELPH-INites might be entertained by it.

Curiously,
Emily

p.s. Discourse directed me to an earlier discussion about this, where @johnca suggested checking that chart-packing-p is set to NIL. It is.

1 Like

Hi Emily,

In my chart, I see two VP1-BOTTOM-COORD edges over čá-í; one has undergone optcomp and the other has not. Interactively unifying the latter produces a failure as COMPS on the coordinands disagree (transitive vs intransitive). Interactively unifying the former produces a cycle failure for me. Interactive unification through ace unfortunately doesn’t tell you where cycle failures occur by default. If you throw -vvv on the command line and manage to endure the other junk that comes out, when you do the interactive unification that produces a cycle failure it spits out one of the cycle paths, which for me was:

ARGS FIRST SYNSEM LOCAL CAT VAL SUBJ FIRST NON-LOCAL SLASH LIST NEW-LIST

At the moment I’m not sure (a) what that might portend, or (b) why you aren’t getting an interactive unification failure when doing the same thing in the LKB, or © whether that might mean I’m not doing the same steps you are to reproduce it the problem :slight_smile:.

-Woodley

1 Like

Thank you, Woodley! That definitely gives me something to work with. (It doesn’t solve the mystery of why interactive unification is building something that’s not in the chart, but it does tell me where to start looking…)

In that other thread, the issue went away for me after I modified my subject extraction rule… Which sounds related, looking at the cycle that Woodley uncovered? Though I am not seeing a subject extraction rule per se in the attached grammar.

OK, I’ve dug to something resembling the bottom of this.

The core problem here is that append lists record their computation history. The coordination rule very sensibly says that its daughers’ NON-LOCAL must be identical. Considered as lists, their SLASH values are identical, but those values have different computation histories: the one from the intransitive verb is something like list from its lexical entry, whereas the one from the transitive verb has a null prepended during the optional complement rule. The history of that computation shows up as the structure under the APPEND feature; the second coordinand says (simplified): [ APPEND < null, #1 & list > ] while the left daughter says [ APPEND #1 & list ]. Unifying these produces an infinite (cyclic) list.

There’s another cycle caused by the append lists here too, with similar though somewhat distinct pedigree, which I will try to sketch. The coordination rule unifies the daughters’ VAL structures. The left daughter says something like [ SUBJ…SLASH #1, SLASH #1 ]. The right daughter says something like [ SUBJ…SLASH.NEW-LIST #1, SLASH #1 ]. When these two are unified, we end up with [ SUBJ…SLASH #1, SUBJ…SLASH.NEW-LIST #1], which is cyclic. This again is a symptom of keeping computation history around; on the right daughter, the SLASH value was computed as an append, and so its value is linked to the appended lists’ NEW-LIST value, whereas on the left daughter the SLASH value was just copied up.

Formally, this is kind of a big problem. We want to be able to say two lists are the same regardless of their computational history, and with append lists, the computational history is part of the feature structure. From a technical standpoint, it may not be such a big problem. You can make it go away by adding APPEND, NEW-LIST and END-LIST to the deleted-daughters setting in ACE’s config.tdl (and I believe there is an equivalent setting for LKB and PET):

deleted-daughters := ARGS HEAD-DTR NON-HEAD-DTR DTR APPEND NEW-LIST END-LIST.

With that change, I was able to parse the offending sentence successfully. I also verified that the appends still constructed a plausible looking list of relations for the MRS. I don’t know for sure that the above won’t have unintended consequences on append calculation somewhere sneaky, but I think it’s unlikely, at least so long as nobody is writing constraints about rules’ daughters’ lists’ computational histories.

2 Likes

Thanks for the sleuthing, Woodley!

I think I can get rid of the first cycle by identifying SLASH.LIST (and QUE.LIST and REL.LIST) across the conjuncts & coordinate phrase, rather than the whole NON-LOCAL value, but I need to think through how to do this for the valence features. We already have an enormous collection of coordination rules, but at the cost of a few more, I suppose I could change identifying the full VAL structure to identifying e.g. LOCAL and then each LIST inside NON-LOCAL for the subject. (Doing this for COMPS is vexed, though, since I don’t know the length of that list, and I’m not keen on making separate rules for each possibility.)

@guyemerson, @olzama: Do either of you have any insight here?

Meanwhile, the fix you suggest worked for me for ace, but the analogous change in lkb/globals.lsp doesn’t, which is puzzling.

And then of course the difference in interactive unification v. actual parsing remains. Is it perhaps that things are more aggressively pruned in interactive unification, somehow?

I’m also really interested to understand why this is a problem for append-lists when it wasn’t for diff-lists, which I thought also carried along a lot of their history. (But I don’t have a deep understanding of either.)

I think I am missing some bit here; are we talking about e.g. this type:

coord-phrase := binary-phrase &
  [ SYNSEM [ LOCAL [ COORD-STRAT #cstrat,
                   CAT [ HEAD.MOD #mod,
                         VAL #val ] ],
	     NON-LOCAL #nl ],
    LCOORD-DTR #ldtr & sign & [ SYNSEM [ LOCAL [ CAT [ HEAD.MOD #mod,
                                                     VAL #val ] ],
				         NON-LOCAL #nl ] ],
    RCOORD-DTR #rdtr & sign & [ SYNSEM [ LOCAL [ COORD-STRAT #cstrat,
                                               CAT [ HEAD.MOD #mod,
                                                     VAL #val ] ],
					 NON-LOCAL #nl ] ],
    ARGS < #ldtr, #rdtr > ].
  • specifically the val identity? Why would you need to know the length of COMPS here?

Diff lists don’t carry their computation history. If you look at a diff list that has 5 items on it, for instance, you can’t tell whether it arose by appending a 2 and a 3 or by appending a 1 and a 4 or if it just started as a 5. The information is sort of available in the form of reentrancies with the lists that were appended, when they themselves have been kept around, but it’s not part of the diff list structure itself. With append lists the history is up front and center and gets compared whenever the append list structure is compared. As you point out you can avoid this by comparing the LIST inside of it instead of the append list container, but that makes a big headache when you wanted to have a rule identify a big chunk of feature geometry that happens to have some append lists buried deep inside of it.

It’s an interesting question whether this type of problem can come up with diff lists under the right circumstance. To the extend that the computation history is there at all, even implicitly, somewhere in some other part of the feature geometry, some of the time, I would think that it might be possible to construct such a case, but I’m not sure. I haven’t seen one anyway :-).

Woodley

2 Likes

The solution that I applied to the NON-LOCAL values was this:

coord-phrase := binary-phrase &
  [ SYNSEM [ LOCAL [ COORD-STRAT #cstrat,
                   CAT [ HEAD.MOD #mod,
                         VAL #val ] ],
	     NON-LOCAL [ SLASH.LIST #slash,
			 REL.LIST #rel,
			 QUE.LIST #que ] ],
    LCOORD-DTR #ldtr & sign & [ SYNSEM [ LOCAL [ CAT [ HEAD.MOD #mod,
                                                     VAL #val ] ],
				         NON-LOCAL [ SLASH.LIST #slash,
						     REL.LIST #rel,
						     QUE.LIST #que ] ] ],
    RCOORD-DTR #rdtr & sign & [ SYNSEM [ LOCAL [ COORD-STRAT #cstrat,
                                               CAT [ HEAD.MOD #mod,
                                                     VAL #val ] ],
					 NON-LOCAL [ SLASH.LIST #slash,
						     REL.LIST #rel,
						     QUE.LIST #que ] ] ],
    ARGS < #ldtr, #rdtr > ].

… but if I want to do essentially the same for the VAL features, I have to talk about the SLASH.LIST and QUE.LIST of each valence element separately, which entails knowing how many things are on the COMPS list.

This is really interesting! I had wondered if the APPEND feature would cause problems somewhere…

I agree that this is a problem for append-lists and not diff-lists. The re-entrancies in a diff-list are only relevant if you’re looking at a structure large enough to contain both the resulting list and the original lists. With an append-list, that happens immediately.

Given that we already have features like ARGS that carry around the derivation history, this doesn’t seem like a formal problem to me (although I will admit that ARGS is further away in the structure).

It would be possible to move all of the append calculations further away, but this would make the syntax awkward, which would go against my original motivation… We could have an APPEND feature at the top level (like ARGS), which contains a list of list-appends, as pairs of (resulting list, list of lists to be appended). This would be a solution if it’s important that both: 1. we can close lists and still append to them, and 2. we cannot have the derivation history “nearby”.

Thinking more generally – if this solution is appealing, we could introduce a RELATIONAL feature at the top level, which has a feature for each type of “relational constraint” defined in the type hierarchy, i.e. what I called “wrapper types” in my talk at the last summit. So RELATIONAL.APPEND contains a list of the list appends used in the current feature structure, and then if we also want to have logical or numeric operations, we could have RELATIONAL.AND, RELATIONAL.SUM, etc.

If someone is writing constraints about rules’ daughters’ lists’ computational histories… well, good luck to them :stuck_out_tongue:

And finally, if the number of coordination rules is causing a problem, wrapper types should be able to cut this down somewhat (at least at the level of an individual grammar, if not the core Matrix), e.g. choosing a gender for the mother as a function of the gender of the children. Although they would also run into this problem of carrying around the derivation history (unless we move the constraints, as described above).

At the risk of accumulating further technical debt… I could write you a type that would identify the NON-LOCAL LISTs of each COMPS element. But this would add extra structure in a similar way to append-lists. (i.e. either nearby in the structure, which is more readable, or far away, which is less readable but avoids problems like the above.)

I think using deleted-daughters is a more sustainable way to avoid the problem. But I can’t comment on why it works in ACE but not the LKB.

Mockup of proposed syntax, where all lists are really of type list (i.e. there are no append-lists or diff-lists anywhere):

my-unary-phrase := phrase &
  [ SYNSEM.LOCAL.CONT [ RELS #r,
                        HCONS #h,
                        ICONS #i ],
    DTR.SYNSEM.LOCAL.CONT [ RELS #r1,
                            HCONS #h1,
                            ICONS #i1 ],
    C-CONT [ RELS #r2,
             HCONS #h2,
             ICONS #i2 ],
    RELATIONAL.APPEND < [ INPUT: < #r1, #r2 >,
                          OUTPUT: #r ],
                        [ INPUT: < #h1, #h2 >,
                          OUTPUT: #h ],
                        [ INPUT: < #i1, #i2 >,
                          OUTPUT: #i ] > ].

The “input” to each “relational constraint” would still be destructively modified, but this is already true for diff-lists (the LIST of a diff-list contains the local list followed by everything that was appended to it). The important point is that for both diff-lists with manual appending, and the above proposal, you cannot locally see the derivational history in the list.

Interesting – I think the idea of a “RELATIONAL” feature that stores all of this stuff far enough away in the feature structure that it can more easily be stripped out (avoiding the problem encountered here) while also being sufficiently conceptually simple.

And yes, I can also see the application to feature resolution in coordination (which is only part of why we have many coordination rules, but it’s a combinatoric explosion, so even reducing that factor would be nice)…

relational constraints at last :slight_smile:

1 Like

Yeah, a feature RELATIONAL would make our favorite type of HPSG paper title, “X and Y without relational constraints”, somewhat ironic :slight_smile:. Not that it is a reason not to use it.

Sadly, I have to resurrect this thread and recant my earlier heresy. Using deleted-daughters to remove the computation features does indeed destroy the evidence of the computational history, but at an unacceptable cost that I failed to foresee. The trick works well enough for appends of the most vanilla type where the contents of the lists to be appended is already known.

Unfortunately, it does not work for appends where the lists to be appended are not yet specified at the point in the tree where the append lives. This happens in just about every sentence in the form of lexical threading of SLASH values. The append is stipulated on the lexical values, and at that point all we know about the resulting list is that it is list. The magic that computes its value happens down the road when the arguments are realized and their SLASH lists become known, since that is when the list-copy types get specialized to cons-copy or null-copy and whatever other wizardry. If there are grammar rules interposed between the lexeme and the argument realization rule (as is very often the case), the deleted-daughters trick helpfully erases all record of those computation types, so when the argument eventually does get discharged, the computation doesn’t happen and the SLASH value remains list. This in turn opens the grammar up to licensing all manner of reprobate trees.

So, I think using deleted-daughters to solve the problem is not a solution, at least if lexical threading is to be implemented using append-lists.

I remember discussing both the deleted-daughters option and lexical threading in relation to append lists at the summit in Cambridge, but I can’t quite recall whether we predicted and then forgot about this problem or just didn’t connect the dots then (as I failed to last week).

1 Like

Indeed – we did notice it: http://moin.delph-in.net/CambridgeExtractionAppend

So, I think that takes us back to moving the computation out far enough that we’re not trying to identify structures that include it.

@guyemerson – in your mock up above, is the idea that the value of RELATIONAL.APPEND is all of the appends taking place in the local feature structure? That is, that list is always of known length and is defined in either a lexical type or a (lexical or phrase structure) rule?

All – Do you think it would be cleaner to pull such computation out into a “RELATIONAL” feature across the board (e.g. including the RELS and HCONS lists) or only where we need to (NON-LOCAL)?

I’m concerned that the top level RELATIONAL feature approach will fail for basically the same reason (although I would be happy to be shown wrong). The computation machinery for the lexical threading append will be in the RELATIONAL feature at the lexical level of the tree. By the time that edge has undergone a rule or two and is ready to pick up its arguments, the append types will be buried at some path like ARGS FIRST ARGS FIRST RELATIONAL. Since ARGS is on the deleted-daughters list, the (granddaughter’s) append types won’t actually be there anymore on the daughter and the computation won’t happen.

In the original scheme, the computation types were automatically carried up the tree since they were part of the list structure, so they didn’t get lost when ARGS was trimmed.

@sweaglesw Thanks for looking into this further!

This sounds solvable, with the same mocked up syntax that I’ve shown above, but invoking even more machinery behind the scenes…

The RELATIONAL constraints would need to get passed up the tree, to avoid getting deleted. So we would need another feature, say ACCUMULATED-RELATIONAL, which accumulates the RELATIONAL constraints of the daughters (using list appends). The daughters’ constraints get deleted (because they’re inside ARGS) but they’ve already been copied up, and the copies can still be enforced.

@ebender As for whether we want both mechanisms, I think using append-lists allows a nicer syntax, and is more efficient than having ACCUMULATED-RELATIONAL (I would need to implement this to quantify how much). I agree it would be cleaner to have just one way to specify appends, though.