Infinite Monkeys and Finite Patterns

What you need to know about Haskell QuickCheck and the limited edition UNIQLO x Marimekko collab

Welcome, new JeanStack subscribers! JeanStack is the most fun place on the Internet to get your weekly dose of “runway PL” and fast fashion. More about the goals here.

In 1913, French mathematician Émile Borel introduced the infinite monkey theorem, stating that a monkey hitting typewriter keys at random for an infinite amount of time would almost surely type any given text, including the complete works of William Shakespeare. An infinite amount of times, at that. (Yes, I know this idea has also been attributed to English scientist Thomas Huxley and also to Aristotle. But having three attributions was jamming up my opening sentence.)

For centuries, the idea that random sequences of inputs can replace inspired genius—or good old hard work—has captured the imaginations of everyone from mathematicians to scientists to philosophers to literary greats like Jorge Luis Borges. The infinite monkey theorem is also core to an important question in programming languages and software engineering research: how much is it possible to replace insight and intention with randomness when it comes to testing software?

What’s the big deal with QuickCheck?

I picked today’s “runway PL” topic because of how it’s captured people’s imaginations for the last two decades. Appearing at the International Conference on Functional Programming (ICFP) Conference in 2000, Koen Claessen and John Hughes’s paper “QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs” showed a nice way of using random testing to not just find crashes, but to find high-level program bugs. This is now called property-based testing. In this post, I’ll talk not just about how QuickCheck works, but also its significance in the broader landscape of programming languages research.

Here’s what QuickCheck does. Normally, a software developer tests their code by writing specific test cases. For instance, take the standard list reversal function, reverse. We know that reversing a unit list [x] should yield the same list, that reversing appended lists xs and ys should reverse each list and flip the order, and that reversing a reversed list should yield the original list:

reverse [x] = [x]
reverse (xs++ys) = reverse ys++reverse xs
reverse (reverse xs) = xs

How a programmer would normally unit test code for these properties is to manifest them as test cases for specific instances of x, xs, and ys, for instance:

TestCase (assertEqual "for (reverse [3])" [3] (reverse [3]))

You can extrapolate from here just how many test cases you’d need to cover just the three properties above. If you’ve written a lot of software, you’re probably all too familiar with the tedium of having to enumerate all of your test cases, as well as the horror when you realize that your code was missing a case.

QuickCheck captured the imaginations of programmers around the world by promising to make all of this go away! In QuickCheck, we can simply define these properties as Haskell functions:

prop_RevUnit x =
  reverse [x] == [x]

prop_RevApp xs ys =
  reverse (xs++ys) == reverse ys++reverse xs

prop_RevRev xs =
  reverse (reverse xs) == xs

Now we can just rely on the QuickCheck to test these properties with random input values. If these functions return True for every argument, then the test passes.

With QuickCheck, it’s also possible to define our own generators for the inputs to test, for instance:

instance Arbitrary Int where
  arbitrary = choose (-20, 20)

It’s also possible to do this for user-defined data types, for instance:

data Tree a = Leaf a | Branch (Tree a) (Tree a)

instance Arbitrary a => Arbitrary (Tree a) where
  arbitrary = frequency
    [ (1, liftM Leaf arbitrary)
    , (2, liftM2 Branch arbitrary arbitrary) ]

And just like this, Classen and Hughes showed how to combine random testing with clean abstractions to create a powerful force against software bugs. All implemented in ~300 lines of Haskell. The simplicity, the elegance, and the accessibility of QuickCheck captured the attention of programmers around the world.

The research that made QuickCheck possible

Neither random testing nor the idea of reference implementations were new at the time, but the QuickCheck paper showed how to put all of these ideas together in an incredibly elegant and lightweight way. The revolutionary thing about QuickCheck was the ability to randomly test against such clean, fine-grained, and high-level properties. And the emergence of Haskell very much facilitated the design and implementation of this.

Even when QuickCheck came around in 2000, random program testing had been around for a few decades. Fuzzing, an automated software testing technique that uses random inputs to trigger crashes and/or potential memory leaks, first came about in the 1950s, when programmers would use trashed punch cards or random cards to find bugs. Random testing had also been around since 1971. There had, for instance, been prior work that tested C++ classes against an algebraic specification. People had also previously used grammars for test input generation. At the time QuickCheck came out, random testing was primarily for crashes and memory leaks and anything more was pretty heavyweight stuff.

