4 ms·

Knuth and McIlroy Approach a Problem (2021)

58 points by ingve 4y ago

phtrivier 4y ago
Every few years, I contemplate the idea of trying out literate programming. I get that notebooks have continued to trends of "mixing prose and code" to great success ; however, I really wonder how the "out of order programming" works out in practice. Sadly, I never managed to go passed the "my editor cannot show syntax highlighting for a mix of languages." :/
- iib 4y ago
  This is doable in Emacs, using org-mode and org-babel.
  - phtrivier 4y ago
    You're right, I should have mentioned org-babel as the closest thing to something that would work for me. However, as soon as I start using noweb syntax for "out of order" programming, I stumble into long standing bugs (references are not always found, links in the tangled code are broken, detangling does not work, etc...)
- wolfgang42 4y ago
  Not sure what editor you use, but most syntax highlighters these days can mix languages: you see this e.g. in HTML <style> tags and Markdown fenced code blocks. As for 'out of order programming', I think that TANGLE-style reordering is a lot less important with modern programming languages: they don't do one-pass compilation and so can deal with forward references. Note that most of the cross-references in Knuth's program could be replaced with function calls or constant names, rather than the semiautomatic inlining that WEB performs. I've had some success in writing literate programs in a Markdown file, with a small script to extract the code blocks into a file for execution. This seems to work fine, at least on a small scale, and is very easy to implement and then extend if needed. Edit: and by “small script” I mean: import sys code = False for line in sys.stdin.read().splitlines(): if line == '```': code = False # End block if code: print(line) # Only output block contents if line == '```md': code = True # Start block It also seems worth noting that you can get much the same result just by writing a lot of comments; this technique is mainly useful when you also want more formatting than can be reasonably squeezed into plain text. /edit
