6 ms·

That was quite unfair criticism, and even Doug McIlroy knew it (as he admitted later). The background is this: - Bentley, the author of the column, invited Knu

by svat 8y ago

That was quite unfair criticism, and even Doug McIlroy knew it (as he admitted later). The background is this: - Bentley, the author of the column, invited Knuth to demonstrate literate programming using a program of his choice. - Knuth insisted that to be fair, Bentley ought to specify the program to be written; else someone might object that Knuth chose a program that would be good for literate programming. - Bentley chose (what we'd now call) the term frequency problem (list the top k most frequent words in a text file), and accordingly Knuth wrote a system program for solving just this one particular task. (Did everything from opening the input file to formatting the output, etc.) - Doug McIlroy was asked to “review” this program, the way works of literature are reviewed. He happens to be the inventor of Unix pipes. Towards the end of his review, along with many other points (e.g. Knuth didn't include diagrams in cases where most of us would appreciate them, something I still struggle with when reading TeX and other programs), he used the opportunity to demonstrate his own invention, a shell pipeline using now-standard Unix tools (tr, sort, uniq, sed). There are a few things wrong with this criticism: - The main thing is that DEK wrote the program he was asked to write, so pointing out that he shouldn't have written that program is a criticism of the one who chose the program (Bentley mentioned this when printing McIlroy's review). - At the time, Unix wasn't even widely available outside Bell Labs and a few places; it definitely wasn't available to Knuth or most of the column's readers. - Knuth's program, fine-tuned for the task, is more efficient than the shell pipeline. - Even if you use a shell pipeline, someone has to write the “standard” programs that go into it (the "tr", "sort", "uniq" and "sed" above), and literate programming can be used there. In fact, Knuth did exactly that a few years later, rewriting Unix's “wc” (IIRC) and compared the resulting program with that of Sun Unix's wc, and his LP version had, among things, better error handling. (He's explained it by saying that in conventional programming, if you have a small function and 90% of it is error-checking, it looks like the function is “about” error-checking, so there's a psychological resistance to doing too much of that, while with LP you move the error-handling to a separate section entirely about error-checking and then you tend to do a better job. BTW, TeX's error handling is phenomenally good IMO; the opposite of the situation with LaTeX.) All that said, there is some valid criticism that Knuth prefers to write monolithic programs, but that works for him. He seems not to consider it a problem that to change something you have to understand more-or-less the entire program; he seems to prefer doing that anyway (he reads other people's code a lot: in Peter Seibel's Coders at Work, he was the only person interviewed who read others' programs regularly).

atannen 8y ago
re: At the time, Unix wasn't even widely available outside Bell Labs and a few places; it definitely wasn't available to Knuth or most of the column's readers. At that time, 1986, Unix was widely available - there were more than 100k Unix installations around the world by 1984. AT&T Unix Sys V and UCB 4.3bsd were available. Knuth was friendly with McIlroy, who was head of the Bell Labs computer science research group that begat Unix. Sun Microsystems was formed in 1982 - their boxes ran Unix, and Sun was a startup spun off from Stanford.
- deleted 8y ago
  [deleted]
- vram22 8y ago
  >Sun Microsystems was formed in 1982 - their boxes ran Unix, and Sun was a startup spun off from Stanford. Right. Even their name was derived from Stanford University Network: https://en.wikipedia.org/wiki/Sun_Microsystems#History https://en.wikipedia.org/wiki/Sun_Microsystems#History
- svat 8y ago
  Hmm interesting; I remember checking this for the time when TeX was written (1977, because of questions about building on top of troff) -- what I remember finding is that Unix wasn't widely available at colleges then. Perhaps things changed in the next 9 years. As far as I know, Knuth's access to computers at the time was still through Stanford's AI Lab (that's why the first version of TeX in 1977-1978 was written in SAIL; see also the comment for 14 Mar 1978 in http://texdoc.net/texmf-dist/doc/generic/knuth/errata/errorlog.pdf#page=3 http://texdoc.net/texmf-dist/doc/generic/knuth/errata/errorl...). Do you know if Unix was installed on Stanford lab computers by 1986? What was the distribution of these 100k Unix installations (academia/industry)?
