Friday, September 11, 2009

Sudoku in Coders At work

Once upon a time, I wrote this blog entry. Peter Norvig references it (indirectly) in his interview in Peter Seibel's great new book "Coders At Work".


"Seibel: Though your job now doesn’t entail a lot of programming you still write programs for the essays on your web site. When you’re writing these little programs, how do you approach it?


Norvig: I think one of the most important things is being able to keep everything in your head at once. If you can do that you have a much better chance of being successful. That makes a small program easier. For a bigger program, you need extra tools to be able to handle that. It’s also important to know what you’re doing. When I wrote my Sudoku Solver, some bloggers commented on that.

They said, “Look at the contrast—here’s Norvig’s Sudoku thing and then there’s this other guy, whose name I’ve forgotten, one of these test-driven design gurus. He starts off and he says, “Well, I’m going to do Sudoku and I’m going to have this class and first thing I’m going to do is write a bunch of tests.” But then he
never got anywhere. He had five different blog posts and in each one he wrote a little bit more and wrote lots of tests but he never got anything working because he didn’t know how to solve the problem. I actually knew—from AI—that, well, there’s this field of constraint propagation—I know how that works. There’s this field of recursive search—I know how that works. And I could see, right from the start, you put these two together, and you could solve this Sudoku thing. He didn’t know that so he was sort of blundering in the dark even though all his code “worked” because he had all these test cases.

Then bloggers were arguing back and forth about what this means. I don’t think it means much of anything—I think test-driven design is great. I do that a lot more than I used to do. But you can test all you want and if you don’t know how to approach the problem, you’re not going to get a solution.

Seibel: So then the question is, how should he have known that? Should he have gone and gotten a PhD and specialized in artificial intelligence? You can’t know every algorithm. These days you have Google, but finding the right approach to a problem is a little different than finding a web framework.

Norvig: How do you know what you don’t know?
Seibel: Exactly.

Norvig: So I guess it’s two parts. One is to recognize that maybe there is a known solution to this. You could say, “Well, nobody could possibly know how to do this, so just exploring randomly is as good as everything else.” That’s one possibility. The other possibility is, “Well, probably somebody does know how to do this. I just don’t know what the words are for it, so I
have to discover those.” I guess that’s partly just intuition and saying, “It seems like the kind of thing that should be in the body of knowledge from AI.” And then you have to figure out, how do I find it? And probably he could’ve done a search on Sudoku and found it that way. Maybe he thought that was cheating. I don’t know

.
Seibel: So let’s say that is cheating—say you were the first person ever to try and solve Sudoku. The techniques that you ended up using would still have been out there waiting to be applied.

Norvig: Let’s say I wanted to solve some problem in biology. I wouldn’t know what the best algorithms were for doing gene sequencing or whatever. But I’d have a pretty good idea that there were such algorithms. Then I could start looking around. At another level, some of these things are pretty fundamental—if you don’t know what dynamic programming is, then you’re at a severe disadvantage. It’s going to come up time and time
again. If you don’t know this idea of search in general—that you can make a choice and backtrack when you don’t need it. These are all ideas from the ’60s. It was only a few years into programming that people discovered these things. It seems like that’s the type of thing that everyone should know. Some things that were discovered last year, not everybody should know.


Seibel: So should programmers go back and read all the old papers?
Norvig: No, because there are lots of false starts and lots of mergers where two different fields develop completely different technology and terminology, and then they discover they were really doing the same thing. I think you’d rather have a story from the modern point of view rather than have to follow all the steps. But you should have them. I don’t know what the best books are for that since I picked it up the hard way, piecemeal."


Dr. Norvig is a much nicer (and wiser) person than I am. I (completely) agree with him that bloggers' blather (including mine) doesn't mean much and TDD is great as one (vs the only) tool in one's arsenal.

That said, I still think many so called "agile" "gurus" can't program for nuts, as Jeffries so amply demonstrates. It is hypocrisy of the first order that people who don't know how to program well advise the rest of us how to. The "agile" movement brimmeth over with such pseudo programmer snake oil salesmen.

"These are all ideas from the ’60s. It was only a few years into programming that people discovered these things. It seems like that’s the type of thing that everyone should know."

"Should know" is correct. It is also true that most "developers" wouldn't know Dynamic Programming if it showed up at the front door and slapped them silly.

