This is the third edition of Code Reads, a weekly discussion of some of the central essays, documents and texts in the history of software. You can go straight to the comments and post something if you like. Here’s the full Code Reads archive.
This will be a briefer entry than I originally planned. I’ve fallen behind a bit this week! So rather than post about all three essays I mentioned last week, I’m going to confine myself to “The Humble Programmer,” Edsger Dijkstra’s Turing Lecture, delivered in 1972.
In “The Humble Programmer” (text, PDF) Dijkstra offers an overview of the programming universe as he saw it in 1972. In the ’50s and early ’60s, programming pioneers struggled against the “painfully pinching shoe” of inadequate equipment. Then they got the more powerful machines they longed for. “But instead of finding ourselves in the state of eternal bliss of all progamming problems solved,” Dijkstra wrote, “We found ourselves up to our necks in the software crisis!” The problem was that the upward curve of ambition driven by new hardware capacity outran the improvements in software:
As the power of available machines grew by a factor of more than a thousand, society’s ambition to apply these machines grew in proportion, and it was the poor programmer who found his job in this exploded field of tension between ends and means. The increased power of the hardware, together with the perhaps even more dramatic increase in its reliability, made solutions feasible that the programmer had not dared to dream about a few years before. And now, a few years later, he had to dream about them and, even worse, he had to transform such dreams into reality!
From its title to the repetition of phrases like “the poor programmer” to its references to “the intrinsic limitations of the human mind,” the essay presents a chastened vision of the human capacity to create software: the programmer, Dijkstra says, must be “fully aware of the strictly limited size of his own skull.”
Despite this deliberate lowering of the eyes, Dijkstra does offer a not-so-humble prediction: that, “well before the seventies have run to completion, we shall be able to design and implement the kind of systems that are now straining our programming ability, at the expense of only a few percent in man-years of what they cost us now, and that besides that, these systems will be virtually free of bugs.” The first prediction essentially came true, as the programming field managed to continue to produce increasingly ambitious systems. The second, however, is still nowhere in sight.
Dijkstra presents six arguments for why his prediction is technically feasible, built on the proposition that we should “confine ourselves to intellectually manageable programs.” This sounds sensible, but it will always run up against the nature of software innovation, which always pushes us to try new stuff at the edge of what’s possible, because that’s what’s worth doing.
Mixed in among his other arguments is a prophetic description of a test-first process that developers today would call “test-driven development” (Roy Osherove comments on this as well), and a warning against the sort of language or toolset that invites “clever tricks” (or “the one-liners” — showy stunts aimed at impressing fellow programmers).
There’s something pleasing about the down-to-earth way Dijkstra expresses the strangely-bound-together optimism and pessimism of his world-view, in which the trajectory of software is always progressive — but that very progress is what keeps the process from getting any easier:
Programming will remain very difficult, because once we have freed ourselves from the circumstantial cumbersomeness, we will find ourselves free to tackle the problems that are now well beyond our programming capacity.
I wonder if other readers will have the reaction I had to Dijsktra’s argument that bugs are simply not to be tolerated: “If you want more effective programmers, you will discover that they should not waste their time debugging, they should not introduce the bugs to start with.” If he means, it’s easier to fix errors at the time you make them rather than much later, that makes some sense; but it sounds more like “you simply shouldn’t make any mistakes in the first place.” That would be nice. But it doesn’t sound like the real world programmers everywhere have experienced, all the way back to that seminal moment in the ’40s when Maurice Wilkes realized he would spend a “large part of his life” correcting his own mistakes.
(For a fascinating contemporary argument on why software producers consciously ship products with bugs, Eric Sink’s article is worth a look.)
Post Revisions:
There are no revisions for this post.
Argument three is nothing at all to do with test-driven development; TDD is in fact exactly the sort of thing he said we’d get rid of. Roy Osherove, writing,
gets it entirely wrong. TDD (of which I am a big fan and constant practitioner, incidently) is nowhere near a proof instead of a test; it’s simply moving the testing around, and suffers from the problem Dijkstra mentioned: it can only show the non-presence of particular bugs, not the absence of any bugs. For this we need to
formally verify our code. Some progress has been made on this; tools such as the Z notation have been used to construct programs that are at least in part formally verified.
As for the debugging comments, some people have managed to reduce debugging drastically, and in the real world yet. I’ve spent the last few years working on techniques for comprehensive automated testing, and my debugging load on these sorts of systems has dropped to ten to twenty percent of what it was for the systems I was working on five years ago. Even on large, complex systems, many bugs are fixed in a few minutes, the vast majority within half an hour, and I’ve had only a handful of multi-hour debugging sessions in the past three years. I’ve also stopped using bug databases; the administrative overhead has become higher than the cost of just fixing bugs as soon as they’re discovered.
So no, on that front, I didn’t have the same reaction as you did.
Along the same lines as Curt, Dijkstra’s comment that “you simply shouldn’t make any mistakes in the first place” is not a call for infallibility. If you take a look at his “A Discipline of Programming” (which is admittedly not an easy sit for the general reader) you’ll understand he’s talking about “correct-by-construction” programming. What he advocates is a discipline in which the programmer starts with a statement of correctness, then builds the program step-by-step in a stylized way, ensuring that each step preserves correctness.
It is an extremely interesting and informative way to think about programming. The main problem with it is that the average programmer does not have the subtle and sophisticated mind of Edsger Dijkstra! A lot of work in the verification community has gone into supporting this style of programming with automatic tools, but… well, automated theorem provers aren’t Edsger Dijkstra either. ;-)
Also, to add to what Curt said, “test-driven development” is not the same as “correct-by-construction”, but TDD is a reasonable approximation of formal verification, especially at the limit. A typical statement of correctness would be: “for all inputs, we terminate with the following outputs and nothing bad happens along the way.” What a test suite gives you is a large set of inputs (which is nevertheless far, far fewer than “all inputs”) for which the program terminates with the correct outputs and does nothing bad along the way. As the number of tests approaches infinity, the probability of correctness approaches 1.
Doesn’t
sounds like
?
(That second quote is from No Silver Bullet by Fred Brooks)
Yes it does. There’s a definite echo there that I noticed too. “No Silver Bullet” most definitely demands its own discussion, but since we started with Brooks I plan to return to it down the road.
Curt and Chris: Thanks for the corrections, clarifications and explanations. As Dan Gillmor says, “My readers know more than I do.” On this topic that is surely the case.
The most poignant comment was the one about society not tolerating that hardware cost is going down and programming cost going up. Yet, this is exactly what has happened.
I consider the absolute worst programming construct to be subroutine or the function. We’ve used it for over 50 years now and we’re still having difficulty reducing complexity. What if the unthinkable were true? What if the subroutine was the cause of all our problems? I can prove how the subroutine causes all parts of our software to become coupled and as such cannot support this as the basic building blocks of software.
I find the subroutine and all the technology around it (OOP, functional, AOP, etc.) are like a sinking ship where you keep throwing more lifeboats when what you really need is a new boat. (The ship being the subroutine and the lifeboats are OOP, funcional, AOP, etc.).
I posit a fourth “condition” for being able to produce better software and that is being able to recognise what specifically isn’t working and be ready to ditch it. I see no indication of this for at least another 20 or 70 years give or take 100 years.
Computing Industry’s Best Kept Secret: The function is *NOT* necessary to build software and may in fact be a bad tool.
Cleo, what is your proposed alternative to the function (or to typical uses of functions)? Or: what’s wrong with having a reusable piece of code with a name, and with a list of well-defined parameters and return values (if your language allows more than one ;-) ) ?
Since we’re talking about code, i.e. execution behavior, not necessarily objects (which also need code to execute!), IMHO the most basic reusable unit seems to be a function. OO languages extended the notion of function, while other – functional – languages extended it in other ways (such as anonymous functions/blocks).
What Ulrich said. If the subroutine/function is unnecessary, or even harmful (?), I would *really* like to hear about the alternative(s).
I’ve come to a slightly different perspective on the test-vs-prove debate. The EWD approach of regarding correctness as a fundamental design issue is certainly in stark contrast to the “James Joyce school of programming”, which a collegue of mine described it as “code your brains out and debug it until it works.” And in one of his lesser-cited papers (EWD648), Dijkstra offers some insight on why software testing can’t even be thought of in the same way as hardware testing.
I’ll leave it to the philologs among us to look into the etymology and usage of the word “proof”; the connections with “test” are strong! With a background in Mathematics and computing science, I certainly understand the difference between rigorous reasoning and trial-and-error. However, I find it very ironic that the current popularity of “test-driven development” can be seen as approaching the same underlying issue as “proof-driven development”.
In both cases, the practitioner is urged to BEGIN the process by thinking “How can I verify that each little bit of what I’m building, as well as each step of their composition, is verifiably correct?” Working from that perspective, the risks of failure or wasted time are greatly reduced. In addition, responding to a defect by FIRST writing a test that reveals the root issue, then modifying the program to address that issue without breaking any of the growing body of previous tests, is a far cry from the random twiddling so common when “The Humble Programmer” was written.
Of course, it is still true that a non-trivial program can never be completely covered or verified merely by trying out selected test cases! It is also true that no amount of predicate calculus applied to the design will detect or prevent a typo when the source code is offered to the compiler. But the discipline of thinking at every step “How can I verify that this is correct?” has led me to think of testing and proof as complementary, rather than contradictory. And the net improvement in quality and productivity has persuaded me that it is returning to one of EWD’s fundamental principles–that of beginning with design and structure, rather with details of the artifact–is still our best way forward.
And part of the implicit lesson of “The Humble Programmer” is for those of us who prefer either extreme of the “proof-AND-testing” continuum to be willing to allow those at the other end (or in the middle ;-) to teach us something.
An alternative to function calls is the continuation-passing style. What Cleo wrote reminded me of:
“Then why do I claim it is flawed? Simple. Implementation details. Alan Kay and every other implementation of OOP left in the function call. Messages that are sent must return before you can send another one.” http://my.ope
ra.com/Vorlath/blog/show.dml/202787
(I do not see a description of the input language of this blog near the text field, e.g., to find out whether URIs will be converted to HTML-anchors. There also is no pre-view option.)
With functions, it’s stack based. You have to wait until the function returns in order to process the next function unless it’s an internal function. This is the first in, last out rule just like a stack. I don’t mean that functions are bad in of themselves for certain things. I mean that maybe they’re not the *only* way. Just like different data structures have different uses. Right now, everyone is using the function. Imagine if the stack was the only data structure you could use. What a horrible world. Yet this is what we have with the function.
Unix has pipes. These are queues. As data is piped, software on both ends of the queue can execute at the same time. As data passes from one end of the queue to the other, there is no concept of execution point. Only data transformations and transfers. Another example is the Internet where messages (real ones) get passed back and forth. Simple idea that scales and is in active use.
We’ve look into the stack based way of programming to death. Maybe the queue or other data processing model can be looked at, especially to solve concurrency. I feel it’s a shame that there are perfectly acceptable tools available that get sidelined for the status quo.
BTW, history dictates that the function is not reusable. Well, maybe it’s reusable like sand is reusable to build glass. Once it’s actually used, it is forever transformed into something else that can no longer be separated from the whole.
Daijkstra is a real false prophet.
According to wikipedia – “…Dijkstra is also noted for owning only one computer (late in life) and rarely actually using them…”. Well why am I not surprised?
Not even one of his “prophecies” has come true. Actually I don’t understant why is he paid so much attention. All his articles must be tought in course of “How NOT to train programmer”.
“…Argument one is that, as the programmer only needs to consider intellectually manageable programs, the alternatives he is choosing between are much, much easier to cope with…” – What’s the hell is “intellectually manageable” programs ??? Are they program with mathemetically proven correcteness that Dijkstra suggests..? Oh Well in this case I must format my disk because none of the programs comply with this requirement… but wait some of them work fine and I am totally pleased with it. Dijkstra is totally not synchronized with reality and lives in his wortld of small nice algorithms.He is too unexperienced in programming, and managing large projects, to understand that demanding mathematical prove is impossible task. Not only that, Mr Dijkstra doesn’t know, that it is not the proof is the problem but knowing what is wright and what is wrong. How can you prove mathematically that this GUI interface is better that this?
“…Therefore I present our recent knowledge of vital abstraction patterns as the fourth argument…” – Well Is someone here thinks that patterns are the answer??? The most arrogant and stupid programmers I knew were very proud of using patterns in their disgusting code.
fifth argument – Well one word Java. Yeah that was their motto rememeber? “…Disciplined language…, Lean language”. Now they with their tongues outside are trying to close the gaps with “agile” languages (and even C#) that are full of syntax sugar.
I want to know what large projects Dijkstra managed as an VP R&D or something like that. According to wikipdeia none.
Well, Boris, two serious development projects of EWD’s come to mind immediately: the development of a multitasking operating system for the Technical University of Eindhoven (mid- to late-1960’s), and heavy involvement in early definition and implementation of Algol 60 (date obvious ;-). Many of the concepts and techniques which we take for granted these days–i.e. the stack and the semaphore (later developed into the “monitor”, the basis of “synchronized” routines in Java)–are due to Dijkstra’s work in those early days of commercial and academic computing.
As for your first question, by “intellectually manageable” programs, I believe the (large) body of Dijkstra’s work supports my understanding that he meant programs which are carefully and thoughtfully designed, and whose structure makes them accessible to verification and maintenance. In other words, the programmer who wishes to make robust, correct, long-lived programs would do well to think first, rather than typing in the first thoughts that come to mind.
I’m sure that all of us have experienced that golden moment where, in a burst of inspiration, we sat down and composed a few hundred lines of code which worked correctly on the first attempt. As exciting and gratifying as that experience is, I think all of us who’ve worked on large commercial/industrial projects know that such efforts don’t scale up. Introducing multiple-programmers, mission-criticality, long time-frames, large and complex requirements, etc. means that a more careful approach is required.
The fields of programming and computing science are certainly large and fruitful enough to support many different perspectives and specialties. An “humble programmer” would be cautious about expressing contempt for someone whose path has seldom intersected with his or her own.
The incompleteness of Wikipedia is to be laid at Wikipedia’s door, not at the feet of any person whose biography is inadequate.
Joel,
Firstly I have no doubt about great achievments of Dijkstra in applied computer sciences. But between this and his vision on ideal software, programmers disicipline, programming tools to use in large projects and development methodologies there’s a terribly large gap.
Algol 60 – IMHO is a well known failure of “yet another best language in the world” and exactly proves my point.
“intellectually manageable” – your defintions is circular in nature. Good programs = “programs which are carefully and thoughtfully designed”=Good programs. By the way, your “think first” approach resembles me another well known failure – a Waterfall design model.
As to “bursts of inspiration”: A good article which may answer you is:-
http://www.bleading-edge.com/Publications/C++Journal/Cpjour2.htm
I think Dijkstra missed one very important point. He understood that there’s a terrible complexity in doing large projects but he didn’t understand that “cathedral” order in doing such projects will not help. It is kinda “flow with it” attidude that he misses. His concepts are almost of “silver bullets” nature and that’s why it is annoying.
Boris,
First of all, thanks very much for the link to the 1992 C++ Journal article! I’ve sympathetic with the author’s view that source code is precisely a design artifact. In fact, I suggest that the only reasonable analogy between software development and manufacturing is to regard the *transaction* as the unit of mass production (toaster, car, etc.), because that is the artifact that is produced in large quantity. Therefore, the running code is the factory (the means of mass-production), and the source code is the design for the factory.
I’m not sure how to apply that analogy to “bursts of inspiration”, except to observe that the insight and excitement of designing an effective motor mount for a conveyer system probably can’t be sustained throughout the development of the blueprints for the entire factory.
On another topic, I simply don’t agree with describing ALGOL 60 as a failure. Most contemporary languages take for granted concepts that were pioneered in ALGOL 60, including block structure, recursion, a richer set of datatypes than those built into the hardware of the day, etc. Java (along with its imitators) traces many of its core ideas back to Simula 67, which was a dialect/offspring of ALGOL.
If “failure” refers to current usage, then of course it is no longer in use! We no longer consider the DC-9 a state-of-the-art aircraft, but it was a tremendous step forward in its time. After all, consider that ALGOL 60 was created about 85% of the lifetime of commercial computing ago!
Finally, the references to “waterfall” and “cathedral” lead me to think that we are coming away from Dijkstra’s writings with radically different understandings of what he said. In a paper of 32 years ago (EWD 450, written in November of 1974), Dijkstra writes of “…challenging the choice of a posteriori verification of given programs as the most significant problem, the argument against that choice being that programs are not “given”, but must be designed. Instead of trying to find out which proof-patterns are applicable when faced with a given program, the program designer can try to do it the other way round: by first choosing the proof-pattern that he wants to be applicable he can then write his program in such a way as to satisfy the requirements of that proof.”
He argued against constructing giant cathedrals of code and then attempting after-the-fact demonstrations of their correctness. Further, if we substitute the word “test” for “proof”, the last part of the above quotation seems curiously similar to the position of the most enthusiastic proponents of test-driven-development.
Dijkstra didn’t believe in silver bullets; his position was: “The training of programmers cannot be “easy”, for programming is and will remain difficult. The point is that “learning the language” should, indeed” be a minimal affair, and the major attention should be given to mastering an orderly discipline how to use it.” (EWD 526, a set of comments on the “Woodenman” draft leading to ADA).
It is the hucksters who’ve tried to make every step in the development of programming (HLLs, structured programming, databases, OO, etc.) into a silver bullet. It is the manager who wishes to “deskill” programming into a commodity production activity performed by cheap labor who is the hucksters’ natural prey. It is the uncompromising curmudgeon such as Dijkstra who keep insisting “It’s not that simple!”
(So much for my proofreading skills! The second sentence should have begun “I’m sympathetic…” My apologies for the error.)
Joel,
As to Algol I still see it in one raw with other artifacts of computer history that we learned more from their failures then from their real achievments. It was important stage of learning curve but I would not call them achievements by themsleves. Algol, Multix, CORBA etc all failed partially due to rigorous design process which totally neglected “real life” requirements and addressing it as “implementation issues”. By the way FORTRAN was invented before ALGOL and is still in more extensive use. DC-9 flew a lot, ALGOL never really got airborne.
It not easy arguing with you as you don’t give any concrete anchor examples as how to implement Dijkstra vision of “intellectually manageable software”. You rejected mathematical proof as what Dijkstra meant and you didn’t give any example of methodology that would get us close to what Dijkstra would approve.
Actually this is another problem with Dijkstra article. What are concrete steps we must take to improve the current state of affairs.
“…restrict ourselves to the subset of the intellectually manageable programs…” – Too vague advice to be of any usefulness.
“…vital abstraction patterns…” – I answered that before.
Argument three – sounds to me as test-driven (in this case I totally support it) but I am quite not sure that Dijkstra meant it.
“…use better languages/tools..”! – Tottally agree. But when Dijkstra tries to be a little more concrete with his “baroque” concept, he looses me. “baroque languages” (php, perl, python, ruby) are the ones that are winning over disciplined ones (java).
“…The wider applicability of nicely factored solutions…”- C’mon who will argue, but how? How you decide which abstraction is better then other. Actually overabstraction is more problematic anmongst young programmer then under-abstraction. But this is theme for another article.
Reading it over and over I couldn’t find any really useful advice of how to imrove my work starting toady. Can you help me?
I find this comment from Dijkstra’s article to be particularly relevant as a working programmer.
“The competent programmer is fully aware of the strictly limited size of his own skull; therefor he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague.”
It reminds me of Richard Gabriel’s “Habitability”:
“Habitability is the characteristic of source code that enables
programmers, coders, bug-fixers, and people coming to the code
later in its life to understand its construction and intentions and
to change it comfortably and confidently”.
(from http://www.dreamsongs.com/Files/PatternsOfSoftware.pdf)
“Clever tricks” are likely to reduce habitability. This is not to say that they are never warranted, just (in production code) not as ends in themselves. To improve type safety or efficiency in some critical piece of code, quite possibly.
I also appreciated the sentiment of this comment from Dijkstra’s summary:
“We shall do a much better programming job, provided that we approach the task with a full appreciation of its tremendous difficulty, provided that we stick to modest and elegant programming languages, provided that we respect the intrinsic limitations of the human mind and approach the task as Very Humble Programmers.”
More easily said than done of course, and what constitutes a “modest and elegant programming language” is a minefield, but one worth carefully exploring.
Boris,
I’m reminded of the famous remark attributed to Sir Tony Hoare, “I don’t know what the programming language of the year 2000 will look like, but I know it will be called Fortran.” I used FORTRAN in the 60s. And I am totally confidant that if we could time-transport to 2006 a FORTRAN programmer and an ALGOL programmer of the mid-60s, the ALGOL programmer would be *far* more at home with FORTRAN 2003 than the FORTRAN programmer. Finally, there is much evidence that the relative frequency of use between FORTRAN and ALGOL (in the US!) had more to do with IBM and politics than technical considerations.
One of the papers that helped me understand the POV of Dijkstra, and other significant European computing scientists, is “On the fact that the Atlantic Ocean has two sides”. (EWD 611)
I didn’t mean at all to deny formal, mathematical methods as an important part of what Dijkstra taught and wrote. Rather, what I had hoped to emphasize is that our field is now coming [back] to some of the core concerns that motivated his work, such as verifiability as a core design concept.
Few (if any) of Dijkstra’s writings can be used as quick recipes (and I suspect he would have been horrified at an attempt to do so ;-). I personally found his book, _A_Discipline_of_Programming_ (1976), simultaneously challenging to read and rewarding to contemplate and apply. If I had to suggest concrete applications of his ideas, the first one that comes to mind is, “Never write a line of code without first asking yourself how you’ll verify that it is correct.” If I could master that one and avoid the creation of unnecessary complexity, then that would be enough for me.
“as the number of tests approaches infinity, the probability of correctness approaches 1.”
I agree. Tests are not proof but they are a close substitute. I saw some statistics from large software projects showing that testing even one execution path through a function found 55% of the defects in that function. Testing two execution paths found 65% of the defects. It takes surprisingly few test cases (say a dozen good tests) to reach 95%. These are averages of course, but they point to the power of TDD.
To call Algol 60 a “failure” because no large production systems use it would be–even if this claim were true–akin to calling the Wright Flyer a failure because it didn’t carry cargo.
Joel
Firstly, one point of agreement is that ensuring verifiability is crucial goal of every project. However the only technique i know which works is multi level automated testing. Dijkstra in the article does not address any of this technique. Another technique that I expect to gain the momentuim is independent usability reviews. But this is only my speculation.
There’s a great article of perl creator Lary Wall http://www.oreilly.com/catalog/opensources/book/larry.html
Let me quote from it:-
…This is important, and a little hard to understand. English is useful because it’s a mess. Since English is a mess, it maps well onto the problem space, which is also a mess, which we call reality. Similarly, Perl was designed to be a mess (though in the nicest of possible ways)…
You see, Perl, was designed on purpose as a “mess” (nicest mess though). That’s why it is so useful. Do you think Dijkstra would approve this “mess” approach in design of the languiage? I have an impression that not. And that is my main point of criticism.
The point is not that every problem that we trying to solve in programs is so somplicated that we should abandon any hope to improve the quality of the code. But the variance of problems themselves that software engeneering is applied to is so big that any attepmt of finding universal approach to this is doomed to fail.
The strategy lies not in “limiting” techinques – like the one’s Dijkstra suggests, but on opposite inserting more “nice mess” as in Perl or even C++. See how “loosely typed” languages are getting momentum. The world is going in quite opposite direction than Dijkstra predicted.
I’m sure that by “losely typed” languages you mean dynamically typed languages (languages where variables are untyped, and type-correctness is enforced at runtime). Scripting languages, unlike C, are very strongly typed; it’s pretty much impossible to perform an operation on data that’s not valid for the data type.
But I think you have wrong the reason people are making this move. It’s not because people don’t like strong typing as much as they don’t like the pain-in-the-you-know-what declarative typing that languages like Java use. Type inference makes a world of difference.
“one of the most important aspects of any computing tool is its influence on the thinking habits of those that try to use it”
Remineds me of a line from Paul Graham’s essay, Hackers and Painters:
“A programming language is for thinking of programs, not for expressing programs you’ve already thought of”
Thinking is done in a language and the design of the language has influence on the thinking.
i want to appriciate you for your excellent job that you did