Mighty morphing power strategies

The Hypothesis API is a bit of a bizarre sleight of hand. It pretends to be very clean and simple, but that’s mostly a distraction to stop you thinking too hard about it. Everything looks easy, so you aren’t surprised when it just works, and you don’t think too hard and realise that what it just did should actually have been impossible.

Take for example this piece of code using the Django integration (this comes straight from the docs):

from hypothesis.strategies import lists, just
def generate_with_shops(company):
  return lists(models(Shop, company=just(company))).map(lambda _: company)
company_with_shops_strategy = models(Company).flatmap(generate_with_shops)

We take a strategy that generates a model inserted into the database, then use flatmap to create a strategy for children of that and bind that in. Everything just works neatly and everything will simplify just fine – the list of children can be simplified, both by throwing away children and simplifying individual children, the original element can be simplifies, everything lives in the database, all is good with the world. Examples will be persisted into the Hypothesis example database as normal. Everything works great, no reason to think twice about it.

Except it is completely ridiculous that this works, and it’s certainly unique to Hypothesis. No other Quickcheck has anything like it.

Some of this is just the magic of Hypothesis templating at work. There’s a lot more information available than is present in the end result, and this also explains how you can mutate the value by adding children to it and have simplification still work, etc.

But there’s something that should make you very suspicious going on here: We cannot create the strategy we need to generate the children until we have already performed some side effects (i.e. put some things in the database). What could the template for this possibly be?

The answer to this is quite bad. But it’s quite bad and hidden behind another abstraction layer!

The answer is that we have a type called Morpher. As far as we are concerned for now, a Morpher has one method called “become”. You call my_morpher.become(my_strategy) and you get a value that could have been drawn from my_strategy.

You can think of Morphers as starting out as a reproducible way of getting examples from strategies, but there’s more to it than that, for one very important reason: A Morpher can be simplified and serialized.

This gives us a very easy implementation of flatmap:

def flatmap(self, f):
    return builds(lambda s, m: m.become(f(s)), self, morphers())

i.e. we generate an element of the strategy, apply f to it to get a new strategy, and then tell the morpher to become an instance of that. Easy!

Easy, that is, except for the fact that it still looks completely impossible, because we’re no closer to understanding how morphers work.

I’m not going to explain how they work in too much detail, because the details are still in flux, but I’ll sketch out how the magic works and if you want the gory details you can check the code.

As it starts out, a Morpher is simple: It contains a random seed for a parameter value and a template value, and become() just draws parameters and templates with those standard seeds and then reifies the result.

This would achieve all of the desired results except for simplification: You can save the seeds and you can now generate.

So how do we simplify? Noting that each time we may have to become a different strategy and that templates are not compatible between strategies.

There is a two part trick to this:

  1. The template for a Morpher (which is actually the Morpher itself) is secretly mutable (actually quite a lot of Hypothesis template strategies are mutable). When we call become() on a Morpher, the strategy used is stored on the template for later so we have access to it when we want to simplify, as is the template that was produced in the course of the become() call.
  2. As well as storing a random seed we also store a list of serialized representations of possible templates. These are the representations that would be used when saving in the database. The reason for this is that the Hypothesis database has the following really helpful invariant: Any serialized representation can either be turned into a valid template for the strategy or rejected as invalid. Moreover the representations are quite straightforward, so usually similar strategies will have compatible representations.
  3. When we wish to become a strategy, we first try our serialized representations in order to see if one of them produces a valid template. If it does, we use that template, otherwise if we reach the end we generate a fresh one using the random seed method mentioned above.
  4. When we simplify, we try to simplify the last template generated with the last strategy used, and then replace the representation that generated that strategy with the simplified form of it, thus generating a new morpher with the same seed and parameter but a simplified serialized representation.

If you’re reading that thinking that it’s horrifying, you’re not wrong. It’s also quite fragile – there are definitely some corner cases of it that I haven’t quite shaken out yet, and it’s why flatmap is somewhat slower and buggier than things using more normal methods of generation.

But it’s also really powerful, because you can use this technology for things other than flatmap. I originally intended it as a shared implementation between flatmap and the stateful testing, although for various reasons I haven’t got around to rebuilding the stateful testing on top of it yet. It’s also what powers a really new cool new feature I released today (I know I said I wasn’t doing new features, but I couldn’t resist and it only took me an hour), which is essentially a form of do notation for Hypothesis strategies (only more pythonic).