brudgers 4y ago
If you want to understand McIlroy's code, you can always read the what McIlroy wrote in what McIlroy wrote in Communications of the ACM. If you want to understand Knuth's code, you can always read what Knuth wrote in the code Knuth wrote. To the degree "programs must be written for people to read, and only incidentally for machines to execute" McIlroy's code traded incidental complexity for brevity. Considering his ordinary expectation that readers would be "old Unix hands" at Bell Labs, this is probably an entirely reasonable engineering tradeoff. Knuth's intended audience has always included at least his future self. To the degree "debugging is twice as hard as writing code in the first place" verbosity is also an entirely reasonable engineering tradeoff. He's been working with some of some of his algorithms for sixty years. If I had a criticism of McIlroy's response -- and I say "had" because it's been forty years more or less -- it's the either or approach. Literate programming is a not-for-me for a lot of people. That doesn't make it bad or good. Just a not-for-me. But hell, forty years ago we didn't have so many chances to scratch itches to argument. Arguments always drive engagement for publishers. Some things don't change very much.
jacknews 4y ago
Another point is how long did Knuth spend on this solution? These days this is an interview question to be completed in an hour, lol.
svat 4y ago
The story, as a dialogue: Knuth: I've come up with an idea I like, called literate programming, and a system called WEB. I wrote TeX in WEB. Bentley: I took a look, and I love it! But TeX is 600 pages long; could you give me a WEB example of a few pages, that I can publish in my magazine column? Knuth: Sure, but that would be too easy: why don't YOU tell me what program to write in WEB? Bentley: Ok, write me a WEB program to find the top K most common words in a text file. Knuth: Sure, here's a WEB program for the problem, as you asked. It's long enough that your readers can see the main features of WEB, and I also came up with a new data structure so that everyone learns something. Apparently, according to many commentators (such as the linked post), Knuth ought to have instead replied with something like: Knuth: Ok, well, you asked me to write a program to illustrate WEB, but actually… Most of your readers won't know this, because it's still 1986, but if they go to a place like Bell Labs they can find the Unix operating system, where Doug McIlroy has come up with a system for combining programs called Unix pipelines, and other people have already written text-processing programs with names like 'tr', 'sort' and 'uniq' (you can look up what they do). So, if any of your readers is using such a system, they can just use those pre-existing programs with an appropriate pipeline. Ta-da! Even though this solution is much slower, I'm sure you won't mind that I didn't give you a WEB program for your column as you asked. This reply would make no sense! Only with a game of telephone/whispers does the story become cast as a "competition". Anyway, for completeness, the rest of the story was: Bentley: Thank you for your program. I've asked Doug McIlroy to write a review. McIlroy: (After writing the review.) BTW, our Unix land is awesome, we have this thing called pipes; we could solve this problem with just… A couple of previous discussions (there have been many): https://news.ycombinator.com/item?id=31301777 https://news.ycombinator.com/item?id=31301777 - Donald Knuth was framed (2020) | May 2022 | 137 comments https://news.ycombinator.com/item?id=30017311 https://news.ycombinator.com/item?id=30017311 - More shell, less egg (2011) | Jan 2022 | 24 comments https://news.ycombinator.com/item?id=22406070 https://news.ycombinator.com/item?id=22406070 - Donald Knuth was framed | Feb 2020 | 183 comments
Avshalom 4y ago
Once again: this does not demonstrate Knuth's approach to solving a problem, it demonstrates Knuth's approach to pedagogy. also it was not a 'competition'
- thr-nrg 4y ago
  I'm reminded of the old adage about playing chess with a pigeon. It knocks down the pieces, shits on the board and flies off.
  - luispauloml 4y ago
    What made you remind of it?
    - thr-nrg 4y ago
      The response to Knuth. He wrote a general program to solve the problem. The supposed solution in bash depends on the exact programs existing already. If you changed any of the original requirements you'd need to do write a c program to do the new type of filtering. If you did it for the literate program you need to read some prose and modify some already existing code.
      - hurril 4y ago
        While there seems to be a difference in how they perceived what the stated problem actually was (where Knuth interpreted it as a call for a pedagogically laid out solution and McIlroy seemingly didn't?) I disagree with your conclusion here. They chose different languages to express themselves in or with. Bash and WEB, respectively. Given other and perhaps even changing requirements, who knows what they'd have done? Why would McIlroy have had to resort to implementing (parts of) his solution in C and not, say, AWK or just in terms of more and other Bash constructs? The conciseness, perhaps even terseness, to McIlroys expression is very elegant and despite the fact that I could not repeat that, I'd still call him a winner in a number of different hypothetical competitions drawn from this context of interactions. And I'm in love with Donald Knuth!
mordae 4y ago
Evolution of Haskell Programmer[1] comes to mind. [1]: http://www.willamette.edu/~fruehr/haskell/evolution.html http://www.willamette.edu/~fruehr/haskell/evolution.html
KRAKRISMOTT 4y ago
When did they hold the competition? I believe the textbook solution to this is using a heap.
- abecedarius 4y ago
  It wasn't a competition. As I remember it, Jon Bentley asked Knuth to write an introductory example of literate programming, and McIlroy to review it in something like the way a literary critic would critique an essay. Both responses were thoughtful. I learned more from the Knuth, but then I was already familiar with the Unix philosophy. To use the heap you still need to look up the words efficiently.
  - bombcar 4y ago
    It’s reprinted in Knuth collections so even he notes the point - there’s a time and place for everything. And one requires WEB and the other requires the entire Unix tool chain. (And the only reason the Unix critique is ever mentioned is because of the literate programming version. Which would programmatical archeologists love to find in 2525 - if man is still alive?)
  - KRAKRISMOTT 4y ago
    > To use the heap you still need to look up the words efficiently. Why? Just split the text and put everything into the heap, the heap algorithm will maintain the sorted order by rebalancing during insertion
    - abecedarius 4y ago
      The textbook solution I assume you meant, to find the most common k elements of a list, uses an updatable priority queue (heap). This orders the (key, count) pairs by the count. But that's a separate question from how you look up the key (i.e. given a word, find the pair whose count you want to increment), which is what Knuth's hash tries were for here.
      - 4y ago
pieterr 4y ago
See also: https://news.ycombinator.com/item?id=3329668 https://news.ycombinator.com/item?id=3329668 https://news.ycombinator.com/item?id=18699342 https://news.ycombinator.com/item?id=18699342
ranting-moth 4y ago
That unfortunate remark by McIlroy did more harm to himself that Knuth.
- benj111 4y ago
  Only because you agree with Knuth. Both McIlroy and Knuth have valid points. There's a reason that not all shell scripts are written in the literate style. There's also a good reason why large programs aren't written like shell scripts
  - Jtsummers 4y ago
    > Both McIlroy and Knuth have valid points. Knuth was asked to write a program illustrating his technique of literate programming, which he did. He was not making a "point". He was making an example. Very different things. McIlroy came in and made a point in his review. Other people, presumably illiterate because the source is available and we can know what was written, made it into a competition or debate. Which it was not.
  - Avshalom 4y ago
    There's nothing to "agree" with Knuth here. He wrote it to demonstrate WEB and literate programming, not because he thought it was the best-fit solution to this task.
    - benj111 4y ago
      Ok, but McIlroy was asked to critique it. I suppose you could say that he was asked to critique a literate program, but that seems to me like complaining to Mr Ford, because you asked for a faster horse, and he came back with a car. Literate program is meant to solve a problem. The goal should be finding the best way to solve that problem. Not solving the problem based on some preconceived notion. Perhaps "agree" was the wrong word, but this exchange is remembered for a reason.

58 points by ingve 4y ago

Every few years, I contemplate the idea of trying out literate programming. I get that notebooks have continued to trends of "mixing prose and code" to great success ; however, I really wonder how the "out of order programming" works out in practice. Sadly, I never managed to go passed the "my editor cannot show syntax highlighting for a mix of languages." :/

iib 4y ago
This is doable in Emacs, using org-mode and org-babel.
- phtrivier 4y ago
  You're right, I should have mentioned org-babel as the closest thing to something that would work for me. However, as soon as I start using noweb syntax for "out of order" programming, I stumble into long standing bugs (references are not always found, links in the tangled code are broken, detangling does not work, etc...)
wolfgang42 4y ago
Not sure what editor you use, but most syntax highlighters these days can mix languages: you see this e.g. in HTML <style> tags and Markdown fenced code blocks. As for 'out of order programming', I think that TANGLE-style reordering is a lot less important with modern programming languages: they don't do one-pass compilation and so can deal with forward references. Note that most of the cross-references in Knuth's program could be replaced with function calls or constant names, rather than the semiautomatic inlining that WEB performs. I've had some success in writing literate programs in a Markdown file, with a small script to extract the code blocks into a file for execution. This seems to work fine, at least on a small scale, and is very easy to implement and then extend if needed. Edit: and by “small script” I mean: import sys code = False for line in sys.stdin.read().splitlines(): if line == '```': code = False # End block if code: print(line) # Only output block contents if line == '```md': code = True # Start block It also seems worth noting that you can get much the same result just by writing a lot of comments; this technique is mainly useful when you also want more formatting than can be reasonably squeezed into plain text. /edit

brudgers 4y ago

If you want to understand McIlroy's code, you can always read the what McIlroy wrote in what McIlroy wrote in Communications of the ACM. If you want to understand Knuth's code, you can always read what Knuth wrote in the code Knuth wrote. To the degree "programs must be written for people to read, and only incidentally for machines to execute" McIlroy's code traded incidental complexity for brevity. Considering his ordinary expectation that readers would be "old Unix hands" at Bell Labs, this is probably an entirely reasonable engineering tradeoff. Knuth's intended audience has always included at least his future self. To the degree "debugging is twice as hard as writing code in the first place" verbosity is also an entirely reasonable engineering tradeoff. He's been working with some of some of his algorithms for sixty years. If I had a criticism of McIlroy's response -- and I say "had" because it's been forty years more or less -- it's the either or approach. Literate programming is a not-for-me for a lot of people. That doesn't make it bad or good. Just a not-for-me. But hell, forty years ago we didn't have so many chances to scratch itches to argument. Arguments always drive engagement for publishers. Some things don't change very much.

jacknews 4y ago

Another point is how long did Knuth spend on this solution? These days this is an interview question to be completed in an hour, lol.

svat 4y ago

The story, as a dialogue: Knuth: I've come up with an idea I like, called literate programming, and a system called WEB. I wrote TeX in WEB. Bentley: I took a look, and I love it! But TeX is 600 pages long; could you give me a WEB example of a few pages, that I can publish in my magazine column? Knuth: Sure, but that would be too easy: why don't YOU tell me what program to write in WEB? Bentley: Ok, write me a WEB program to find the top K most common words in a text file. Knuth: Sure, here's a WEB program for the problem, as you asked. It's long enough that your readers can see the main features of WEB, and I also came up with a new data structure so that everyone learns something. Apparently, according to many commentators (such as the linked post), Knuth ought to have instead replied with something like: Knuth: Ok, well, you asked me to write a program to illustrate WEB, but actually… Most of your readers won't know this, because it's still 1986, but if they go to a place like Bell Labs they can find the Unix operating system, where Doug McIlroy has come up with a system for combining programs called Unix pipelines, and other people have already written text-processing programs with names like 'tr', 'sort' and 'uniq' (you can look up what they do). So, if any of your readers is using such a system, they can just use those pre-existing programs with an appropriate pipeline. Ta-da! Even though this solution is much slower, I'm sure you won't mind that I didn't give you a WEB program for your column as you asked. This reply would make no sense! Only with a game of telephone/whispers does the story become cast as a "competition". Anyway, for completeness, the rest of the story was: Bentley: Thank you for your program. I've asked Doug McIlroy to write a review. McIlroy: (After writing the review.) BTW, our Unix land is awesome, we have this thing called pipes; we could solve this problem with just… A couple of previous discussions (there have been many): https://news.ycombinator.com/item?id=31301777 https://news.ycombinator.com/item?id=31301777 - Donald Knuth was framed (2020) | May 2022 | 137 comments https://news.ycombinator.com/item?id=30017311 https://news.ycombinator.com/item?id=30017311 - More shell, less egg (2011) | Jan 2022 | 24 comments https://news.ycombinator.com/item?id=22406070 https://news.ycombinator.com/item?id=22406070 - Donald Knuth was framed | Feb 2020 | 183 comments

Avshalom 4y ago

Once again: this does not demonstrate Knuth's approach to solving a problem, it demonstrates Knuth's approach to pedagogy. also it was not a 'competition'

thr-nrg 4y ago
I'm reminded of the old adage about playing chess with a pigeon. It knocks down the pieces, shits on the board and flies off.
- luispauloml 4y ago
  What made you remind of it?
  - thr-nrg 4y ago
    The response to Knuth. He wrote a general program to solve the problem. The supposed solution in bash depends on the exact programs existing already. If you changed any of the original requirements you'd need to do write a c program to do the new type of filtering. If you did it for the literate program you need to read some prose and modify some already existing code.
    - hurril 4y ago
      While there seems to be a difference in how they perceived what the stated problem actually was (where Knuth interpreted it as a call for a pedagogically laid out solution and McIlroy seemingly didn't?) I disagree with your conclusion here. They chose different languages to express themselves in or with. Bash and WEB, respectively. Given other and perhaps even changing requirements, who knows what they'd have done? Why would McIlroy have had to resort to implementing (parts of) his solution in C and not, say, AWK or just in terms of more and other Bash constructs? The conciseness, perhaps even terseness, to McIlroys expression is very elegant and despite the fact that I could not repeat that, I'd still call him a winner in a number of different hypothetical competitions drawn from this context of interactions. And I'm in love with Donald Knuth!

mordae 4y ago

Evolution of Haskell Programmer[1] comes to mind. [1]: http://www.willamette.edu/~fruehr/haskell/evolution.html http://www.willamette.edu/~fruehr/haskell/evolution.html

KRAKRISMOTT 4y ago

When did they hold the competition? I believe the textbook solution to this is using a heap.

abecedarius 4y ago
It wasn't a competition. As I remember it, Jon Bentley asked Knuth to write an introductory example of literate programming, and McIlroy to review it in something like the way a literary critic would critique an essay. Both responses were thoughtful. I learned more from the Knuth, but then I was already familiar with the Unix philosophy. To use the heap you still need to look up the words efficiently.
- bombcar 4y ago
  It’s reprinted in Knuth collections so even he notes the point - there’s a time and place for everything. And one requires WEB and the other requires the entire Unix tool chain. (And the only reason the Unix critique is ever mentioned is because of the literate programming version. Which would programmatical archeologists love to find in 2525 - if man is still alive?)
- KRAKRISMOTT 4y ago
  > To use the heap you still need to look up the words efficiently. Why? Just split the text and put everything into the heap, the heap algorithm will maintain the sorted order by rebalancing during insertion
  - abecedarius 4y ago
    The textbook solution I assume you meant, to find the most common k elements of a list, uses an updatable priority queue (heap). This orders the (key, count) pairs by the count. But that's a separate question from how you look up the key (i.e. given a word, find the pair whose count you want to increment), which is what Knuth's hash tries were for here.
    - 4y ago

pieterr 4y ago

See also: https://news.ycombinator.com/item?id=3329668 https://news.ycombinator.com/item?id=3329668 https://news.ycombinator.com/item?id=18699342 https://news.ycombinator.com/item?id=18699342

ranting-moth 4y ago

That unfortunate remark by McIlroy did more harm to himself that Knuth.

benj111 4y ago
Only because you agree with Knuth. Both McIlroy and Knuth have valid points. There's a reason that not all shell scripts are written in the literate style. There's also a good reason why large programs aren't written like shell scripts
- Jtsummers 4y ago
  > Both McIlroy and Knuth have valid points. Knuth was asked to write a program illustrating his technique of literate programming, which he did. He was not making a "point". He was making an example. Very different things. McIlroy came in and made a point in his review. Other people, presumably illiterate because the source is available and we can know what was written, made it into a competition or debate. Which it was not.
- Avshalom 4y ago
  There's nothing to "agree" with Knuth here. He wrote it to demonstrate WEB and literate programming, not because he thought it was the best-fit solution to this task.
  - benj111 4y ago
    Ok, but McIlroy was asked to critique it. I suppose you could say that he was asked to critique a literate program, but that seems to me like complaining to Mr Ford, because you asked for a faster horse, and he came back with a car. Literate program is meant to solve a problem. The goal should be finding the best way to solve that problem. Not solving the problem based on some preconceived notion. Perhaps "agree" was the wrong word, but this exchange is remembered for a reason.