One reason for this is that most "enterprise" programming uses essentially two data structures, the List and the Hashtable and most language implementations provide default implementations of these. And a lot of "programmers" do this all their lives and think they are cool because they drank the latest/greatest shiny methodology Kool Aid. And these folks get the "gurus" they deserve!

"Seibel: What about the idea of using tests to drive design?

Norvig: I see tests more as a way of correcting errors rather than as a way of design. This extreme approach of saying, “Well, the first thing you do is write a test that says I get the right answer at the end,” and then you run it and see that it fails, and then you say, “What do I need next?”—that doesn’t seem like the right way to design something to me."


heh! heh!

Anyway, it is great that something I wrote got reflected, however indirectly, in this great book.


Coders at Work is a great book with legendary programmers talking in great detail about many aspects of programming. It is very interesting how Peter Seibel (the author) has captured each "voice" so perfectly. Every programmer should read this book, *especially* if you are stuck in a sucky job writing leasing systems (or accounting systems or whatever).

"What power would Hell have if those imprisoned there were not able to dream of Heaven?" as the Dream King says in Neil Gaiman's "The Sandman", but even at the cost of granting Hell some power, do dream of Heaven, say I, for that way lies eventual redemption.

This book provides a glimpse of what programming looks like for people who are already "in heaven".

23 comments:

himanshu said...

The thing about tests is very correct, they should only be used as *tests* i.e. to check if something is right/wrong. People have the tendency to always exploit the good things to a level where they lose their original meaning. So, probably some of those people did this evolution of test -> test driven development -> test driven design

Anonymous said...

"they should only be used as *tests* i.e. to check if something is right/wrong. "

And by using them as a regression suite, to continue to ensure that things are *still* right (or wrong).

Use of tests to "design" is crazy.

chandrakant said...

You had me with the Sandman reference :)
Just kidding, thanks for the excerpt, I think I will buy this one.

Nested said...

I believe the big problem is the ambiguity in the word 'design'. Clearly there are situations where you need to know your over-arching algorithm ahead of time, but that's not always the case. Sometimes you really do have to develop pieces of working code one step at a time and re-evaluate as you go along (whether you write tests as you go is a separate issue). To me 'design' is mostly about the algorithm, i.e. how to solve the problem irrespective of programming language. How do I fill this polygon? How do I encrypt this file? How do I sort this large data set? etc... A separate is step is shaping the code. This is also sometimes referred to as 'design'. This is the step where I think a test-driven approach can be helful in a number of ways: improving the clarity of the code, checking for correctness, and regression.

Nested said...

A more elaborate reply:

http://vladimirlevin.blogspot.com/2009/09/spy-vs-spy.html

Ravi said...

Vlad,
I don't have much time but this will have to be short.

It seems you are on a mission to defend TDD as a "design" method by changing the meaning of "design" to fit! (which is fine by me of course!)

I agree with much of what you say, for example,

"TDD is a technique to help you write better code. "

This is perfectly correct and on the dot. I call it Tests Driven Coding. I even use it sometimes when using an OO/imperative language(vs something like Haskell).

But what you call "hill climbing"( where you say TDD helps) sounds suspiciously like what Mr Jeffris does, blundering around thrashing.

My (and Norvig's) point is that even when you do this, you have to have some elementary knowledge of things that were discovered in the sixties. Things like dynamic programming. This will ensure that you have to "hill climb" only in situations that really call for it.

And when you have to do *real* hill climbing , when you are trying to do domething which doesn't have any literature supporting it, , *TDD* is still of little use. (If you think otherwise, please point me at a research paper where someone actually discovered a new algorithm using TDD)


You'd do better thinking, forming a hypotheses, writing a quick prototype, observing results and forumatng the next hypothesis. TDD is incidental to this process.

Once your understanding has been refined, you can then doa TDD for the final implementation.

So there are two kinds of "hill climbing". One is when you are in a genuinely new situation where you are doing research on the frontiers of human knowledge. Here, sure you do "hill climbing", but you start the climb equipped with the best mental tools you know. Nobody parachutes into unexplored woods without shoes and a compass and nothing to eat or drink starts blundering around and calls it "exploring".

Jeffries "hill climbing" (the second kind) is that of someone who is clueless about the fundamentals of his craft (and no algorithms are not something exotic and "edgy"). Basic algorithms should be understood by *every* programmer *before* he sets out to do "TDD" or "RUP" or whatever.

A decent "structure of the code" (which TDD provides, if done right) is of no use if the person writing the code is an idiot without knowledge of the fundamentals of the craft, which in my opinion Mr Jeffries(along with a large contingent of agile preachers) is.

And no solving a sudoku puzzle is not "algorithm discovery", any more than writing a for loop is "programming language research".


Dismissing writing a sudoku solver as a a problem of "algorithm discovery", is intellectual laziness. It is "discovery" only for people who don't know their trade.

Marcel said...

This is perfectly correct and on the dot. I call it Tests Driven Coding.

Good. The next thing you need to understand is "the code is the design". That makes "test driven coding" a form of design - coding is design. Once you grok that, you can understand the meaning of TDD :)

