🔗 Fun with parsers

Wednesday, 28 November, 2018 — links

In The Hardest Program I’ve Ever Written – journal.stuffwithstuff.com, Bob Nystrom writes:

The hardest program I’ve ever written, once you strip out the whitespace, is 3,835 lines long. That handful of code took me almost a year to write. Granted, that doesn’t take into account the code that didn’t make it. The commit history shows that I deleted 20,704 lines of code over that time. Every surviving line has about three fallen comrades.

If it took that much thrashing to get it right, you’d expect it to do something pretty deep right? Maybe a low-level hardware interface or some wicked graphics demo with tons of math and pumping early-90s-style techno? A likely-to-turn-evil machine learning AI Skynet thing?

Nope. It reads in a string and writes out a string. The only difference between the input and output strings is that it modifies some of the whitespace characters. I’m talking, of course, about an automated code formatter.

This is an interesting walkthrough. In particular, I like the extra detail on paths pursued and later abandoned in the face of new information, new optimizations, or, particular code paths raising the Halting Problem.

Another element I appreciate here is Nystrom not trivializing the amount of work that went into the project.