[darcs-users] How to extend a patch theory to fully commute

[Ben Franksen]

Am 08.08.20 um 22:51 schrieb James Cook:
>> Why are you so hung up on this tree / cycle thing? What is wrong about
>> your original context addresses and patch (sequence) adresses? If
>> efficiency is the concern, we are talking about a factor of two here.
>> This is irrelevant. For the theory you need to get the asymptotics
>> right, the rest are implementation details.
>
> Sorry for the long silence; I was distracted by other things. I'm
> hoping to take some time soon to review the thread and respond to
> parts of it.

Hi James,

it's goo to hear from you again. I was pretty busy myself, so nothing lost.

> To respond to your quoted question above: I was concerned my
> "canonical context address" representation of patches might not make
> enough things equivalent, i.e. distinguish things that shouldn't be
> distinguished.
> 
> This came up when we talked about inverses: we need to add some rule
> in order to guarantee that the starting context of A^ equals the
> ending context of A.
> 
> When I raised the concern, you suggested* "with inversion added, every
> context address has two minimal forms: forward and backward, and these
> denote the same extended context."

I did.

> I was concerned that adding just that one new kind of equivalence
> might not be enough.

I think you first need a more precise definition of what inversion means
for primitive patches. For instance, if inverse patches come into play,
your definition of context addresses runs into problems because now the
same patch can occur multiple times in a sequence, so you can no longer
uniquely refer to the patches in a sequence by their names. For
instance, if you split A;A^;A;B after the A^, your patch name sets will
be X={A,A^} and Y={A,B}, where A now occurs in both X and Y.

A good way to see if your definition holds up is to see whether you can
prove your

Conjecture 1: Every context address points to at most one context.

> But I didn't think it through carefully. Honestly
> I thought the cycle representation seemed kind of neat, but I guess I
> don't really have a justification for it right now.

I agree that it'd be nice to have a canonical representation, but I
think it is too early to search for it. You first need a firm
understanding of how context addresses behave in the presence of inverse
patches.

Cheers
Ben