Obviously this is open for discussion. I am ready to defend this proposal
and explain how and why I think this is better by means of one or two
concrete examples. That is, if you actually need convincing...

A big hurray to the type indexing (witnesses). Without this I would never
have dared to make such a far-reaching change down in the core of Darcs. As
it was, I made the three basic changes explained in the comment and then
fixed all the resulting type errors. The first version that compiled also
ran all the tests without error.

1 patch for repository http://darcs.net/screened:

patch d55e1b7ccb59a93675bb5c475eb37ebd7b95b6a2
Author: Ben Franksen <benjamin.franksen@helmholtz-berlin.de>
Date:   Tue Feb 10 17:02:40 CET 2015
  * changed the argument order of PatchSet and backward operators
  
  This simple (if tedious) refactoring makes the constructor :<: of RL and the
  backward concatenation operator +<+ left-associative and flips their
  argument order. This means backward lists (RL) are constructed by adding
  elements to the right (xs :<: x). Concatenating backward lists (xs +<+ ys)
  means the xs are earlier than the ys, in symmetry with (xs +>+ ys). IMO this
  greatly improves the ease with which one can read and write patch
  commutation code, since the order of identifiers in patterns and expressions
  is now always the same: left = apply earlier to right = apply later, no
  matter from which end we add elements.
  
  The data type PatchSet was changed to match this: first come the tagged
  chunks, then the rest of the patches. Thus we now pattern match and
  construct PatchSets in the intuitive order e.g.  PatchSet tagged (ps :<: p)
  gives us the latest patch p.

Attachments

• changed-the-argument-order-of-patchset-and-backward-operators.dpatch
• patch-preview.txt
• unnamed

I have no objection to the idea.

I'm not entirely sure if it's better or not, but I certainly get confused by the 
ordering of these "reverse" operators as they stand, so even if I still get 
confused I don't think I'll have lost anything :-)

Reordering :<: should be pretty safe as both the witnesses and the patch type 
themselves will be changed. I'm mildly concerned that we could miss places where 
+<+ needs to change because there are places in the code where we do unsafe 
things with the witnesses, but I think with the backup of the tests the risk 
should be fairly low.

I am not sure I understand your remark about +<+. Could you give an
example (i.e. point me to some code) of what you mean with "doing unsafe
things with witnesses"?

Thanks Ganesh. I am not yet screening this because I'd like a few more
opinions.

2015-02-10 22:06 GMT-03:00 Ben Franksen <bugs@darcs.net>:
>
> Ben Franksen <benjamin.franksen@helmholtz-berlin.de> added the comment:
>
> Thanks Ganesh. I am not yet screening this because I'd like a few more
> opinions.
>
> __________________________________
> Darcs bug tracker <bugs@darcs.net>
> <http://bugs.darcs.net/patch1267>
> __________________________________
> _______________________________________________
> darcs-devel mailing list
> darcs-devel@darcs.net
> http://lists.osuosl.org/mailman/listinfo/darcs-devel

I don't mind changing the definition of RL if it is an improvement.
However, I'd like to ask you to hold it a couple of weeks before
screening it because otherwise it will go into 2.10, and there are a
couple of bugfixes that are going to depend on this patch. I know it
makes more work for you, but in the meantime there can be interesting
discussions about this change.

On 10/02/2015 19:57, Ben Franksen wrote:
> 
> Ben Franksen <benjamin.franksen@helmholtz-berlin.de> added the comment:
> 
> I am not sure I understand your remark about +<+. Could you give an
> example (i.e. point me to some code) of what you mean with "doing unsafe
> things with witnesses"?

There are a few cases witnesses can't/don't cover completely.

(1) Constructing entirely new patches.

Almost by definition, you can construct these with any witnesses you
like and the type system will be none the wiser.

So for example in this code:

   foo = (Move (fp2fn "foo") (fp2fn "bar") :<: NilRL) +<+
         (Move (fp2fn "bar") (fp2fn "baz") :<: NilRL)

Nothing would detect the arguments to (+<+) being swapped.

In general when you use a primitive patch constructor both witnesses are
entirely polymorphic so the caller gets any witnesses they like.

This problem is partially addressed by the (rather complicated)
'FreeLeft' and 'FreeRight' types in Darcs.Patch.Witnesses.Sealed. The
core idea there is that you choose one witness or the other to be
polymorphic, and the other ends up being an existential (i.e. the caller
chooses one, and the callee chooses the other). This sort of expresses
the concept that when recording a new patch into a known repository, the
caller knows the starting context (the existing state of the repository)
but can't control what the ending context will be.

