7 ms·

A Short Introduction to the Art of Programming (1971) [pdf]

296 points by Rescis 8y ago

unclepresent 8y ago
this is a smart dude, he invented one of the most popular algorithms of finding a shortest path in a graph.
- fernly 8y ago
  ...to say the very least! From [1], > His fundamental contributions cover diverse areas of computing science, including compiler construction, operating systems, distributed systems, sequential and concurrent programming, programming paradigm and methodology, programming language research, program design, program development, program verification, software engineering principles, graph algorithms, and philosophical foundations of computer programming and computer science. Many of his papers are the source of new research areas. Several concepts and problems that are now standard in computer science were first identified by Dijkstra or bear names coined by him. [1] https://en.wikipedia.org/wiki/Edsger_W._Dijkstra https://en.wikipedia.org/wiki/Edsger_W._Dijkstra
  - AceJohnny2 8y ago
    Did someone say semaphores? https://en.wikipedia.org/wiki/Semaphore_(programming) https://en.wikipedia.org/wiki/Semaphore_(programming)
    - TimJYoung 8y ago
      Semaphores are great for creating simple read-write locks.
- deleted 8y ago
  [deleted]
- skrebbel 8y ago
  IMO that's the least spectacular of his contributions. It's not like that algorithm is particularly mindblowing. In fact, I'd wager that any sufficiently experienced engineer with some algorithm work under their belt would arrive at the exact same thing. Actually, I bet there's engineers all over the world who invent it every year, independently, simply because they need it and they didn't go to college or know that there's a thing out there called "Commonly Known Algorithms That Have Names and Wikipedia Pages" so they just worked it out. In fact, I'd wager someone already came up with it somewhere before Dijkstra did, put it in the code (or, well, on the punch card), and quietly went home, happy about a good day's work. Dijkstra just was the first one to publish it :-) His true contributions were, IMO: * Being the first tech blogger[0] (handwritten!) * Teaching people to use while/for instead of goto * Pioneering mathematically verified algorithm derivation He's also the reason Dutch universities have no independent Computer Science departments. They're always paired with Mathematics, even at universities of technology, which makes no sense and which has effectively halved research funding for both disciplines for decades. He was a better programmer than politician. [0] http://www.cs.utexas.edu/users/EWD/indexChron.html http://www.cs.utexas.edu/users/EWD/indexChron.html - I'm calling it a blog because both the median length and the frequency of publishing is a lot more like blogging than anything else. I'm not aware of other people doing this as much in that day and age (but I'm probably wrong)
  - dragonwriter 8y ago
    > Being the first tech blogger (handwritten!) It's not a web log (for which “blog” is short) if it's not on the web.
    - EliRivers 8y ago
      I've certainly heard the youngsters describe something as "a blog, but on paper". Son enough, the word 'blog' will transcend its etymology.
- ofrzeta 8y ago
  Even smarter: "Simplicity is prerequisite for reliability." I wish more people or "the industry" would take this advice. On the other hand what would be left to sell if everything were simple and reliable.
