[developers] cycle check inside *deleted-daughter-features*

[Stephan Oepen]

hi woodley,

belatedly, thanks for the careful report!

i would agree with your assessment and consider the behavior you describe a bug in PET.  would you happen to have a grammar and test case available, to share and preserve for future debugging?

i used to be aware of the LKB code you mention, but cannot recall any discussion of this particular issue among PET developers.

as an alternative to the detection of cycles as they arise (the technique i take it you now added to ACE), i am wondering whether it might be more efficient to delegate such rigor to the (selective) unpacker.  arguably, we should confirm that parsing gave us a valid (non-cyclic) full HPSG sign before counting a derivation as a result.

without access to the PET code just now, i suspect the above fix could be an even smaller change than the approach you took?  if so, might you be inspired to compare the relative efficiency of either technique?

best wishes, oe



On Jul 11, 2012, at 1:07 AM, Woodley Packard <sweaglesw at sweaglesw.org> wrote:

> Hi developers!
> 
> The report below essentially amounts to a bug in both ACE and PET.  The PET developers may already be aware of it and have decided it costs too much efficiency to fix, but I thought I would bring it up in case it is unknown.
> 
> In a nutshell: as you know, with quasi-destructive unification, an apparently successful unification can leave latent cycles in the resulting DAG.  We generally detect them when we copy() that result.  However, any time a cycle occurs in a part of the DAG that is inside *deleted-daughter-features* and only turns up when realizing the last argument of a rule, the cyclic portion of the DAG is tossed before the cycle is found.  Grammars rely on cycle detection to rule out rule applications, so the behavior is incorrect.
> 
> The problem is not just hypothetical and was leading to spurious readings for quite a few items on the GG test suite I was working with.  (I have not observed any spurious readings with the ERG.)  At the least, it's worth having this discrepancy documented.
> 
> It turns out the clever authors of the LKB anticipated this contingency.  Since LKB (and PET) only removes the *deleted-daughter-features* when they are at the root of the FS, it is possible to comparatively efficiently do a cycle check on the to-be-deleted portion of the FS before starting to copy the rest.  Still, it involves an extra traversal through a large section of FS that ACE and PET have just been skipping.
> 
> A preliminary fix for ACE shows a slowdown of 7% or so -- milder than I expected.  That doesn't necessarily seem too high a price to pay for increased correctness. I suppose it would also be possible to ask grammar writers to keep a pointer to expected cycle failures (usually diff lists, I guess) accessible from the mother edge, although that seems somewhat cumbersome.
> 
> Back to work...
> Woodley