Ravi Mohan's Blog

Monday, June 19, 2006

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.

15 comments:

Siddhi said...

Hi Ravi,

Naturally, agile cannot work for everything. Certain projects cannot be run in an agile way, while some can be run partially using some principles. It is up to the experience of the person to see what can be done rather than blindly following a methodology.

But concrete rules have an advantage in helping non-experts get things done. Imagine if instead of cookery recipes we had "take ingredients, mix, and cook until done". While this is what the expert cook does, it doesnt help you or me. The same goes for methodologies. Not everyone is in the top bracket with all the experience to be able to know what to do in every situation. So in a way these rules are helpful, but you have to know when to not use them.

It is also easy to mix up the 'agile camp' and 'XP camp', because the XP camp is the most vocal. There are agile methodologies like Crystal Clear, FDD and DSDM that do not advocate TDD or pair programming, and have distinct design phases up front with documentation.

I had written a couple of posts about these a while ago:

http://siddhi.blogspot.com/2006/05/agile-is-not-xp.html

http://siddhi.blogspot.com/2006/05/shu-ha-ri.html


Siddharta

Ravi said...

Siddharta,

I am not saying that Agile as a whole is utterly useless. I spent about 2.5 years (at Thoughtworks) working in an almost totally agile fashion, working with some brilliant people. i know that *** when used appropriately***, the agile practices can be very rewarding.

However, of late there has been an upsurge of what I call "religious agile", characterized by a lack of critical thought and awareness of context. There are people who go around making ridiculous statements like "tests are specifications", "tdd is about design" etc, and more importantly stating (or implying) that "agile is the One True Way".

This "religiosity" provokes a backlash from more thoughtful developers who (rightly imo) reject the more "fundamentalist" claims of these "born again" "agilists".

Every (set of) tool(s) in a developer (teams)'s toolkit has its limits and contexts where its use is appropriate. No practice or methodology should be beyond critical thought and no methodology needs evangelical fervor for its propogation. The best way to "popularize" (ignoring for now the folks who do this ot fatten their wallets) XP/Agile would be to logically (and if possible scientifically) demonstrate its virtues. Not by "preaching at" others.

Your comments (and blog entries) are well balanced and I have no problems agreeing whole heartedly with them.

Regards,

Anonymous said...

Great post! After 5 years of experience on mostly "Agile" projects, I'm feeling similarly. Now I wonder what is next? I blogged about some of my observations here.

-Jonathan

Ravi said...

Jonathan,
Your blog makes for very interesting reading. "Post Agile" I like that phrase!

Anonymous said...

Thanks for the kind words. Tim Beck has some interesting things over on the Pliant Alliance web site. I recently met him and had a great conversation. I would imagine you, me and Tim in a room would have some great stories to share.

-Jonathan

Ravi said...

"pliant" seems to the the spirit (vs the letter) of agile and tim certainly has some interesting things to say. Hopefully "pliant" won't become the next religion.

:-)

Jason Yip said...

Read what Linus has to say about designing Linux.

http://kerneltrap.org/node/11