Ravi said...

"the code is the design"

Sure. The building is the plan, the play is the script and the music is the sheet of paper with the funny squiggles on it ;-)

The code *embodies* the design. It isn't the same thing. Anybody who thinks they are the same hasn't been writing code long enough.


Better people than you (e.g Martin Fowler) have made an argument for this notion. And it is still not very credible.

It would be a valid argument if its practitioners could *show* us examples of superior code they wrote/shipped this way.

The book "Coders At Work" (which is the topic of this post btw ;-) )
deals with people who *have* programmed great works in software. And not *one* of them thinks TDD is a method of *designing* code (vs building a regression suite, or trapping an error and so on). And in the lines quoted above, Peter Norvig explicitly doesn't agree with this "extreme notion"

Allow me to quote (since you obviously haven't *read* the post)

"This extreme approach of saying, “Well, the first thing you do is write a test that says I get the right answer at the end,” and then you run it and see that it fails, and then you say, “What do I need next?”—that doesn’t seem like the right way to design something to me."


On matters of *programming* Peter Norvig is much more credible than the agile gaggle.



The people who promote TDD as a design method on the other hand have ZERO intersection with great programmers and have nothing *to show*.

They just *talk* about how cool their "design method" is. When it comes to actual coding with TDD they end up like Mr Jeffries with his Sudoku solver. That Mr Jeffries and other fanatics like Bob Martin are leading lights for this "design method" and accepted as such by its practitioners is all that needs to be said.


When people start thinking coding and designing are identical you get horror shows (again like Jeffries's Sudoku Solver).


Nice Try anyway.

Look if you "design" your code with TDD and the people who pay you are foolish enough to let you get away with it,I don't care. Go right ahead. Don't come here and preach your kool aid religion.

I'll happily live in the "Stone Ages" of programming.

Marcel said...

The building is the plan...

Ahh... here's the problem. You're building hardware. I thought we were discussing software. Hint: we don't use cement in software; we keep it SOFT. We keep changing it. That's what makes it design instead of rocks.

Oh well. You'll learn. Oh, and you might want to google the phrase before long... there's a tiny chance you might learn something.

Ravi said...

Ahh more foolishness from the agilist hordes.

"Hint: we don't use cement in software; we keep it SOFT. "

Look I *said* Martin Fowler said this much better than you.

"That's what makes it design instead of rocks."

heh Music is even "softer" than software. No capable musician has a problem distinguishing design performance. No playwright has a problem distinguishing plotting and performance.

Instead of blindly repeating what Fowler said, do some thinking for yourself.

Instead of blathering about how superior your "design method" is on other people's blogs, why don't use that superior design method to write some great code.

Here'e the challenge.

Show us. Don't make sales pitches.

Show. Superior. Code.

THEN preach.

Simple Idea isn't it?

When people using TDD as "design method" write great codebases/software products at the level of the people interviewed in CaW, THEN tell us how you did it.

Till then take your religious blabbering elsewhere. While your "masters" stumble around for days on simple problems with your "superior design method" you have zero credibility.

Peter Thomas said...

I'm waiting eagerly for Marcel's next comment. For the comedy.

Ravi said...

"I'm waiting eagerly for Marcel's next comment."

Heh. I am sure he is off somewhere using his superior TDD based design skillz to build a world beating product to show us unbelievers the efficiacy of his religion.

I am sick of stupid agile zealots who preach at others. They tell others how to write code but never write any great code themselves.

Ravi said...

Vlad,
"too soft to matter" is a value judgment.

Also I wasn't talking about music on a CD (then we'll have to talk about a sw binary on a CD) , but music as in an orchestra.

"You can change a piece of music as much as you want to as you're working on it without any repercussions."


Do you play any instrument or sing? The above is completely wrong. The "repercussion" in music is cacophony and people throwing eggs at you.

You can change a piece of sw as much as you want, if you now how. . A partuclar change might sound cacophonous in music or give odd results with sw. Changes have consequences.

"Once a piece of music is published/recorded, that's it, just as with a novel or a skyscraper"

Ditto SW burned onto a chip or CD.

Anyway you are on teh wrong track. My point wasn't to say music was exactly equivalent to sw in all aspects. No two things are exactly equivalent.

Marcel was ignoring the main point I made("Design" in not unque to sw and is distinct from an embodiment of the design. Nor is the "softness" of sw *unique*.)

Naivete is different from wilful foolishness.

Marcel said...

About two years ago, I exchanged a couple of emails with Mr. Norvig - as it happens, about that exact Sudoku program. I wrote one, and mine was in a compiled language (Delphi) and it was SLOWER than the times he reported for a Python program. I couldn't figure out the reason - the solver had a similar architecture, I had optimizations on, so he assumed he was using better hardware. He's a nice guy. But... I don't know him from Joe.

The problem with a lot of people is that they worship authority. For various reasons (like an incredible ego), I don't. I only care about stuff that makes sense to me, no matter who is saying it. So "Peter Norvig says X" is absolutely meaningless to me... and I can't argue with it, because it's not an argument; it's a childish, emotional statement.

Misko Hevery's writings make a lot of sense to me. So do those of Daniel Cazzulino. When Misko says "don't use the new keyword because you're mixing stuff that shouldn't be mixed" - I read, I think, and I agree. When he says "here's how I know TDD is good: because it enables me to do X and Y" - I read, I think, and I ultimately agree.

On the other hand, most people prefer not to think. Thinking is hard, and they would get it wrong anyway. Instead, they cheat - they pick someone famous who agrees with their preconceptions and say "look, this guy says X, he's more famous than you, so there". That, for them, is enough. I'd have assumed that only americans do that (I indicate my reasoning on my blog), but apparently it's more widespread than this.

Oh well. I have code samples on my blog; not developed using TDD unfortunately (I really need to do that sometime), but I'm pretty happy with where I am as a programmer. So don't worry - I really don't care to measure dick sizes or anything. Go and program with my blessings, and may the best programmers win.

Nested said...

I don't want to belabour my point too much since it's tangential to the main thrust of your argument about design, wherein I think we largely agree anyway. Still, I am tempted to clarify a bit:

My sense is that software is rather special in the particular way it is expected to be soft, and this does indeed have ramifications vis. ongoing design. To compare I offer an example of something much softer and something much harder, both being qualitatively different (imo):

Let's say I publish an online book, or a blog. I can change the contents, and *publish* those contents live, at any time. If it's a story, I can change any aspect of the plot, the names of the characters, the order of the chapters, etc. The worse thing that that could happen is it may be a little confusing for some readers. If I make changes that people don't like, well, it's a matter of taste, but you can't say it "doesn't work" in any sense that is completely objective.

Now for something truly as hard as a rock: Once you've actually put up a skyscraper, you are basically stuck with what you've got. Even minor changes, like say adding one extra story, become prohibitively expensive. Making ongoing changes to a building that is already "in production" is very difficult.

Software occupies a weird middle ground. Once software has been published, either as a CD or as a live Web application, the same code is expected to undergo continual change over the lifetime of that piece of software. On one hand, making even a seemingly innocuous change to a piece of software can *break* that software. On the other hand, it is in indeed *possible* to make such continual updates to "live" software in a way that isn't really possible for physical structures.

Without getting into TDD at all, that is why the design of software generally should to be fairly abstract and loosely coupled, and that's also why having a reasonable suite of automated tests is pretty much non-negotiable for any real piece of software that's out there.

Ravi said...

Vlad
"don't want to belabour my point too much since it's tangential to the main thrust of your argument about design, wherein I think we largely agree anyway."

I agree we are largely in harmony.

"I can change any aspect of the plot, the names of the characters, the order of the chapters, etc. The worse thing that that could happen is it may be a little confusing for some readers. If I make changes that people don't like, well, it's a matter of taste, but you can't say it "doesn't work""


Huh but that *is* exactly how stories "work".

As you said, let us not go down this rabbit hole?

"On the other hand, it is in indeed *possible* to make such continual updates to "live" software in a way that isn't really possible for physical structures."

You can have updates to music or a play too.And you ignore Sw on a CD or a chip and restrict yourself to server side sw. You can *update* at the risk of something breaking. True for everything.


"that is why the design of software generally should to be fairly abstract and loosely coupled, and that's also why having a reasonable suite of automated tests is pretty much non-negotiable for any real piece of software that's out there."

Ahh but no one is arguing automated tests are bad. We are talking about using TDD( which is NOT having a suite of automated tests to assure regression) as a design method.

Ravi said...

"But... I don't know [Peter Norvig] from Joe."

Heh I figured :-) And it shows in your ramblings.

