Ian,
first of all I do apologize for having sent html mail before.
Hope this is better.
I think I'm getting slowly what the theory means.
Let me sum up and sprinkle in further questions or hints to open issues.
We have a non-empty set P, which may be infinite.
Its elements are called "patches" for convenience, but this has no meaning,
really, on this level of exposition.
On the set P there is a composition (p,q) --> p.q which is associative.
There is a mapping c:PxP --> (PxP) + {fail} which is called "commutation".
Here (and later on) we mean "+" to denote union of sets, and "x" to denote the
cartesian set product.
When c(p,q) = fail, we say that p and q do not commute, otherwise that they
commute.
When (r,s) = c(p,q) the following notation is used: (p,q) <--> (r,s).
Using the notation implies, in fact, that p and q commute.
Commutation has to satisfy the following axioms:
(1) When (p,q) <--> (r,s) then p.q = r.s
(2) When c(p,q) = (r,s) then c(r,s) = (p,q)
Note that (1) cannot be reversed, that is from p.q = r.s we cannot conclude
that p and q commute resulting in (r,s).
Axion (2) means that the <--> relation is symmetric.
Any other axioms? Yes!
Definition (5.4) contains three axioms that composition of patches must
somewhat respect commutation.
I find them too complex to write down here. Forgive me :-)
In axiom (4.2) the "inverse" of a patch comes up.
So the set P is required to have a neutral element e (see definition 5.1) and
the existence of inverses makes P into a group.
Patch inversion must be compatible with commutation in this way: [let 1/p
denote the inverse of patch p]
(4.4) When c(p,q) = (r,s) then c(1/r,p) = (s,1/q).
In section 4 the names of patches come up. What is a "name" ?
All names obviously form a group N and we have a group homomorphism n:P-->N .
Moreover, the group N has an additional structure: It can be partitioned into
"positive" and "negative" names.
It is not entirely clear what properties this partition has.
Probably the composition of two positive names must be positive.
The inverse of a positive name is negative, and vice versa.
What about the empty name?
It should be neither positive nor negative, probably.
The mapping n is required to be invertible. It is thus an injective map of P
into N.
Patches p such that n(p) is positive are called "normal". When n(p) is
negative, p is called a "rollback".
The neutral patch e is probably neither.
It follows that p is positive if and only if its inverse is negative.
What abount mixed compositions of several positive and negatives patches?
One does not really get, what names are used for. Are they only used to defined
what positive and negative patches are?
And why do we need to know what positive patches are?
In section 5 a "context" is introduced as a set of names. An arbitrary empty or
non-empty subset?
Patches are then interpreted as transitions from one context to another.
In fact, when B is a context and p is a patch, the result of "applying p to B"
is the context B + {n(p)}.
It would be interesting to apply a product p.q to a context B.
Obviously, this must be B+{n(p.q)}, which is B plus one-element set.
Now, n(p.q) = n(p).n(q) .
On the right hand side we have composition of names.
The paper says that this is B+{n(p),n(q)}, which is B plus some two-element set.
This identity is difficult to convince oneself of.
In what respect is the above interpretation of patches really important or
significant?
In section 5 also "patch sequences" are introduced.
A patch sequence is clearly different from the composition of all its
components or elements.
In fact, the set of patch sequences looks like the free monoid generated by all
patches.
It looks as though patch sequences are what really matters, since they are
"merged" later on.
A Boolean property "sensible" is introduced on the set of all patch sequences.
It needs to satisfy certain axioms which I omit here.
One has no idea (at this point) what the concept is used for. The explanation
given here uses notions which are still somewhat unrelated.
At the end of section 5 repository states make their appearance again in the
explanations.
Is a repository state a context?
At the end of section another fundamental definition is made rather quietly.
Two patch sequences are considered "equal" when a certain condition holds.
In fact, we have the equivalence relation generated by the commutation relation
<--> .
What happens when during commutation you get a patch and its inverse next to
each other? Can you "cancel" them?
Section 6 is informal and describes the "merging of patches".
Merging of patches is probably the wrong term, because it seems that merging of
*patch sequences* is meant.
It begins with two repositories, but we have never said what a repository is.
It looks as though a repository is a patch sequence.
What the result of merging?
Another patch sequence?
It looks as though we start with two patch sequences xq and xr.
Here x is any patch sequence and q and r and individual patches.
And juxtaposition means the natural composition of sequences.
We then try to find two more patches q and r such that c(q,r) = (q,r) or
(q,r) <--> (qr).
We then declare the patch sequence (=repository) x(r.q) as the result of the
merge.
In the general case we have two patch sequences which have a common prefix.
By merging them we arrive at a resulting patch sequence.
The merging algorithm is, naturally, somewhat complex, and may fail, of course,
when there are conflicts.
Here I have to leave the paper at the moment.
It is good to make an effort and base darcs development on a sound logical
foundation.
Thanks again for making available early drafts of the theory.
There is great potential there, but understandably also great need for
streamlining.
Hubert
________________________________________________________________________
Schon gehört? Bei WEB.DE gibt' s viele kostenlose Spiele:
http://games.entertainment.web.de/de/entertainment/games/free/index.html
_______________________________________________
darcs-users mailing list
[email protected]
http://lists.osuosl.org/mailman/listinfo/darcs-users