- acqq 8y ago
  OK, Unix was probably available to Knuth, but the task given to Knuth was not to promote any already written programs! Had he done so it would be claimed that he missed to do what was requested of him to do. Even today, if you would get the exactly same task, with the goal to make the most efficient solution when you have to care about the limitations of hardware available to you and to produce the self contained program (e.g. because your algorithm should run with hundreds of billions of words of input) you'd still at the end probably produce something closer to what Knuth did then what McIlroy did. Which doesn't mean that it's not brilliant. But it's also not obvious, i.e. not something a "normal user" would "know": - even if you knew that "tr command translates the characters to characters" did you know that you could (and must) write tr -cs A-Za-z' ' to perform the first operation from 6? What the -c does? What the -s does? That you could and even had to form the command line to contain the newline? I bet a lot of Unix users of today would still not know that one. - did you know what the fifth line was supposed to do "sort -rn" Would you know that you're to sort "numerically" (-n) and that it would "work"? - "sed ${1}q" how many people even today would know that one? And after all that, the first of two sorts needs to sort the file that is as big as the original input! If you have hundreds of gigabytes of input, you'd have to have at least that much more just to sort it. McIlroy's approach is a good one for one-off program or not too big input processing, and if you knew that you can use these commands as he used them. But it's still not "a program" in the same sense a Knuth's program is. Knuth's algorithm would, unsurprisingly, handle the huge inputs orders of magnitude more efficiently. And that is what McIlroy was aware of and intentionally hand-waved it in his "critique." Read the original text: https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/pearls-2.pdf https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/pearls-... But the major point is still: Knuth's task was not "use the existing programs" (or libraries) but "write a program" that does what's said to be done: The fair comparison would then include the source of all the sort, uniq, tr etc. programs which McIlroy used. And once that is being done, McIlroy's code would still be both less readable, less efficient and worse overall. Which on the other side also doesn't mean that for some purposes "worse" isn't "better": https://yosefk.com/blog/what-worse-is-better-vs-the-right-thing-is-really-about.html https://yosefk.com/blog/what-worse-is-better-vs-the-right-th... But for some purposes, on "better" works and "worse" simply doesn't, e.g. when the scale of the problem is big enough. And Knuth teaches us how to solve such, harder problems. And presents the complete solution v.s. doing tricks (just call that library/executable which I'm going to avoid to explain you how it is implemented and what its limitations really are). And giving the misunderstanding in the difference between showing how something is implemented (most efficiently) and that "just use pre-written tool X" approach, I understand even more why Knuth uses assembly in his "The Art of Computer Programming" books.

by svat 8y ago

atannen 8y ago

re: At the time, Unix wasn't even widely available outside Bell Labs and a few places; it definitely wasn't available to Knuth or most of the column's readers. At that time, 1986, Unix was widely available - there were more than 100k Unix installations around the world by 1984. AT&T Unix Sys V and UCB 4.3bsd were available. Knuth was friendly with McIlroy, who was head of the Bell Labs computer science research group that begat Unix. Sun Microsystems was formed in 1982 - their boxes ran Unix, and Sun was a startup spun off from Stanford.

deleted 8y ago
[deleted]
vram22 8y ago
>Sun Microsystems was formed in 1982 - their boxes ran Unix, and Sun was a startup spun off from Stanford. Right. Even their name was derived from Stanford University Network: https://en.wikipedia.org/wiki/Sun_Microsystems#History https://en.wikipedia.org/wiki/Sun_Microsystems#History
svat 8y ago
Hmm interesting; I remember checking this for the time when TeX was written (1977, because of questions about building on top of troff) -- what I remember finding is that Unix wasn't widely available at colleges then. Perhaps things changed in the next 9 years. As far as I know, Knuth's access to computers at the time was still through Stanford's AI Lab (that's why the first version of TeX in 1977-1978 was written in SAIL; see also the comment for 14 Mar 1978 in http://texdoc.net/texmf-dist/doc/generic/knuth/errata/errorlog.pdf#page=3 http://texdoc.net/texmf-dist/doc/generic/knuth/errata/errorl...). Do you know if Unix was installed on Stanford lab computers by 1986? What was the distribution of these 100k Unix installations (academia/industry)?
acqq 8y ago
OK, Unix was probably available to Knuth, but the task given to Knuth was not to promote any already written programs! Had he done so it would be claimed that he missed to do what was requested of him to do. Even today, if you would get the exactly same task, with the goal to make the most efficient solution when you have to care about the limitations of hardware available to you and to produce the self contained program (e.g. because your algorithm should run with hundreds of billions of words of input) you'd still at the end probably produce something closer to what Knuth did then what McIlroy did. Which doesn't mean that it's not brilliant. But it's also not obvious, i.e. not something a "normal user" would "know": - even if you knew that "tr command translates the characters to characters" did you know that you could (and must) write tr -cs A-Za-z' ' to perform the first operation from 6? What the -c does? What the -s does? That you could and even had to form the command line to contain the newline? I bet a lot of Unix users of today would still not know that one. - did you know what the fifth line was supposed to do "sort -rn" Would you know that you're to sort "numerically" (-n) and that it would "work"? - "sed ${1}q" how many people even today would know that one? And after all that, the first of two sorts needs to sort the file that is as big as the original input! If you have hundreds of gigabytes of input, you'd have to have at least that much more just to sort it. McIlroy's approach is a good one for one-off program or not too big input processing, and if you knew that you can use these commands as he used them. But it's still not "a program" in the same sense a Knuth's program is. Knuth's algorithm would, unsurprisingly, handle the huge inputs orders of magnitude more efficiently. And that is what McIlroy was aware of and intentionally hand-waved it in his "critique." Read the original text: https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/pearls-2.pdf https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/pearls-... But the major point is still: Knuth's task was not "use the existing programs" (or libraries) but "write a program" that does what's said to be done: The fair comparison would then include the source of all the sort, uniq, tr etc. programs which McIlroy used. And once that is being done, McIlroy's code would still be both less readable, less efficient and worse overall. Which on the other side also doesn't mean that for some purposes "worse" isn't "better": https://yosefk.com/blog/what-worse-is-better-vs-the-right-thing-is-really-about.html https://yosefk.com/blog/what-worse-is-better-vs-the-right-th... But for some purposes, on "better" works and "worse" simply doesn't, e.g. when the scale of the problem is big enough. And Knuth teaches us how to solve such, harder problems. And presents the complete solution v.s. doing tricks (just call that library/executable which I'm going to avoid to explain you how it is implemented and what its limitations really are). And giving the misunderstanding in the difference between showing how something is implemented (most efficiently) and that "just use pre-written tool X" approach, I understand even more why Knuth uses assembly in his "The Art of Computer Programming" books.