Now they have two problems

Some people, when confronted with a problem, think “I know, I'll use regular expressions.” Now they have two problems.

It is the most quoted sentence in the field, it is attributed to Jamie Zawinski, and unusually for a thing everybody quotes, he really did write it. Tuesday, the twelfth of August 1997, in a newsgroup argument about Perl. A newsgroup was how the internet argued before websites had comment sections, and Perl was the language you reached for when you had to mangle text in a hurry, which it made so easy that people did it whether or not they should. Somebody actually went and found the post, which is more than can be said for most attributions.

Where it gets interesting is that he was not inventing the joke. He was using it. The same construction turns up in 1988, in a discussion of a different tool entirely, and the shape of it, some people respond to X by reaching for Y, now they have two Ys, was already a going concern. Zawinski's version is the one that stuck because he aimed it at the right target at the right moment, which is what most authorship consists of.

So the quote is honest and the attribution is roughly right and the thing it is aimed at is nearly fifty years older than the joke.

The idea comes from Stephen Kleene, a logician, in a 1951 paper about nerve nets and finite automata. He was not thinking about text. He was describing which sets of events a very simple machine can recognise, and he needed a notation for them, so he made one up and called them regular events. The asterisk you type a dozen times a day is named after him: the Kleene star, meaning any number of these, including none.

It sat in the logic literature for seventeen years. Then Ken Thompson wrote a paper in 1968 explaining how to make a computer search text with one at usable speed, and put the result into a text editor. Thompson would go on to build Unix, the operating system nearly everything you use is descended from, so this is nowhere near his most famous piece of work. From there it went into a command whose name is a fossilised keystroke: in that editor you typed g, then the pattern, then p, to print every matching line, and the command that does it is still called grep.

Which is the part the joke misses, and it is worth saying out loud before we agree with the joke anyway. Regular expressions are not a hack that got out of hand. They are a piece of formal mathematics with a proof attached, and the reason a simple one is fast is that a machine can decide it without ever guessing.

The two problems arrive later, and from a different direction. What people mean by regex today is mostly not what Kleene defined. It has picked up backreferences, lookaheads and lazy quantifiers. All useful. All outside Kleene's theory, and the moment you step outside the theory you leave the proof behind, and the speed guarantee with it. There are patterns of that kind that will match a short string in an afternoon.

And then there is the reading problem, which no amount of theory fixes. A regular expression is written once, by somebody holding the whole shape of it in their head, and read afterwards by people who are not. It has no room for a name, a comment or a paragraph break. It is the only thing in the codebase with no way to explain itself, which is exactly why it looks, on the page, like a test you are failing.