TITLE: Edsger Dijkstra, Test-Driven Developer
AUTHOR: Eugene Wallingford
DATE: July 28, 2004  2:10 PM
DESC: tests as proof of correctness
-----
BODY:
I don't usually think of Edsger Dijkstra as an "agile methods" kind of
guy, but yesterday as I re-read "The Humble Programmer", his 1972 Turing
Award lecture, an interesting connection formed in my mind.  (I ran
across this paper again at
<A HREF="http://weblogs.java.net/pub/wlg/1694">Malcolm Davis's blog</A>.)

As a part of Dijkstra's argument that it is possible for computer
scientists to develop large programs at reasonable cost, he considers
the problem of correctness.  The value of testing as traditionally
practiced is limited:

<BLOCKQUOTE>
... program testing can be a very effective way to show the presence
of bugs, but it is hopelessly inadequate for showing their absence.
</BLOCKQUOTE>

So, rather than write code then test it, or even write code then prove
it correct,

<BLOCKQUOTE>
... the programmer should let correctness proof and program grow hand
in hand. ...  If one first asks oneself what the structure of a
convincing proof would be and, having found this, the constructs a
program satisfying this proof's requirements then these correctness
concerns turn out to be a very effective heuristic guidance.
</BLOCKQUOTE>

This sounds a lot like test-driven development to me.  The tests
in TDD are really more about <I>specification</I> than testing, and
as such act as assertions, or delimiters of correctness.  Each test
is a claim about what the code should do.  A test guides the development
of a part of the code, and the body of tests and the program grow
hand in hand.

Dijkstra would certainly argue for a systematic and sound development
of tests that define the system, but I do think he would appreciate
TDD's emphasis on writing tests first.

This lecture has so many neat ideas that resonate today, from the
value of patterns to language design to the conservatism of the
academic computer science community.  I will save some of those ideas
for other days.

However, I can't resist quoting Dijkstra on the importance of
computing.  The conclusion of the paper is worthy of a Turing Award
lecture and offers a deeply inspirational message.  Two quotes stand
out for me.  First,

<BLOCKQUOTE>
[Computers] have had a great impact on our society in their capacity
of tools, but in that capacity their influence will be but a ripple
on the surface of our culture, compared with the much more profound
influence they will have in their capacity of intellectual challenge
without precedent in the cultural history of mankind.
</BLOCKQUOTE>

And then later,

<BLOCKQUOTE>
This challenge, viz. the confrontation with the programming task, is
so unique that this novel experience can teach us a lot about
ourselves.  It should deepen our understanding of the processes of
design and creation, it should give us better control over the task
of organizing our thoughts.  If it did not do so, to my taste we
should not deserve the computer at all!
</BLOCKQUOTE>

The desire to understand creation and design better is exactly what drew
me to computer science in my undergraduate days, what led me to study AI
as a graduate student, and what continues to drive me today.  Dijkstra's
position also reminds me of Alan Kay's forty-year advocacy that we can
-- must -- do so much more with computers than we currently do, that the
digital computer can fundamentally alter how we create and communicate
ideas.  We are lucky to be guided by such visionaries.

But, as Dijkstra might say, do we deserve them?
-----