def list_and_sample(draw, elements):
    values = draw(lists(elements, min_size=1))
    redraw = draw(lists(sampled_from(values)))
    return (values, redraw)

list_and_sample(integers) now gives you a strategy which draws a list of at least one integer, then draws another sample from that list (with replacement)

What this does is give you a magic “draw” function that produces examples from a strategy, and composes these all together into a single strategy built on repeatedly calling that draw function as many times as you like.

This is also black magic, but it’s not novel black magic: It’s just morphers again. We generate an infinite stream of morphers, then map a function over it. draw maintains a counter, and the nth time you call it it gets the nth element from the stream and tell it to become the strategy that you’ve just passed in. There’s a bit more fiddling and details to work out in terms of making everything line up right, but that’s more or less it. We’ve vastly simplified the definition of strategies that you would previously have used an ugly chain of lambdas and flatmaps to build up.

If you want to read more about this feature, I commend you to the documentation. It’s available in the latest release (1.11.0), so have fun playing with it.

This entry was posted in Hypothesis, Python on by .

The two voices of progress

There are two voices in my head.

Both are just my inner monologue of course. But sometimes it speaks with one voice, sometimes another.

One voice says: Here’s how you can make this happen.

The other says: Here’s what will happen if you do that.

Historically I often described the former as the software developer’s role and the latter as the ops role. I think the reality is that everyone needs both, and not just because we’re all devops now.

There are many ways to fail to make progress, but ultimately all of them come down to hitting some sort of obstacle and failing to be able to get past it.

Sometimes the obstacle is a creative block: You could get past it if you just had the right solution. Other times it’s a foresight block: You needed to plan for this six months ago, and if you didn’t there’s actually not much you can do here. Different voices tell you how to overcome different obstacles.

I think most people are predisposed to listen to and value one voice over the other. Certainly historically I’ve been much more of a “here’s how you can make this happen” type of person, and have gradually learned that the other voice has useful contributions that would have prevented this debacle we’ve found ourselves in if I’d only listened to the other one.

But you don’t have to be good at listening to both voices when they’re inside your head, because the voices come from outside your head too: Your team mates.

The problem comes not when you’re not good at thinking in both ways, the problem comes when you discount what people who are good at thinking in the way that you’re not are saying as unimportant.

This is probably familiar to anyone who has tried to be the voice of reason in the room: A bunch of cowboys dismiss your concerns as probably not very important in practice and how likely is that to happen? Lets be pragmatic here.

My impression is that right now the tech industry is heavily biased towards the “lets make it work” voice, as exemplified by the “move fast and break things” attitude, but it goes the other way too. When you see everything constantly being broken around you it’s tempting to think that if only everyone would just listen to you everything would be great.

I think this is a mistake too. The danger of being too far on the predictive side is that it prevents you from experimenting. It also tends to produce a sort of analysis paralysis: Many ideas that have proven to be very successful would never have been started if their creators had realised how much work they were going to be.

I think in many ways the optimal way to do progress is to have the two voices handing off to each other. Experiment, then stabilize, then repeat. Skip the experiment step and you don’t get anywhere, skip the stabilize step and you get somewhere you didn’t want to be.

It seems very hard to get these two approaches in balance. I’d like to fix that. I’m not sure how to make it happen, but I’m pretty sure that what will happen if we do is pretty great.

This entry was posted in Uncategorized on by .

Apparently I’m still doing this fanfic thing

After a discussion on Twitter about the mechanics of wishing (a niche interest of mine, and apparently of others) I somehow ended up being talked into / talking myself into writing some fanfic of Disney’s Aladdin.

Yeah, I know.

I keep thinking “It’s completely impossible to write this becauseĀ  once (event happens) then (character) has too much power and you just can’t construct a plot around that” and then I come up with a great solution to that problem and I come up with a scene around that and then I write that scene.

The result is that it’s not really a whole fiction so much as a set of isolated scenes that probably make sense if you’ve seen the movie and definitely don’t if you haven’t. There will almost certainly be a certain amount of backfilling and it may eventually turn into a complete story in its own right.

Current features:

  1. The Genie features a very large number of rules, which are dynamically altered as people try to work around them. WIshing is powerful but you simply can’t bootstrap into godhood with it. Mostly because every time I think of a way of bootstrapping into godhood I write a scene in where someone tries to do that and then the rules are added to in a way that prevents it.
  2. Everyone who gets their hand on the lamp (and it’s not just Aladdin and Jafar) is severely clued in and makes intelligent use of their wishes.
  3. Jasmine is a character with a great deal of agency and does not do the whole “I’m not just a prize to be won!” thing followed by having all her agency taken away and acting as a prize to be won in a fight between two men.
  4. Jasmine is scary. Don’t mess with her. You’ll regret it.