Haskell’s appearance in 1990 provided a clean playground for working out QuickCheck’s main innovation: being able to do random testing against fine-grained, high-level program properties—all in a lightweight way. (Fun fact that I learned in grad school: there were so many Haskell-like languages floating around in 1987 that the researchers formed a committee to consolidate them—and the result was Haskell.) First of all, Haskell is purely functional, meaning it has no side effects. Setting up states and keeping track of state updates is often a complicated part of properly testing, so not having to deal with this makes things much simpler. Haskell’s strong static type system and monads make both the implementation and the use of QuickCheck super succinct. (I’m still blown away that the implementation was ~300 lines of Haskell and ran in the interpreter!) This, no doubt, made it easier for other people to understand and appreciate these ideas—and implement them in messier contexts in mainstream languages.

In short, people had been trying to do what QuickCheck did for a long time. QuickCheck finally made a version of random testing that was practical enough and accessible enough to get picked up in mainstream programming.

(Above: the IFIP Working Group 2.8 for Functional Programming in 1992. Photo courtesy of Simon Peyton-Jones, initially for this interview I did with him.)

What’s next?

In 2003, researchers did an experiment with actual monkeys to see if their keystrokes are actually random. It turns out that monkeys love typing the letter ‘S,’ perhaps because they also loved Soiling the keyboards. Today, it is believed that monkeys are not a great source of keyboard randomness.

Fortunately, there are many other sources of keyboard randomness, allowing both random testing and property-based testing to continue gaining momentum. In my bubble of programming tools geeks, QuickCheck itself has quite a bit of name recognition. Property-based testing also has something of a cult following among developers of a certain disposition. You’ll be able to find property-based testing libraries for many mainstream libraries, for instance, Hypothesis for Python.

The idea that QuickCheck popularized, the idea that you can automatically find a lot of issues of interest without doing too much extra work to specify what you care about, is a magical one. ✨ It’s definitely inspired the work we’ve been doing at my company, Akita Software, where we’re approaching this problem at the API level rather than the language level. If this is something that sounds interesting to you, check out our beta.

And for everyone in general: I recommend checking out QuickCheck because who knows what tooling it might inspire you to build! ⚡️

Also tangentially related to monkeys: the Marimekko+Uniqlo collab

Speaking of monkeys, today’s accessible fashion tip has to do with what the most iconic monkey designer, Paul Frank, was really good at: collaborations. It seems like Paul Frank worked with everybody: Barbie, Elvis Presley Enterprises, the Andy Warhol estate, and Hello Kitty. (Paul Frank for Andy Warhol pictured below.)

Paul Frank was an early part of a greater trend. As part of the democratization of fashion, designers have been collaborating more with social media stars and also with mass-market brands, for instance, Versace x H&M in 2011. This is good for the designers because it helps them build hype. It’s also great for people who are interested in fashion, but who might not have the interest or ability to drop the $$ on the designer version. (Note: modulo environmental and labor issues. An informative read is Elizabeth L. Cline’s Overdressed.)

This brings us to our find of the week: the limited edition UNIQLO x Marimekko collab. Known for their bright, simple patterns, Marimekko is a Finnish Design House specializing in home furnishing and textiles. When I was a grad student at MIT, I loved walking across the bridge to the Marimekko store on Newbury Street. It wasn’t the most affordable on my PhD stipend, but the designs made me so happy. (Above is a photo of me in a Marimekko dress eating an egg sandwich, taken by my friend Aliza in Brooklyn in 2014.)

You can imagine my excitement when I recently discovered that Marimekko is collaborating with the Japanese casualwear brand UNIQLO. (More here about the significance.) This is like a QuickCheck fan discovering that their language of choice has a property-testing library that is almost as clean and easy-to-use!! You’re likely sacrificing on precision and/or semantic cleanness, but the price/utility tradeoff is just so good. I have, of course, ordered some items and am waiting for them to arrive. (Caveat: this collab is only for women’s and children’s clothing. BUT Marimekko and UNIQLO individually have a lot of cool menswear.) A lot was already out of stock when I ordered, so time is of the essence!

Anyway, I have to get on with my Sunday, but I recommend everyone check out QuickCheck, Marimekko, this amazing UNIQLO x Marimekko collab, and the UNIQLO x Marimekko collabs that are property testing libraries in mainstream languages. ✨

—

⚡️ Liked what you saw? Subscribe to JeanStack for your weekly dose of runway PL and fast fashion! Tell all of your friends!!

👾 If you’re interested in accessible PL conversations, you might also like my PLTalk Twitch livestream with Hongyi Hu (security @ Figma) Fridays at 3pm PT. (Watch our latest stream on practical formal methods, with guest Hillel Wayne, here.)

✨ You may also be interested in checking out what we’re doing with API tools at my company, Akita Software. As I mentioned, we’re very much applying QuickCheck-like ideas at the API level. If this sounds exciting to you, we’d love to have you try out our beta!