by Edsger W. Dijkstra

isbn: 013215871X
subject: Nonfiction, Computing, Mathematics
finished: 12/29/2001

Although programming languages and techniques differ widely, it is the case that virtually every sizable computer program ever written has achieved robustness through testing and is inadequately understood even by its designers. Dijkstra believes that this method of constructing computer programs is fundamentally broken. Rather, programming should be viewed as an exercise in manipulating logical predicates in such a way that a desired predicate can be shown to have been established upon termination of a program. In other words, we don't write a program and hope that it's correct; we don't write a program and then try to prove it correct; rather, we develop the program and proof concurrently -- the program is then correct by construction. From this point of view, the fact that a program can be executed by an actual machine is almost incidental. Practically speaking, there are two main problems with Dijkstra's approach. First, it isn't how programming is taught. Second, most of us find it incredibly difficult to apply in practice, and this difficulty translates to economic infeasibility for real-world development efforts.

A Discipline of Programming begins with the development of a bare-bones programming language; its syntax and semantics resemble those of Pascal augmented with nondeterministic guarded commands. The rest of the book consists of essays and solutions to a number of increasingly difficult programming problems, culminating with computation of a convex hull in three dimensions. I found this book to be quite challenging. Dijkstra admits as much, and claims that it is a result of the inherent difficulty of the material, as opposed to being a result of poor presentation. I think he's right: the book is well-written and rigorous reasoning about programs (or anything else complicated) is tremendously hard -- our brains are little and the world is big.

To evaluate A Discipline of Programming I think we need to ask two questions. First, does it accomplish its goals and second, is it important in a larger sense? Certainly the book accomplishes its stated goal of presenting attractive, formal solutions to a number of programming problems. I suppose the book is important in a larger sense only if it effectively convinces people to program differently. Speaking only for myself (obviously Dijkstra's methodology has not taken over the world in the two decades since the book was published), it won't have a direct impact on the way I program, but I suspect it will have an indirect impact through the way I think about problems. I look forward to rereading this book in a couple of years -- maybe then I'll even do the exercises. This is a book that computer scientists should read, if only to be exposed to this type of thinking.