Hypothesis: Ideas for new numpy strategies

[rsokl]

Hey all, I have written a few numpy-centric search strategies that have proven to be quite useful in my MyGrad development as well as in some of my research projects. I figured it might be fruitful for us to chat about these and whether they would serve hypothesis.extra.numpy well!

I will include links to my current implementations of these strategies in case you are interested in what these look like under the hood presently.

broadcastable_shape

Given an array-shape, generate broadcast-compatible shape. The user can constrain the length of the resulting shape. Examples from this strategy shrink towards the original input shape. (This may be useful for @rdturnermtl 's work on gufunc-strategies in #1784)

Example:

>>> [broadcastable_shape((3, 2)).example() for i in range(4)]
    [(), (2,), (1,), (1, 3, 1)]

slice_index

Generate a slice index for and array axis of a given size. The user can control the possible start, stop, and step values. Examples from this strategy shrink towards slice(0, 0, 1). Examples are selected so that they seldom yield empty sequences. (this probably does not belong in extra.numpy, but it is needed for the next strategy..)

Example:

>>> [slice_index(4).example() for i in range(4)]
[slice(0, None, -1),
 slice(None, None, 2),
 slice(None, None, -1),
 slice(None, 2, 2)]

basic_index:

Given an array's shape, generates valid indices for that array that conform to the basic indexing (i.e. no-copy indexing) specification. Examples from this strategy shrink from indices that produce high-dimensional views of the input array, down to indices that select a single element from the array.
Example:

>>> [basic_index((3, 2)).example() for i in range(4)]
[(-3, 1),
 (-1, slice(None, None, 1)),
 (slice(2, -2, -2), None, 1),
 (slice(0, None, -1), slice(None, None, -1))]

advanced_integer_index

Given an array's shape, generate valid indices that conform to the advanced integer indexing (i.e. copy-indexing) specification. The user controls the min/max side/dim of the array that would be produced by the index. Examples from this strategy shrink towards the index: len(shape) * (np.array([0]), )

Example:

>>> [adv_integer_index((3, 2), max_dims=1).example() for i in range(4)]
[(array([0]), array([0])),
 (array([1]), array([-2])),
 (array([-3, -3]), array([ 0, -1])),
 (array([ 2, -1]), array([1, 0]))]

valid_axes

Given an array of a given dimensionality, generates valid arguments to numpy sequential functions that accept and axis or axes argument. This is still a work in progress.

Example:

>>> [valid_axes(3).example() for i in range(4)]
[(1, 2), (-2, 2), (-3, 2), (-1, -3, -2)]

Please excuse the long post! I look forward to discussing if these might have a place in Hypothesis proper. I hope that this is a constructive way to start this conversation; if it is not, I am happy to refactor this.

[Zac-HD]

Hi Ryan - this is a fantastic way to start, and an exciting proposal!

My immediate reaction is that I would love to have these strategies as part of Hypothesis' Numpy extra. Practically speaking, there are a couple of considerations:

• We like small pull requests, which are much easier to review. Personally I'd start one for slice_index and basic_index, and talk to @rdturnermtl (also Ryan...) about how the broadcast-related strategies might work together.
• If possible, it's faster to return a strategy from an ordinary function than to use @composite, because you don't have to pay the cost of validating arguments for every example you draw.
• Check out our dev guides, especially on API style. The most relevant part is probably that we try to validate input much more tightly than Numpy does, and we're OK with disallowing things that would work to simplify the mental model (and to a lesser extent the validation logic).
• I'd probably remove most of the arguments to slice_index, on the basis that with that much customization I'd rather just point users at builds or @composite. Minimalism is also easier to keep backwards-compatible if we want to change the args later!
• For discussion: deprecating "or a strategy for" option for the shape and dtype argument to arrays, and explicitly encourage use of @composite or .flatmap instead. Fixed shapes would be more consistent with all the other strategies we're looking at!

[Zac-HD]

The other thing is that @DRMacIver and I have both been impressed by what you've been doing with Hypothesis and Numpy in MyGrad, and we'd love to do some more work together. To that end:

How would you like to join the Hypothesis maintainers team?

Accepting doesn't imply any obligation - you can dip in and out (or just out) as suits you; for an all-volunteer project supporting each other to not do things can be the most important part. In practice accepting just means that you can approve and merge pull requests (except your own), cancel or restart most CI jobs, and get extra credibility in design discussions matching whatever work you put in.

[rsokl]

Thank you for taking the time to review this proposal and for the valuable feedback. I will start working on slice_index and basic_index. In the meantime I will use this thread to ask questions as they come up.

I would be very happy to join the Hypothesis maintainers team! It is heartening to know that you and @DRMacIver like what I have been doing with MyGrad. I'm excited to serve the team and to leverage my background where I can, and I certainly look forward to working with all of you.

Thanks again!

[Zac-HD]

Tracking update:

• #1852 added valid_tuple_axes() to the Numpy extra
• #1878 adds broadcastable_shapes (approved but not yet merged)

With the PyCon sprints coming up, I'm going to open an independent issue for a slices(sequence_size) strategy, since I think that can be general rather than numpy-specific. Note that it's missing all but the one mandatory argument - as a compatibility thing it's much easier to add them later, and since the fine controls seem little used I'd rather push people to builds() rather than complicate things for ourselves.

---

API design notes: I think advanced_integer_indexes() should only take two arguments: the shape of the input array, and the shape of the output array. I'm tempted to say "a strategy for output shapes", but not quite sure... either way, this can be implemented without @composite and quite efficient.

Similarly, I'd substantially simplify the API of basic_indexes(shape), at least initially - taking only the single argument for shape. The simple implementation is then return tuples(*map(slices, shape)), and it'll shrink towards selecting only the first element of the array!

In all cases I'd be open to expanding the argspec for these strategies later, but I'd prefer to get them out into the wild and see if anyone asks for the additional features before committing to maintain them.

[rsokl]

@Zac-HD these all sound like good ideas to me. I especially like your insights for advanced_integer_indexes. I have been working on that strategy, and I was finding it to be too convoluted and ambitious with all of its options.

Regarding basic_indexes, it should be noted that a basic index is a bit more general than being a tuple of slices. Most importantly, there can be a mix of integers and slices. Additionally numpy.newaxis (i.e. None), and Ellipsis are also permitted. These last two items are the biggest nuisances to deal with - especially newaxis which can be stuck absolutely anywhere. I would be happy to leave those two out for now.

[Zac-HD]

I'm glad my idea makes sense to you too!

Re: basic indexing, of course it can be more complicated than that - but a tuple of (integers-or-) slices is a good place to start.

IMO we should deliberately leave newaxis out of this strategy, or possibly have an allow_newaxis=False argument to support it - increasing the dimensionality of data while taking a subset is at least unintuitive to me!

My first instinct for Ellipsis was to omit it, and I still think that's a good place to start - we can add it as an enhancement in a later version. The larger picture there is the trade-off between larger arrays (bad for shrinking - maybe ensure that Ellipsis applies to at most two dimensions?) but still putting it in some to expose code which assumes that e.g. the result of indexing has the same number of dimensions as the tuple of indexes.

(so... should the advanced index strategy also support basic indexes or Ellipsis for some dimensions? Hmm.)

[rsokl]

We are definitely on the same page regarding newaxis and Ellipsis. My instinct would probably start off with excluding both of them from the implementation. I just wanted to make sure integers would be included along with the slices.

Regarding the advanced index strategy, I specifically brand it as "advanced integer indexing" to avoid the muddle of including advanced boolean indexing as well as mixed basic-advanced indexing. For therein lies madness.

Boolean indexing might make for nice low-hanging fruit for a newcomer, although it may be too trivial to include in extra.numpy. It basically is an alias for: nps.arrays(shape, dtype=bool).

The mixed-style is simply too hellish in my mind. Potentially shrinking from copy-on-indexing to view-on-indexing seems like we are basically writing bugs in peoples' tests for them 👿

[Zac-HD]

Yep, that all sounds good to me. Simple and non-mixy strategies are a good default!

IMO boolean indexing is so easy to implement that we should make end-users do it, and just document the pattern.

[Zac-HD]

Closing this meta-issue, as I've opened a more specific issue for each remaining strategy incorporating our conversation here. Super excited by the improvements to our Numpy support - thanks again @rsokl!