If that sounds appealing, here’s the work in progress.

This entry was posted in Uncategorized on by .

Notes on London flat hunting

So I’ve decided to move back to London, and yesterday I started hunting for a flat to rent. About four hours later I put down a holding deposit on a flat (ok, sort of a flat, it’s really more of a bedsit, but that’s actually what I’m looking for right now – a 6 month ish tolerable environment for as little money as I can get away with in London).

Apparently this is surprising behaviour and not at all what people are used to with the experience of London flat hunting. And there’s absolutely no doubt that I got lucky. But some of it is also that I’ve learned the tricks, and some of it is that I have flexibility available to me to solve the problem.

So I thought I’d put together some notes on what I’ve found helps in looking for a London flat.

Note that I’m very far from an expert on this (I have successfully done this three times, plus an additional two that don’t count, plus this one which I’m not counting as a success until I move in). So these are very much intended as descriptive rather than normative rules. They seem to be what I do that works. You may wish to emulate them.

Rule one: You have no time, you have no bargaining power. When you see the flat, if you want it you say “Yes I’ll take it. Show me the paperwork” right there and then. If you say “let me think about it” or “yes but” then you have said no. It is completely OK to say no and if it’s a shitty flat then you should of course do that, but London flats move so quickly that you don’t get to say yes conditionally. If you’re not walking away having put down a holding deposit you’re walking away from the flat.

And yes, this is terrible. It’s a large part of why the London housing situation is so bad. But as a renter there’s not much you can do about it.

Rule two: Flexibility about time and money will get you far. I can’t currently demonstrate a convincing income stream but I can pay for multiple months up front. This opens a lot of doors that would otherwise be closed to me. Flexibility about move-in dates is also a big deal: If you can say “I can move in at any date within this fairly large range” a lot more flats are open to you.

Obviously this rule is the very definition of financial privilege. Sorry.

Rule three: If it’s been on the market more than 24 hours it’s gone. Don’t bother. If you call up about it the letting agent will be all “sorry it’s gone but we do have this remarkably similar flat that costs about 50% more. Are you interested?”.

Rule four: Be specific about your requirements, turn them into a rightmove search (remember the 24 hours thing! You can filter by that). Look through the listings, turn on instant (not daily!) alerts for this search. You will get very used to calling up letting agents and saying “Hi I’m calling about a listing on rightmove and would like to check if it’s still available and arrange a viewing if it is”. They will often try to talk you into seeing other properties and you should let them.

Rule five: “I can do a viewing as soon as possible. Like, literally right now if you’re available. It will take me X minutes to get there. OK, so you’ve suggested a viewing at Y, can you maybe do a little earlier?”. Remember rule one: This is a race. If people are viewing before you then you’ve got a very good chance of losing the flat if it’s actually good.

Rule six: Make sure you have a hard upper bound on your monthly rent in mind because if you talk to letting agents they will try to talk you up. “I know you’ve said you’re only in the market for $X / month but I have this great flat for only $X + 200 / month. Would you like to take a look?”. It is OK to lie to letting agents about your upper bound and claim it is lower than it actually is in order to take advantage of this process.

I think that’s mostly it. It’s a shitty process and you have to be super aggressive about it, but it does seem to work.

This entry was posted in Uncategorized on by .

Hypothesis 1.10.2 and 1.10.3 are out

Two small bug fix releases. I released one and then immediately found and fixed some unrelated problems, so two patch release for the price of one.

Changelog entries:

  • lists(elements, unique_by=some_function, min_size=n) would have raised a ValidationError if n > Settings.default.average_list_length because it would have wanted to use an average list length shorter than the minimum size of the list, which is impossible. Now it instead defaults to twice the minimum size in these circumstances.
  • basic() strategy would have only ever produced at most ten distinct values per run of the test (which is bad if you e.g. have it inside a list). This was obviously silly. It will now produce a much better distribution of data, both duplicated and non duplicated.
  • star imports from hypothesis should now work correctly.
  • example quality for examples using flatmap will be better, as the way it had previously been implemented was causing problems where Hypothesis was erroneously labelling some examples as being duplicates.
This entry was posted in Hypothesis, Python on by .