Not TDD (which isn't === Agile by the way) but emergent design.

Ravi said...

Jason,

Since I never attacked "emergent design" but "emergent design through ***TDD grinding***",
this is such a strawman argument that is almost not worth replying to.

1. You didn't mention the context of the whole debate.
Someone(Larry?) seems to have claimed that the "sun way" of designing is better than Linux's "random" movement. And Linus is reacting to that.

"To get back to the original claim - where Larry idolizes the Sun engineering team for their singlemindedness and strict control - and the claim that Linux seems to get better "by luck": I really believe this is
important."

2. I am against "emergent design THROUGH TDD grinding" . (EDTG from now) .please note the emphasis.

(a) EDTG is not the same as "emergent design"

(b) this is not the same as emergent design resulting from massive parallelism of effort like for the Linux Kernel.

3. Let me repeat . I do NOT believe ******TDD driven 'emergent design'***** (TDD as defined in kent's book) will work for complex software like the kernel (or an optimizing compiler).

You need to be an expert in the domain to design well in certain domains even when taking small steps (see Ralph Johnson's quote). THIS is my point.


Are you telling me that Linus knows nothing of OS kernels? Or that someone who knows no OS theory can create an OS kernel with TDD? If not we have no disagreement.

Nothing Linus said is sufficient to show that TDD gives rise to good design. What he said is that massive parallelism of effort + availability of source to thousands of people coupled with "random" changes produces more robust design than a BUFD(like sun). I agree. How exactly does this validate TDD?

Using linus's comments out of context to prove the validity of TDD is the kind of illogical mindstretch the whole of "agile" ie built on.

Linus said exactly

"In fact, most developers don't know even what the right _intermediate_
destinations are, much less the final one. And having somebody who shows
you the "one true path" may be very nice for getting a project done, but I
have this strong belief that while the "one true path" sometimes ends up
being the right one (and with an intelligent leader it may _mostly_ be the
right one), every once in a while it's definitely the wrong thing to do.

And if you only walk in single file, and in the same direction, you only
need to make one mistake to die.

In contrast, if you walk in all directions at once, and kind of feel your
way around, you may not get to the point you _thought_ you wanted, but you
never make really bad mistakes, because you always ended up having to
satisfy a lot of _different_ opinions. You get a more balanced system.

This is what I meant by inbreeding, and **************the problem that UNIX
traditionally had with companies going for one niche.*************)


"


(emphasis mine). In other words Linus is discussing the weaknesses of "niche targeted unices" with the "random growth" of Linux. This random growth is created by parallelism of effort by having thousands of people working on teh source and moving the kernel in directions that seem to suit their interest(overseen of course by th benevolennt dictator Linus).

This supports TDD? news to me!


this strawman of "anyone who points out flaws with the tdd approach is actually supporting non evolutionary design" should be laid to rest so we can have a more productive discussion.

Evolutionary design can occur with out being test DRIVEN.

You can write tests after you write the code, or not write any tests at all, and still have evolutionary design and extremely robust software.

Again just to avoid another strawman attack ,let me clarify I am agianst test DRIVEN design , not tests, not design, not emergent design.

The Linux kernel is the best example SUPPORTING this claim , which is my position. the kernel was and is not developed test DRIVEN AFAIK. Please feel free to correct me.

Now if you have any quotes from Linus (or anyone else of that calibre) supporting TDD as a way to write OS kernels or optimizing compilers, do let me know. I am genuinely interested and will be happy to hear of any success stories.

So since I never opposed "emergent design" per se (vs the idea that without a baisc grasp of the underlying complexities of the domain , ***TDD** (TDD!= evolution) will "emerge" a good design " - an idea i call TDD grinding) and Linus was never talking in terms of TDD or Agile, but rather saying that evolved systems are more robust than total BUFD systems( a position with which I agree compeletely) this quote is relevant how xactly?

If there are sentences in my blog post which seem to oppose "emergent design" and not "TDD" , do let me know and I will be glad to correct them.


I'll end up with a Linus quote from the link you sent me.

"You know what the most complex piece of engineering known to man in the
whole solar system is?

Guess what - it's not Linux, it's not Solaris, and it's not your car.

It's you. And me.

And think about how you and me actually came about - not through any
complex design.

Right. "sheer luck".

Well, sheer luck, AND:
- free availability and _crosspollination_ through sharing of "source
code", although biologists call it DNA.
- a rather unforgiving user environment, that happily replaces bad
versions of us with better working versions and thus culls the herd
(biologists often call this "survival of the fittest")
- massive undirected parallel development ("trial and error")

I'm deadly serious: we humans have _never_ been able to replicate
something more complicated than what we ourselves are, yet natural
selection did it without even thinking.

Don't underestimate the power of survival of the fittest.

And don't EVER make the mistake that you can design something better than what you get from ruthless massively parallel trial-and-error with a feedback cycle. That's giving your intelligence _much_ too much credit"

iow Linus is talking of biological evolution. the key point is "massively parallel feedback" an "ruthless, blind enviironments". How is this relevant to tdd ?

tdd == emergent design driven by massive parallelism and availability of source code since when?

bleh!

Anonymous said...

What Ravi said was

"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."

see the word "just"?

Let me indulge in some pseudo logic now.

1. The Theory Of Evolution is a scientific theory.

2. Agile/XP/TDD(take your pick) is an evolutionary process. Therefore it too has a scientific basis.

3. So Agile is the methodology that has scientific backing!


wow! I should inform the agile alliance immediately. Do you think I could get a Turing Award? The logic in the 3 sentences above is flawed because one sentence(hint one of two statements in (2) ) makes an invalid assertion.

Sarcasm aside, I believe it is incumbent on commenters to react to what was actually said by the author, not what they think he said. And what was said by the author turns on the word "just". Read that sentence out loud again.

What Linus said, while very interesting in no way (logically) contradicts anything Ravi said.

Equating TDD to evolution is utter foolishness. Jason didn't do this, strictly speaking. for that matter neiether did Linus.

I think Jason's point was that Linus says that the linux kernel evolves and is consequently much better than other unix kernels.

How this clashes with Ravi's point that good design does not emerge *just* from the test-code-refactor cycle, I am not able to make out.

Linus is talikg of evolution. Ravi is talking about TDD. Unless someone can prove that "TDD= evolution", (not just draw an analogy) Ravi and Linus are making at best parallel and at worst unrelated statements. In other words, What Ravi says does not contradict what Linus says and vice versa.

Ravi states that the (emergent or otherwise. This is an orthogonal dimension) design of "complex software" (of which the Linux kernel is an instance. Ravi uses an "optimizing compiler backend" as another example) cannot be designed with TDD alone.

fwiw, I agree. The easy way to disprove this assertion is to show a counter example. Does anyone know of any TDD OS kernels? or "optimizing compiler backends"(whatever those are).

Anonymous said...

Jason said
>>Read what Linus has to say about designing Linux.

http://kerneltrap.org/node/11

Not TDD (which isn't === Agile by the way) but emergent design.<<

I take it that Jason has assumed that Ravi is saying things against "emergent design" and posted a link to a discussion where Linus is talking about software evolution.

Ravi's blog post is not about "emergent design" at all. He just mentioned that he does not accept the idea of "emergent design" through TDD grinding.

Jason also points out that "TDD isn't === Agile". I don't see where Ravi gives the impression that it is otherwise. May be the following fragment (which is a question that a friend of Ravi asked) prompted Jason to point it out- "Will you be coding the compiler in an Agile fashion? I mean using TDD etc?".


Thanks,
Rajesh Babu

Ravi said...

Rajesh,

you say
"May be the following fragment (which is a question that a friend of Ravi asked) prompted Jason to point it out- "Will you be coding the compiler in an Agile fashion? I mean using TDD etc?"."



You are right. I never claimed TDD= agile. This is another instance of "commenters reading what the author didn't say" in Joes' words.

A quote is exactly that, a literal quote.

I zeroed in on TDD by the second paragraph. The only other places where XP or Agile come in are when discussing points made by Ralph Johnson or mayan or Ron Jeffries or Tom Cargill or Don Wells.

Anyway the sentence that seems to have provoked Jason's reaction was "Maybe we should perusade Linus to "TDD" the Linux kernel." I particularly mention TDD (not agile or xp) here.

While I would like to see a good TDD-ed kernel or TDD-ed optimizing compiler backend (a good one), there are fundamental reasons why such a feat is impossible. Other than Ron who refused to answer any of MAyan's hard questions no one else has even claimed these things are possoible let alone that someything like that actually exists.

And no , Linus saying that millions of people working on the open source Linux kernel make it more robust than Sun's kernel does not imply that TDD can be used to create one.

Wishful thinking is one thing. Reality is quite another.

Ravi said...

Delete
Ravi said...

Ok I read the actual "Linus comments on design" thread.

You missed this one

some choice quotes..

Linus (referred to as the "academic twit" etc in the post) said ..

"However, I still would not call "pthreads" designed.

Engineered. Even well done for what it tried to do. But not "Designed".

This is like VMS. It was good, solid, engineering. Design? Who needs design? It _worked_.

But that's not how UNIX is or should be. There was more than just engineering in UNIX. There was Design with a capital "D". Notions of "process" vs "file", and things that transcend pure engineering. Minimalism.

In the end, it comes down to aesthetics. pthreads is "let's solve a problem". But it's not answering the big questions in the universe. It's not asking itself "what is the underlying _meaning_ of threads?". "What is the big picture?". "

and also

"> Think about WHY our system call latency beats everybody else on the planet. Think about WHY Linux is fast. It's because it's designed right. "


This sounds a little different doesn't it? Of course, here I am guilty of doing what someone else did. Providing random quotes lifted out of context in an attempt to contradict a point that was never made. So I apologize. But I couldn't resist :-)


The day someone designs a threading mechanism or any other significant part of an OS kernel using TDD, my point about TDD being an inadequate *design method* in complex contexts will be proved wrong.

oh btw the original linus quotes can be found
here Fascinating reading.

Jason Yip said...

Hi Ravi,

I didn't actually make an argument. I just provided a link.

Evolutionary design with TDD is not supposed to be blind, http://jchyip.blogspot.com/2004/12/evolutionary-design-using-tdd-is-not.html

So if all you're saying is that blind TDD doesn't work well, then sure I'll agree but they way I'm reading this is that you're saying TDD = blind TDD.

To Rajesh:
The Agile != TDD comment comes from the initial question from the "friend", the implication that XP means design with blind TDD, and that Agile falls flat on concurrency because blind TDD falls flat on concurrency.

Ravi said...

Jason,
"I didn't actually make an argument. I just provided a link."

right you are. It sounded like a rebuttal. Sorry for the misinterpretation. My bad.

"the way I'm reading this is that you're saying TDD = blind TDD."

I am saying that whatever tdd (or the tdd practitioner to be more precise) "sees" is not *enough* to evolve a design (in some specified contexts).

So it is not so much a matter of blind/sighted tdd as the type and acuity of vision needed to design in certain contexts (kernels compilers massivelyy parallel programs) being different from the "vision" of the design space provided by (even the best possible) tdd.


I've already said that TDD works in the normal (business) app dev space (I've seen it fall down there too but I am not sure there weren't other issues involved so I don't claim it is a TDD problem).

Over the last two years (after leaving TW) I have consistently encountered situations( mostly involving programs with masssive concurrency requirements, running on supercomputing clusters -millions of "threads" -using non oo paradigms) where TDD is plain ineffective (as a *design* method). With an upcoming compiler project, it again looks as if TDD won't serve. So this is hardly some kind of empty theorizing :-). I *need* to know this stuff :-)

If design of massively parallel programs involving hairy math and design of compilers could be done with TDD, no one would be happier than I.

Alas, this is simply not possible. This is not the "fault" of TDD, any more than its is a hammer's "fault" that it is a poor screw driver. Different contexts need different tools.

What I oppose is making TDD (or anything else) into some kind of universally superior tool appropriate for *all* contexts and substituting blind belief for pragmatism.

Again, apologies if I saw an argument where there was none. Your comments are certainly highly appreciated. The kernel-dev thread made for intersting reading!

Thanks again,

Anonymous said...

Hopefully "pliant" won't become the next religion.

It certainly won't become a religion on my watch. I like learning from history... it is a little hobby of mine. :)