wsc981 8y ago
Not directly related, but here’s a short documentary on his life and career (Dutch spoken, English subtitles): https://m.youtube.com/watch?v=RCCigccBzIU https://m.youtube.com/watch?v=RCCigccBzIU
sohkamyung 8y ago
For those who prefer a plain text version, start reading from [1] [1] http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD316.html http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EW...
- mhd 8y ago
  I'm quite surprised that the original PDF wasn't handwritten anyway, as Dijkstra really seemed keen on that (and back in the olden days, I remember some kind of PostScript module that faked this)
  - jgtrosh 8y ago
    I read a lot of EWD texts last year, and he transitioned from typed to handwritten later in his life, about halfway through the number of scripts that he published. From his Wikipedia page [1]: > Dijkstra never wrote his articles using a computer. He preferred to rely on his typewriter and later on his Montblanc pen. Dijkstra's favorite writing instrument was the Montblanc Meisterstück fountain pen. [1]: https://en.wikipedia.org/wiki/Edsger_W._Dijkstra https://en.wikipedia.org/wiki/Edsger_W._Dijkstra
  - Someone 8y ago
    I think you’re thinking of the “Dijkstra” TrueType font (available from zillions of places. I remember there being different versions, so it probably is worthwhile to download a few and pick the largest (or, better, to inspect them for their glyphs))
    - mhd 8y ago
      I definitely remember it being in PostScript (back in the days when that was much more prevalent in Linux and I actually used jwz' scripts to print CD cases). It might be this http://ftp.math.utah.edu/u/ma/hohn/linux/misc/quickscript/dijkstra.qs http://ftp.math.utah.edu/u/ma/hohn/linux/misc/quickscript/di... If so, that appears to be a regular vector font, too, no random deviations or letter variants to make it appear more handwritten.
escherplex 8y ago
Still a good read (from 1971 then with .pdf Adobe Acrobat optimized). The Towers of Hanoi simulation section brings back memories of an old Wang 2200 Basic machine (64K as I remember) buried in storage at my old prep school which we managed to bring back to life (more or less) . Decided to write a Towers of Hanoi game using its available box graphics, which could be animated but which quickly taught the maxim: write forward then erase behind (otherwise the imagery appears jumpey). The results were similar to the 'Towers of Hanoi' app now on ROKU 4. But how to add an animated 'solve' function? Raw strings (for 2: top small 1 -> 2, top small 1 -> 3, top small 2 -> 3) ate up too much memory beyond 7 (2^n - 1 = 127) so system analysis suggested: give the smallest box a life of it's own and if total number of discs to be moved is even, script the smallest to follow a path 1 -> 2, 2 -> 3, 3 -> 1, 1 -> 2 etc. for first then every other move. If total number of discs odd, script it a path 1 -> 3, 3 -> 2, 2 -> 1, 1 -> 3 etc for first then for every other move (until you're done). Each next alternate move is any valid move (top smallest on any other column move to any other column with no disks or with column with top disk larger than that one). Seem to recall Martin Gardner had a similar solution in an old Scientific American 'Mathematical Games' article.
altro 8y ago
the name should be Edsger
coldtea 8y ago
>The market is already so heavily overloaded with introductory texts on computers and computer programming that one must have rather specific reasons to justify the investment of one's time and energy in the writing of yet another "Short Introduction to the Art of Programming". In 1971? I seriously doubt that... >[people] who identify the programmer's competence with a thorough knowledge of the idiosyncrasies of one or more of the baroque tools into which modern programming languages and systems have degenerated This, however, is as valid as ever...
- jcelerier 8y ago
  In 1971 there was already 15 years of FORTAN books, and 10 years of ALGOL and COBOL books
  - coldtea 8y ago
    All 100 of them? Today we have more books than all those FORTRAN and ALGOL and COBOL books combined just for a single language, like Python or Ruby.
    - IncRnd 8y ago
      People in the field during 1971 may have read more books or papers about Introduction to Programming than people do today, where people read about Language X for Dummies.
    - seanmcdirmid 8y ago
      Landin’s “next 700 programming languages” seminal paper was done in 1965 you know. If anything, there was probably more variety in the 70s computing scene (books, languages, and so on) than there is today.
- bryanrasmussen 8y ago
  He should have written 'justify the investment of my time and energy' to invalidate your view from the future.
scscsc 8y ago
Quite an insightful thought for 1971: "With the advent of what is called "large scale integration" (being a term from the computer field, its acronym LSI is better known!) it seems to become technically feasible to build machines more like "clouds of arithmetic units" with information processing activities going on simultaneously all over the place, for shorter periods of time even independently of each other. Programming for such machines will pose completely different trade-off problems: one will be willing to invest in potentially useful computing activity before its actual usefulness has been established, all for the sake of speeding up the whole computation. But although I know such machines may be coming, I shall not touch these problems for the following reasons. First, as far as general purpose applications are concerned, I have my doubts about the effectiveness with which such forms of parallelism can ever be exploited. Second —and that is the most important consideration— parallel programming is an order of magnitude more difficult than sequential programming." Also, the first mention of "cloud", although with a different meaning.
- bernarpa 8y ago
  That's right, this is more a description of how speculative execution works within modern processors (a quite familiar topic lately thanks to Meltdown, Spectre & co.).
  - seanmcdirmid 8y ago
    Except the author was assuming manual scheduling where today speculative execution is mostly done transparently in hardware (barring failed general purpose VLIW attempts).
    - romwell 8y ago
      There's no assumption of manual scheduling in that text.
