[darcs-devel] [patch2184] more Arbitrary cleanups

Ganesh Sittampalam bugs at darcs.net
Fri Jun 4 18:25:16 UTC 2021

Ganesh Sittampalam <ganesh at earth.li> added the comment:

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 at 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 at 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 at 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.

title: replace Triple with a general instance A... (and 8 more) -> more Arbitrary cleanups

Darcs bug tracker <bugs at darcs.net>

More information about the darcs-devel mailing list