"I only care about stuff that makes sense to me, no matter who is saying it. So "Peter Norvig says X" is absolutely meaningless to me... "

As do I. Replace Peter Norvig with Jeffries or Marcel.

The difference is, Peter Norvig's competence is obvious in the superior *code he wrote *.

Jeffries' stupidity is obvious in the *code* he wrote with TDD.

So who should we listen to again? :-P You agile morons are hilarious.

Your inanities are rejected by programmers because they don't make sense and are not valid and because you don't have the superior code to validate your supposed superior design methodology, not on the basis of your level of fame.

You have a *claim* about having a superior dessign method in TDD. and you preach it endlessly, including on other people's blogs. You just don't have the code to back it up. All hat No cattle.

"On the other hand, most people prefer not to think. Thinking is hard, and they would get it wrong anyway. Instead, they cheat - they pick someone famous who agrees with their preconceptions and say "look, this guy says X, he's more famous than you, so there".
"


This is EXACTLY how agile preachers like you think , as you show just below. This is why your leaders are people who can't code for nuts (Ward Cunnigahm excepted but then he doesn't go around preaching TDD).


"Oh well. I have code samples on my blog; not developed using TDD unfortunately (I really need to do that sometime)"


In other words you don't have any TDD'd code good enough to show that you are a programmer we should listen to, *yet* you preach the virtues of TDD to me on *my* blog comments.

