May 13th, 2014

eyes black and white

The Great ASDF Bug Hunt

With the release of ASDF 3.1.2 this May 2013, I am now officially retiring not just from ASDF maintenance (Robert Goldman has been maintainer since ASDF 3.0.2 in July 2013), but also from active ASDF development. (NB: ASDF is the de facto standard Common Lisp build system, that I took over in November 2009.) I'm still willing to give information on where the code is coming from and advice where it might go. I'm also still willing to fix any glaring bug that I may have introduced, especially so in UIOP (indeed I just committed a few simple fixes (for Genera of all platforms!)). But I won't be writing new features anymore. (However, you will hopefully soon see a bunch of commits with my name on them, of code I have already written that addresses the issue of syntax modularity; the code was completed and is committed in a branch, but is not yet merged into the master branch, pending tests and approval by the new maintainer).

Before I left, though, I wanted to leave the code base in order, so I made sure there are no open bugs beside wishlist items, I dumped all my ideas about what more could be done in the TODO file, and I did a video walkthrough of the more subtle parts of the code. I also wrote a 26-page retrospective article on my involvement with ASDF, a reduced version of which I submitted to ELS 2014. There, I gave a talk on Why Lisp is Now an Acceptable Scripting Language.

The talk I would have liked to give instead (and probably should have, since I felt like preaching to the converted) was about the great ASDF bug hunt, which corresponds to the last appendix of my paper (not in the reduced version), a traverse across the build. It would have been a classic monster hunt story:

  • The setting is a seemingly peaceful and orderly little village on the (programming) frontier. It is a familiar old place, not a big one, but a good, comfortable one. Though it is not perfect, and monsters roam at night, it looks fundamentally healthy. (That would be ASDF, in daily use by tens or even hundreds of Common Lisp programmers, despite bugs that catch the unwary.)
  • The protagonist is the (bug) hunter. (I should tell the story in the first person, but for now, third person will do.) In the beginning he is young and naïve — but capable (of improvement). When he comes into town, our protagonist kicks out a few baddies that were victimizing the population; soon enough he replaces the ailing sheriff. (That would be me becoming ASDF maintainer in 2009 when Gary King steps down, after fixing some pathname related bugs.)
  • Under the new sheriff, monsters big and small are hunted down. The inhabitants are not afraid anymore, though some of them remain grumpy. (That's me fixing bugs with the help of many other programmers, while the unwary remain blissfully ignorant of having been saved.) The protagonist builds fortifications, and finds he has to extend the city limits to make it easier to defend, adding new buildings along the way. (That would be improving the ASDF design to be more robust, and adding features.) Often he has to hunt monsters that he himself let in, sometimes after they hurt citizens. (That's when I introduce bugs myself, and sometimes fail to fix them before release.) The protagonist feels guilty about it and learns to be a better sheriff. (That's when I get to deeply respect the regression test suite.) But by and large, his endeavor is a success. At long last, he thinks the place is now safe, and that he knows everything about the town and its now former monsters. — My, how wrong he is! (That's me at the time of ASDF 2.26)
  • Now, a monster has been terrorizing innocent citizens for years. No one has seen the monster, but the way he picks his victims and what he does to them is characteristic. (That's the old bug whereby changes in dependencies are not propagated correctly across modules.) The protagonist's best buddy has found a good way to protect homes against the monster, but it still roams in the streets at night. (That's when Robert Goldman fixes the bug and gets dependency changes to trigger rebuild across modules within a system, but dependency changes still fail to trigger rebuild across systems.) Our sheriff, having finally vanquished all other monsters, and having no other foe left in town, sets off to catch this one last monster. And so, he has to enter hitherto unexplored caverns deep below the village, a place abandoned long ago, where the creature lurks. (That would be the ASDF traverse algorithm.) And of course that's when the story turns ugly.
  • Our protagonist thinks the monster will be an easy catch, what with his all experience and technology. But it's actually a long, hard fight to the death. It's the toughest enemy ever. (And that's the story of writing ASDF 2.27, that eventually becomes ASDF 3, after months of struggle.)
  • Along the way, many times, the protagonist thinks he has almost won, but not at all; many times, he thinks he is lost, but he keeps at it. (More code was written in the year or so since ASDF 2.26 was released than in the entire decade before.) Quickly though, he realizes that the monster he was chasing is but a henchman of a bigger monster that has been ruling over the village all along. The apparent orderliness of the village was but a lie, all that he thought he knew was fake! (That's the fundamental algorithm behind ASDF having deep conceptual bugs.) Happily, a mysterious wise man left him cryptic instructions on how to defeat the monster before he even became a sheriff, though he only understands them when comes the confrontation. (That would be Andreas Fuchs and his POIU, the maintenance of which I had also inherited, and that brought all the essential insights just at the right moment.)
  • In the end, the sheriff vanquishes his foes and defeats the great monster for good, but not until he has learned to respect his enemy. And his real prize is in the lessons he learned and the final illumination he reaches. (And I hope you too can enjoy this illumination.)

The final illumination is that inasmuch as software is "invented", it isn't created ex nihilo so much as discovered: Daniel Barlow, who wrote the initial version ASDF, obviously didn't grok what he was doing, and can't be said to have created the ASDF algorithm as it now stands, since what he wrote had such deep conceptual flaws; instead, he was experimenting wildly, and his many successes overshadow and more than redeem his many failures. I, who wrote the correct algorithm, which required a complete deconstruction of what was done and reconstruction of what should have been done instead, cannot be said to have created it either, since in a strong sense I "only" debugged Daniel's implicit specification. And so, the code evolved, and as a result, an interesting algorithm was discovered. But no one created it.

An opposite take on the same insight, if you know Non-Standard Analysis, is that Daniel did invent the algorithm indeed, but specified it with a non-standard formula: his formula is simple (a few hundreds of lines of code), and captures the desired behaviour in simple enough cases with standard parameters (using SBCL on Unix, without non-trivial dependency propagation during an incremental build) but fails in non-standard cases (using other implementations, or dealing with timestamp propagation). My formula specifies the desired behaviour in all cases with all the details correct, and is much more elaborate (a few thousands of lines of code), but is ultimately only a Standardization of Daniel's formula — a formal elaboration without any of Daniel's non-standard shortcuts, but one that doesn't contain information not already present in Daniel's version, only making it explicit rather than implicit.

The two interpretations together suggest the following strategy for future software development: There is a lot of untapped potential in doing more, more daring, experimentations, like Daniel Barlow did, to more quickly and more cheaply discover new interesting designs; and conceivably, a less constrained non-standard representations could allow for more creativity. But this potential will remain unrealized unless Standardization is automated, i.e. the automatic specification of a "standard" formal program from a "non-standard" informal one; a more formal standard representation is necessary for robustly running the program. This process could be viewed as automated debugging: as the replacement of informal variables by sets of properly quantified formal variables; as an orthogonal projection onto the hyperplane of typed programs; as search of a solution to a higher-order constraint problem; as program induction or machine learning; etc. In other word, as good old-fashioned or newfangled AI. This process itself is probably hard to formalize; but maybe it can be bootstrapped by starting from a non-standard informal specification and formalizing that.