RFC: Arbitrary derivation and registration

[kurtschelfthout]

There has been a fair amount of discussion about his in various issues: #109, #198, #334, #390. Since in v3 there is an opportunity to redesign and improve, I'd like to open a broader discussion here to get a good overview of the ins and outs.

Why is it worth having a 'T -> Arbitrary<'T> mapping?

It is possible to make a working FsCheck without any mapping at all. It would mean that:

• the user would have to always specify Arbirtary instances explicitly, instead or in addition to the types,
• reflective derivation of Arbitrary instances is removed or significantly limited. (The latter obviously depends on some map of T -> Arbitrary<T> for at least the primitive types.)

One could argue the difference between fun (a:string) -> ... and Prop.forAll(Arb.Default.String(), fun a -> ...) is not big.

Where it does become annoying is if you are generating a more elaborate type, e.g. a tuple-like type:

Prop.forAll(Arb.Tuple(Arb.Int,Arb.String,myArbForMyType, Arb.Option(Arb.char)), fun (i,s,mytype,charopt) -> ....)

For a record type the API could look like:

Prop.forAll(Arb.Tuple(Arb.Int,Arb.String,myArbForMyType, Arb.Option(Arb.char)) |> Arb.convert tupleToMyRecordType tupleFromMyRecordType, 
fun myRecord -> ....)

For a union type, esp. a recursive it's unclear to me if there is a short way of describing and Arbitrary instance. Presumably we need an Arb.fix, Arb.choice and Arb.apply to deal with recursion, choice between different union types and applying the union case to its field respectively.

It all seems a bit tedious.

Furthermore, having a mapping is appealing to newcomers because really all you have to know is how to write a function checking some property of a random instance of your type, and there is a very good chance FsCheck will already be able to run some tests for you.

The mapping is also a place where users can easily extend and tweak the whole set of automatically generated types:

• Extend: say you have a custom type that FsCheck doesn't handle out of the box. Then you can simply register a generator for that type, and presto, FsCheck can now not only generate that type, but also lists, arrays, record types, union types, etc of that type.
• Tweak: say you don't want to generate NaN for floats, because it's not important for your domain. But the default list, array, record type generators will all generate NaN if they contain floats. Then you can simply override the generator for floats, and all the other generators will pick up the custom generator and so you won't get NaNs anywhere.

What is bad about having a 'T -> Arbitrary<'T> mapping?

It is currently implemented as a piece of global, mutable state and so carries associated costs.

Should it be global? ThreadLocal? AsyncLocal? SomethingElseLocal?

Also it's not clear which arbitrary instances are in effect at any one time in the code, because it depends on which Arb.register calls have been executed beforehand. This is particularly problematic in multi-threaded scenarios.

Some specific problems with the current implementation

