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

List:       darcs-conflicts
Subject:    Re: [darcs-conflicts] Conflict Resolution
From:       Grant Husbands <darcsconflicts () grant ! x43 ! net>
Date:       2006-03-07 23:50:55
Message-ID: 440E1C5F.5060602 () grant ! x43 ! net
[Download RAW message or body]

Terminology for this email as it diverges from accepted terminology:
Atom: Primitive patch (because I don't want to type primitive, lots).
Invariant Atom: Atom in minimal context with explicit dependencies.
Unmerge: Taking two consecutive atoms and making them parallel.

Ganesh Sittampalam wrote:
> In particular, not having a proper notion of inverses means that the 
> correspondence between merging and commutation no longer exists.

I think all DAG operations can be defined in terms of only merges and 
unmerges of atoms, if that helps. In fact, a commutation just looks like 
an unmerge followed by a merge, to me.

In a way, it would make sense if the fundamental operation for DAG-Darcs 
was a merge, rather than a commutation.

> We need commutation for unpull

We could define unpull as the creation of a new repository without the 
atom in question - then only merges are required. As we hope a 
repository is uniquely defined by the invariant atoms it contains, this 
shouldn't be a problem. Doing it any other way (through unmerges or 
commutation) could be deemed an optimisation (albeit a very useful one).

> The "commute it to the end of the list" is actually a merge operation. 
> In a commute, we start off with two sequential patches, but in a merge, 
> we start off with two parallel patches (patches which start at the same 
> place), and that's what we have here.

That's a fair point - I'll try to tighten up on my terminology.

> So we end up having a system with both merging and commutation, but 
> without inverses we cannot relate the two, or prove any nice properties 
> that end up giving us a consistency guarantee.

It does seem that inverses can be useful for proofs; I'm just not sure 
where they would fit in an implementation of a DAG-biased scheme. I'll 
admit that I'm out of my depth when it comes to arguing the mathematical 
properties of the operations and tend to hand-wave and think in terms of 
specific atom-types.

I'm going to have to give all this some more thought, but I'll throw 
this out, as is, to see whether it makes any sense to anyone else.

Regards,
Grant.

_______________________________________________
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]