[darcs-users] Patch Theory in action

[David Roundy]

On Sun, Nov 23, 2003 at 11:32:35AM -0800, Kevin Smith wrote:
> David Roundy wrote:
> >>P = Q : P and Q are exactly the same patch: for every tree
> >>        they either both are inapplicable, or they both
> >>        give the same result tree.
> >>    [NOTE: So commutation would be written as P1;Q1 = Q2;P2;
> >>           see the following notation.]
> >
> >
> >That's not really true.  Commutation doesn't just indicate that the
> >composition of the two patches is the same patch in each case, it also
> >indicates that the two commuted patches correspond to the same two
> >*changes* in reverse order.
> 
> But wouldn't the resulting trees after P1;Q1 and Q2;P2 be identical? If
> so, then if patch R1 *is* P1;Q1 and patch R2 *is* Q2;P2, then R1 = R2.

It is true that if P1 commutes with Q1 to give Q2;P2, then P1;Q1 = P2;Q2,
but it is not true that if P1;Q1 = Q3;P3 then P2 = P3 and Q2 = Q3.  In
other words, "P1;Q1 = Q3;P3" doesn't mean that P1 and Q1 commute, or that
their commutation produces Q3 and P3.

Another example would be (P;Q);R = P;(Q;R), but certainly no commutation
has been performed.

> >An interesting feature of darcs is that "rename file F to G" is actually
> >defined even if file F doesn't exist.  :)  In other words, I decided to let
> >(my notation)
> >
> >  {mv F G} {add F} <---> {add G} {mv F G}
> >
> >It seems a little silly, but causes no problems, as long as {rm G} {mv F G}
> >doesn't commute.
> 
> So adding a file and then moving it is commutable with moving a 
> non-existent file and then adding a file of the new name.
> 
> But moving a file and then deleting the new file cannot commute with 
> deleting a file and then moving the non-existent file to a new name?
> 
> Why? Or perhaps more to the point, why would it cause problems if those 
> two did commute?

Because I made a mistake.  I should have said {add F} {mv F G} doesn't
commute, and neither does {mv F G} {rm G} (remembering I'm still in the old
backwards notation for this question).  In words, you can't commute
renaming a file and then adding a file with the old name.

> >Well, I'm afraid I do like superscripts and subscripts! :) (Although I also
> >appreciate your imput).
> 
> One of my problems with the current notation is that you can have P1'-1, 
> which when written with super and subscripts looks like P decorated with 
> three different kinds of "1". (The ' looks like a superscript 1). Very 
> confusing.
> 
> So if you're going to keep the ' I would strongly encourage you to adopt 
> ~ or ! (or perhaps even the haskell oddity /) as the inversion flag.

Hmmmm.  I'll think about that...

> >I still think a commute operator is necesary, and like the <---> operator
> >for this.  But I need to be clearer about <---> being an operation (or
> >function?), not just a relationship.  
> 
> I'm ok with <--->, and I view it as a relationship, not just an 
> operation. If someone hands me valid patches A, B, A' and B' then
>    <0|AB <---> <0|B'A'
> even though I didn't perform any operations myself.

But the only way you know that AB commutes to B'A' is by applying the
commute operation yourself to either AB or B'A'.  So it's a relationship in
the same sense that "equal to the inverse of" is a relationship.

> There is a commute function which given AB will return B'A'. But 
> commutability is a state. Am I missing something?

It is both a relationship and an operation, but I think it's better
(although less natural, especially given the notation) to view it primarily
as an operation, which suggests a different notation.  The awkwardness
comes from the fact that it takes two patches as input and gives two
patches as output.  Normal infix operators usually take two inputs but give
only one output, and I'm not familiar with a nice notation for functions
that give more than one output.
-- 
David Roundy
http://www.abridgegame.org