[prev in list] [next in list] [prev in thread] [next in thread] 

List:       darcs-conflicts
Subject:    Re: [darcs-conflicts] Effects of permutations of N non-commuting
From:       David Roundy <droundy () darcs ! net>
Date:       2006-01-17 11:32:39
Message-ID: 20060117113237.GA10685 () abridgegame ! org
[Download RAW message or body]

On Tue, Jan 17, 2006 at 05:02:10AM +0100, Arjan Boeijink wrote:
> David Roundy wrote:
> 
> >I had a chance to look at writing the three-way conflicting merge using
> >your notation and have a vague idea where the difficulty will lie:
> >
> >        (A^)    (B)       B^(C)
> ><-> AB   A^(B)   (A^)B     B^(C)
> ><-> AC   A^(B)   A^BB^(C)  (A^)BB^C
> >
> >Here I've just somewhat naively applied your notation to this situation.
>
> I think the last line is incorrect as can be seen when rewriting it as a 
> commutation of 4 non-commuting patches:
...
> replacing E with A^, F with B, G with B^ and H with C the last line with 
> effect becomes:
> 
>  <-->A^C    A^(B) [A^]   A^bB^(C) [B]   (A^)Bb^C [B^]
> 
> While the effects still don't make much sense, it's at least a valid 
> sequence of effects.

You're right.  That does make more sense, and suggests that the
patch-inverse pairs we need to be looking for may always be of the form Bb^
(i.e. one capital and one lower-case).

> >What's missing from the notation (or my application of it) is any support
> >for the idea of a patch and its inverse.  We know from the properties of
> >the commute that
> >
> >         (A)    (A^)    (B)
> ><-> A^B   (A)    A^(B)   (A^)B
> ><-> AB    (B)    B^(A)   (A^)B
> >
> >but this last commute breaks the simple interpretation of the A(B)cD
> >notation, with the equivalence that AA^(B) == B and (A)a^B == B^(A).  The
> >former is consistent with your table, but the latter rule seems to break
> >the table's behavior, since one would expect the effect of (A)a^B to be
> >[_], but in reality the effect is [B^].  
>
> The former is also inconsistent because the effect of AA^(B) = [AA^] =  
> [_]  and the effect of (B) is [B]

Ah yes.

> >So there's something we need to be careful with in applying that
> >table--one can only straightforwardly apply it if we know there aren't
> >any inverse patches involved.
> >
> >Getting back to the three-way merge, it looks like we've got some wrong
> >effects, since what I wrote as (A^)BB^C really ought to have no effect at
> >all, while it looks like it would have the effect of [C].  No surprise
> >here, since we've got a BB^ present.  Perhaps I should also note that this
> >conflictor could equally well have been written (A^)CC^B if we had done the
> >commute in the other order, which is why the conflictor *has* to have no
> >effect.  So this problem just results from the previous one, which is that
> >I'd like our notation to reflect somewhat the commutation properties--in
> >particular those involving inverses.
> >
> >How might we manage this? I'm not sure, but my intuition is that something
> >like the simplification you made when grouping together BCD etc into a
> >single letter might help--if there was a canonicalization procedure that
> >always gave the equivalence of (A)a^B == B^(A), then perhaps that
> >canonicalization would also help solve the harder problems, provided it was
> >expressed in a suitably general way.  I can't see it yet, but I'm hoping
> >someone else will be able to see such a canonicalization...
>
> I think we need something like pairs of rewrite rules that are applied 
> after each commutation where inverse are involved.
> The simplest one of these rules would be AA^(B) => (B), (A)a^B => B^(A)  
> that changes two no effects to a patch and its inverse.
> Having an additional step after commutation makes it a lot harder find 
> the representation by the original sequence and the order of patch 
> identities, which is why I prefer to figure out the mix of commuting and 
> non-commuting patches first.

I agree about the rewrite rule, but suspect that when working with mixed
commuting patches you'll have the same trouble.  Either problem could be
tackled first.

> Another place where the new notation breaks down is the case of two 
> conflicting patches with a resolution patch (using old notation):
>          A  <A^;@B|  C
>  <-->BC  A  <A^;@C|  |@B;C>

I don't think this is quite right.  I'm not sure of the permutations of
this, but if you do things in a different order you get

         A  <A^;@B|  C
 <-->AB  B  <B^;@A|  C
 <-->AC  B  <B^;@C|  |@A;C>

And then what happens when C is commuted to be the first patch?

 <-->BC  C  <C^;@B|  |@A;C>

Never mind, that does look like it'll work, but leads to the very
interesting result that <C^;@B| |@A;C> <-> <C^;@A| |@B;C>

> With the new notation this becomes:
>          (A)  A^(B)  (C)
>  <-->BC  (A)  ??(C)  A^(B)C
> 
> This makes no sense at all since B doesn't fit into the sequence A^(B)C. 
> For these cases a notation for a patch (identity) that doesn't have its 
> effect anywhere might be needed.

I think this is just showing that you *need* the rewrite rules (as I'm sure
you're aware) in order to get reasonable results when inverses are present.

Simply translating the old notation into the new, it seems that we want

         (A)  A^(B)  (C)
 <-->BC  (A)  A^(C)  (B)C

which is definitely a weird rule, and I'm still not sure that the
old-notation commute is really right.  It doesn't seem natural that

<^A;@B| C <-> <^A;@C| |@B;C>

since it seems that the C patch is "not noticing" that it conflicts with
B.  On the other hand, when we apply this same rule to the AC commute, we
get quite a reasonble answer, so maybe the only trouble here is with our
interpretation of the conflictors.  Which I suspect is the trouble with
then new notation as well.  The notation is designed to be trivially
interpretable in the all-conflicting case, but in other cases I think
there needs to be less of a one-to-one mapping between notation and
"commute history".
-- 
David Roundy
http://www.darcs.net

_______________________________________________
darcs-conflicts mailing list
darcs-conflicts@darcs.net
http://www.abridgegame.org/cgi-bin/mailman/listinfo/darcs-conflicts
[prev in list] [next in list] [prev in thread] [next in thread]