DRMacIver

So with the caveat that I'm not super familiar with Validity...

The biggest thing that leaps out at me looking at it is that Hegel is very built around flexible user-specified data generation (using the library's base generators and combinators) mixed freely with test execution. Validity in contrast looks extremely type-based, which is convenient when you're only testing fairly general properties of built-in types, but I've never found flexible enough to be a really good basis for property-based testing once your testing needs get even a bit more complicated. e.g. a lot of tests want some sort of upper and lower bounds on their numbers, and I don't want to define a type for each.

For an only slightly more involved example of this, suppose you've got, say, a Project type, and Projects have an owner that is a User. You might want a test that is about a single user that has some number of projects. In a generator-based approach, this is easy: You just generate a User object, then you generate a bunch of Project objects that have to have that User as their owner. Just works.

In contrast, in a type based approach, there's basically no way to express this without e.g. defining a new ProjectsOwnedByASingleUser type and defining what it means to be a valid instance of that type... It's a lot of machinery for what is IMO a strictly worse user experience.

They're random but with a lot of tweaks to the distribution that makes weird edge cases pop up with fairly high probability, and with some degree of internal mutation, followed by shrinking to turn them into nice tidy test cases. In Python we do a little bit of code analysis to find interesting constants, but Hegel doesn't do that, it's just tuned to common edge cases.

I think all the examples I had in the post are typically found in the first 100 test cases and reliably found in the first 1000, but I wouldn't swear that that's the case without double checking.

We don't do any coverage-guidance in Hegel or Hypothesis, because for unit testing style workflows it's rarely worth it - it's very hard to do good coverage guidance in under like... 10k test runs at a minimum, 100k is more likely. You don't have enough time to get really good at exploring the state space, and you haven't hit the point where pure random testing has exhausted itself enough that you have to do something smarter to win.

It's been a long-standing desire of mine to figure out a way to use coverage to do better even on short runs, and there are some kinda neat things you can do with it, but we've not found anything really compelling.

Yeah, that's true. I was going to say that it's maybe not fair to count things that just don't even make sense in Rust, but I guess the logical analogue is something like `Box<dyn MyTrait>` which it would make sense to have a default generator for but also we're totally not going to support that.

To all you amateur Hegel enthusiasts out there: there is no synthesis in Hegel.

Looks like the mods deleted the last long thread about this, so best not to relitigate, but short version: Yes, we know. We liked the name and thought it was funny so we kept it.

Otherwise: Congratulations on the QuickCheck-style testing in Rust. At work, I’m always surprised that property-based testing is so little known and so rarely used outside of functional programming.

Actually, it's Hypothesis-style testing in Rust. There was already QuickCheck style.

Property-based testing is in fact far more widely used in Python than in functional programming (probably not as a percentage of users, but in terms of raw numbers), which I'm always surprised that the functional programming community seems mostly unaware of.

You're very welcome! I'm glad it's been useful for you.

Ugh, yeah. Duplicating the code under test is a bad habit that Claude has had when writing property-based tests from very early on and has never completely gone away.

Hmm now that you mention it we should add some instructions not to do that in the hegel-skill, though oddly I've not seen it doing it so far.

What do you think we're currently missing that Python's `from_type` has? I actually think the auto-deriving stuff we currently have in Rust is as good or better than from_type (e.g. it gets you the builder methods, has support for enums), but I've never been a heavy from_type user.

Please let us know how it goes!

As Liam says, the derive generator is not very well dogfooded at present. The claude skill is a bit better, but we've only been through a few iterations of using it and getting Claude to improve it, and porting from proptest is one of the less well tested areas (because we don't use proptest much ourselves).

I expect all of this works, but I'd like to know ways that it works less well than it could. Or, you know, to bask in the glow of praise of it working perfectly if that turns out to be an option.

Answered this over here: https://news.ycombinator.com/item?id=47506274

The short answer to how it fits into existing ecosystems is... in competition I suppose. We've got a lot of respect for the people working on these libraries, but we think the Hypothesis-based approach is better than the various approaches people have adopted. I don't love that the natural languages for us to start with are ones where there are already pretty good property-based testing libraries whose toes we're stepping on, but it ended up being the right choice because those are the languages people care about writing correct software in, and also the ones we most want the tools in ourselves!

