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

[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.

> It reminds me of the darcs-1 patch format, where a "merger" patch is
> defined as the ordered pair consisting of both conflicting patches.

I think I read about darcs-1 conflictors a long time ago, so that
general idea has been on my mind for a while.

James