Generating random closures and CoArbitrary

[Centril]

It would be neat to be able to generate random closures. Doing so will allow us to generate things like random std::iter::Filter.

To that end, I've started some work here: https://github.com/Centril/proptest-arbitrary/blob/master/src/coarbitrary.rs

I essentially replicate QuickCheck's CoArbitrary class as:

/// `CoArbitrary` defines a method for perturbing an RNG
/// based on the value of `&self`.
pub trait CoArbitrary {
    /// Perturbs the given underlying RNG according to
    /// the structure of the given `&self` value.
    fn coarbitrary(&self, var: Varianter);
}

 // Varianter is just a wrapper around &mut XorShiftRng

To define impls we'll need a primitive operation:

/// Perturbs the RNG with an integer seed.
pub fn variant(rng: &mut XorShiftRng, seed: usize) {
    unimplemented!()
}

which I don't know how to define yet, but I've asked around at: https://github.com/rust-lang-nursery/rand/issues/231

Perhaps we could have CoStrategy instead of CoArbitrary - I'm not sure if that makes sense or is useful tho.

One problem I ran into when trying to define the ClosureStrategy was that I have to do .unwrap() as seen here: https://github.com/Centril/proptest-arbitrary/blob/master/src/coarbitrary.rs#L231 So it might be a good idea to have some sort of infallible strategy trait T: InfallibleStrategy |- T: Strategy that just returns Self::Value instead of NewTree<Self>. This is a bit akin to ExactSizeIterator and other schemes run in libstd.

Can you check my logic for ClosureStrategy and GenClosure for bugs btw?

[AltSysrq]

You linked to https://kseo.github.io/posts/2016-12-14-how-quick-check-generate-random-functions.html in the rand thread, but I'm copying it here because it's the first description of CoArbitrary I've come across that actually makes sense to me.

That said, what's the purpose of CoArbitrary in this code? For the most part it looks like it's just a less chaotic Hash, but since the value is being used to perturb an RNG, the more regular outputs don't seem like they'd bring much benefit.

variant

My first thought is to take https://github.com/AltSysrq/proptest/blob/91aa82cf14e9afcc962d1c4ffb3f2fbdf5de3807/src/test_runner.rs#L578-L591 and xor each seed value by successive hashes (i.e., hash(x), hash(hash(x)), …) of the perturbation value.

unwrap() … InfallibleStrategy

The issue I see with InfallibleStrategy is that it either would get lost through BoxedStrategy, or there would need to be an additional pair of BoxedInfallibleStrategy types. unwrap() seems reasonable to me though.

CoStrategy

Now that I actually understand what this is, I'd feel positively about bringing that in to core proptest under a more direct name like FnStrategy.

bugs

• IMHO CoArbitrary should pay for holding an Arc<Mutex<TestRunner>> so that it can maintain the rejection counts over time. (Also, if this were in core proptest, it could use a shallow clone and also pool these counts with everything else.)

• <bool as Coarbitrary>::coarbitrary() always returns 1.

[AltSysrq]

Another question, do you know of any practical uses of CoArbitrary? All I've been able to find is the example in The Design and Use of QuickCheck, which is largely hyopthetical. (To be clear, I'm not trying to be dismissive here, but genuinely curious.)

[Centril]

First, a status update: I've refactored and implemented CoArbitrary for most of the standard library, the code lives here right now: https://github.com/Centril/proptest-arbitrary/tree/master/src/coarbitrary

That said, what's the purpose of CoArbitrary in this code? For the most part it looks like it's just a less chaotic Hash, but since the value is being used to perturb an RNG, the more regular outputs don't seem like they'd bring much benefit.

I mostly just did a faithful translation from Haskell - which might not make sense =) I agree on the Hash bit, and if we had specialization, we could blanket impl CoArbitrary for any Hash type - and I think that is a good idea for the future.

CoArbitrary would allow us to do things like:

 (Arbitrary a, CoArbitrary b) => CoArbitrary (a -> b)

This means that it is possible to generate higher order functions like (a -> b) -> c (I think), tho I don't know how useful that is in Rust.

My first thought is to take

That was my inspiration for the definition of variant I included in the rand repo =)

and xor each seed value by successive hashes (i.e., hash(x), hash(hash(x)), …) of the perturbation value.

Not exactly sure what you mean here - something like (rough sketch) this?

fn variant(rng: &mut XorShiftRng, seed: u32) {
     let mut seed_hash = seed;
     let mut seed_arr = <[u32;4] as Rand>::rand(&mut self.rng); 
     for word in &mut seed_arr {
         seed_hash = hash(seed_hash); // assume we have a function  hash :: u32 -> u32
         *word ^= seed_hash;
     }
     rng.reseed(seed_arr);
}