I think right now if you're a happy proptest user it's probably not clear that you should switch to Hegel. I'd love to hear about people trying, but I can't hand on my heart say that it's clearly the correct thing for you to do given its early state, even though I believe it will eventually be.

But roughly the things that I think are clearly better about the Hegel approach and why it might be worth trying Hegel if you're starting greenfield are:

* Much better generator language than proptest (I really dislike proptest's choices here. This is partly personal aesthetic preferences, but I do think the explicitly constructed generators work better as an approach and I think this has been borne out in Hypothesis). Hegel has a lot of flexible tooling for generating the data you want.

* Hegel gets you great shrinking out of the box which always respects the validity requirements of your data. If you've written a generator to always ensure something is true, that should also be true of your shrunk data. This is... only kindof true in proptest at best. It's not got quite as many footguns in this space as original quickcheck and its purely type-based shrinking, but you will often end up having to make a choice between shrinking that produces good results and shrinking that you're sure will give you valid data.

* Hegel's test replay is much better than seed saving. If you have a failing test and you rerun it, it will almost immediately fail again in exactly the same way. With approaches that don't use the Hypothesis model, the best you can hope for is to save a random seed, then rerun shrinking from that failing example, which is a lot slower.

There are probably a bunch of other quality of life improvements, but these are the things that have stood out to me when I've used proptest, and are in general the big contrast between the Hypothesis model and the more classic QuickCheck-derived ones.

Ouch. Classic Claude. It does tend to cheat when it gets stuck, and I've had some success with stricter harnesses, reflection prompts and getting it to redo work when it notices it's cheated, but it's definitely not a solved problem.

My guess is that you wouldn't have had a better time without PBT here and it would still have either cheated or claimed victory incorrectly, but definitely agreed that PBT can't fully fix the problem, especially if it's PBT that the agent is allowed to modify. I've still anecdotally found that the results are better than without it because even if agents will often cheat when problems are pointed out, they'll definitely cheat if problems aren't pointed out.

TBF PBT has been the present in Python for a while now.

10 years ago might have been a little early (Hypothesis 1.0 came out 11 years ago this coming Thursday), but we had pretty wide adoption by year two and it's only been growing. It's just that the other languages have all lagged behind.

It's by no means universally adopted, but it's not a weird rare thing that nobody has heard of.

So I think a short list of big API differences are something like:

* Hypothesis/Hegel are very much focused on using test assertions rather than a single property that can be true or false. This naturally drives a style that is much more like "normal" testing, but also has the advantage that you can distinguish between different types of failing test. We don't go too hard on this, but both Hegel and Hypothesis will report multiple distinct failures if your test can fail in multiple ways.

* Hegelothesis's data generation and how it interacts with testing is much more flexible and basically fully imperative. You can basically generate whatever data you like wherever in your test you like, freely interleaving data generation and test execution.

* QuickCheck is very much type-first and explicit generators as an afterthought. I think this is mostly a mistake even in Haskell, but in languages where "just wrap your thing in a newtype and define a custom implementation for it" will get you a "did you just tell me to go fuck myself?" response, it's a nonstarter. Hygel is generator first, and you can get the default generator for a type if you want but it's mostly a convenience function with the assumption that you're going to want a real generator specification at some point soon.

From an implementation point of view, and what enables the big conveniences, Hypothesis has a uniform underlying representation of test cases and does all its operations on them. This means you get:

* Test caching (if you rerun a failing test, it will immediately fail in the same way with the previously shrunk example)

* Validity guarantees on shrinking (your shrunk test case will always be ones your generators could have produced. It's a huge footgun in QuickCheck that you can shrink to an invalid test case)

* Automatically improving the quality of your generators, never having to write your own shrinkers, and a whole bunch of other quality of life improvements that the universal representation lets us implement once and users don't have to care about.

The validity thing in particular is a huge pain point for a lot of users of PBT, and is what drove a lot of the core Hypothesis model to make sure that this problem could never happen.

The test caching is because I personally hated rerunning tests and not knowing whether it was just a coincidence that they were passing this time or that the test case had changed.

But the problem remains verifying that the tests actually test what they're supposed to.

Definitely. It's a lot harder to fake this with PBT than with example-based testing, but you can still write bad property-based tests and agents are pretty good at doing so.

I have generally found that agents with property-based tests are much better at not lying to themselves about it than agents with just example-based testing, but I still spend a lot of time yelling at Claude.

So "a huge part" - possibly, but there are other huge parts still missing.

No argument here. We're not claiming to solve agentic coding. We're just testing people doing testing things, and we think that good testing tools are extra important in an agentic world.

It's on the agenda! We definitely want to rewrite the Hegel core server in rust, but not as much as we wanted to get it working well first.

My personal hope is that we can port most of the Hypothesis test suite to hegel-rust, then point Claude at all the relevant code and tell it to write us a hegel-core in rust with that as its test harness. Liam thinks this isn't going to work, I think it's like... 90% likely to get us close enough to working that we can carry it over the finish line. It's not a small project though. There are a lot of fiddly bits in Hypothesis, and the last time I tried to get Claude to port it to Rust the result was better than I expected but still not good enough to use.

We looked at it and given that the repo was archived nearly two years ago decided it wasn't a problem.

Conversation with Will (Antithesis CEO) a couple months ago, heavily paraphrased:

Will: "Apparently Hegel actually hated the whole Hegelian dialectic and it's falsely attributed to him."

Me: "Oh, hm. But the name is funny and I'm attached to it now. How much of a problem is that?"

Will: "Well someone will definitely complain about it on hacker news."

Me: "That's true. Is that a problem?"

Will: "No, probably not."

(Which is to say: You're entirely right. But we thought the name was funny so we kept it. Sorry for the philosophical inaccuracy)

Post author here btw, happy to take questions, whether they're about Hegel in particular, property-based testing in general, or some variant on "WTF do you mean you wrote rust bindings to a python library?"

How popular do you want it to be?

The Python survey data (https://lp.jetbrains.com/python-developers-survey-2024/) holds pretty consistently at 4% of Python users saying they use it, which isn't as large as I'd like, but given that only 64% of people in the survey say they use testing at all isn't doing too badly, and I think certainly falsifies the claim that Python programs don't have properties you can test.

Interesting. I've not seen that before. My best guess is that it might be an old trio version or something, but I'm not sure.

FWIW shrinkray gets to 162 bytes if I leave it to run for about 10 minutes. https://gist.github.com/DRMacIver/ee025c90b4867125b382a13aaa...

I think it might do a little but not a lot better if I left it to run for longer but it looked to have mostly stalled then so I got bored and killed it.

I think the easiest way to think about it is that it's gradient descent, it's just a slightly weird form of it over a discrete space.

If you imagine you've got some neighbourhood function N(x) that takes a program and returns a large sample of valid programs that are "similar" to x (its neighbourhood), then your basic test-case reduction algorithm is just:

1. Start with some initial test case. 2. Look at the neighbourhood of your current test case. If any elements of it are both interesting and smaller than your current test case, move to one of those. If not, stop. 3. Return the smallest interesting test case you've seen at the end.

And most of what varies from test-case reducer to test-case reducer is that neighbourhood function (how you explore the neighbourhood also varies, but you can think of that as an implementation detail that mostly only affects performance).

This approach will generally work pretty well because the sort of bugs you tend to find are "dense in program space". This will e.g. do nothing if you start from the property that the file has a particular sha1 hash, but if you start from a property like "this uses this particular pair of language features", most nearby programs will share it.

The nice thing about doing test-case reduction is that it doesn't actually matter if your neighbourhood contains only valid programs, because you can rely on the interestingness test to filter out any invalid program. So all you care about really is:

1. It contains a fairly large set of valid programs among the test cases you consider. 2. It's not too large so as to be prohibitive to explore.

And this frees you up to just try a bunch of heuristics that are likely to work pretty well, and it turns out that there are a lot of easily accessible ones. In particular, deleting contiguous chunks of a program pretty often produces a valid program, which will always be shorter.

For a trivial example, imagine you've got something like:

if True:

    blah()

This isn't a real example exactly. C-reduce I think won't find this particular one (but I might be misremembering its exact heuristics here). Shrinkray will, but it will do so by understanding Python - it stops at 10-byte sequences, which won't work here. But it demonstrates the sort of thing that can work surprisingly well without understanding syntax.

Another thing you can do is you can understand just enough syntax in a general purpose way. For example, shrinkray (and I think C-Reduce) will look for integer literals in the program and try replacing them with integer literals representing a smaller number. In order to do this, it doesn't have to know anything about the program's lexical syntax, it just has to know what a number looks like.

Heuristics like this will often fail to work, but that's OK, you just need them to succeed enough, and often some pretty crude stuff will get you down to something that is small enough that a human can get it the rest of the way.

Yes, that's me.

I accidentally got obsessed with test-case reduction as a result of writing Hypothesis, and wrote shrinkray because I thought it was ridiculous that I hadn't put all of the things I'd learned about test-case reduction into some general purpose tool that other people could benefit from.

Shrinkray is still a bit under-advertised and rough around the edges in places, but I think that basically there's no good reason to use C-reduce over shrinkray for things that aren't C or C++. Shrinkray has very good generic heuristics that should work in most languages (it even works pretty well on binary files apparently, although I've not tested this myself), a couple of language specific passes for other languages, and is much more fun to watch.

It might even be the case that you should use shrinkray for C and C++ too (because I use C-Reduce's transformations for those languages), but I'm less confident that that's true. The best I'll confidently claim is "probably more competitive than you'd expect".

Well, I do have my own reducer (shrinkray is mine), but I actually hadn't considered using TreeSitter grammars for it. That's a good idea, thanks!

This isn't a coincidence. I wrote both.

Perses isn't language agnostic, it just knows the syntax of a lot of languages because there are antlr grammars for most commonly used languages.

Really there's no such thing as a language-agnostic test-case reducer. shrink ray is much closer than most, but all this means is that it's got some heuristics that work well for a wide variety of common languages (e.g. the bracket balancing thing). It's also got a bunch of language-specific passes.

This is sortof inherent to the problem, because in order to get good results and good performance, a test-case reducer has to have a strong idea of what sort of transformations are likely to work, which in turn means it has to have a strong idea of what sort of languages it's likely to be run on.

I think mathematicians have mostly moved past the idea of fighting over whether something is or isn't a number. There are lots of interesting number systems that never made it into widespread use in the same way that the "core" number systems did, and there are lots that see niche usage, but people are pretty relaxed about whether they are "actually" numbers - they might or might not typicaly be referred to as numbers, but the strongest negative answer to "Is this a number?" you'd typically see would probably be to shrug and say "sure I guess, if you like?"

One example of previous attempts which we'd now consider to be invalid is a lot of operations on infinite series. In early days of analysis you'd get people concluding things like "1 - 1 + 1 - 1 + ... = 1/2", which gets you into more hot water the more you look at it. The problem here isn't that they are philosophically unsound per se - you can define all sorts of notions of "infinite sum" that make this work, like cesaro summation - but they don't behave as nicely as people intuitively expected them to and the naive versions of them don't really work.

I mean, I guess I am? I'm technically doing a PhD in it at the moment, but my opinions on philosophy of mathematics don't have much to do with the finer details of test-case reduction.

My actual degree, which is where most of my philosophy of mathematics opinions were developed, is in very pure mathematics. I've done quite a lot of software development since and that's definitely shaped the framing, but the core philosophy is one that I've had since long before I knew much about computer science at all.

I think the writer is understating the importance of the exercises.

I think it's not so much that I'm understating the importance of the exercises as that I'm coming from a position where by the time I want to read a textbook these days I effectively have my own exercises to work on.

That being said, it's true that I've always had a more-than-healthy aversion to actually doing the textbook exercises, and it's something I should work on.

A (somewhat non-standard but I think compatible with general usage) definition I tend to use is that fuzzing is the data generation part and property-based testing is layering interesting non-trivial tests on top of fuzzing.

You then get different tools optimised for different spaces. Things labelled fuzzers tend to be optimised for one or two data types (usually text or bytes) and for long-running processes where you can leave the fuzzer running for days or weeks (Google spent a CPU-millenium fuzzing ffmpeg!). Property-based testing libraries on the other hand tend to be optimised for making it easy to write fuzzers for arbitrary data types and assume that tests are short running (seconds or less).

Fundamentally the tools for this are all "the same sort of thing" but there's a very large design space and most things called property-based testing libraries currently sit at more or less the opposite corner from most things called fuzzers.

Hypothesis is maybe a little closer to a classic fuzzer than a classic property-based testing library in design, but that's mostly an implementation detail at present and from the outside/API level it definitely looks more like the latter than the former.