Writing correct code, part 3: preconditions and postconditions (binary search part 4c)

Having dealt (briefly and informally) with invariants and bound functions in the two previous installments of this series, it’s time to look at preconditions and postconditions.  These will likely be familiar to most of you, even those who’d not heard of invariants before, because these days they are known by the trendy, XP-friendly name design by contract.  (OK, it’s not quite the same thing; but they’re closely related concepts.)

Writing correct code, part 2: bound functions (binary search part 4b)

Following on from yesterday’s article on invariants, this time we’ll talk about a second tool in the kit for thinking about code.  This one will be much shorter, because the Concept Of The Day is so simple.  It gets talked about even less than invariants, but let’s change that!

(Oh, and today is vegetarian-friendly Cheese Day at The Reinvigorated Programmer, though it still may not be much use to the vegans among you.)

What free music-studio software should I use?

A quick question, since you’re all here.  (I promise to post the article on bound functions tonight, this one is not the day’s main article.)

I would like, if I can, to use an open source program as a music studio — something that I can use to record individual tracks from a line in (microphone, piano, etc.), record one track while listening to others, mix down to stereo, export as .wav, etc.  I am using Ubuntu GNU/Linux 9.10, so Windows-only programs are no use to me.

Because I have never done this before, I have no idea whether the program that I want even exists, and if so what it’s called, or whether there are competing alternatives, or what.  I’m guessing that for those in the know, there a single The Right Answer, just as the GIMP is the The Right Answer for photo manipulation and OpenOffice for WYSIWYG document preparation.  (I know that there are alternatives to both, but they are clear category leaders.)

Writing correct code, part 1: invariants (binary search part 4a)

I’m struggling with my article numbering now :-)

Regular readers will have noticed that I am running a whole bunch of series in parallel on this blog: one reviewing programming books, one on the issue of simplicity in programming, one reviewing Series 5 of Doctor Who, a related one on Russell T. Davies’s contributions, and one on learning Lisp.  To my huge surprise, what started out as a review of Jon Bentley’s book Programming Pearls [amazon.com, amazon.co.uk] has led through a sequence of digressions and become a series of its own on binary search.  This is part 4 of that series: when I’ve finished part 4, I will — at last! — progress to the actual review.  But since part 4 is about the distinctly non-trivial subject of writing correct code, it will itself have to be composed of multiple sub-parts.  So this article on invariants is both part 1 of the new writing-correct-code series and part 4a of the binary-search series.  Hope that’s clear.

A few people have complained about the sushi pictures on this blog, so before I plough into the article proper, here is something completely different.

The Time of Angels (11th Doctor, episode 4)

[A revised and improved version of this essay appears in my book The Eleventh Doctor: a critical ramble through Matt Smith’s tenure in Doctor Who.]

12:12pm — zero minus six hours

I don’t plan to make a habit of starting my reviews of Doctor Who Series 5 before the episode airs, as I did with The Beast Below.  But I wanted to get my thoughts down about the Weeping Angels beforehand, because they worry me.  Although I’ve avoided watching the trailer for this week’s episode, it would hardly be possible not to know that it’s the first of a two-parter featuring these creatures.  Their only previous appearance was in the Tenth Doctor episode Blink, also written by showrunner Steven Moffat, which by common consent is among the very best episodes of the revived series.  Among other accolades, it won the 2008 Hugo Award for Best Dramatic Presentation, Short Form.  I concur with majority opinions here — Blink is quite brilliant.

Testing is not a substitute for thinking (binary search part 3)

The contributions to the original binary search thread continue to trickle in, and now stand at an astonishing tally of 679 comments, most of them containing code.  Thanks once more to all of you who’ve attempted this challenge, and to everyone who’s commented.

In one of the more interesting comments, Darius Bacon tested a sample of 20 of the Python submissions, and found that exactly 10% of them both passed the functional test and appeared to run in O(log n) time — which of course is exactly in line with Jon Bentley’s original statistic, that 10% of the professional programmers he’d examined were able to write correct binary search code (albeit under rather different conditions).  It subsequently became apparent, though, that Darius’s testing code was overly strict, and that a further two of the sampled routines did run correctly (though not necessarily in O(log n) time).  Still — it’s a surprisingly low hit-rate, especially when you bear in mind that, contrary to the rules, many of the programmers did use testing to help them develop the code. (You should read the second linked comment, as it has plenty of other interesting observations, too.)

[Update, an hour or two later: as Darius Bacon points out in a comment below, I misinterpreted his results.  Once the testing code had been fixed, his sample of 21 routines found 9 that passed all test, of which 6 were O(log n).]

Common bugs and why exercises matter (binary search part 2)

Many, many thanks to all of you who have contributed to the astonishing response to the previous article on the difficulty of getting binary search right.  I’ve never seen anything like this: in just over 24 hours since I posted the article, 541 comments have been posted, and they’re still rolling in.  (That number is a bit inflated by people re-posting the same code-samples multiple times after seeing WordPress mangle their source, but even taking that into account it still amazes me.)

You guys rule.  Seriously.

I have a lot to say in response to it all.  Read on …

Are you one of the 10% of programmers who can write a binary search?

There are some programming books that I’ve read from cover to cover repeatedly; there are others that I have dipped into many times, reading a chapter or so at a time.  Jon Bentley’s 1986 classic Programming Pearls is a rare case where both of these are true, as the scuffs at the bottom of my copy’s cover attest:

(I have the First Edition [amazon.com, amazon.co.uk], so that’s what I scanned for the cover image above, but it would probably make more sense to get the newer and cheaper Second Edition [amazon.com, amazon.co.uk] which apparently has three additional chapters.)

Oh, and by the way …

River Song.  Jackson Lake.  Amy Pond.  Coincidence?

Just saying.

If the next story introduces a character called Adrian Aqueduct, I guess we’ll be able to draw our own conclusions.

Victory of the Daleks (11th Doctor, episode 3)

[A revised and improved version of this essay appears in my book The Eleventh Doctor: a critical ramble through Matt Smith’s tenure in Doctor Who.]

If The Eleventh Hour was very obviously a new start for Doctor Who, and if The Beast Below was where the new series hit its stride, then the third episode, Victory of the Daleks, represents another new challenge: it’s the first episode under the new regime to be written by someone other than showrunner Steven Moffat himself — specifically, Mark Gatiss, previously responsible for Series One’s highly regarded The Unquiet Dead and Series Two’s widely derided The Idiot’s Lantern.  With his previous work varying so wildly, Gatiss still has plenty to prove as a Who writer, and it was brave of Moffat to entrust him with the Doctor’s oldest and most iconic enemies, the Daleks.