Re:Edsger Dijkstra's note on starting array indices at 0 (pd...
by kragen on Thursday June 23, 2011 @01:43PM
(#2688903)
In Dijkstra's heyday --- up to about 1970 --- logical proofs of correctness were a great deal more practicable than tests as a way to assure software quality. There were several reasons for this:
1. You weren't writing the software in a portable high-level language, but in assembly or machine code. Consequently a new machine was running new software, or simulating an old machine (very slowly). Waiting until the new machine was ready to begin writing the software (assemblers, simulators, compilers, OS) would have enormously delayed delivering the machine to customers.
2. Computers, and thus tests, ran a lot slower. Logical proofs of correctness ran at almost the same speed. Consider the System/360 Model 30: http://www-03.ibm.com/ibm/history/exhibits/mainframe/mainfra... --- 34500 32-bit-word additions per second, compared to 10 billion or so on the machine sitting on your desk, not counting the GPU or possible SIMD instructions. A test that would take your machine a millisecond to run would take the Model 30 about 5 minutes. This also meant that the cost of a bug that necessitated re-running a big compute job was substantial, even if it was caught and didn't produce any worse results than a resubmission.
(There are, of course, proofs of correctness that we can do today with computer help that were not practical then; but those were mostly not what Dijkstra was considering.)
3. Computers mostly weren't interactive. Timesharing was being born, but it hadn't taken off yet, and there were only a small number of computers dedicated to the usage of a single person, or on which you could reserve single-person time. This means that the speed problem is actually much more severe than it appears --- your 1-millisecond test might take 5 minutes to run, but you have to put it in the job queue, and you'll get the result probably within 24 to 48 hours --- and also that the most valued properties of your program are things like "correctness" and not "usability" or "fun". (Usability was actually already important in avoiding user errors and associated incorrect results and wasted computer time, but most people didn't realize this yet.)
4. Computers and support software were much simpler. (And, to hear the old-timers tell it, much more likely to behave as specified.)
Despite all this, I think that some of Dijkstra's emphasis on structuring software so that its correctness is easy to verify is part of the mainstream today, and it's essential in making the software testable. Take a look at The Elements of Programming Style and compare the programs they quoted from textbooks to almost any modern code.
1. You weren't writing the software in a portable high-level language, but in assembly or machine code. Consequently a new machine was running new software, or simulating an old machine (very slowly). Waiting until the new machine was ready to begin writing the software (assemblers, simulators, compilers, OS) would have enormously delayed delivering the machine to customers.
2. Computers, and thus tests, ran a lot slower. Logical proofs of correctness ran at almost the same speed. Consider the System/360 Model 30: http://www-03.ibm.com/ibm/history/exhibits/mainframe/mainfra... --- 34500 32-bit-word additions per second, compared to 10 billion or so on the machine sitting on your desk, not counting the GPU or possible SIMD instructions. A test that would take your machine a millisecond to run would take the Model 30 about 5 minutes. This also meant that the cost of a bug that necessitated re-running a big compute job was substantial, even if it was caught and didn't produce any worse results than a resubmission.
(There are, of course, proofs of correctness that we can do today with computer help that were not practical then; but those were mostly not what Dijkstra was considering.)
3. Computers mostly weren't interactive. Timesharing was being born, but it hadn't taken off yet, and there were only a small number of computers dedicated to the usage of a single person, or on which you could reserve single-person time. This means that the speed problem is actually much more severe than it appears --- your 1-millisecond test might take 5 minutes to run, but you have to put it in the job queue, and you'll get the result probably within 24 to 48 hours --- and also that the most valued properties of your program are things like "correctness" and not "usability" or "fun". (Usability was actually already important in avoiding user errors and associated incorrect results and wasted computer time, but most people didn't realize this yet.)
4. Computers and support software were much simpler. (And, to hear the old-timers tell it, much more likely to behave as specified.)
Despite all this, I think that some of Dijkstra's emphasis on structuring software so that its correctness is easy to verify is part of the mainstream today, and it's essential in making the software testable. Take a look at The Elements of Programming Style and compare the programs they quoted from textbooks to almost any modern code.