However code has to choose to use 'FreeLeft'/'FreeRight', and even if it
does, the 'foo' example above would still be a problem.

In practice I think that's mainly a risk in the test code where concrete
patches are used for examples. But I'd also have a look through bits
like the coalescing code (Darcs.Patch.Prim.V1.Coalesce), the diffing
code (Darcs.Repository.Diff.treeDiff), and perhaps the patch reading
code (Darcs.Patch.Prim.V1.Read).

(2) Uses of unsafeCoerceP (grep for this).

Again rather by definition, this lets you do anything with the
witnesses. Typically it's needed in two cases:

(a) where we have some external information that the witnesses must be
the same and we need to tell GHC this. This applies for example when
comparing two repositories (from memory, functions like
getCommonAndUncommon), or indeed two patches (any implementation of the
Darcs.Patch.Witnesses.Eq.MyEq via the unsafeCompare method).

(b) to work around what appear to be bugs in the V1 merging code that I
didn't dare fix when adding witnesses for fear of making the situation
worse e.g. with already saved respositories.

Hope that makes some sense...

Cheers,

Ganesh

Ben, do you still want to go ahead with this patch?

Yes, thanks for the reminder. Probably need to rebase it.

PS: sorry for being absent for so long. I will have to read up on what's
going on.

Looks like it just needs a small conflict resolution to apply to current screened

2 patches for repository darcs-unstable@darcs.net:screened:

Tue Feb 10 16:02:40 GMT 2015  Ben Franksen <benjamin.franksen@helmholtz-berlin.de>
  * changed the argument order of PatchSet and backward operators
  
  This simple (if tedious) refactoring makes the constructor :<: of RL and the
  backward concatenation operator +<+ left-associative and flips their
  argument order. This means backward lists (RL) are constructed by adding
  elements to the right (xs :<: x). Concatenating backward lists (xs +<+ ys)
  means the xs are earlier than the ys, in symmetry with (xs +>+ ys). IMO this
  greatly improves the ease with which one can read and write patch
  commutation code, since the order of identifiers in patterns and expressions
  is now always the same: left = apply earlier to right = apply later, no
  matter from which end we add elements.
  
  The data type PatchSet was changed to match this: first come the tagged
  chunks, then the rest of the patches. Thus we now pattern match and
  construct PatchSets in the intuitive order e.g.  PatchSet tagged (ps :<: p)
  gives us the latest patch p.

Tue Jun  9 22:43:16 BST 2015  Ganesh Sittampalam <ganesh@earth.li>
  * resolve conflicts
  
  between d55e1b7ccb59a93675bb5c475eb37ebd7b95b6a2
   (changed the argument order of PatchSet and backward operators)
  and 2e9b0734ca3e84159bf328c948b60d5236895fe2
   (resolve issue2260: skip internal patches when counting)

Attachments

• changed-the-argument-order-of-patchset-and-backward-operators.dpatch
• patch-preview.txt
• unnamed

Just giving my opinion: now that 2.10 I'm glad we carry on with this
kind of big refactorings :-)

I've thought about this a bit more and I think this change definitely 
makes sense. It's consistent with how the "snoc" operation generally seems 
to be defined and as Ben says it makes contexts go in a sensible order.

For consistency I think we need to change the order of arguments to 
directed reverse pairs (:<) too. I'll have a go at that.

I'm now getting a bit less sure about this now.

Changing the order of arguments to (:<) will leave it either exactly the same 
as (:>), or the same but with the type arguments reversed. So that suggests 
we should remove it completely.

I then realised/remembered that the '>' and '<' characters are supposed to 
provide the intuition of which way the contexts go. So by reversing the order 
of arguments to (:<:) we are changing that meaning completely. Perhaps we 
should change the constructor too? For a couple of initial (not very good) 
ideas, perhaps (:|>:) or (:>>:)?

Sorry for the stream of consciousness...

It turns out I had already rebased this change, so here goes.

1 patch for repository http://darcs.net/screened:

patch 7e9c43e06df01116abb58d0b4e2fc4b43a26f534
Author: Ben Franksen <benjamin.franksen@helmholtz-berlin.de>
Date:   Thu Feb 19 22:49:25 CET 2015
  * changed the argument order of PatchSet and backward operators
  
  This simple (if tedious) refactoring makes the constructor :<: of RL and the
  backward concatenation operator +<+ left-associative and flips their
  argument order. This means backward lists (RL) are constructed by adding
  elements to the right (xs :<: x). Concatenating backward lists (xs +<+ ys)
  means the xs are earlier than the ys, in symmetry with (xs +>+ ys). IMO this
  greatly improves the ease with which one can read and write patch
  commutation code, since the order of identifiers in patterns and expressions
  is now always the same: left = apply earlier to right = apply later, no
  matter from which end we add elements.
  
  The data type PatchSet was changed to match this: first come the tagged
  chunks, then the rest of the patches. Thus we now pattern match and
  construct PatchSets in the intuitive order e.g.  PatchSet tagged (ps :<: p)
  gives us the latest patch p.
  
  Also renamed consRLSealed to snocRLSealed and swapped order of arguments.

Attachments

• changed-the-argument-order-of-patchset-and-backward-operators.dpatch
• patch-preview.txt
• unnamed

i have now screened the latest version of this patch. Should I change
the status in the tracker?

Yes, it should be moved to needs-review at that point - I've done that 
now.

Any thoughts about the naming and how to handle :< ?

Removing (:<) is indeed the logical consequence. In view of what (:<:)
and (:>:) mean (now) I would even go further and also rename (:>) to
something that does not contain a < or > symbol. What about (:-) ?

Hmm, I think my preference is still to rename :<: and maintain the idea  
that > indicates a direction for contexts. (a :<: b) :- c doesn't read 
as well for me as something like (a :>>: b) :> c. But I don't feel too 
strongly. We should definitely do something though.

I think we agree that the syntactic order should always indicate
application order, i.e.

  a :: A x y, b :: B y z
  ----------------------
  a `op` b :: C x z

with suitable A, B, and C. This is what my order reversal patch started
and what eliminating :< finishes (I think). So far so good.

Now what to do about the naming?

I am unsure what you mean with "where the context is" and why you think
this is relevant.

My idea was to interpret the < and > symbols to indicate where the
"small" and the "large" thing is (a list is a large thing, a single
element a small one). When using ordered pairs (the :> operator) there
is no small or large side: one can have a single patch or a sequence on
either side. So the symbols < and > don't feel right to me.

I am not wedded to :- (I agree that sometimes it looks weird, especially
with _ on the RHS i.e. p :- _). We could as well use :|: or :* (the
latter is often used for product, so that might give people an intuition).

On 14/06/2015 18:20, Ben Franksen wrote:
> 
> Ben Franksen <benjamin.franksen@helmholtz-berlin.de> added the comment:
> 
> I think we agree that the syntactic order should always indicate
> application order, i.e.
> 
>   a :: A x y, b :: B y z
>   ----------------------
>   a `op` b :: C x z
> 
> with suitable A, B, and C. This is what my order reversal patch started
> and what eliminating :< finishes (I think). So far so good.

Yep.

> Now what to do about the naming?
> 
> I am unsure what you mean with "where the context is" and why you think
> this is relevant.

I mean that '>' should also indicate application order - I think I meant
to say something like "how the contexts are ordered".

That does mean it's redundant, since we now always have the syntactic
order to indicate that. But I still feel it would help to make
expressions more readable.

> My idea was to interpret the < and > symbols to indicate where the
> "small" and the "large" thing is (a list is a large thing, a single
> element a small one). When using ordered pairs (the :> operator) there
> is no small or large side: one can have a single patch or a sequence on
> either side. So the symbols < and > don't feel right to me.

I guess that part of my wish to use '>' to indicate application order is
that it's what we did before so I'm used to it. But also I think I like
that it helps indicate asymmetry, in that you can't swap the arguments
in a directed tuple purely because of the contexts.

I also just remembered that we still have the "parallel" operators :\/:
and :/\: that indicate "convergence" with the arrows - the pointy end is
where the patches have the same context. Hmm, I guess that doesn't fit
too well with the '>' notation :-)

> I am not wedded to :- (I agree that sometimes it looks weird, especially
> with _ on the RHS i.e. p :- _). We could as well use :|: or :* (the
> latter is often used for product, so that might give people an intuition).

:|: wouldn't work well, because we have :||: for parallel pairs (pairs
of patches with the same starting and ending contexts).

Cheers,

Ganesh

Declaring this reviewed - there's still some follow-up discussion on 
the naming of the FL and RL constructors, but we can handle that 
separately.