• The mapping is kept in a single, immutable dictionary, but there is one ThreadLocal value where that dictionary is set. This seems to make it work with xunit's parallelization. It almost certainly does not work with Task.
• There is a single source of default Arbitrary instances in Arbitrary.fs which is kept in a format so that the registration mechanism (in TypeClass.fs) can read it. Each instance is defined as a parameter-less static method. This has several disadvantages:
• If a generator is dependent on another generator, e.g. FsList() : Arbitrary<list<T>> needs a generator for T, that other generator is accessed via Arb.from<T> in the implementation of FsList which recurively consults the Arbitrary mapping to lookup the Arbitrary instance for T. This in effect allows the tweaking of the mapping I described above: if the user overrides the mapping for int, then int list will effectively be changed to, viz it will use the overridden int Arbitrary. But it causes confusion because it's pretty easy to accidentally call the generator for the type you're defining a mapping for, which leads to an infinite loop.
• There is no method like FsList(Arbitrary<'a>) to parametrize the list generator in a more explicit way. So even if users would want to use the explicit style explained above to define Arbitrary instances, if they want to change any of the Arbitrary instances globally, they'll need to redefine that Arbitrary from scratch.
• It's harder (but not impossible) to split the file in multiple more coherent pieces.

Some ways to take this forward

• Option 1: do away with the mapping altogether. Users have to write Prop.forAll explicitly and pass in the Arbitrary instances to use. The problem with this is that it makes reflective Arbitrary instance derivation based on the type impossible - some map somewhere from type to Arbitrary is clearly necessary to do that. One can use a method like the current Arb.Default.Derive<'T>() which may take some configuration parameters - e.g. it can take the map to use explicitly, and throw like it does now when it can't derive an instance reflectively and it's not in the given map.
• Option 2: we have a mapping but it's immutable. I.e. basically like we have now but Arb.register does not exist. This makes tweaking or extending the map impossible, but this can be remediated by basically separating the mapping and the API in Arb.Default. I.e. if we parameterize all the methods on Arb.Default to take the Arbitrary instances they need, instead of relying on Arb.from<'T> and such, including Arb.Default.Derive, it's still possible to tweak and extend the reflective Arbitrary generation in Arb.Default.Derive. But the mapping can't be extended outside of FsCheck itself. I.e. it becomes harder to support extenal libraries that have Arbitrary instances for new types out of the box - these would always have to be used explicitly. Not that this is actually happening now, but it's worth mentioning.
• Option 3: we have a mapping but it's append-only. I.e. you can only add new types. Trying to override an existing type in the mapping throws. Similar limitation re:tweaking Arbitrary instances as option 2, but this does allow extending the mapping. And I don't think it has any of the downsides mentioned above, because you'd see clear error messages when anything untoward happens.
• Option 4: we have a mutable mapping but it's not global, but passed around while building the Property (so likely via the Gen computation expression somehow). So it's like a state monad really, the mapping is passed around functionally but implicitly. The default mapping could be set in Config.
• Option 5: we have a global, one-time mutable mapping that is defined and fixed at static initialization time, e.g. when the first test in an assembly is run. We could implement this by scanning the test assembly for places where mappings are defined (somehow, e.g. types attributed with a FsCheck defined attribute) and then building the map before the first test is run. It is impossible to change or affect any other way.

API for defining the map

Given the above, it seems unavoidable to have a map somewhere (unless you want to try and argue to throw out reflective Arbitrary derivation. That is a very hard sell.) so the question comes up on how to define the mapping from type T to Arbitrary of T. Note that it must be some place that allows to bring new type parameters in scope, to allow for the definition of Arbitrary instances for generic types. Again, a few options:

• static methods (as now) - can get the mapping by calling something like ArbMapping.Derive<ArbType>()
• instance methods (has the slight advantage that the Arbitrary instance for a set of instance methods can be parametrized by values, i.e. mapping is derived by ArbMapping.Derive(new ArbType(...parameters...))
• types that derive from Arbitrary<T>, mapping derived by ArbMapping.Derive(new Int32Arb(), new CharArb(),...) and to be anywhere near convenient we'd need to have some way to scan an assembly for these types as well.

Thanks for reading this far....

[Rattenkrieg]

Actually I'm not expierencing any issues with custom arbs, but if I have to vote for something I'd pick option 4.
.... or maybe five...

[0x53A]

Different unit tests should not interfere with each other, so my vote is against any static global state.

I would like to have the ability for a scoped Arb registration.

So my preference would be

• a core context which contains all the base Arbs (int, strings, ...) and autogenerated Arbs (tuples, lists, ...)
• a way to either create a new context, or update a contaxt.
• contexts should be immutable, so any update creates a new context (basically ImmutableDictionary)

So from a user perspective, I would like to write either

Prop.forAll(fun a -> ...)

which just uses the default context, or

let myArbContext = ArbContext.Core.Add(myCustomArb)
Prop.forAll(myArbContext , fun a -> ...)

where I create a custom isolated context and pass that through.

With the context being just a normal variable, they can be shared, created in helper methods, ...
It should also be possible to replace Arbs, so I should be able to write ArbContext.Core.Add(myIntArb).

It may also make sense to differentiate between an immutable Core context, and a mutable Default context (well, a mutable binding, the context itself would still be immutable).

The Core context is everything included by default in FsCheck.

The Default context defaults to the Core context, but if all my tests use the same Arbs anyway, then I could overwrite the Default context once, and all calls that do not explicitly pass a different context will use that.

Your assembly-scanning strategy also looks usefull, so there could be a helper method which creates a Context from an Assembly:

ArbContext.Default <- ArbContext.FromAssembly(Assembly.GetCurrentAssembly)
// or
ArbContext.Default <- ArbContext.FromAllCurrentlyLoadedAssemblies()

---

This is basically your option 4), but with an immutable context instead of a mutable one.

[kurtschelfthout]

This is basically your option 4), but with an immutable context instead of a mutable one.