nickjj 8y ago
It's really eye opening to read something like, knowing it was written in 1971: > It is not unusual —although a mistake— to consider the programmer's task to be the production of programs. (One finds terms such as "software manufacturing", proposals to measure programmer productivity by the number of lines of code produced per month etc., although I have never seen the suggestion to measure composer productivity by the number of notes, monthly scribbled on his score!). 47 years later, a lot of people still measure programming productivity by LOCs. Hell, even major freelance marketplaces try to track your every billed second by taking screenshots of your desktop or webcam "just to make sure you're working".
- sspencer 8y ago
  > Hell, even major freelance marketplaces try to track your every billed second by taking screenshots of your desktop or webcam "just to make sure you're working". Well that's some dystopian nightmare stuff I had no idea was happening. EDIT: refine quote and add italics
- 0x445442 8y ago
  A big part of the problem IMO is the software development community has gravitated toward rate compensation instead of product compensation. A composer is commissioned to deliver a product and is compensated for said product, not for the time he/she worked to create the product. This was real eye opening for me when I did contract/consultant work, even as a 1099. I can understand the enterprise, butts in the seat model of developers being on retainer but for contracting houses I don't get it. If developers don't want to be bound by these metrics they need to get better at forcing the client into contracts for deliverables with clearly defined acceptance criteria. Also, it seems to me that the best way to get proficient and creating and updating these contracts is by having to work twice as long to deliver a work product as was initially estimated.
  - commandlinefan 8y ago
    I'm not very optimistic that we'll ever be able to reach that utopian state, though. After all, the only person in the fixed-bid equation with any incentive to nail down requirements up front is the developer - it's in the best interest of the buyer to be as vague as possible so that they can defer actually making any decisions until they've had a chance to see the finished product, when the consequences of the decisions are most obvious. Then they can turn around and say, "the requirements clearly state that..." or in other words, you're going to be working for free. Once you get up into even five-figure bids (never minds something that might take a year to deliver), the people writing the checks are happy to put more effort into deliberately obscuring the requirements gathering process than actually gathering requirements, just to keep their options open, and they have a legal department that you don't.
guylepage3 8y ago
“The sole reason one likes to write is insufficient...” Interesting that they did not seem to want to attract people who just enjoy programming..
- Jtsummers 8y ago
  That's in the context of writing the text, not of writing programs. So I'm not quite sure what your point is.

296 points by Rescis 8y ago

unclepresent 8y ago

this is a smart dude, he invented one of the most popular algorithms of finding a shortest path in a graph.

fernly 8y ago
...to say the very least! From [1], > His fundamental contributions cover diverse areas of computing science, including compiler construction, operating systems, distributed systems, sequential and concurrent programming, programming paradigm and methodology, programming language research, program design, program development, program verification, software engineering principles, graph algorithms, and philosophical foundations of computer programming and computer science. Many of his papers are the source of new research areas. Several concepts and problems that are now standard in computer science were first identified by Dijkstra or bear names coined by him. [1] https://en.wikipedia.org/wiki/Edsger_W._Dijkstra https://en.wikipedia.org/wiki/Edsger_W._Dijkstra
- AceJohnny2 8y ago
  Did someone say semaphores? https://en.wikipedia.org/wiki/Semaphore_(programming) https://en.wikipedia.org/wiki/Semaphore_(programming)
  - TimJYoung 8y ago
    Semaphores are great for creating simple read-write locks.
deleted 8y ago
[deleted]
skrebbel 8y ago
IMO that's the least spectacular of his contributions. It's not like that algorithm is particularly mindblowing. In fact, I'd wager that any sufficiently experienced engineer with some algorithm work under their belt would arrive at the exact same thing. Actually, I bet there's engineers all over the world who invent it every year, independently, simply because they need it and they didn't go to college or know that there's a thing out there called "Commonly Known Algorithms That Have Names and Wikipedia Pages" so they just worked it out. In fact, I'd wager someone already came up with it somewhere before Dijkstra did, put it in the code (or, well, on the punch card), and quietly went home, happy about a good day's work. Dijkstra just was the first one to publish it :-) His true contributions were, IMO: * Being the first tech blogger[0] (handwritten!) * Teaching people to use while/for instead of goto * Pioneering mathematically verified algorithm derivation He's also the reason Dutch universities have no independent Computer Science departments. They're always paired with Mathematics, even at universities of technology, which makes no sense and which has effectively halved research funding for both disciplines for decades. He was a better programmer than politician. [0] http://www.cs.utexas.edu/users/EWD/indexChron.html http://www.cs.utexas.edu/users/EWD/indexChron.html - I'm calling it a blog because both the median length and the frequency of publishing is a lot more like blogging than anything else. I'm not aware of other people doing this as much in that day and age (but I'm probably wrong)
- dragonwriter 8y ago
  > Being the first tech blogger (handwritten!) It's not a web log (for which “blog” is short) if it's not on the web.
  - EliRivers 8y ago
    I've certainly heard the youngsters describe something as "a blog, but on paper". Son enough, the word 'blog' will transcend its etymology.
