Fast and Loose DSLs

Oct. 27 2017compilershaskellhedgehogtalktesting

Last night I presented at FP Syd, our local user group.

In 2016, I used Hedgehog's predecessor, Jack, while developing a small typed programming language. The language in question was fairly complicated, with type inference, sum types, records, and limited polymorphism. Jack was more than adequate for the task. A small investment upfront in writing good generators paid off in spades.

Generating well-typed terms and arbitrary terminating programs in Jack using naive methods led to really good shrunk well-typed / terminating counterexamples. It even picked up a few variable capture bugs! Free shrinking means you're free to write much more complicated generators for much more precise properties.

Once all my properties passed and I'd added a few golden tests, I was confident enough in my implementation to put it into production.

The hardest part of that task was wrangling QuickCheck, which Jack uses under the hood. It was a lot of work to ensure my generators terminated, and the ergonomics of interactively testing such complex QuickCheck became quite poor. Since then, Jack's polished sibling Hedgehog has been released, doing away with QuickCheck altogether and making all of those problems go away.

I've been wanting to write a long blog post on this topic for almost a year, but haven't had time to update my generators for Hedgehog. This scheduled talk was a nice forcing function. I still haven't had time, but I mocked up a small STLC-based compiler to get ammunition for my slides. As a result, this talk is missing a lot of detail for the interesting parts. I would like to include a lot more interesting real-world counterexamples.

There are a lot of rough edges in the slide deck, I wrote it and delivered it on the same day with little time for precision or revision. Try not to email me about it. I know!

Nevertheless, I hope it whets your appetite for the eventual detailed writeup, or persuades you to figure it out yourself. Trust me, naive methods in Hedgehog are good enough for most tasks! When they fail, just reduce the scope of your generator a little bit until you have something tractable. We want as much randomised coverage as we can get, it doesn't need to be perfect.


Fast and Loose DSLs with Hedgehog

Property-based testing is great for programming languages, and Hedgehog turns the dial up to 11. This allows imbeciles such as myself to implement complicated programming languages with unwarranted confidence. This talk is about how Hedgehog can be used to test parsers, type checkers, and codegen.