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

[Glenn Slayden]

Thanks Woodley,

It turns out that my method is, in fact, weak. As explained in the "Array
TFS storage" paper, forwarding in my unifier is from 'slot' to 'slot,' where
each slot is a feature "arc" inbound to a node. The rough idea, which was
not examined in the paper, was that if forwarding were opportunistically
shortened to a single step, then cycles would be detected by checking for
identity between the governing slot (programmatically carried) and the
terminal slot after following the substructure forwarding.

Indeed I ran your example TDL and the cycle *is* detected (during the
unification pass) by this method. But the exercise then left me thinking
that the method only works across a single level of substructure nesting
(such as your example, where the essential fault is that #1 lies below #1),
and this limitation is unrelated to the short-cutting of the chains.

For a true fix, note that one may examine the call stack. Anytime the
unifier is forwarding to a node which exists on an upper frame, you are
introducing a cycle.

Glenn

-----Original Message-----
From: Woodley Packard [mailto:sweaglesw at sweaglesw.org] 
Sent: Wednesday, July 11, 2012 2:26 PM
To: Glenn Slayden
Cc: 'developers'
Subject: Re: [developers] cycle check inside *deleted-daughter-features*

Glenn,

I wasn't talking about the possibility of cycles in the unifier's forwarding
chains, actually -- I guess those would indicate a bug in the unifier.  I
was talking about cycles in the arc structure of the DAGs (directed
*acyclic* graphs).  If you try to unify the following two DAGs:

x := [ LIST #1, LAST #1 ].
y := [ LIST [ FIRST my-type, REST #2 ], LAST #2 ].

then the result is the following directed graph:

x & y := [ LIST #1 [ FIRST my-type, REST #1 ], LAST #1 ].

This graph is cyclic in the sense that the paths LIST, LIST.REST,
LIST.REST.REST, LIST.REST.REST.REST etc are all reentrant.  We consider that
a unification failure.  It's not hard to test the resulting structure to see
if cycles are present, but detecting their formation during unification is
not, to my knowledge, easy.

Or maybe you have a trivial check for that type of cycles built into your
unifier?  I would be interested to learn how it works.

Woodley

On 07/11/2012 01:45 PM, Glenn Slayden wrote:
> 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
>
>