Yes, it's basically what I meant. the "mutable" there applies to the conceptual mapping: there is some way to change the mapping. In all cases I'd store the mapping in a persistent, "immmutable" data structure. I apologize, in hindsight I chose confusing terminology :)

[cmeeren]

My two cents:

I have these main "problems" with the current Arb stuff:

• If I define custom types (e.g. NonNegativeInt) but forget to register an Arb for them, there are no compiler errors. Not a huge problem - it's usually clear why the test fails - but it's annoying.
• Using XUnit and the R# test runner (and possibly others?), there's nowhere to call Arb.Register. Also not a huge problem, I just use the Arbitrary parameter in PropertiesAttribute.

The thing I like best about the current implementation is that it allows my test methods to take simple parameters like NonNegativeInt i and then just use them directly in the test. I cannot understate how much this cleanliness means to me; I'd be really loathe to use Prop.forAll syntax in every test that required custom Arbs (quite a lot of them) - I would probably look for another test framework if that were the case.

The reason for this is that, like all others, I'm not paid to write and maintain tests; I'm paid to deliver code I'm confident in. FsCheck allows me to write really simple and thorough tests with almost no boilerplate at all, and I'm willing to forgo a bit of type safety in the tests for that benefit. If a really simple test fails due to a bug in the test (e.g. a missing Arb registration), it usually doesn't take me very long to figure that out.

As for your suggestions: I really like the idea of one-time, implicit registrations (option 5?). You just define mappings somewhere in your assembly, and the types you map can then be used directly as test parameters. It seems to me there's really nothing you can't do with this - if you have any type with an existing mapping and you want slightly different behavior, just wrap it in a singe-case DU and create a mapper for that with the desired behavior. Really simple to use, robust under all test runners (I assume?), and if it's append-only, there's no unexpected results from globally overriding Arbs for primitive types. Again, you get no compiler errors if you forget to create a mapper, but now we're not talking about registration, we're talking about defining a mapper in the first place, so it's even less of a problem.

[kurtschelfthout]

As for your suggestions: I really like the idea of one-time, implicit registrations (option 5?). You just define mappings somewhere in your assembly, and the types you map can then be used directly as test parameters. It seems to me there's really nothing you can't do with this

There is one thing - you can't "tweak" the mapping for an existing type in more than one way in your test assembly. For example, say you want non-null strings in test class Foo, and possibly null but ASCII chars only strings in test class Bar, both in the same assembly. Assuming you have more complex types that contain these two kinds of strings, for one set you'd have to re-define the Arbitrary instances from scratch.

[ploeh]

It is possible to make a working FsCheck without any mapping at all.

I think it'd be a good idea to do this. This will have an impact on usability, so I don't suggest that this should stand alone, but creating a 'core' of FsCheck that works like that would, ACAICT, enable us (and third parties) to evolve a 'usability layer' on top of the core engine.

FsCheck could still ship with a default Arbitrary mapping, but with enough of the core exposed to enable other people to do things differently.

I'm not saying that I want to have things radically different; I only have an intuition that separating concerns like this would lead to a better architecture overall.

Should it be global? ThreadLocal? AsyncLocal? SomethingElseLocal?

It should be immutable, and the context should be explicit. It's just a map. If you want to change it, pass it as an argument to a function.

---

As the options go, I'd prefer a combination where option 1 is the core of FsCheck, but with option 4 on top of it. I'm not sure why you write 'mutable mapping', though... Is that a typo? Shouldn't it be immutable mapping?

Option 5 seems debilitating, because you'd only be able to change FsCheck once for an entire test run. This implies to me that it would be impossible to run two different test cases with different configurations.

---

Regarding an API for mappings, I'd suggest to do away with the type class emulation. The way .NET works, it adds overhead, but no type safety.

The map itself could be defined purely in terms of functions. The map'd be something like Type -> Arbitrary option. The problem is that at the bottom level of Reflection, things aren't generic. In order to create a generic value (like, say, Arbitrary<Foo>), you need some sort of run-time conversion. This, again, implies to me some sort of option-based API.

If we want to be able to scan a type (or assembly) for custom definitions, I think that we should define a proper .NET interface, so that users at least get a bit of type-safety: Implement this interface, and you can register your custom Arbitrary. If you do it wrong, then your code doesn't compile.

[kurtschelfthout]

FsCheck could still ship with a default Arbitrary mapping, but with enough of the core exposed to enable other people to do things differently.