I have to admit - I am largely ignorant about the design of RNGs, so I'll buy anything you tell me wholesale here ;)

The issue I see with InfallibleStrategy is that it either would get lost through BoxedStrategy, or there would need to be an additional pair of BoxedInfallibleStrategy types. unwrap() seems reasonable to me though.

Oh yeah... That is a real problem I thought of as well :( Static-dispatch existential quantification (-> impl Trait) will hopefully ease this problem? I guess the value added of having the extra trait would be a stronger hint to users, but .unwrap() also kinda works I guess.

Now that I actually understand what this is, I'd feel positively about bringing that in to core proptest under a more direct name like FnStrategy.

I don't know myself what CoStrategy even means, it was mostly a weird thought that hit me "can we make this more general?" - it is not the ClosureStrategy I define in the linked file. FnStrategy makes sense for ClosureStrategy.

Tho I was thinking of using that particular name FnStrategy for:

/// Shorthand for `Generator<V, fn() -> V>`.
pub type FnGenerator<V> = Generator<V, fn() -> V>;

/// Strategy for generating `V`s from an `Fn() -> V`.
/// It's not a very interesting Strategy, but required sometimes
/// when the only means of creating an object of some type is
/// via a function while type type is also not Clone.
#[derive(Clone, Copy)]
pub struct Generator<V, F: Fn() -> V> {
    generator: F,
}

impl<V, F: Fn() -> V> Generator<V, F> {
    /// Constructs a `Generator` strategy.
    pub fn new(generator: F) -> Self {
        Self { generator }
    }
}

impl<V: Debug, F: Clone + Fn() -> V> Strategy for Generator<V, F> {
    type Value = Self;
    fn new_value(&self, _: &mut TestRunner) -> Result<Self::Value, String> {
        Ok(Generator { generator: self.generator.clone() })
    }
}

impl<V: Debug, F: Fn() -> V> ValueTree for Generator<V, F> {
    type Value = V;
    fn current(&self) -> Self::Value { (self.generator)() }
    fn simplify(&mut self) -> bool { false }
    fn complicate(&mut self) -> bool { false }
}

which is used in proptest_derive right now and in some other places when you don't necessarily have Clone types.

IMHO CoArbitrary should pay for holding an Arc<Mutex> so that it can maintain the rejection counts over time. (Also, if this were in core proptest, it could use a shallow clone and also pool these counts with everything else.)

Just the rejection count right? The function still has to start over each time with a cloned RNG so that the same input generates the same output each time or it wouldn't be a real function. But I am not sure why this applies to CoArbitrary... Shouldn't it apply to ClosureStrategy? Also, on rejection, ClosureStrategy has no other choice but to panic since it has to provide a return value for the function (which it can't if there is rejection..)

::coarbitrary() always returns 1.

Good catch 👍

Another question, do you know of any practical uses of CoArbitrary? All I've been able to find is the example in The Design and Use of QuickCheck, which is largely hyopthetical. (To be clear, I'm not trying to be dismissive here, but genuinely curious.)

Consider defining a strategy for a Filter iterator - then you need to be able to generate a closure from A -> bool, in which case you need CoArbitrary. Generally, if you have higher order algorithms, CoArbitrary can be beneficial to you cause it enables the generation of closures. On its own it is not very interesting tho.

[AltSysrq]

Consider defining a strategy for a Filter iterator

Yeah, I get things like that. I was more hoping to find an example that is less trivial to cover with traditional unit testing methods. I could see it maybe being useful for this "fault" system ensync uses for some of its tests, but there'd need to be some way of shrinking and for usefully displaying the function for it to really work well.

[Centril]

I'll do some more research and get back to you =)

[Centril]

Just jotting down some barely-finished ideas here now... reading some papers about this, so I'll have a more informed view later =)

Ideas:

• For the sake of error reporting, a ClosureStrategy or FnStrategy (whatever we call it) may keep a tally of all the tuples (input, output) and then present those as a relation [(input, output] (or the last one). This entails that output: Clone. This does however not help with shrinking (I think).

Examples in the small:

• In 2.2, the quickcheck paper talks about testing that function composition is associative. That is a trivial property, but I think it is these small and fundamental properties that can be useful to test here. These kinds of properties are spread in core algorithmic crates like itertools.
• You could for example envisage generating random iterators lazily with unfold logic.

Examples in the big:

• TODO

[Centril]

Just a status update: I'm currently reading papers on shrinking and showing functions and trying to get hold of Koen Claessen on this subject. I think it should be possible to generate shrinkable and showable functions in proptest; I'm experimenting on that at the moment =)

[turion]

What's the status on this? It would be really nice to have a CoArbitrary class.