ofrzeta 8y ago
Even smarter: "Simplicity is prerequisite for reliability." I wish more people or "the industry" would take this advice. On the other hand what would be left to sell if everything were simple and reliable.

wsc981 8y ago

Not directly related, but here’s a short documentary on his life and career (Dutch spoken, English subtitles): https://m.youtube.com/watch?v=RCCigccBzIU https://m.youtube.com/watch?v=RCCigccBzIU

sohkamyung 8y ago

For those who prefer a plain text version, start reading from [1] [1] http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD316.html http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EW...

mhd 8y ago
I'm quite surprised that the original PDF wasn't handwritten anyway, as Dijkstra really seemed keen on that (and back in the olden days, I remember some kind of PostScript module that faked this)
- jgtrosh 8y ago
  I read a lot of EWD texts last year, and he transitioned from typed to handwritten later in his life, about halfway through the number of scripts that he published. From his Wikipedia page [1]: > Dijkstra never wrote his articles using a computer. He preferred to rely on his typewriter and later on his Montblanc pen. Dijkstra's favorite writing instrument was the Montblanc Meisterstück fountain pen. [1]: https://en.wikipedia.org/wiki/Edsger_W._Dijkstra https://en.wikipedia.org/wiki/Edsger_W._Dijkstra
- Someone 8y ago
  I think you’re thinking of the “Dijkstra” TrueType font (available from zillions of places. I remember there being different versions, so it probably is worthwhile to download a few and pick the largest (or, better, to inspect them for their glyphs))
  - mhd 8y ago
    I definitely remember it being in PostScript (back in the days when that was much more prevalent in Linux and I actually used jwz' scripts to print CD cases). It might be this http://ftp.math.utah.edu/u/ma/hohn/linux/misc/quickscript/dijkstra.qs http://ftp.math.utah.edu/u/ma/hohn/linux/misc/quickscript/di... If so, that appears to be a regular vector font, too, no random deviations or letter variants to make it appear more handwritten.

escherplex 8y ago

Still a good read (from 1971 then with .pdf Adobe Acrobat optimized). The Towers of Hanoi simulation section brings back memories of an old Wang 2200 Basic machine (64K as I remember) buried in storage at my old prep school which we managed to bring back to life (more or less) . Decided to write a Towers of Hanoi game using its available box graphics, which could be animated but which quickly taught the maxim: write forward then erase behind (otherwise the imagery appears jumpey). The results were similar to the 'Towers of Hanoi' app now on ROKU 4. But how to add an animated 'solve' function? Raw strings (for 2: top small 1 -> 2, top small 1 -> 3, top small 2 -> 3) ate up too much memory beyond 7 (2^n - 1 = 127) so system analysis suggested: give the smallest box a life of it's own and if total number of discs to be moved is even, script the smallest to follow a path 1 -> 2, 2 -> 3, 3 -> 1, 1 -> 2 etc. for first then every other move. If total number of discs odd, script it a path 1 -> 3, 3 -> 2, 2 -> 1, 1 -> 3 etc for first then for every other move (until you're done). Each next alternate move is any valid move (top smallest on any other column move to any other column with no disks or with column with top disk larger than that one). Seem to recall Martin Gardner had a similar solution in an old Scientific American 'Mathematical Games' article.

altro 8y ago

the name should be Edsger

coldtea 8y ago

>The market is already so heavily overloaded with introductory texts on computers and computer programming that one must have rather specific reasons to justify the investment of one's time and energy in the writing of yet another "Short Introduction to the Art of Programming". In 1971? I seriously doubt that... >[people] who identify the programmer's competence with a thorough knowledge of the idiosyncrasies of one or more of the baroque tools into which modern programming languages and systems have degenerated This, however, is as valid as ever...

