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

[James Cook]

On Wed, 1 Jul 2020 at 21:14, Ben Franksen <ben.franksen at online.de> wrote:
> Am 01.07.20 um 18:45 schrieb James Cook:
> >> Just to check I understood the idea (up to this point): roughly
> >> speaking, you represent "unrepresentable" states by formally commuting
> >> patches.
> >>
> >> That is, if we regard the primitive states as vertices and primitive
> >> (named) patches as edges in a graph, then you extend the graph with new
> >> nodes and edges.
> >
> > That's exactly the intuition.
> >
> > If you had n patches that all commuted, this graph would be a
> > hypercube, i.e. the nodes are the 2^n subsets of patches and each edge
> > adds one patch.
> >
> > I think my theory always extends this graph exactly to that hypercube,
> > filling in exactly those nodes and edges that are missing. I haven't
> > thought carefully about that point of view so maybe that's not true.
> >
> >> The construction works by inductively taking any pair of incommutable
> >> patches (in sequence, i.e. with a common middle state) and then
> >> "formally" commuting it. The new node is represented as that pair of
> >> patches. Is that, essentially, the idea?
> >
> > Yes, that's exactly what happens when there are only two patches
> > involved and they don't commute.
>
> Okay, good. Now, you go on to define
>
> > Definition: Given any primitive patch theory, the /extended patch
> > universe/ is the set of all patch addresses. A primitive patch P going
> > from context a to b is embedded as (a, b, [P], name of P, {}, {}).
>
> Here you cleverly rename your concept. Before this point you talk about
> patch /sequence/ addresses, now it's only patch addresses. Perhaps just
> an ommision, but I suspect a bit of wishful thinking here.

Definition: A /patch address/ is a patch sequence address where the
sequence (nj) has length one.

Sorry, there are a lot of definitions, but maybe you missed that one?

> Indeed, given a minimal patch sequence address in its general form (a,
> b, (Qi), (nj), X, Y), is this now a new *singular* patch in the extended
> theory, regardless of how long the sequence Qi is? I don't see how how
> this can work. Isn't that universe much larger than what was intended?

I intended only to include patch addresses, i.e. where (nj) has length
one. On the other hand, (Qi) is not restricted in length.

> I think calculating this for a small but non-trivial example would be
> highly instructive. Say we have primitive patches A;B;C, where neither
> A;B nor B;C commute. What does the extended universe look like here?

I think that primitive patch theory has four contexts. Call them a, b,
c, d: a A b B c C d.

The new patch theory should have 2^3=8 contexts. Here are the
remaining four. (I'm using patches and their names interchangeably.)

(1) After just applying B: (a, c, [A, B], {B}, {A}). (This is the
simple case of switching two patches.)

(2) After just applying C: (a, d, [A, B, C], {C}, {A, B}). (We can't
get C without A and B, so we need everything here.)

(3) After applying A and C (missing B): (b, d, [B, C], {C}, {B}).
(This is another example of the simple case of switching two patches.)

(4) After applying B and C: (a, d, [A, B, C], {B, C}, {A}). (This
situation is similar to (2), but with everything reversed.)

The new patch theory should have 12 patches (a cube has 12 edges).
Three are primitive, so there are 9 left to add.

(a) B in the sequence B;A;C. (In other words, commute A and B and look
at B.) This patch's starting context is a, its ending context is (1)
above, and as a canonical patch address, it is represented as: (a, c,
[A, B], [B], {}, {A}). The first three elements of the tuple tell us
this patch lives somewhere on the square of edges between a and c, and
the last three elements locate the patch within the square: the patch
is named B; nothing comes before the patch; and A comes after the
patch.

(b) C in the sequence C;A;B (or C;B;A) is (a, d, [A, B, C], [C], {}, {A, B}).

(c) A in the sequence B;A;C is (a, c, [A, B], {B}, {})

(d) A in the sequence C;A;B is (a, d, [A, B, C], {C}, {B}).

(e) B in the sequence C;B;A is (a, d, [A, B, C], [B], {C}, {A}).

(f) C in the sequence A;C;B is (b, d, [B, C], {}, {B}).

(g) C in the sequence B;C;A is (a, d, [A, B, C], {B}, {A}).

(h) B in the sequence A,C;B is (b, d, [B, C], [B], {C}, {}).

(i) A in the sequence B;C;A (or C;B;A) is (a, d, [A, B, C], [A], {B, C}, {}).


In my opinion, the trickier part is arguing that extended patches can
be "merged" into extended patch sequences as described in Chapter 5,
in such a way that separating that sequence would recover the original
patches. We need the merge and separate operations in order to permute
the order of extended patches.

Let's try using this procedure to commute the primitive patches A;B
from their original places in the sequence. They should turn into (a)
and (c) above.

First, we merge the patches by following the proof of Proposition 4.
Conveniently, A and B have the same names. They are embedded as A=(a,
b, [A], [A], {}, {}) and B=(b, c, [A], [A], {}, {}).

In this case, M = b = (b, b, [], {}, {}).

The next sentence says it is possible to permute (Qi) = [A] so that it
starts with the patches in {A} U {} \ {}, then follows the sequence
(Si) = []. It's trivial in this case: [A] is already permuted to have
the form [A] ++ [].

Similarly, [B] already has the form [] ++ [B].

Finally, the proof says to construct AB = (a, b', Qpre ++ S ++ Q'post,
(nj) ++ (n'j), X, Y'). In this case, that's
(a, c, [A] ++ [] ++ [B], [A] ++ [B], {}, {}) = (a, c, [A, B], [A, B], {}, {}).

Okay, we've finished merging. Now we wanted to swap A and B. That's as
simple as swapping the names in the name list (nj): our new sequence
is (a, c, [A, B], [B, A], {}, {}).

Finally, we separate back to individual patches. (This may not always
be necessary, depending on how you want to represent the repository.)

The definition of separation (just before Proposition 3) says we end up with:

* The minimal form of (a, c, [A, B], [B], {} U {}, {} U {A}) = (a, c,
[A, B], [B], {}, {A}). That's already minimal, and it's example (a)
above.

* The minimal form of (a, c, [A, B], [A], {} U {B}, {} U {}) = (a, c,
[A, B], [A], {B}, {}). That's also already minimal, and it's example
(c) above.


---

I also wrote some examples of computing starting and ending contexts
as defined in Chapter 4. Later I decided the merging procedure above
is more important, but since I wrote it anyway, here it is in case you
want to read it.

Example (c):

By definition, the starting context is the minimal form of (a, d, [A,
B, C], {C}, {A} union {B}) = (a, d, [A, B, C], {C}, {A, B}). This
address is already minimal, because C can't be moved to the start of
the sequence and A and B can't be moved to the end. This is context
(2) in the list above. This makes sense: we embedded B in the middle
of the sequence C;B;A, so the starting context should be one where
just C has been applied.

Similarly, the ending context is (a, d, [A, B, C], {B, C}, {A}), which
is context (4) above. This also makes sense: the ending context should
be one where everything but A has been applied.

Example (a):

By definition, the starting context is the minimal form of (a, c, [A,
B], {}, {A, B}). We can move A and B to the end of the sequence
(they're already there) so the minimal form is (a, a, [], {}, {}) = a.
This makes sense: in example (a), we permuted b so it came first, so
the starting context should be a.

The ending context is the minimal form of (a, c, [A, B], {B}, {A}).
This is already minimal, and it's (1) in the list above.



James