4 ms·

Has anyone here actually learnt what Dijkstra advocates in almost all EWDs and used it to any benefit? Basically almost all his essays in one way or another end

by stiff 13y ago

Has anyone here actually learnt what Dijkstra advocates in almost all EWDs and used it to any benefit? Basically almost all his essays in one way or another end up being about the need to prove programs correct using formal logic and specifically a particular approach to correctness proofs he devised. In fact he even advocates starting from a formal logical specification of a problem and then deriving the program using purely syntactical transformations. I tried to read the "Discipline of programming" where he explains his approach, but it was barely understandable and it takes 300 pages for him to get to the point of developing simple algorithms of the type you meet in the first chapter of an algorithm textbook. It could have been the translation (didn't read the English original), but I doubt it, because I have never read anything technical from him that would actually be interesting. I am afraid his essays are liked because of the general sentiment for "more rigour" in programming, whatever it would mean, and not because of any understanding of what precisely he advocates and the merits of his techniques. The living proof is some comment in this thread how Dijkstra sheds insight into the value of TDD... So, if you upvote his articles, what precisely have you learned from Dijkstra?

killahpriest 13y ago
How to get a rat out of a maze. http://www.cse.usf.edu/~rtindell/courses/DataStructures/Projects/RescueRemy2/Instructions.pdf http://www.cse.usf.edu/~rtindell/courses/DataStructures/Proj... On a serious note, you do have a good point. I haven't read much of Dijkstra's work myself.
- stiff 13y ago
  Well, he didn't derive his algorithm using the approach he advocated, here is what he himself has to say on it: One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years late. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame. I found it in the early ’60’s in a German book on management science - - “Das Dijkstra’sche Verfahren.” Suddenly, there was a method named after me Source: http://conservancy.umn.edu/bitstream/107247/1/oh330ewd.pdf http://conservancy.umn.edu/bitstream/107247/1/oh330ewd.pdf
btilly 13y ago
You need to put it in historical perspective. Essays like this one were written at the dawn of the "structured programming" debate. If you're programming in a language and codebase where goto is rare or non-existent, then Dijkstra's ideas have had an impact on your environment. More precisely he is always a champion of the idea of having programs express things in a direct and understandable way which makes comprehension straightforward. And a champion of getting there by removing unneeded features from languages. This was a necessary overcorrection to now-forgotten excesses. But today it is clear that he went too far. As an example, I would consider Go's a language which is heavily influenced by Dijkstra's ideas on the value of simplicity in language design. However the internal loop exit implied by break exists. Multiple return values are used to separate out data (the result of a calculation) from metadata (the presence and details of errors). We use features beyond what Dijkstra considered wise.
- stiff 13y ago
  There are hundreds of EWDs and I haven't seen a single one where Dijkstra would talk about making programming languages simple to make comprehension straightforward, this is something that modern programming "gurus" are more likely to say. The reason Dijkstra wants simple programming languages, and most EWDs are more or less about this, is because he wants to prove theorems about programs, which is possible only with a simple language. Not only that, as I said he wants to reduce program development to well defined transformations on a specification of a problem in the language of mathematical logic. His stance is very nicely summarized here: http://en.wikipedia.org/wiki/The_Cruelty_of_Really_Teaching_Computer_Science http://en.wikipedia.org/wiki/The_Cruelty_of_Really_Teaching_... You have to understand some mathematics and mathematical logic to really understand Dijkstra however, you cannot look at it from a pure software engineering background because you will only take away platitudes from what he says without actually understanding him. If you have some background you can read about his real technical ideas: http://en.wikipedia.org/wiki/Program_derivation http://en.wikipedia.org/wiki/Program_derivation http://en.wikipedia.org/wiki/Guarded_Command_Language http://en.wikipedia.org/wiki/Guarded_Command_Language http://en.wikipedia.org/wiki/Predicate_transformer_semantics http://en.wikipedia.org/wiki/Predicate_transformer_semantics This is the area Dijkstra worked most on during his research career. Those ideas actually go back centuries before anyone ever thought about structured programming. For hundreds of years there has been a fundamental debate ongoing on whether all kinds of reasoning can be reduced to some kind of calculi with well specified rules, which would be equivalent to being able to construct a (at least theoretical) machine for automating it. This is where computers come from, this goes back to Charles Babbage, to the works of Leibniz, Boole, Turing etc. Dijkstra is in the same historical tradition. The program I understand Dijkstra has for Computer Science is similar to the program Hilbert had for mathematics with what is now called formalism, from which the work of Goedel and Turing sprung off. When programming was still mainly done by mathematicians this has been a lively research area, there were various systems of proving correctness invented, various ways of deriving programs, there has been a very heated debate on when proofs are needed and to what extent ordinary programmers have to master them etc. You can find loads of books and monographs written in the 70s and 80s about this. Now as far as research goes program derivation seems to be an almost dead topic, but there are still people today championing it in some alternative form. Richard Bird wrote a book called "Pearls of Functional Algorithm Design" where he derives algorithms using algebraical properties: http://www.cs.ox.ac.uk/people/richard.bird/ http://www.cs.ox.ac.uk/people/richard.bird/ Alexander Stepanov has been advocating something similar and wrote a book called "Elements of Programming": http://www.elementsofprogramming.com/ http://www.elementsofprogramming.com/ https://www.youtube.com/watch?v=Ih9gpJga4Vc https://www.youtube.com/watch?v=Ih9gpJga4Vc
gngeal 13y ago
it takes 300 pages for him to get to the point of developing simple algorithms of the type you meet in the first chapter of an algorithm textbook That's impossible; Discipline of Programming has only 217 pages of text. Surely you've been so enthralled by your reading that you didn't notice skipping through the covers to the book laying below!
skrebbel 13y ago
I (re)learned programming this way. I studied CS at Eindhoven University of Technology, where Dijkstra ran a research group for years. You need to understand that Dijkstra's primary research focus was algorithms. Mathematically deriving algorithms from formal specifications isn't a weird idea at all. Sure, it feels cumbersome when the algorithm you're deriving is a commonly known one, like a mergesort or a binary search. The idea is that you can derive other, more specific algorithms in the same way, and you'll have proven their correctness. These days, algorithms are not a major part of most computer systems. Trying to apply Dijkstra's approach to a user interface or a JSON parser makes little sense. But this does not invalidate the method for its intended domain. It also does not make Dijkstra's ramblings misguided nonsense.
- mathattack 13y ago
  "These days, algorithms are not a major part of most computer systems." I disagree... While GUI developers don't worry about O(n^2) versus O(n log n) performance, sites like Google wouldn't respond in real time without a focus on the best underlying algorithms. I agree with the rest of what you say.

by stiff 13y ago

killahpriest 13y ago

How to get a rat out of a maze. http://www.cse.usf.edu/~rtindell/courses/DataStructures/Projects/RescueRemy2/Instructions.pdf http://www.cse.usf.edu/~rtindell/courses/DataStructures/Proj... On a serious note, you do have a good point. I haven't read much of Dijkstra's work myself.

stiff 13y ago
Well, he didn't derive his algorithm using the approach he advocated, here is what he himself has to say on it: One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years late. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame. I found it in the early ’60’s in a German book on management science - - “Das Dijkstra’sche Verfahren.” Suddenly, there was a method named after me Source: http://conservancy.umn.edu/bitstream/107247/1/oh330ewd.pdf http://conservancy.umn.edu/bitstream/107247/1/oh330ewd.pdf

btilly 13y ago

You need to put it in historical perspective. Essays like this one were written at the dawn of the "structured programming" debate. If you're programming in a language and codebase where goto is rare or non-existent, then Dijkstra's ideas have had an impact on your environment. More precisely he is always a champion of the idea of having programs express things in a direct and understandable way which makes comprehension straightforward. And a champion of getting there by removing unneeded features from languages. This was a necessary overcorrection to now-forgotten excesses. But today it is clear that he went too far. As an example, I would consider Go's a language which is heavily influenced by Dijkstra's ideas on the value of simplicity in language design. However the internal loop exit implied by break exists. Multiple return values are used to separate out data (the result of a calculation) from metadata (the presence and details of errors). We use features beyond what Dijkstra considered wise.

stiff 13y ago
There are hundreds of EWDs and I haven't seen a single one where Dijkstra would talk about making programming languages simple to make comprehension straightforward, this is something that modern programming "gurus" are more likely to say. The reason Dijkstra wants simple programming languages, and most EWDs are more or less about this, is because he wants to prove theorems about programs, which is possible only with a simple language. Not only that, as I said he wants to reduce program development to well defined transformations on a specification of a problem in the language of mathematical logic. His stance is very nicely summarized here: http://en.wikipedia.org/wiki/The_Cruelty_of_Really_Teaching_Computer_Science http://en.wikipedia.org/wiki/The_Cruelty_of_Really_Teaching_... You have to understand some mathematics and mathematical logic to really understand Dijkstra however, you cannot look at it from a pure software engineering background because you will only take away platitudes from what he says without actually understanding him. If you have some background you can read about his real technical ideas: http://en.wikipedia.org/wiki/Program_derivation http://en.wikipedia.org/wiki/Program_derivation http://en.wikipedia.org/wiki/Guarded_Command_Language http://en.wikipedia.org/wiki/Guarded_Command_Language http://en.wikipedia.org/wiki/Predicate_transformer_semantics http://en.wikipedia.org/wiki/Predicate_transformer_semantics This is the area Dijkstra worked most on during his research career. Those ideas actually go back centuries before anyone ever thought about structured programming. For hundreds of years there has been a fundamental debate ongoing on whether all kinds of reasoning can be reduced to some kind of calculi with well specified rules, which would be equivalent to being able to construct a (at least theoretical) machine for automating it. This is where computers come from, this goes back to Charles Babbage, to the works of Leibniz, Boole, Turing etc. Dijkstra is in the same historical tradition. The program I understand Dijkstra has for Computer Science is similar to the program Hilbert had for mathematics with what is now called formalism, from which the work of Goedel and Turing sprung off. When programming was still mainly done by mathematicians this has been a lively research area, there were various systems of proving correctness invented, various ways of deriving programs, there has been a very heated debate on when proofs are needed and to what extent ordinary programmers have to master them etc. You can find loads of books and monographs written in the 70s and 80s about this. Now as far as research goes program derivation seems to be an almost dead topic, but there are still people today championing it in some alternative form. Richard Bird wrote a book called "Pearls of Functional Algorithm Design" where he derives algorithms using algebraical properties: http://www.cs.ox.ac.uk/people/richard.bird/ http://www.cs.ox.ac.uk/people/richard.bird/ Alexander Stepanov has been advocating something similar and wrote a book called "Elements of Programming": http://www.elementsofprogramming.com/ http://www.elementsofprogramming.com/ https://www.youtube.com/watch?v=Ih9gpJga4Vc https://www.youtube.com/watch?v=Ih9gpJga4Vc

gngeal 13y ago

it takes 300 pages for him to get to the point of developing simple algorithms of the type you meet in the first chapter of an algorithm textbook That's impossible; Discipline of Programming has only 217 pages of text. Surely you've been so enthralled by your reading that you didn't notice skipping through the covers to the book laying below!

skrebbel 13y ago

I (re)learned programming this way. I studied CS at Eindhoven University of Technology, where Dijkstra ran a research group for years. You need to understand that Dijkstra's primary research focus was algorithms. Mathematically deriving algorithms from formal specifications isn't a weird idea at all. Sure, it feels cumbersome when the algorithm you're deriving is a commonly known one, like a mergesort or a binary search. The idea is that you can derive other, more specific algorithms in the same way, and you'll have proven their correctness. These days, algorithms are not a major part of most computer systems. Trying to apply Dijkstra's approach to a user interface or a JSON parser makes little sense. But this does not invalidate the method for its intended domain. It also does not make Dijkstra's ramblings misguided nonsense.

mathattack 13y ago
"These days, algorithms are not a major part of most computer systems." I disagree... While GUI developers don't worry about O(n^2) versus O(n log n) performance, sites like Google wouldn't respond in real time without a focus on the best underlying algorithms. I agree with the rest of what you say.