jcelerier 8y ago
In 1971 there was already 15 years of FORTAN books, and 10 years of ALGOL and COBOL books
- coldtea 8y ago
  All 100 of them? Today we have more books than all those FORTRAN and ALGOL and COBOL books combined just for a single language, like Python or Ruby.
  - IncRnd 8y ago
    People in the field during 1971 may have read more books or papers about Introduction to Programming than people do today, where people read about Language X for Dummies.
  - seanmcdirmid 8y ago
    Landin’s “next 700 programming languages” seminal paper was done in 1965 you know. If anything, there was probably more variety in the 70s computing scene (books, languages, and so on) than there is today.
bryanrasmussen 8y ago
He should have written 'justify the investment of my time and energy' to invalidate your view from the future.

scscsc 8y ago

Quite an insightful thought for 1971: "With the advent of what is called "large scale integration" (being a term from the computer field, its acronym LSI is better known!) it seems to become technically feasible to build machines more like "clouds of arithmetic units" with information processing activities going on simultaneously all over the place, for shorter periods of time even independently of each other. Programming for such machines will pose completely different trade-off problems: one will be willing to invest in potentially useful computing activity before its actual usefulness has been established, all for the sake of speeding up the whole computation. But although I know such machines may be coming, I shall not touch these problems for the following reasons. First, as far as general purpose applications are concerned, I have my doubts about the effectiveness with which such forms of parallelism can ever be exploited. Second —and that is the most important consideration— parallel programming is an order of magnitude more difficult than sequential programming." Also, the first mention of "cloud", although with a different meaning.

bernarpa 8y ago
That's right, this is more a description of how speculative execution works within modern processors (a quite familiar topic lately thanks to Meltdown, Spectre & co.).
- seanmcdirmid 8y ago
  Except the author was assuming manual scheduling where today speculative execution is mostly done transparently in hardware (barring failed general purpose VLIW attempts).
  - romwell 8y ago
    There's no assumption of manual scheduling in that text.

nickjj 8y ago

It's really eye opening to read something like, knowing it was written in 1971: > It is not unusual —although a mistake— to consider the programmer's task to be the production of programs. (One finds terms such as "software manufacturing", proposals to measure programmer productivity by the number of lines of code produced per month etc., although I have never seen the suggestion to measure composer productivity by the number of notes, monthly scribbled on his score!). 47 years later, a lot of people still measure programming productivity by LOCs. Hell, even major freelance marketplaces try to track your every billed second by taking screenshots of your desktop or webcam "just to make sure you're working".

sspencer 8y ago
> Hell, even major freelance marketplaces try to track your every billed second by taking screenshots of your desktop or webcam "just to make sure you're working". Well that's some dystopian nightmare stuff I had no idea was happening. EDIT: refine quote and add italics
0x445442 8y ago
A big part of the problem IMO is the software development community has gravitated toward rate compensation instead of product compensation. A composer is commissioned to deliver a product and is compensated for said product, not for the time he/she worked to create the product. This was real eye opening for me when I did contract/consultant work, even as a 1099. I can understand the enterprise, butts in the seat model of developers being on retainer but for contracting houses I don't get it. If developers don't want to be bound by these metrics they need to get better at forcing the client into contracts for deliverables with clearly defined acceptance criteria. Also, it seems to me that the best way to get proficient and creating and updating these contracts is by having to work twice as long to deliver a work product as was initially estimated.
- commandlinefan 8y ago
  I'm not very optimistic that we'll ever be able to reach that utopian state, though. After all, the only person in the fixed-bid equation with any incentive to nail down requirements up front is the developer - it's in the best interest of the buyer to be as vague as possible so that they can defer actually making any decisions until they've had a chance to see the finished product, when the consequences of the decisions are most obvious. Then they can turn around and say, "the requirements clearly state that..." or in other words, you're going to be working for free. Once you get up into even five-figure bids (never minds something that might take a year to deliver), the people writing the checks are happy to put more effort into deliberately obscuring the requirements gathering process than actually gathering requirements, just to keep their options open, and they have a legal department that you don't.

guylepage3 8y ago

“The sole reason one likes to write is insufficient...” Interesting that they did not seem to want to attract people who just enjoy programming..

Jtsummers 8y ago
That's in the context of writing the text, not of writing programs. So I'm not quite sure what your point is.