This is a followup to the discussion in patch2166.
I'll send a separate email with some commentary. I've
deliberately marked lots of the patches WIP to
force me to actually write better docs before
submitting for real.

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

patch 3ebd041e425ab956e407be8ba395aded4d053e7d
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Jun  4 17:50:49 BST 2021
  * replace Triple with a general instance ArbitraryWS (:>)

patch 22e46d05ee5828469beeae8d19f0d4e2b93f2d2c
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Jun  4 18:36:27 BST 2021
  * WIP: propagate "next prim" in PrimV1

patch 34b7203a8934e8a5267e916080437afd9e4216dc
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Jun  4 18:41:49 BST 2021
  * WIP: propagate "next prim" in PrimFileUUID

patch 17eb340ed94e8a38742dc188542a619e3f9d5e41
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Jun  4 18:42:52 BST 2021
  * WIP: drop ArbitraryWS and arbitraryStatePair

patch 897cde83dc76d3c387b4fea3c9fdcae222ae776d
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Jun  4 18:47:44 BST 2021
  * WIP: get rid of Pair

patch 526665c1ef6ebd8cf2bbfb6ae2d3d42658aef106
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Jun  4 18:58:24 BST 2021
  * WIP: inline/remove dead code

patch 787b4030cbd16b769da22c7bcb0eb039c9a793f6
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Jun  4 19:13:50 BST 2021
  * replace ArbitraryS2 (:\/:) with MergeableSequence

patch ad82418c20e76d2cdcae00039e1cd6c1a71b3c93
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Jun  4 19:17:31 BST 2021
  * WIP: inline instance

patch e21c2d6f1cd7da83ca02456d302f9cd62c7e76b6
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Jun  4 19:22:43 BST 2021
  * WIP: get rid of end state in WithState

Attachments

• patch-preview.txt
• replace-triple-with-a-general-instance-arbitraryws-____.dpatch
• unnamed

On 04/06/2021 08:19, Ben Franksen wrote:
> 
> Right, so the specialization for prim pairs means we can't generalize
> such an implementation of pairs to triples. Indeed, aPrimPair can only
> work if the types coincide.

I had a go at implementing the idea I mentioned in my last email about
generalising aPrimPair by carrying forward properties from the left-hand
side of the :> to influence generation of the right-hand side. It
actually works out quite nicely:

> patch 22e46d05ee5828469beeae8d19f0d4e2b93f2d2c
> Author: Ganesh Sittampalam <ganesh@earth.li>
> Date:   Fri Jun  4 18:36:27 BST 2021
>   * WIP: propagate "next prim" in PrimV1

The basic idea is that if are generating a prim, we can choose to
generate a pair of hunks, and then store the second half in the "model"
that will be available for the generation of the next prim anyway. And
if something is currently available in the model, then we
unconditionally use it.

It's a small abuse of the concept of the model, and for PrimV1 it
involves a little bit of type games to cope with polymorphism. But
overall I think it actually captures what we want really nicely, and it
means that Triple, FL etc all get a higher proportion of commutable pairs.

One more caveat that only occurred to me while writing this message is
that it will make generation of Par in MergeableSequence rather prone to
duplicates, as if you generate one half of a hunk pair before a Par,
then both branches of the Par will automatically use it. More thought
needed there, maybe it's as simple as always clobbering 'nextPrim' for
the second branch of a Par.

> On the other hand we have a generic implementation, where we generate
> both members of the pair independently, and such an implementation can
> always be generalized to two different types (provided they have the
> same state type i.e. ModelOf). For instance we use that when generating
> FLs of patches.
> This suggests that we may want to use the Pair type *only* when we
> expect a specialized implementation, and perhaps similarly with Triple.
> Whereas for the cases where we chose elements independently, a single
> generic instance for (:>) with (possibly) different type variables for
> lhs and rhs should suffice.

Yep, and in fact as it stands Triple does choose elements independently
and can be removed, as demonstrated by this patch which is independent
of the above ones:

> patch 3ebd041e425ab956e407be8ba395aded4d053e7d
> Author: Ganesh Sittampalam <ganesh@earth.li>
> Date:   Fri Jun  4 17:50:49 BST 2021
>   * replace Triple with a general instance ArbitraryWS (:>)

But on the other hand, if we don't generalise the aPrimPair concept,
maybe we would instead want aPrimTriple to get better permutivity tests.

Most of the other patches in this bundle are cleanups that become
possible if we drop Pair - just leaving us with ArbitraryS2 as the
remaining bit of "glue". That's likely to be harder to remove as we do
need some kind of glue between the Arbitrary-based code coming from
Test.QuickCheck and the fact that in our code we want to work with
witnessed objected.

However there are actually only two instances of ArbitraryS2 left, for
WithState and WithStartState2. WithState wraps a patch with both
starting and ending states, WithStartState2 just has the starting state
as the name suggests.

It actually turns out that the end state in WithState is barely needed:

> patch e21c2d6f1cd7da83ca02456d302f9cd62c7e76b6
> Author: Ganesh Sittampalam <ganesh@earth.li>
> Date:   Fri Jun  4 19:22:43 BST 2021
>   * WIP: get rid of end state in WithState

Which in theory means we could merge WithState and WithStartState2.
However, WithStartState2 came out of the work on MergeableSequence and
has some quite sophisticated shrinking logic that comes with some
complex constraints:

> instance
>   ( ArbitraryState p, Shrinkable p, RepoModel s
>   , s ~ ModelOf p
>   , s ~ ModelOf prim
>   , Effect p
>   , Apply prim, ApplyState prim ~ RepoState s
>   , prim ~ PrimOf p, Invert prim, ShrinkModel prim, PropagateShrink prim p
>   )
>   => ArbitraryS2 (WithStartState2 p) where
>   arbitraryS2 = do
>     repo <- aSmallRepo @s
>     Sealed (WithEndState p _) <- arbitraryState repo
>     return (Sealed2 (WithStartState2 repo p))
>   shrinkS2 w@(Sealed2 (WithStartState2 repo p)) =
>     [...]

Contrast this with:

> instance (ArbitraryState p, RepoModel (ModelOf p)) => ArbitraryS2 (WithState p) where
>   arbitraryS2 = do
>     s <- aSmallRepo
>     Sealed (WithEndState p _) <- arbitraryState s
>     return $ seal2 $ WithState s p
>   shrinkS2 _ = []

In practice when we try to replace WithState with WithStartState2 those
constraints become a bit painful. It's mostly because of prims not
having the same instances as repopatches (e.g. Effect, Apply etc) which
is a non-trivial problem in itself, but maybe with a bit more
thought/tweaking it'll be possible to do something clean here.