That was *the point*.

I worked on TDD'd projects for years at ThoughtWorks with some of the best agilists in the world - the quiet, "focus on business value and code quality" type of people, not loudmouths like messrs Jeffries and Bob Martin). So when I dismiss TDD as a design method, at least I know what I speak about.

See the difference?

Till you have code at the level of people in CaW, (again this is about code not fame) don't bother telling us that we should listen to you vs them.

"I really don't care to measure dick sizes or anything."

To compare dick sizes you should have one. In this context ,"dicks" = superior code. You don't have any. Hard to compare sizes of non existent dicks.

"and may the best programmers win."

Programming is not a contest, but yeah whatever. Some sanity at last.

Goodbye!

Ravi said...

Vlad,

as always we largely agree and any differences are ones of emphases and phrasing.

Regds,

Anonymous said...

"Marcel: I really don't care to measure dick sizes or anything."

Ravi: To compare dick sizes you should have one. In this context ,"dicks" = superior code. You don't have any. Hard to compare sizes of non existent dicks.

"


Zing! Pwned!

Ravi, you are completely right. Thanking you for taking on this cult. Agilists are the Scientologists of programming.

Hey agilistas, Before telling other people how to code or design, how about showing some results of your superior approaches tools?

less gab. more code.

Otherwise, please, please just SHUT up.


SHUT UP!

Jass said...

I read that interview between norvig and seibel about a couple months back. Did know that, this was the blog that he referred to then. Chanced on your blog today. Lot of interesting posts you got there ravi! Looks like I have a lot of reading to do today. My google reader is already overflowing ;)

Jass said...

oops!I meant to say that I did not know that it was this blog then in my previous comment. ate one word.

Aniruddha said...

You've pretty much hit the nail on the head :) "It is hypocrisy of the first order that people who don't know how to program well advise the rest of us how to." - that is so true !

Bill Yang said...

I prefer not to boil this down to religion, I actually agree with some of Marcel's more concrete point (i.e. read, think then agree), though I ultimately do not agree the usefulness of TDD.

On the other hand, he is also a jerk, as shown in his earlier empty/taunting comments.