I agree, but then I am surprised you seemed to disagree with adding methods with parameters in Arbitrary.Default to make it possible to generate a list of positive integers like Arb.Default.ListOf(Arb.Default.PositiveInt)) in #390. I think that is the major API that is missing today, which makes the explicit style unnecessarily hard. But perhaps I misunderstood your objection.

Would also be interested to know if you see any other roadblocks to making the explicit style possible.

I'm not sure why you write 'mutable mapping', though... Is that a typo? Shouldn't it be immutable mapping?

I realize (now) this is confusing terminology, but I meant users can change the mapping - add keys, update keys (maybe remove keys but seems unnecessary in this case) while tests are being executed. I didn't mean it in terms of the data structure that holds the mapping. The data structure would still be a so-called immutable data structure, as it actually is now. There is now a ThreadLocal reference that holds the "canonical" current reference to the mapping.

The map itself could be defined purely in terms of functions. The map'd be something like Type -> Arbitrary option. The problem is that at the bottom level of Reflection, things aren't generic. In order to create a generic value (like, say, Arbitrary), you need some sort of run-time conversion. This, again, implies to me some sort of option-based API.

Not sure I understand. Let's make a small example to focus on the issues.

Say I'd like to add arbitrary instances to the mapping for byte, int, list<'a>. The Arbitrary instance for list<'a> should be generic - i.e. it shouldn't matter what the 'a is.

Then, given a mapping, I would like to then be able to lookup Arbitrary instances for byte, int, list<int>, and list<list<byte>>.

How would that look?

[ploeh]

A mapping like that... At the lowest level, I don't see you could do better than a Map<Type, obj> or similar... After pulling the object out of the map, you'd need to cast it to a particular Arbitrary<'a>.

That's what I meant. A map like that is conceptually identical to a function from the key to the value, but since the key could be missing, you need to map the key to an option of a value... If using a Map, you'd need to use Map.tryFind...

Type values can contain open generics, so you could have one entry for list<>... This does, however, add the extra spice that typeof<list<>> is not equal to, say, typeof<list<int>>. So perhaps one rather needs something like Map.tryPick...

[kurtschelfthout]

At the lowest level yes it's that kind of map. But that's not so interesting for this discussion, at least from my perspective What would it look like for the user? Would you get them to write the tryPick themselves, for example?

[charlesroddie]

Is there currently a good way to avoid Arbitrary use when testing? I don't like using Arbitrary for the reasons in the OP.
For example can you do

[<Test>]
let distributiveTest() =
    gen{
        let! a = intGen
        let! b = intGen
        let! c = intGen
        return (a+b)*c = a*c+b*c
    } |> Gen.Assert

, where Gen.Assert: Gen<bool> -> unit? Does Gen.Assert or something like it exist, or can it be created easily?

[cmeeren]

@charlesroddie I know this is kind of a non-answer, but you could try Hedgehog (integrated shrinking) and Hedgehog.Experimental (auto-generation support for arbitrary types - not really experimental anymore).

[charlesroddie]

Thanks for this @cmeeren . We could move to Hedgehog just to get access to a Gen<bool> -> unit.
In Hedgehog this can be defined by:

let forAll (g:Gen<bool>) = Property.forAll g Property.ofBool |> Property.check

[kurtschelfthout]

I'm confused. Defining that function in FsCheck is easy enough:

let forAll (g:Gen<bool>) = Check.QuickThrowOnFailure g

This thread is about derivation of Arbitrary instances based on type, and how to modify/configure that mapping. I'm not sure how that and your question relate.

[charlesroddie]

Thanks @kurtschelfthout . I'm new to fscheck, just started using it this morning and didn't see that function.

[kurtschelfthout]

No worries. The advantage of using hedgehog for things like this is that it would automatically derive shrinkers together with defining the generator, whereas in FsCheck you'll lose the shrink capabilities if you use gen, or you'll have to write the shrinker separately, and then package them together into an Arbitrary.

Merging generating and shrinking better in one API is "planned" for FsCheck v3 but my free time has been limited for a long time now. On the other hand experimental v3 is available now, and while it doesn't give you this it does give you multithreaded and async testing and associated speedups.

[kurtschelfthout]

With #547 merged to fscheck3 branch I'm closing this issue. Essentially I went with option 4 from the OP; so far I am happy with it, and besides some polishing and smaller changes it looks like a keeper. What's nice about it is that nothing stops us from adding convention-based registration like ideas in #334 and option 5 later on.