darcs

Patch 1267 changed the argument order of PatchSet and backward operators

Title changed the argument order of PatchSet and backward operators
Superseder Nosy List bf, ganesh
Related Issues
Status accepted Assigned To
Milestone

Created on 2015-02-10.16:23:17 by bf, last changed 2015-06-16.17:17:52 by ganesh.

Files
File name Status Uploaded Type Edit Remove
changed-the-argument-order-of-patchset-and-backward-operators.dpatch dead bf, 2015-02-10.16:23:16 application/x-darcs-patch
changed-the-argument-order-of-patchset-and-backward-operators.dpatch dead ganesh, 2015-06-09.21:50:57 application/x-darcs-patch
changed-the-argument-order-of-patchset-and-backward-operators.dpatch bf, 2015-06-11.11:10:45 application/x-darcs-patch
patch-preview.txt bf, 2015-02-10.16:23:16 text/x-darcs-patch
patch-preview.txt ganesh, 2015-06-09.21:50:57 text/x-darcs-patch
patch-preview.txt bf, 2015-06-11.11:10:45 text/x-darcs-patch
unnamed bf, 2015-02-10.16:23:16
unnamed ganesh, 2015-06-09.21:50:57
unnamed bf, 2015-06-11.11:10:45
See mailing list archives for discussion on individual patches.
Messages
msg18058 (view) Author: bf Date: 2015-02-10.16:23:16
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
msg18059 (view) Author: ganesh Date: 2015-02-10.18:57:12
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.
msg18061 (view) Author: bf Date: 2015-02-10.19:57:44
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"?
msg18076 (view) Author: bf Date: 2015-02-11.01:06:40
Thanks Ganesh. I am not yet screening this because I'd like a few more
opinions.
msg18077 (view) Author: gh Date: 2015-02-11.18:54:23
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
msg18078 (view) Author: gh Date: 2015-02-11.19:11:46
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.
msg18138 (view) Author: ganesh Date: 2015-02-13.21:43:44
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
msg18431 (view) Author: ganesh Date: 2015-06-09.05:27:07
Ben, do you still want to go ahead with this patch?
msg18432 (view) Author: bf Date: 2015-06-09.09:04:20
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.
msg18434 (view) Author: ganesh Date: 2015-06-09.21:50:57
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
msg18435 (view) Author: gh Date: 2015-06-09.21:57:38
Just giving my opinion: now that 2.10 I'm glad we carry on with this
kind of big refactorings :-)
msg18436 (view) Author: ganesh Date: 2015-06-10.05:49:49
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.
msg18437 (view) Author: ganesh Date: 2015-06-10.06:15:22
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...
msg18439 (view) Author: bf Date: 2015-06-11.11:10:45
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
msg18474 (view) Author: bf Date: 2015-06-13.12:54:55
i have now screened the latest version of this patch. Should I change
the status in the tracker?
msg18481 (view) Author: ganesh Date: 2015-06-13.15:06:26
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 :< ?
msg18491 (view) Author: bf Date: 2015-06-14.11:40:03
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 (:-) ?
msg18493 (view) Author: ganesh Date: 2015-06-14.16:09:35
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.
msg18494 (view) Author: bf Date: 2015-06-14.17:20:04
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).
msg18496 (view) Author: ganesh Date: 2015-06-14.18:04:37
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
msg18509 (view) Author: ganesh Date: 2015-06-16.05:56:57
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.
History
Date User Action Args
2015-02-10 16:23:17bfcreate
2015-02-10 18:57:12ganeshsetnosy: + ganesh
messages: + msg18059
2015-02-10 19:57:44bfsetmessages: + msg18061
2015-02-11 01:06:40bfsetmessages: + msg18076
2015-02-11 18:54:24ghsetmessages: + msg18077
2015-02-11 19:11:46ghsetmessages: + msg18078
2015-02-13 21:43:44ganeshsetmessages: + msg18138
2015-06-09 05:27:07ganeshsetstatus: needs-screening -> in-discussion
messages: + msg18431
2015-06-09 09:04:20bfsetmessages: + msg18432
2015-06-09 21:50:57ganeshsetfiles: + patch-preview.txt, changed-the-argument-order-of-patchset-and-backward-operators.dpatch, unnamed
messages: + msg18434
2015-06-09 21:57:38ghsetmessages: + msg18435
2015-06-10 05:49:50ganeshsetmessages: + msg18436
2015-06-10 06:15:22ganeshsetmessages: + msg18437
2015-06-11 11:10:46bfsetfiles: + patch-preview.txt, changed-the-argument-order-of-patchset-and-backward-operators.dpatch, unnamed
messages: + msg18439
title: changed the argument order of PatchSet and backward op... -> changed the argument order of PatchSet and backward operators
2015-06-13 12:54:55bfsetmessages: + msg18474
2015-06-13 15:06:27ganeshsetstatus: in-discussion -> needs-review
messages: + msg18481
2015-06-14 11:40:03bfsetmessages: + msg18491
2015-06-14 16:09:36ganeshsetmessages: + msg18493
2015-06-14 17:20:05bfsetmessages: + msg18494
2015-06-14 18:04:37ganeshsetmessages: + msg18496
2015-06-16 05:56:57ganeshsetstatus: needs-review -> accepted-pending-tests
messages: + msg18509
2015-06-16 17:17:52ganeshsetstatus: accepted-pending-tests -> accepted