Compilers, TDD, Mastery

I was talking to a friend yesterday about the upcoming compiler project when he asked me a question "Will you be coding the compiler in an Agile fashion? I mean using TDD etc?". This turns out to be an intriguing question.

I got sick of the "silver bullet" style evangelization of the Agile Religion and formally gave up "agile" some time ago. However I do believe in programmer written unit tests being run frequently and that is part of "agile". What I do not believe in is the notion of the design "emerging" from the depths of the code like the Venus of Milo from the waters by just repeating the "write-test, write code, refactor" cycle, a practice otherwise known as TDD.

Anyway, I decided to google for compiler s and tdd and came up with some absolute gems.Here's the first.

On the comp.lang.extreme-programming mailing list, I came across this absolutely hilarious exchange.

In the midst of a tedious discussion on whether XP scales to large projects, "mayan" asked,

I am not asking what kinds of companies are doing XP work - I believe a lot of them are, and successfully. What I am asking is anyone using XP for large size/high complexity/high reliability problems. To be more specific - stuff like optimizing compilers, OS kernels, fly-by-wire systems, data-base kernels etc

Ron Jeffries, one of the "gurus" of agile, replied,

. I'm not aware of any teams doing compilers or operating systems using XP, but having done both, I'm quite sure that they could be done with XP, and the ones I did (at least) would have benefited from it, even though they were successful both technically and in the market.

Aha this looked interesting! Someone actually thinks a compiler can be written in a XP (and presumably TDD) fashion. Mayan issued a challenge to Ron which looked like this

Excellent: lets talk about the following problem: write an optimizing back-end for a C compiler (assume we purchased the front-end from someone). How would we use XP, or adapt XP to it?

Some problems with compiler back-ends:

- its fairly clear what has to be done (core {intermediate-language/instruction selection/register-allocation/code-generation} + set of optimizations); its fairly clear what order they have to be done in (first the core, then a particular sequence of optimizations)

- you don't really need customer input. Having a customer around doesn't help.

- you can't demo very much till you have a substantial portion of the code written - the core (say about 30-60klocs) - no small (initial) release

- you had better get your IL (intermediate language) data-structures right - if you pick ASTs or 3 or 4 address form, you will do fine for the basic "dragon-book" optimizations, but later on you will either run into severe problems doing more advanced optimizations, or you will have to rewrite your entire code base [probably about 100-150klocs at this time]. Is this BUFD?

- you had better think of performance up front. Toy programs are easy; but a compiler has to be able to handle huge 100kloc+ single functions. Many heuristics are N^2 or N^3. Both run-time efficiency and memory usage end up being concerns. You can't leave optimization till the end - you have to keep it in mind always. It also pretty much determines your choice of language and programming style.

- TDD may be applicable for some of the smaller optimizations; on the other hand, for doing something like register-allocation using graph coloring, or cache blocking - I wouldn't even be able to know where to begin.

- The basic granule (other than the core) is the optimzation. An optimization can be small (constant propagation in a single basic block) or large (unroll-and-jam, interprocedural liveness analysis). The larger ones take multiple days to be written. Integrating them "often" is either pointless (you integrate the code, but disable the optimization) or suicidal (you integrate the code, but it breaks lots and lots of tests; see below). Best case: integrate once the optimization is done.

- Its not easy to split an optimization into subproblems; so typically one (programmer/pair) works on an optimization. For the larger ones, if it needs to be tweaked, or fixed, the unit that wrote it is the best unit to fix it. The overhead to grok a couple of thousand lines of code (or more!) vs. getting the original team to fix it is way too high.

- Testing, obviously, is a lot more involved. Not only do we have to check for correctness, we have to check for "goodness" of the produced code. Unfortunately, many optimizations are not universally beneficial - they improve some programs, but degrade others. So, unit testing cannot prove or disprove the goodness of the implementation of the optimization; it must be integrated with the rest of the compiler to measure this. Further, if it degrades performance, it may not be a problem with that optimization - it may have exposed something downstream from it.

