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

[Glenn Slayden]

Thanks for mentioning this issue. I made a change to Agree a while back
which I think avoids the problem, although I don't have the test cases to be
completely sure. Currently, whenever the Agree unifier follows a forwarding
chain it opportunistically also short-cuts it so that all forwardings end up
being a single step which permits a trivial check for cycles. What I'm not
sure about is the theoretical sufficiency. With the ERG, I don't recall
seeing any cycle problems so I think I created a toy DAG to test it. With
the grammars I test (ERG, Jacy, Matrix*), failures due to well-formedness
checks, while rare, are the only unusual unification rejections I tend to
see.

Glenn 

-----Original Message-----
From: developers-bounces at emmtee.net [mailto:developers-bounces at emmtee.net]
On Behalf Of Woodley Packard
Sent: Tuesday, July 10, 2012 4:07 PM
To: developers
Subject: [developers] cycle check inside *deleted-daughter-features*

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