- Typical compiler test suites involve millions of lines of tests. They tend to be run overnight, and over weekends on multiple machines. If you have a badly integrated optimization, you've lost a nights run. And passing all tests before integration is, of course, an impossibility. Even a simple "acceptance" set of tests will check barely a small percentage of the total function in the compiler.

Hmmm.....does this still look a lot like XP to you? I can see that at least 1/3rd of the XP practices being broken (or at least, severely bent).

Based on your experience, do you disagree with any of the constraints I outlined?

Mayan

I expected Ron to post a reply explaining how all the above can fit into the Agile/XP framework, but there was only [ the sound of crickets chirping].

On the XPChallengeCompilers page, Ron repeats his claim that "I've written commercial-quality compilers, operating systems, database management systems ". Hmm. Yeah. Whatever. He doesn't make any useful points about how one would actually go about doing something like this.

On the same page, Ralph Johnson has (as one would expect) a more thoughtful and articulate view point about how XP would apply to writing a (simple) compiler, but he focusses more on the fact that

" DoTheSimplestThingThatCouldPossiblyWork is true for compilers, as well. My problem is that people seem to think that the simplest thing is obvious, where my experience is that it is often not obvious. One of the things that makes someone an expert is that they KNOW the simplest thing that will really work."

Now this makes sense. There is no hint of the design "emerging" from "average" developers grinding through the tdd cycle and there is a strong hint that you do have to understand the domain of a compiler well before you can even conceive of the "simplest thing". He concludes with

"The XP practices will work fine for writing an E++ compiler. However, I think there will need to be some other practices, such as comparing code to specification, as well as appreciating the fact that you sometimes must be an expert to know what simple things will work and which won't".. Ahh the blessed voice of rationality.

Another area where Agile falls flat on its face is when dealing with concurrency. See the XP Challenge concurrency page for the flailing attempts of an "agilist" to "design by test" a simple problem in concurrency. Tom Cragill proposed a simple synchronization problem and Don Wells (and some of the agile "gurus") attempted to write a test exposing the bug and didn't succeed till Tom pointed the bug out.

Coming back to compilers, there are projects like the PUGS project, led by the incredible Autrijus Tang, in which unit tests are given a very high priority. I couldn't find any references to the PUGS design "evolving" out of the TDD cycle however. It seems as if they build up a suite of programmer written tests and run it frequently.I can see how that practice would be valuable in any project. Accumulating tests and an "automated build" are the practices I retained from my "agile" years. AFAIK the pugs folks don't do "TDD", expecting the design to emerge automagically.

This whole idea of "emergent design" (through TDD grinding) smacks of laziness, ignorance and incompetence. Maybe if you are doing a web->db->web "enterprise" project you can hope for the TDD "emergence" to give you a good design, (well, it will give you a design :-P) but I would be very surprised if it worked for complex software like compilers, operating systems, transaction monitors etc. Maybe we should perusade Linus to "TDD" the Linux kernel. TDD-ShmeeDeeDee! Bah! :P

Update: Via Jason Yip's post, Richard Feynman's brilliant speech exposes what exactly is wrong with the practice of "Agile" today. An excerpt

I think the educational and psychological studies I mentioned are examples of what I would like to call cargo cult science. In the South Seas there is a cargo cult of people. During the war they saw airplanes with lots of good materials, and they want the same thing to happen now. So they've arranged to make things like runways, to put fires along the sides of the runways, to make a wooden hut for a man to sit in, with two wooden pieces on his head to headphones and bars of bamboo sticking out like antennas--he's the controller--and they wait for the airplanes to land. They're doing everything right. The form is perfect. It looks exactly the way it looked before. But it doesn't work. No airplanes land. So I call these things cargo cult science, because they follow all the apparent precepts and forms of scientific investigation, but they're missing something essential, because the planes don't land.